• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 /**
34  * Calls a user function for every basic block in the instruction stream.
35  *
36  * Basic block analysis is pretty easy in our IR thanks to the lack of
37  * unstructured control flow.  We've got:
38  *
39  * ir_loop (for () {}, while () {}, do {} while ())
40  * ir_loop_jump (
41  * ir_if () {}
42  * ir_return
43  * ir_call()
44  *
45  * Note that the basic blocks returned by this don't encompass all
46  * operations performed by the program -- for example, if conditions
47  * don't get returned, nor do the assignments that will be generated
48  * for ir_call parameters.
49  */
call_for_basic_blocks(exec_list * instructions,void (* callback)(ir_instruction * first,ir_instruction * last,void * data),void * data)50 void call_for_basic_blocks(exec_list *instructions,
51 			   void (*callback)(ir_instruction *first,
52 					    ir_instruction *last,
53 					    void *data),
54 			   void *data)
55 {
56    ir_instruction *leader = NULL;
57    ir_instruction *last = NULL;
58 
59    foreach_in_list(ir_instruction, ir, instructions) {
60       ir_if *ir_if;
61       ir_loop *ir_loop;
62       ir_function *ir_function;
63 
64       if (!leader)
65 	 leader = ir;
66 
67       if ((ir_if = ir->as_if())) {
68 	 callback(leader, ir, data);
69 	 leader = NULL;
70 
71 	 call_for_basic_blocks(&ir_if->then_instructions, callback, data);
72 	 call_for_basic_blocks(&ir_if->else_instructions, callback, data);
73       } else if ((ir_loop = ir->as_loop())) {
74 	 callback(leader, ir, data);
75 	 leader = NULL;
76 	 call_for_basic_blocks(&ir_loop->body_instructions, callback, data);
77       } else if (ir->as_jump() || ir->as_call()) {
78 	 callback(leader, ir, data);
79 	 leader = NULL;
80       } else if ((ir_function = ir->as_function())) {
81 	 /* A function definition doesn't interrupt our basic block
82 	  * since execution doesn't go into it.  We should process the
83 	  * bodies of its signatures for BBs, though.
84 	  *
85 	  * Note that we miss an opportunity for producing more
86 	  * maximal BBs between the instructions that precede main()
87 	  * and the body of main().  Perhaps those instructions ought
88 	  * to live inside of main().
89 	  */
90 	 foreach_in_list(ir_function_signature, ir_sig, &ir_function->signatures) {
91 	    call_for_basic_blocks(&ir_sig->body, callback, data);
92 	 }
93       }
94       last = ir;
95    }
96    if (leader) {
97       callback(leader, last, data);
98    }
99 }
100