1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright © 2010 Intel Corporation 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice (including the next 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * paragraph) shall be included in all copies or substantial portions of the 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software. 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * DEALINGS IN THE SOFTWARE. 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \file ir_basic_block.cpp 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Basic block analysis of instruction streams. 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "ir.h" 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "ir_visitor.h" 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "ir_basic_block.h" 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "glsl_types.h" 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Calls a user function for every basic block in the instruction stream. 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Basic block analysis is pretty easy in our IR thanks to the lack of 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * unstructured control flow. We've got: 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * ir_loop (for () {}, while () {}, do {} while ()) 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * ir_loop_jump ( 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * ir_if () {} 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * ir_return 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * ir_call() 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Note that the basic blocks returned by this don't encompass all 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * operations performed by the program -- for example, if conditions 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * don't get returned, nor do the assignments that will be generated 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * for ir_call parameters. 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid call_for_basic_blocks(exec_list *instructions, 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void (*callback)(ir_instruction *first, 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_instruction *last, 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *data), 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *data) 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_instruction *leader = NULL; 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_instruction *last = NULL; 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach_iter(exec_list_iterator, iter, *instructions) { 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_instruction *ir = (ir_instruction *)iter.get(); 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_if *ir_if; 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_loop *ir_loop; 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_function *ir_function; 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!leader) 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org leader = ir; 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ((ir_if = ir->as_if())) { 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org callback(leader, ir, data); 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org leader = NULL; 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org call_for_basic_blocks(&ir_if->then_instructions, callback, data); 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org call_for_basic_blocks(&ir_if->else_instructions, callback, data); 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else if ((ir_loop = ir->as_loop())) { 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org callback(leader, ir, data); 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org leader = NULL; 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org call_for_basic_blocks(&ir_loop->body_instructions, callback, data); 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else if (ir->as_return() || ir->as_call()) { 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org callback(leader, ir, data); 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org leader = NULL; 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else if ((ir_function = ir->as_function())) { 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* A function definition doesn't interrupt our basic block 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * since execution doesn't go into it. We should process the 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * bodies of its signatures for BBs, though. 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Note that we miss an opportunity for producing more 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * maximal BBs between the instructions that precede main() 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and the body of main(). Perhaps those instructions ought 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to live inside of main(). 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach_iter(exec_list_iterator, fun_iter, *ir_function) { 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_function_signature *ir_sig; 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_sig = (ir_function_signature *)fun_iter.get(); 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org call_for_basic_blocks(&ir_sig->body, callback, data); 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org last = ir; 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (leader) { 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org callback(leader, last, data); 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 107