ir_basic_block.cpp revision 29285882676388aacff123e8bdf025904abf8ea9 
1/*
2 * Copyright © 2010 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
21 * DEALINGS IN THE SOFTWARE.
22 */
23
24/**
25 * \file ir_basic_block.cpp
26 *
27 * Basic block analysis of instruction streams.
28 */
29
30#include "ir.h"
31#include "ir_visitor.h"
32#include "ir_basic_block.h"
33#include "glsl_types.h"
34
35class ir_has_call_visitor : public ir_hierarchical_visitor {
36public:
37   ir_has_call_visitor()
38   {
39      has_call = false;
40   }
41
42   virtual ir_visitor_status visit_enter(ir_call *ir)
43   {
44      (void) ir;
45      has_call = true;
46      return visit_stop;
47   }
48
49   bool has_call;
50};
51
52/**
53 * Calls a user function for every basic block in the instruction stream.
54 *
55 * Basic block analysis is pretty easy in our IR thanks to the lack of
56 * unstructured control flow.  We've got:
57 *
58 * ir_loop (for () {}, while () {}, do {} while ())
59 * ir_loop_jump (
60 * ir_if () {}
61 * ir_return
62 * ir_call()
63 *
64 * Note that the basic blocks returned by this don't encompass all
65 * operations performed by the program -- for example, if conditions
66 * don't get returned, nor do the assignments that will be generated
67 * for ir_call parameters.
68 */
69void call_for_basic_blocks(exec_list *instructions,
70			   void (*callback)(ir_instruction *first,
71					    ir_instruction *last,
72					    void *data),
73			   void *data)
74{
75   ir_instruction *leader = NULL;
76   ir_instruction *last = NULL;
77
78   foreach_iter(exec_list_iterator, iter, *instructions) {
79      ir_instruction *ir = (ir_instruction *)iter.get();
80      ir_if *ir_if;
81      ir_loop *ir_loop;
82      ir_function *ir_function;
83
84      if (!leader)
85	 leader = ir;
86
87      if ((ir_if = ir->as_if())) {
88	 callback(leader, ir, data);
89	 leader = NULL;
90
91	 call_for_basic_blocks(&ir_if->then_instructions, callback, data);
92	 call_for_basic_blocks(&ir_if->else_instructions, callback, data);
93      } else if ((ir_loop = ir->as_loop())) {
94	 callback(leader, ir, data);
95	 leader = NULL;
96	 call_for_basic_blocks(&ir_loop->body_instructions, callback, data);
97      } else if (ir->as_return() || ir->as_call()) {
98	 callback(leader, ir, data);
99	 leader = NULL;
100      } else if ((ir_function = ir->as_function())) {
101	 /* A function definition doesn't interrupt our basic block
102	  * since execution doesn't go into it.  We should process the
103	  * bodies of its signatures for BBs, though.
104	  *
105	  * Note that we miss an opportunity for producing more
106	  * maximal BBs between the instructions that precede main()
107	  * and the body of main().  Perhaps those instructions ought
108	  * to live inside of main().
109	  */
110	 foreach_iter(exec_list_iterator, fun_iter, *ir_function) {
111	    ir_function_signature *ir_sig;
112
113	    ir_sig = (ir_function_signature *)fun_iter.get();
114
115	    call_for_basic_blocks(&ir_sig->body, callback, data);
116	 }
117      } else if (ir->as_assignment()) {
118	 ir_has_call_visitor v;
119
120	 /* If there's a call in the expression tree being assigned,
121	  * then that ends the BB too.
122	  *
123	  * The assumption is that any consumer of the basic block
124	  * walker is fine with the fact that the call is somewhere in
125	  * the tree even if portions of the tree may be evaluated
126	  * after the call.
127	  *
128	  * A consumer that has an issue with this could not process
129	  * the last instruction of the basic block.  If doing so,
130	  * expression flattener may be useful before using the basic
131	  * block finder to get more maximal basic blocks out.
132	  */
133	 ir->accept(&v);
134	 if (v.has_call) {
135	    callback(leader, ir, data);
136	    leader = NULL;
137	 }
138      }
139      last = ir;
140   }
141   if (leader) {
142      callback(leader, last, data);
143   }
144}
145