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_cfg.h"
29
30/** @file brw_cfg.cpp
31 *
32 * Walks the shader instructions generated and creates a set of basic
33 * blocks with successor/predecessor edges connecting them.
34 */
35
36static bblock_t *
37pop_stack(exec_list *list)
38{
39   bblock_link *link = (bblock_link *)list->get_tail();
40   bblock_t *block = link->block;
41   link->link.remove();
42
43   return block;
44}
45
46static exec_node *
47link(void *mem_ctx, bblock_t *block)
48{
49   bblock_link *l = new(mem_ctx) bblock_link(block);
50   return &l->link;
51}
52
53bblock_t::bblock_t(cfg_t *cfg) :
54   cfg(cfg), idom(NULL), start_ip(0), end_ip(0), num(0), cycle_count(0)
55{
56   instructions.make_empty();
57   parents.make_empty();
58   children.make_empty();
59}
60
61void
62bblock_t::add_successor(void *mem_ctx, bblock_t *successor)
63{
64   successor->parents.push_tail(::link(mem_ctx, this));
65   children.push_tail(::link(mem_ctx, successor));
66}
67
68bool
69bblock_t::is_predecessor_of(const bblock_t *block) const
70{
71   foreach_list_typed_safe (bblock_link, parent, link, &block->parents) {
72      if (parent->block == this) {
73         return true;
74      }
75   }
76
77   return false;
78}
79
80bool
81bblock_t::is_successor_of(const bblock_t *block) const
82{
83   foreach_list_typed_safe (bblock_link, child, link, &block->children) {
84      if (child->block == this) {
85         return true;
86      }
87   }
88
89   return false;
90}
91
92static bool
93ends_block(const backend_instruction *inst)
94{
95   enum opcode op = inst->opcode;
96
97   return op == BRW_OPCODE_IF ||
98          op == BRW_OPCODE_ELSE ||
99          op == BRW_OPCODE_CONTINUE ||
100          op == BRW_OPCODE_BREAK ||
101          op == BRW_OPCODE_WHILE;
102}
103
104static bool
105starts_block(const backend_instruction *inst)
106{
107   enum opcode op = inst->opcode;
108
109   return op == BRW_OPCODE_DO ||
110          op == BRW_OPCODE_ENDIF;
111}
112
113bool
114bblock_t::can_combine_with(const bblock_t *that) const
115{
116   if ((const bblock_t *)this->link.next != that)
117      return false;
118
119   if (ends_block(this->end()) ||
120       starts_block(that->start()))
121      return false;
122
123   return true;
124}
125
126void
127bblock_t::combine_with(bblock_t *that)
128{
129   assert(this->can_combine_with(that));
130   foreach_list_typed (bblock_link, link, link, &this->children) {
131      assert(link->block == that);
132   }
133   foreach_list_typed (bblock_link, link, link, &that->parents) {
134      assert(link->block == this);
135   }
136
137   this->end_ip = that->end_ip;
138   this->instructions.append_list(&that->instructions);
139
140   this->cfg->remove_block(that);
141}
142
143void
144bblock_t::dump(backend_shader *s) const
145{
146   int ip = this->start_ip;
147   foreach_inst_in_block(backend_instruction, inst, this) {
148      fprintf(stderr, "%5d: ", ip);
149      s->dump_instruction(inst);
150      ip++;
151   }
152}
153
154cfg_t::cfg_t(exec_list *instructions)
155{
156   mem_ctx = ralloc_context(NULL);
157   block_list.make_empty();
158   blocks = NULL;
159   num_blocks = 0;
160   idom_dirty = true;
161   cycle_count = 0;
162
163   bblock_t *cur = NULL;
164   int ip = 0;
165
166   bblock_t *entry = new_block();
167   bblock_t *cur_if = NULL;    /**< BB ending with IF. */
168   bblock_t *cur_else = NULL;  /**< BB ending with ELSE. */
169   bblock_t *cur_endif = NULL; /**< BB starting with ENDIF. */
170   bblock_t *cur_do = NULL;    /**< BB starting with DO. */
171   bblock_t *cur_while = NULL; /**< BB immediately following WHILE. */
172   exec_list if_stack, else_stack, do_stack, while_stack;
173   bblock_t *next;
174
175   set_next_block(&cur, entry, ip);
176
177   foreach_in_list_safe(backend_instruction, inst, instructions) {
178      /* set_next_block wants the post-incremented ip */
179      ip++;
180
181      inst->exec_node::remove();
182
183      switch (inst->opcode) {
184      case BRW_OPCODE_IF:
185         cur->instructions.push_tail(inst);
186
187	 /* Push our information onto a stack so we can recover from
188	  * nested ifs.
189	  */
190	 if_stack.push_tail(link(mem_ctx, cur_if));
191	 else_stack.push_tail(link(mem_ctx, cur_else));
192
193	 cur_if = cur;
194	 cur_else = NULL;
195         cur_endif = NULL;
196
197	 /* Set up our immediately following block, full of "then"
198	  * instructions.
199	  */
200	 next = new_block();
201	 cur_if->add_successor(mem_ctx, next);
202
203	 set_next_block(&cur, next, ip);
204	 break;
205
206      case BRW_OPCODE_ELSE:
207         cur->instructions.push_tail(inst);
208
209         cur_else = cur;
210
211	 next = new_block();
212         assert(cur_if != NULL);
213	 cur_if->add_successor(mem_ctx, next);
214
215	 set_next_block(&cur, next, ip);
216	 break;
217
218      case BRW_OPCODE_ENDIF: {
219         if (cur->instructions.is_empty()) {
220            /* New block was just created; use it. */
221            cur_endif = cur;
222         } else {
223            cur_endif = new_block();
224
225            cur->add_successor(mem_ctx, cur_endif);
226
227            set_next_block(&cur, cur_endif, ip - 1);
228         }
229
230         cur->instructions.push_tail(inst);
231
232         if (cur_else) {
233            cur_else->add_successor(mem_ctx, cur_endif);
234         } else {
235            assert(cur_if != NULL);
236            cur_if->add_successor(mem_ctx, cur_endif);
237         }
238
239         assert(cur_if->end()->opcode == BRW_OPCODE_IF);
240         assert(!cur_else || cur_else->end()->opcode == BRW_OPCODE_ELSE);
241
242	 /* Pop the stack so we're in the previous if/else/endif */
243	 cur_if = pop_stack(&if_stack);
244	 cur_else = pop_stack(&else_stack);
245	 break;
246      }
247      case BRW_OPCODE_DO:
248	 /* Push our information onto a stack so we can recover from
249	  * nested loops.
250	  */
251	 do_stack.push_tail(link(mem_ctx, cur_do));
252	 while_stack.push_tail(link(mem_ctx, cur_while));
253
254	 /* Set up the block just after the while.  Don't know when exactly
255	  * it will start, yet.
256	  */
257	 cur_while = new_block();
258
259         if (cur->instructions.is_empty()) {
260            /* New block was just created; use it. */
261            cur_do = cur;
262         } else {
263            cur_do = new_block();
264
265            cur->add_successor(mem_ctx, cur_do);
266
267            set_next_block(&cur, cur_do, ip - 1);
268         }
269
270         cur->instructions.push_tail(inst);
271	 break;
272
273      case BRW_OPCODE_CONTINUE:
274         cur->instructions.push_tail(inst);
275
276         assert(cur_do != NULL);
277	 cur->add_successor(mem_ctx, cur_do);
278
279	 next = new_block();
280	 if (inst->predicate)
281	    cur->add_successor(mem_ctx, next);
282
283	 set_next_block(&cur, next, ip);
284	 break;
285
286      case BRW_OPCODE_BREAK:
287         cur->instructions.push_tail(inst);
288
289         assert(cur_while != NULL);
290	 cur->add_successor(mem_ctx, cur_while);
291
292	 next = new_block();
293	 if (inst->predicate)
294	    cur->add_successor(mem_ctx, next);
295
296	 set_next_block(&cur, next, ip);
297	 break;
298
299      case BRW_OPCODE_WHILE:
300         cur->instructions.push_tail(inst);
301
302         assert(cur_do != NULL && cur_while != NULL);
303	 cur->add_successor(mem_ctx, cur_do);
304
305         if (inst->predicate)
306            cur->add_successor(mem_ctx, cur_while);
307
308	 set_next_block(&cur, cur_while, ip);
309
310	 /* Pop the stack so we're in the previous loop */
311	 cur_do = pop_stack(&do_stack);
312	 cur_while = pop_stack(&while_stack);
313	 break;
314
315      default:
316         cur->instructions.push_tail(inst);
317	 break;
318      }
319   }
320
321   cur->end_ip = ip - 1;
322
323   make_block_array();
324}
325
326cfg_t::~cfg_t()
327{
328   ralloc_free(mem_ctx);
329}
330
331void
332cfg_t::remove_block(bblock_t *block)
333{
334   foreach_list_typed_safe (bblock_link, predecessor, link, &block->parents) {
335      /* Remove block from all of its predecessors' successor lists. */
336      foreach_list_typed_safe (bblock_link, successor, link,
337                               &predecessor->block->children) {
338         if (block == successor->block) {
339            successor->link.remove();
340            ralloc_free(successor);
341         }
342      }
343
344      /* Add removed-block's successors to its predecessors' successor lists. */
345      foreach_list_typed (bblock_link, successor, link, &block->children) {
346         if (!successor->block->is_successor_of(predecessor->block)) {
347            predecessor->block->children.push_tail(link(mem_ctx,
348                                                        successor->block));
349         }
350      }
351   }
352
353   foreach_list_typed_safe (bblock_link, successor, link, &block->children) {
354      /* Remove block from all of its childrens' parents lists. */
355      foreach_list_typed_safe (bblock_link, predecessor, link,
356                               &successor->block->parents) {
357         if (block == predecessor->block) {
358            predecessor->link.remove();
359            ralloc_free(predecessor);
360         }
361      }
362
363      /* Add removed-block's predecessors to its successors' predecessor lists. */
364      foreach_list_typed (bblock_link, predecessor, link, &block->parents) {
365         if (!predecessor->block->is_predecessor_of(successor->block)) {
366            successor->block->parents.push_tail(link(mem_ctx,
367                                                     predecessor->block));
368         }
369      }
370   }
371
372   block->link.remove();
373
374   for (int b = block->num; b < this->num_blocks - 1; b++) {
375      this->blocks[b] = this->blocks[b + 1];
376      this->blocks[b]->num = b;
377   }
378
379   this->blocks[this->num_blocks - 1]->num = this->num_blocks - 2;
380   this->num_blocks--;
381   idom_dirty = true;
382}
383
384bblock_t *
385cfg_t::new_block()
386{
387   bblock_t *block = new(mem_ctx) bblock_t(this);
388
389   return block;
390}
391
392void
393cfg_t::set_next_block(bblock_t **cur, bblock_t *block, int ip)
394{
395   if (*cur) {
396      (*cur)->end_ip = ip - 1;
397   }
398
399   block->start_ip = ip;
400   block->num = num_blocks++;
401   block_list.push_tail(&block->link);
402   *cur = block;
403}
404
405void
406cfg_t::make_block_array()
407{
408   blocks = ralloc_array(mem_ctx, bblock_t *, num_blocks);
409
410   int i = 0;
411   foreach_block (block, this) {
412      blocks[i++] = block;
413   }
414   assert(i == num_blocks);
415}
416
417void
418cfg_t::dump(backend_shader *s)
419{
420   if (idom_dirty)
421      calculate_idom();
422
423   foreach_block (block, this) {
424      if (block->idom)
425         fprintf(stderr, "START B%d IDOM(B%d)", block->num, block->idom->num);
426      else
427         fprintf(stderr, "START B%d IDOM(none)", block->num);
428
429      foreach_list_typed(bblock_link, link, link, &block->parents) {
430         fprintf(stderr, " <-B%d",
431                 link->block->num);
432      }
433      fprintf(stderr, "\n");
434      if (s != NULL)
435         block->dump(s);
436      fprintf(stderr, "END B%d", block->num);
437      foreach_list_typed(bblock_link, link, link, &block->children) {
438         fprintf(stderr, " ->B%d",
439                 link->block->num);
440      }
441      fprintf(stderr, "\n");
442   }
443}
444
445/* Calculates the immediate dominator of each block, according to "A Simple,
446 * Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken
447 * Kennedy.
448 *
449 * The authors claim that for control flow graphs of sizes normally encountered
450 * (less than 1000 nodes) that this algorithm is significantly faster than
451 * others like Lengauer-Tarjan.
452 */
453void
454cfg_t::calculate_idom()
455{
456   foreach_block(block, this) {
457      block->idom = NULL;
458   }
459   blocks[0]->idom = blocks[0];
460
461   bool changed;
462   do {
463      changed = false;
464
465      foreach_block(block, this) {
466         if (block->num == 0)
467            continue;
468
469         bblock_t *new_idom = NULL;
470         foreach_list_typed(bblock_link, parent, link, &block->parents) {
471            if (parent->block->idom) {
472               if (new_idom == NULL) {
473                  new_idom = parent->block;
474               } else if (parent->block->idom != NULL) {
475                  new_idom = intersect(parent->block, new_idom);
476               }
477            }
478         }
479
480         if (block->idom != new_idom) {
481            block->idom = new_idom;
482            changed = true;
483         }
484      }
485   } while (changed);
486
487   idom_dirty = false;
488}
489
490bblock_t *
491cfg_t::intersect(bblock_t *b1, bblock_t *b2)
492{
493   /* Note, the comparisons here are the opposite of what the paper says
494    * because we index blocks from beginning -> end (i.e. reverse post-order)
495    * instead of post-order like they assume.
496    */
497   while (b1->num != b2->num) {
498      while (b1->num > b2->num)
499         b1 = b1->idom;
500      while (b2->num > b1->num)
501         b2 = b2->idom;
502   }
503   assert(b1);
504   return b1;
505}
506
507void
508cfg_t::dump_cfg()
509{
510   printf("digraph CFG {\n");
511   for (int b = 0; b < num_blocks; b++) {
512      bblock_t *block = this->blocks[b];
513
514      foreach_list_typed_safe (bblock_link, child, link, &block->children) {
515         printf("\t%d -> %d\n", b, child->block->num);
516      }
517   }
518   printf("}\n");
519}
520
521void
522cfg_t::dump_domtree()
523{
524   printf("digraph DominanceTree {\n");
525   foreach_block(block, this) {
526      if (block->idom) {
527         printf("\t%d -> %d\n", block->idom->num, block->num);
528      }
529   }
530   printf("}\n");
531}
532