workbench/libs/mesa/src/glsl/ir_basic_block.cpp

   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 }