Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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.  */
  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.