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 */
50void 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