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  *
  35  * @param irg    the graph which should be optimized
  36  * @param flags  one of osr_flags
  37  *
  38  * The linear function replacement test is controlled by the flags.
  39  * If the osr_flag_lftr_with_ov_check is set, the replacement is only
  40  * done if do overflow can occur.
  41  * Otherwise it is ALWAYS done which might be insecure.
  42  *
  43  * For instance:
  44  *
  45  * for (i = 0; i < 100; ++i)
  46  *
  47  * might be replaced by
  48  *
  49  * for (i = 0; i < 400; i += 4)
  50  *
  51  * But
  52  *
  53  * for (i = 0; i < 0x7FFFFFFF; ++i)
  54  *
  55  * will not be replaced by
  56  *
  57  * for (i = 0; i < 0xFFFFFFFC; i += 4)
  58  *
  59  * because of overflow.
  60  *
  61  * More bad cases:
  62  *
  63  * for (i = 0; i <= 0xF; ++i)
  64  *
  65  * will NOT be transformed into
  66  *
  67  * for (i = 0xFFFFFFF0; i <= 0xFFFFFFFF; ++i)
  68  *
  69  * although here is no direct overflow. The OV occurs when the ++i
  70  * is executed (and would created an endless loop here!).
  71  *
  72  * For the same reason, a loop
  73  *
  74  * for (i = 0; i <= 9; i += x)
  75  *
  76  * will NOT be transformed because we cannot estimate whether an overflow
  77  * might happen adding x.
  78  *
  79  * Note that i < a + 400 is also not possible with the current implementation
  80  * although this might be allowed by other compilers...
  81  *
  82  * Note further that tests for equality can be handled some simplier (but are not
  83  * implemented yet).
  84  *
  85  * This algorithm destoyes the link field of nodes.
  86  */
  87 void opt_osr(ir_graph *irg, unsigned flags);
  88
  89 #endif /* _OPT_OSR_H_ */