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_basic_block.h"
32
33
as_if_skip_discard(ir_instruction * ir)34 static ir_if* as_if_skip_discard (ir_instruction* ir)
35 {
36 ir_if* irif = ir->as_if();
37 if (!irif)
38 return NULL;
39 if (!irif->else_instructions.is_empty())
40 return irif;
41
42 bool only_discards = true;
43 int count = 0;
44 foreach_in_list(ir_instruction, iir, &irif->then_instructions) {
45 if (!iir->as_discard())
46 {
47 only_discards = false;
48 break;
49 }
50 ++count;
51 }
52
53 if (count == 1 && only_discards)
54 return NULL;
55
56 return irif;
57 }
58
59 /**
60 * Calls a user function for every basic block in the instruction stream.
61 *
62 * Basic block analysis is pretty easy in our IR thanks to the lack of
63 * unstructured control flow. We've got:
64 *
65 * ir_loop (for () {}, while () {}, do {} while ())
66 * ir_loop_jump (
67 * ir_if () {}
68 * ir_return
69 * ir_call()
70 *
71 * Note that the basic blocks returned by this don't encompass all
72 * operations performed by the program -- for example, if conditions
73 * don't get returned, nor do the assignments that will be generated
74 * for ir_call parameters.
75 */
call_for_basic_blocks(exec_list * instructions,void (* callback)(ir_instruction * first,ir_instruction * last,void * data),void * data)76 void call_for_basic_blocks(exec_list *instructions,
77 void (*callback)(ir_instruction *first,
78 ir_instruction *last,
79 void *data),
80 void *data)
81 {
82 ir_instruction *leader = NULL;
83 ir_instruction *last = NULL;
84
85 foreach_in_list(ir_instruction, ir, instructions) {
86 ir_if *ir_if;
87 ir_loop *ir_loop;
88 ir_function *ir_function;
89
90 if (!leader)
91 leader = ir;
92
93 if ((ir_if = as_if_skip_discard(ir))) {
94 callback(leader, ir, data);
95 leader = NULL;
96
97 call_for_basic_blocks(&ir_if->then_instructions, callback, data);
98 call_for_basic_blocks(&ir_if->else_instructions, callback, data);
99 } else if ((ir_loop = ir->as_loop())) {
100 callback(leader, ir, data);
101 leader = NULL;
102 call_for_basic_blocks(&ir_loop->body_instructions, callback, data);
103 } else if (ir->as_jump() || ir->as_call()) {
104 callback(leader, ir, data);
105 leader = NULL;
106 } else if ((ir_function = ir->as_function())) {
107 /* A function definition doesn't interrupt our basic block
108 * since execution doesn't go into it. We should process the
109 * bodies of its signatures for BBs, though.
110 *
111 * Note that we miss an opportunity for producing more
112 * maximal BBs between the instructions that precede main()
113 * and the body of main(). Perhaps those instructions ought
114 * to live inside of main().
115 */
116 foreach_in_list(ir_function_signature, ir_sig, &ir_function->signatures) {
117 call_for_basic_blocks(&ir_sig->body, callback, data);
118 }
119 }
120 last = ir;
121 }
122 if (leader) {
123 callback(leader, last, data);
124 }
125 }
126