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