X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firopt.c;h=6b3e6b4187810cd51166aff5f6eadbea1e9e20f3;hb=49ad2542b4cc755e005cf7cd0f3fe76240130dba;hp=951941ce95890137db0fe3f2575b6f9e3adb5baf;hpb=32f76b6359e7d77f5d686fed9c41a14b9fdb8013;p=libfirm

diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c
index 951941ce9..6b3e6b418 100644
--- a/ir/ir/iropt.c
+++ b/ir/ir/iropt.c
@@ -11,7 +11,17 @@
  */
 
 #ifdef HAVE_CONFIG_H
-# include <config.h>
+# include "config.h"
+#endif
+
+#ifdef HAVE_ALLOCA_H
+#include <alloca.h>
+#endif
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
+#ifdef HAVE_STRING_H
+#include <string.h>
 #endif
 
 # include "irnode_t.h"
@@ -27,10 +37,17 @@
 # include "irflag_t.h"
 # include "firmstat.h"
 # include "irarch.h"
+# include "hashptr.h"
 
 /* Make types visible to allow most efficient access */
 # include "entity_t.h"
 
+# ifdef DO_HEAPANALYSIS
+/* heapanal can't cope with NoMems */
+# else /* if defined DO_HEAPANALYSIS */
+#  define USE_NOMEM
+# endif /* defined DO_HEAPANALYSIS */
+
 /**
  * Trivial INLINEable routine for copy propagation.
  * Does follow Ids, needed to optimize INLINEd code.
@@ -90,7 +107,7 @@ static tarval *computed_value_Sub(ir_node *n)
   tarval *tb;
 
   /* a - a */
-  if (a == b)
+  if (a == b && !is_Bad(a))
     return get_tarval_null(get_irn_mode(n));
 
   ta = value_of(a);
@@ -286,8 +303,13 @@ static tarval *computed_value_Eor(ir_node *n)
   ir_node *a = get_Eor_left(n);
   ir_node *b = get_Eor_right(n);
 
-  tarval *ta = value_of(a);
-  tarval *tb = value_of(b);
+  tarval *ta, *tb;
+
+  if (a == b)
+    return get_tarval_null(get_irn_mode(n));
+
+  ta = value_of(a);
+  tb = value_of(b);
 
   if ((ta != tarval_bad) && (tb != tarval_bad)) {
     return tarval_eor (ta, tb);
@@ -420,7 +442,8 @@ static tarval *computed_value_Proj(ir_node *n)
     ab = get_Cmp_right(a);
     proj_nr = get_Proj_proj(n);
 
-    if (aa == ab) { /* 1.: */
+    if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
+      /* BEWARE: a == a is NOT always True for floating Point!!! */
       /* This is a trick with the bits used for encoding the Cmp
          Proj numbers, the following statement is not the same:
       return new_tarval_from_long (proj_nr == Eq, mode_b) */
@@ -580,7 +603,7 @@ static ir_node *equivalent_node_Block(ir_node *n)
      ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
      if (predblock == oldn) {
        /* Jmp jumps into the block it is in -- deal self cycle. */
-       n = new_Bad();
+       n = set_Block_dead(n);
        DBG_OPT_DEAD(oldn, n);
      } else if (get_opt_control_flow_straightening()) {
        n = predblock;
@@ -592,7 +615,7 @@ static ir_node *equivalent_node_Block(ir_node *n)
      ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
      if (predblock == oldn) {
        /* Jmp jumps into the block it is in -- deal self cycle. */
-       n = new_Bad();
+       n = set_Block_dead(n);
        DBG_OPT_DEAD(oldn, n);
      }
    }
@@ -616,15 +639,27 @@ static ir_node *equivalent_node_Block(ir_node *n)
   } else if (get_opt_unreachable_code() &&
              (n != current_ir_graph->start_block) &&
              (n != current_ir_graph->end_block)     ) {
-    int i;
+    int i, n_cfg = get_Block_n_cfgpreds(n);
+
     /* If all inputs are dead, this block is dead too, except if it is
        the start or end block.  This is a step of unreachable code
        elimination */
-    for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
-      if (!is_Bad(get_Block_cfgpred(n, i))) break;
+    for (i = 0; i < n_cfg; i++) {
+      ir_node *pred = get_Block_cfgpred(n, i);
+      ir_node *pred_blk;
+
+      if (is_Bad(pred)) continue;
+      pred_blk = get_nodes_block(pred);
+
+      if (is_Block_dead(pred_blk)) continue;
+
+      if (pred_blk != n) {
+        /* really found a living input */
+        break;
+      }
     }
-    if (i == get_Block_n_cfgpreds(n))
-      n = new_Bad();
+    if (i == n_cfg)
+      n = set_Block_dead(n);
   }
 
   return n;
@@ -638,7 +673,7 @@ static ir_node *equivalent_node_Jmp(ir_node *n)
 {
   /* GL: Why not same for op_Raise?? */
   /* unreachable code elimination */
-  if (is_Bad(get_nodes_block(n)))
+  if (is_Block_dead(get_nodes_block(n)))
     n = new_Bad();
 
   return n;
@@ -651,26 +686,6 @@ static ir_node *equivalent_node_Cond(ir_node *n)
   return n;
 }
 
-/**
- * Use algebraic simplification a v a = a.
- */
-static ir_node *equivalent_node_Or(ir_node *n)
-{
-  ir_node *oldn = n;
-
-  ir_node *a = get_Or_left(n);
-  ir_node *b = get_Or_right(n);
-
-  /* remove a v a */
-  if (a == b) {
-    n = a;
-
-    DBG_OPT_ALGSIM1(oldn, a, b, n);
-  }
-
-  return n;
-}
-
 /**
  * optimize operations that are commutative and have neutral 0,
  * so a op 0 = 0 op a = a.
@@ -821,6 +836,29 @@ static ir_node *equivalent_node_DivMod(ir_node *n)
   return n;
 }
 
+/**
+ * Use algebraic simplification a | a = a | 0 = 0 | a = a.
+ */
+static ir_node *equivalent_node_Or(ir_node *n)
+{
+  ir_node *oldn = n;
+
+  ir_node *a = get_Or_left(n);
+  ir_node *b = get_Or_right(n);
+
+  if (a == b) {
+    n = a;    /* Or has it's own neutral element */
+  } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
+    n = b;
+    DBG_OPT_ALGSIM1(oldn, a, b, n);
+  } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
+    n = a;
+    DBG_OPT_ALGSIM1(oldn, a, b, n);
+  }
+
+  return n;
+}
+
 /**
  * Optimize a & 0b1...1 = 0b1...1 & a =  a & a = a.
  */
@@ -868,12 +906,12 @@ static ir_node *equivalent_node_Conv(ir_node *n)
     if (n_mode == b_mode) {
       if (n_mode == mode_b) {
         n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
-	DBG_OPT_ALGSIM1(oldn, a, b, n);
+    DBG_OPT_ALGSIM1(oldn, a, b, n);
       }
       else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
         if (smaller_mode(b_mode, a_mode)){
           n = b;        /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
-	  DBG_OPT_ALGSIM1(oldn, a, b, n);
+      DBG_OPT_ALGSIM1(oldn, a, b, n);
         }
       }
     }
@@ -881,6 +919,10 @@ static ir_node *equivalent_node_Conv(ir_node *n)
   return n;
 }
 
+/**
+ * A Cast may be removed if the type of the previous node
+ * is already to type of the Cast.
+ */
 static ir_node *equivalent_node_Cast(ir_node *n) {
   ir_node *pred = get_Cast_op(n);
   if (get_irn_type(pred) == get_Cast_type(n))
@@ -888,14 +930,14 @@ static ir_node *equivalent_node_Cast(ir_node *n) {
   return n;
 }
 
+/* Several optimizations:
+   - no Phi in start block.
+   - remove Id operators that are inputs to Phi
+   - fold Phi-nodes, iff they have only one predecessor except
+           themselves.
+*/
 static ir_node *equivalent_node_Phi(ir_node *n)
 {
-  /* Several optimizations:
-     - no Phi in start block.
-     - remove Id operators that are inputs to Phi
-     - fold Phi-nodes, iff they have only one predecessor except
-             themselves.
-  */
   int i, n_preds;
 
   ir_node *oldn = n;
@@ -910,7 +952,7 @@ static ir_node *equivalent_node_Phi(ir_node *n)
   block = get_nodes_block(n);
   /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
      assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
-  if ((is_Bad(block)) ||                         /* Control dead */
+  if ((is_Block_dead(block)) ||                  /* Control dead */
       (block == current_ir_graph->start_block))  /* There should be no Phi nodes */
     return new_Bad();                            /* in the Start Block. */
 
@@ -1001,7 +1043,7 @@ static ir_node *equivalent_node_Proj(ir_node *n)
       n = new_Bad();
     }
   } else if (get_irn_mode(n) == mode_X &&
-             is_Bad(get_nodes_block(n))) {
+             is_Block_dead(get_nodes_block(n))) {
     /* Remove dead control flow -- early gigo. */
     n = new_Bad();
   }
@@ -1109,6 +1151,71 @@ optimize_preds(ir_node *n) {
   } /* end switch */
 }
 
+/**
+ * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
+ * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
+ */
+static ir_node *transform_node_AddSub(ir_node *n)
+{
+  ir_mode *mode = get_irn_mode(n);
+
+  if (mode_is_reference(mode)) {
+    ir_node *left  = get_binop_left(n);
+    ir_node *right = get_binop_right(n);
+    int ref_bits   = get_mode_size_bits(mode);
+
+    if (get_irn_op(left) == op_Conv) {
+      ir_mode *mode = get_irn_mode(left);
+      int bits      = get_mode_size_bits(mode);
+
+      if (ref_bits == bits &&
+          mode_is_int(mode) &&
+          get_mode_arithmetic(mode) == irma_twos_complement) {
+        ir_node *pre      = get_Conv_op(left);
+        ir_mode *pre_mode = get_irn_mode(pre);
+
+        if (mode_is_int(pre_mode) &&
+            get_mode_size_bits(pre_mode) == bits &&
+            get_mode_arithmetic(pre_mode) == irma_twos_complement) {
+          /* ok, this conv just changes to sign, moreover the calculation
+           * is done with same number of bits as our address mode, so
+           * we can ignore the conv as address calculation can be viewed
+           * as either signed or unsigned
+           */
+          set_binop_left(n, pre);
+        }
+      }
+    }
+
+    if (get_irn_op(right) == op_Conv) {
+      ir_mode *mode = get_irn_mode(right);
+      int bits      = get_mode_size_bits(mode);
+
+      if (ref_bits == bits &&
+          mode_is_int(mode) &&
+          get_mode_arithmetic(mode) == irma_twos_complement) {
+        ir_node *pre      = get_Conv_op(right);
+        ir_mode *pre_mode = get_irn_mode(pre);
+
+        if (mode_is_int(pre_mode) &&
+            get_mode_size_bits(pre_mode) == bits &&
+            get_mode_arithmetic(pre_mode) == irma_twos_complement) {
+          /* ok, this conv just changes to sign, moreover the calculation
+           * is done with same number of bits as our address mode, so
+           * we can ignore the conv as address calculation can be viewed
+           * as either signed or unsigned
+           */
+          set_binop_right(n, pre);
+        }
+      }
+    }
+  }
+  return n;
+}
+
+#define transform_node_Add      transform_node_AddSub
+#define transform_node_Sub      transform_node_AddSub
+
 /** Do architecture dependend optimizations on Mul nodes */
 static ir_node *transform_node_Mul(ir_node *n) {
   return arch_dep_replace_mul_with_shifts(n);
@@ -1267,6 +1374,9 @@ static ir_node *transform_node_Cond(ir_node *n)
   return n;
 }
 
+/**
+ * Transform an Eor.
+ */
 static ir_node *transform_node_Eor(ir_node *n)
 {
   ir_node *a = get_Eor_left(n);
@@ -1307,15 +1417,19 @@ static ir_node *transform_node_Not(ir_node *n)
   return n;
 }
 
+/**
+ * Transform a Cast of a Const into a new Const
+ */
 static ir_node *transform_node_Cast(ir_node *n) {
   ir_node *pred = get_Cast_op(n);
   type *tp = get_irn_type(pred);
+
   if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
     n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
-			  get_Const_tarval(pred), tp);
+              get_Const_tarval(pred), tp);
   } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
     n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
-			     get_SymConst_kind(pred), tp);
+                 get_SymConst_kind(pred), tp);
   }
   return n;
 }
@@ -1324,7 +1438,7 @@ static ir_node *transform_node_Cast(ir_node *n) {
  * Transform a Div/Mod/DivMod with a non-zero constant. Must be
  * done here instead of equivalent node because it creates new
  * nodes.
- * Removes the exceptions and routes the memory to the initial mem.
+ * Removes the exceptions and routes the memory to the NoMem node.
  *
  * Further, it optimizes jump tables by removing all impossible cases.
  */
@@ -1349,13 +1463,13 @@ static ir_node *transform_node_Proj(ir_node *proj)
       if (proj_nr == pn_Div_X_except) {
         /* we found an exception handler, remove it */
         return new_Bad();
-      }
-      else {
-	/* the memory Proj can be removed */
+      } else {
+        /* the memory Proj can be removed */
         ir_node *res = get_Div_mem(n);
-        set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
-
-	if (proj_nr == pn_Div_M)
+# ifdef USE_NOMEM
+        set_Div_mem(n, get_irg_no_mem(current_ir_graph));
+# endif /* defined USE_NOMEM */
+        if (proj_nr == pn_Div_M)
           return res;
       }
     }
@@ -1373,13 +1487,14 @@ static ir_node *transform_node_Proj(ir_node *proj)
       if (proj_nr == pn_Mod_X_except) {
         /* we found an exception handler, remove it */
         return new_Bad();
-      }
-      else {
-	/* the memory Proj can be removed */
+      } else {
+        /* the memory Proj can be removed */
         ir_node *res = get_Mod_mem(n);
-        set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
+# ifdef USE_NOMEM
+        set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
+# endif /* defined USE_NOMEM */
         if (proj_nr == pn_Mod_M)
-	  return res;
+          return res;
       }
     }
     break;
@@ -1398,11 +1513,13 @@ static ir_node *transform_node_Proj(ir_node *proj)
         return new_Bad();
       }
       else {
-	/* the memory Proj can be removed */
+        /* the memory Proj can be removed */
         ir_node *res = get_DivMod_mem(n);
-        set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
+# ifdef USE_NOMEM
+        set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
+# endif /* defined USE_NOMEM */
         if (proj_nr == pn_DivMod_M)
-	  return res;
+          return res;
       }
     }
     break;
@@ -1626,6 +1743,8 @@ static ir_op *firm_set_default_transform_node(ir_op *op)
     break
 
   switch (op->code) {
+  CASE(Add);
+  CASE(Sub);
   CASE(Mul);
   CASE(Div);
   CASE(Mod);
@@ -1702,12 +1821,6 @@ static int node_cmp_attr_Call(ir_node *a, ir_node *b)
     return (get_irn_call_attr(a) != get_irn_call_attr(b));
 }
 
-/** Compares the attributes of two FuncCall nodes. */
-static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
-{
-    return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
-}
-
 /** Compares the attributes of two Sel nodes. */
 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
 {
@@ -1767,7 +1880,6 @@ static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
   CASE(Free);
   CASE(SymConst);
   CASE(Call);
-  CASE(FuncCall);
   CASE(Sel);
   CASE(Phi);
   CASE(Cast);
@@ -1799,20 +1911,20 @@ vt_cmp (const void *elt, const void *key)
   if ((get_irn_op(a) != get_irn_op(b)) ||
       (get_irn_mode(a) != get_irn_mode(b))) return 1;
 
-  /* compare if a's in and b's in are equal */
-  irn_arity_a = get_irn_arity (a);
-  if (irn_arity_a != get_irn_arity(b))
+  /* compare if a's in and b's in are of equal length */
+  irn_arity_a = get_irn_intra_arity (a);
+  if (irn_arity_a != get_irn_intra_arity(b))
     return 1;
 
   /* for block-local cse and op_pin_state_pinned nodes: */
   if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
-    if (get_irn_n(a, -1) != get_irn_n(b, -1))
+    if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
       return 1;
   }
 
   /* compare a->in[0..ins] with b->in[0..ins] */
   for (i = 0; i < irn_arity_a; i++)
-    if (get_irn_n(a, i) != get_irn_n(b, i))
+    if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
       return 1;
 
   /*
@@ -1836,41 +1948,39 @@ ir_node_hash (ir_node *node)
 
   if (node->op == op_Const) {
     /* special value for const, as they only differ in their tarval. */
-    h = ((unsigned) node->attr.con.tv)>>3 ;
-    h = 9*h + (unsigned)get_irn_mode(node);
+    h = HASH_PTR(node->attr.con.tv);
+    h = 9*h + HASH_PTR(get_irn_mode(node));
   } else if (node->op == op_SymConst) {
     /* special value for const, as they only differ in their symbol. */
-    h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
-    h = 9*h + (unsigned)get_irn_mode(node);
+    h = HASH_PTR(node->attr.i.sym.type_p);
+    h = 9*h + HASH_PTR(get_irn_mode(node));
   } else {
 
     /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
-    h = irn_arity = get_irn_arity(node);
+    h = irn_arity = get_irn_intra_arity(node);
 
-    /* consider all in nodes... except the block. */
-    for (i = 0;  i < irn_arity;  i++) {
-      h = 9*h + (unsigned)get_irn_n(node, i);
+    /* consider all in nodes... except the block if not a control flow. */
+    for (i =  is_cfop(node) ? -1 : 0;  i < irn_arity;  i++) {
+      h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
     }
 
     /* ...mode,... */
-    h = 9*h + (unsigned) get_irn_mode (node);
+    h = 9*h + HASH_PTR(get_irn_mode(node));
     /* ...and code */
-    h = 9*h + (unsigned) get_irn_op (node);
+    h = 9*h + HASH_PTR(get_irn_op(node));
   }
 
   return h;
 }
 
 pset *
-new_identities (void)
-{
-  return new_pset (vt_cmp, N_IR_NODES);
+new_identities(void) {
+  return new_pset(vt_cmp, N_IR_NODES);
 }
 
 void
-del_identities (pset *value_table)
-{
-  del_pset (value_table);
+del_identities(pset *value_table) {
+  del_pset(value_table);
 }
 
 /**
@@ -1980,6 +2090,7 @@ gigo (ir_node *node)
   if (get_irn_mode(node) == mode_X) {
     ir_node *block = get_nodes_block(node);
     if (op == op_End) return node;     /* Don't optimize End, may have Bads. */
+
     if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
       irn_arity = get_irn_arity(block);
       for (i = 0; i < irn_arity; i++) {
@@ -1993,7 +2104,11 @@ gigo (ir_node *node)
      blocks predecessors is dead. */
   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
     irn_arity = get_irn_arity(node);
-    for (i = -1; i < irn_arity; i++) {
+
+    if (is_Block_dead(get_nodes_block(node)))
+      return new_Bad();
+
+    for (i = 0; i < irn_arity; i++) {
       if (is_Bad(get_irn_n(node, i))) {
         return new_Bad();
       }
@@ -2047,23 +2162,23 @@ optimize_node (ir_node *n)
       if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
         /*
          * we MUST copy the node here temporary, because it's still needed
-         * for DBG_OPT_ALGSIM0
+         * for DBG_OPT_CSTEVAL
          */
         int node_size = offsetof(ir_node, attr) +  n->op->attr_size;
         oldn = alloca(node_size);
 
         memcpy(oldn, n, node_size);
-	CLONE_ARR_A(ir_node *, oldn->in, n->in);
+    CLONE_ARR_A(ir_node *, oldn->in, n->in);
 
-	/* ARG, copy the in array, we need it for statistics */
-	memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
+    /* ARG, copy the in array, we need it for statistics */
+    memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
 
         /* evaluation was successful -- replace the node. */
         obstack_free (current_ir_graph->obst, n);
         n = new_Const (get_tarval_mode (tv), tv);
-	if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
-	  set_Const_type(n, old_tp);
-                                                 DBG_OPT_ALGSIM0(oldn, n);
+    if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
+      set_Const_type(n, old_tp);
+                                                 DBG_OPT_CSTEVAL(oldn, n);
         return n;
       }
     }
@@ -2153,10 +2268,10 @@ optimize_in_place_2 (ir_node *n)
         /* evaluation was successful -- replace the node. */
         n = new_Const (get_tarval_mode (tv), tv);
 
-	if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
-	  set_Const_type(n, old_tp);
+    if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
+      set_Const_type(n, old_tp);
 
-        DBG_OPT_ALGSIM0(oldn, n);
+        DBG_OPT_CSTEVAL(oldn, n);
         return n;
       }
     }