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
37static fs_bblock *
38pop_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
47fs_bblock::fs_bblock()
48{
49   start = NULL;
50   end = NULL;
51
52   parents.make_empty();
53   children.make_empty();
54}
55
56void
57fs_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
63fs_bblock_link *
64fs_bblock::make_list(void *mem_ctx)
65{
66   return new(mem_ctx) fs_bblock_link(this);
67}
68
69fs_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
212fs_cfg::~fs_cfg()
213{
214   ralloc_free(mem_ctx);
215}
216
217fs_bblock *
218fs_cfg::new_block()
219{
220   fs_bblock *block = new(mem_ctx) fs_bblock();
221
222   return block;
223}
224
225void
226fs_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
239void
240fs_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