1 /*
2 * Copyright © 2012 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 *
23 * Authors:
24 * Eric Anholt <eric@anholt.net>
25 *
26 */
27
28 #include "brw_fs.h"
29 #include "brw_fs_cfg.h"
30
31 /** @file brw_fs_cfg.cpp
32 *
33 * Walks the shader instructions generated and creates a set of basic
34 * blocks with successor/predecessor edges connecting them.
35 */
36
37 static fs_bblock *
pop_stack(exec_list * list)38 pop_stack(exec_list *list)
39 {
40 fs_bblock_link *link = (fs_bblock_link *)list->get_tail();
41 fs_bblock *block = link->block;
42 link->remove();
43
44 return block;
45 }
46
fs_bblock()47 fs_bblock::fs_bblock()
48 {
49 start = NULL;
50 end = NULL;
51
52 parents.make_empty();
53 children.make_empty();
54 }
55
56 void
add_successor(void * mem_ctx,fs_bblock * successor)57 fs_bblock::add_successor(void *mem_ctx, fs_bblock *successor)
58 {
59 successor->parents.push_tail(this->make_list(mem_ctx));
60 children.push_tail(successor->make_list(mem_ctx));
61 }
62
63 fs_bblock_link *
make_list(void * mem_ctx)64 fs_bblock::make_list(void *mem_ctx)
65 {
66 return new(mem_ctx) fs_bblock_link(this);
67 }
68
fs_cfg(fs_visitor * v)69 fs_cfg::fs_cfg(fs_visitor *v)
70 {
71 mem_ctx = ralloc_context(v->mem_ctx);
72 block_list.make_empty();
73 num_blocks = 0;
74 ip = 0;
75 cur = NULL;
76
77 fs_bblock *entry = new_block();
78 fs_bblock *cur_if = NULL, *cur_else = NULL, *cur_endif = NULL;
79 fs_bblock *cur_do = NULL, *cur_while = NULL;
80 exec_list if_stack, else_stack, endif_stack, do_stack, while_stack;
81 fs_bblock *next;
82
83 set_next_block(entry);
84
85 entry->start = (fs_inst *)v->instructions.get_head();
86
87 foreach_list(node, &v->instructions) {
88 fs_inst *inst = (fs_inst *)node;
89
90 cur->end = inst;
91
92 /* set_next_block wants the post-incremented ip */
93 ip++;
94
95 switch (inst->opcode) {
96 case BRW_OPCODE_IF:
97 /* Push our information onto a stack so we can recover from
98 * nested ifs.
99 */
100 if_stack.push_tail(cur_if->make_list(mem_ctx));
101 else_stack.push_tail(cur_else->make_list(mem_ctx));
102 endif_stack.push_tail(cur_endif->make_list(mem_ctx));
103
104 cur_if = cur;
105 cur_else = NULL;
106 /* Set up the block just after the endif. Don't know when exactly
107 * it will start, yet.
108 */
109 cur_endif = new_block();
110
111 /* Set up our immediately following block, full of "then"
112 * instructions.
113 */
114 next = new_block();
115 next->start = (fs_inst *)inst->next;
116 cur_if->add_successor(mem_ctx, next);
117
118 set_next_block(next);
119 break;
120
121 case BRW_OPCODE_ELSE:
122 cur->add_successor(mem_ctx, cur_endif);
123
124 next = new_block();
125 next->start = (fs_inst *)inst->next;
126 cur_if->add_successor(mem_ctx, next);
127 cur_else = next;
128
129 set_next_block(next);
130 break;
131
132 case BRW_OPCODE_ENDIF:
133 cur_endif->start = (fs_inst *)inst->next;
134 cur->add_successor(mem_ctx, cur_endif);
135 set_next_block(cur_endif);
136
137 if (!cur_else)
138 cur_if->add_successor(mem_ctx, cur_endif);
139
140 /* Pop the stack so we're in the previous if/else/endif */
141 cur_if = pop_stack(&if_stack);
142 cur_else = pop_stack(&else_stack);
143 cur_endif = pop_stack(&endif_stack);
144 break;
145
146 case BRW_OPCODE_DO:
147 /* Push our information onto a stack so we can recover from
148 * nested loops.
149 */
150 do_stack.push_tail(cur_do->make_list(mem_ctx));
151 while_stack.push_tail(cur_while->make_list(mem_ctx));
152
153 /* Set up the block just after the while. Don't know when exactly
154 * it will start, yet.
155 */
156 cur_while = new_block();
157
158 /* Set up our immediately following block, full of "then"
159 * instructions.
160 */
161 next = new_block();
162 next->start = (fs_inst *)inst->next;
163 cur->add_successor(mem_ctx, next);
164 cur_do = next;
165
166 set_next_block(next);
167 break;
168
169 case BRW_OPCODE_CONTINUE:
170 cur->add_successor(mem_ctx, cur_do);
171
172 next = new_block();
173 next->start = (fs_inst *)inst->next;
174 if (inst->predicated)
175 cur->add_successor(mem_ctx, next);
176
177 set_next_block(next);
178 break;
179
180 case BRW_OPCODE_BREAK:
181 cur->add_successor(mem_ctx, cur_while);
182
183 next = new_block();
184 next->start = (fs_inst *)inst->next;
185 if (inst->predicated)
186 cur->add_successor(mem_ctx, next);
187
188 set_next_block(next);
189 break;
190
191 case BRW_OPCODE_WHILE:
192 cur_while->start = (fs_inst *)inst->next;
193
194 cur->add_successor(mem_ctx, cur_do);
195 set_next_block(cur_while);
196
197 /* Pop the stack so we're in the previous loop */
198 cur_do = pop_stack(&do_stack);
199 cur_while = pop_stack(&while_stack);
200 break;
201
202 default:
203 break;
204 }
205 }
206
207 cur->end_ip = ip;
208
209 make_block_array();
210 }
211
~fs_cfg()212 fs_cfg::~fs_cfg()
213 {
214 ralloc_free(mem_ctx);
215 }
216
217 fs_bblock *
new_block()218 fs_cfg::new_block()
219 {
220 fs_bblock *block = new(mem_ctx) fs_bblock();
221
222 return block;
223 }
224
225 void
set_next_block(fs_bblock * block)226 fs_cfg::set_next_block(fs_bblock *block)
227 {
228 if (cur) {
229 assert(cur->end->next == block->start);
230 cur->end_ip = ip - 1;
231 }
232
233 block->start_ip = ip;
234 block->block_num = num_blocks++;
235 block_list.push_tail(block->make_list(mem_ctx));
236 cur = block;
237 }
238
239 void
make_block_array()240 fs_cfg::make_block_array()
241 {
242 blocks = ralloc_array(mem_ctx, fs_bblock *, num_blocks);
243
244 int i = 0;
245 foreach_list(block_node, &block_list) {
246 fs_bblock_link *link = (fs_bblock_link *)block_node;
247 blocks[i++] = link->block;
248 }
249 assert(i == num_blocks);
250 }
251