nsz Git - libfirm/blob - ir/opt/opt_osr.h

   1 /**
   2  * Project:     libFIRM
   3  * File name:   ir/opt/opt_osr.h
   4  * Purpose:     Operator Strength Reduction,
   5  *              Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick
   6  * Author:      Michael Beck
   7  * Modified by:
   8  * Created:     12.5.2006
   9  * CVS-ID:      $Id$
  10  * Copyright:   (c) 2006 Universität Karlsruhe
  11  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  12  */
  13 #ifndef _OPT_OSR_H_
  14 #define _OPT_OSR_H_
  15
  16 #include "firm_types.h"
  17
  18 /** Possible flags for the Operator Scalar Replacement. */
  19 typedef enum osr_flags {
  20         osr_flag_none               = 0,  /**< no additional flags */
  21         osr_flag_lftr_with_ov_check = 1,  /**< do linear function test replacement
  22                                                only if no overflow can occur. */
  23         osr_flag_ignore_x86_shift   = 2   /**< ignore Multiplications by 2, 4, 8 */
  24 } osr_flags;
  25
  26 /* FirmJNI cannot handle identical enum values... */
  27
  28 /** default setting */
  29 #define osr_flag_default osr_flag_lftr_with_ov_check
  30
  31 /**
  32  * Do the Operator Scalar Replacement optimization and linear
  33  * function test replacement for loop control.
  34  * Can be switched off using the set_opt_strength_red() flag.
  35  * In that case, only remove_phi_cycles() is executed.
  36  *
  37  * @param irg    the graph which should be optimized
  38  * @param flags  set of osr_flags
  39  *
  40  * The linear function replacement test is controlled by the flags.
  41  * If the osr_flag_lftr_with_ov_check is set, the replacement is only
  42  * done if do overflow can occur.
  43  * Otherwise it is ALWAYS done which might be insecure.
  44  *
  45  * For instance:
  46  *
  47  * for (i = 0; i < 100; ++i)
  48  *
  49  * might be replaced by
  50  *
  51  * for (i = 0; i < 400; i += 4)
  52  *
  53  * But
  54  *
  55  * for (i = 0; i < 0x7FFFFFFF; ++i)
  56  *
  57  * will not be replaced by
  58  *
  59  * for (i = 0; i < 0xFFFFFFFC; i += 4)
  60  *
  61  * because of overflow.
  62  *
  63  * More bad cases:
  64  *
  65  * for (i = 0; i <= 0xF; ++i)
  66  *
  67  * will NOT be transformed into
  68  *
  69  * for (i = 0xFFFFFFF0; i <= 0xFFFFFFFF; ++i)
  70  *
  71  * although here is no direct overflow. The OV occurs when the ++i
  72  * is executed (and would created an endless loop here!).
  73  *
  74  * For the same reason, a loop
  75  *
  76  * for (i = 0; i <= 9; i += x)
  77  *
  78  * will NOT be transformed because we cannot estimate whether an overflow
  79  * might happen adding x.
  80  *
  81  * Note that i < a + 400 is also not possible with the current implementation
  82  * although this might be allowed by other compilers...
  83  *
  84  * Note further that tests for equality can be handled some simpler (but are not
  85  * implemented yet).
  86  *
  87  * This algorithm destroys the link field of nodes.
  88  */
  89 void opt_osr(ir_graph *irg, unsigned flags);
  90
  91 /**
  92  * Removes useless Phi cycles, i.e cycles of Phi nodes with only one
  93  * non-Phi node.
  94  * This is automatically done in opt_osr(), so there is no need to call it
  95  * additionally.
  96  *
  97  * @param irg    the graph which should be optimized
  98  *
  99  * This algorithm destroys the link field of nodes.
 100  */
 101 void remove_phi_cycles(ir_graph *irg);
 102
 103 #endif /* _OPT_OSR_H_ */