Home | History | Annotate | Download | only in glsl 
      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:
     37    ir_has_call_visitor()
     38    {
     39       has_call = false;
     40    }
     41 
     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
     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  */
     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