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