X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Finterval_analysis.c;h=36ff2bb667461a3f4d8179385c5f3b249dd3c4fd;hb=95afc5aaefb484a67fb89f02b5e96cc302fe02ef;hp=930e814c29b165c6d64c1dee904dac77239c8e91;hpb=ddb4920b93942bad275d30869ea91e7a6aaf1fe3;p=libfirm

diff --git a/ir/ana/interval_analysis.c b/ir/ana/interval_analysis.c
index 930e814c2..36ff2bb66 100644
--- a/ir/ana/interval_analysis.c
+++ b/ir/ana/interval_analysis.c
@@ -1,3 +1,27 @@
+/*
+ * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
+/**
+ * @file
+ * @brief   Implementation of interval analysis
+ * @version $Id$
+ */
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
@@ -7,7 +31,7 @@
 #endif
 
 #include "interval_analysis.h"
-
+#include "execution_frequency.h"
 #include "firm_common_t.h"
 #include "set.h"
 #include "array.h"
@@ -17,6 +41,7 @@
 #include "irdump_t.h"
 #include "irdom.h"
 #include "irflag.h"
+#include "hashptr.h"
 
 /*------------------------------------------------------------------*/
 /* A new in array via a hashmap. */
@@ -40,9 +65,8 @@ int region_attr_cmp(const void *e1, const void *e2, size_t size) {
   return (ra1->reg != ra2->reg);
 }
 
-static INLINE int attr_set_hash (region_attr *a) {
-  unsigned int v = (unsigned int) a->reg;
-  return v ^ (v>>8);
+static INLINE int attr_set_hash(region_attr *a) {
+  return HASH_PTR(a->reg);
 }
 
 static INLINE region_attr *get_region_attr(void *region) {
@@ -71,7 +95,7 @@ int get_region_n_ins(void *region) {
 
 void *get_region_in(void *region, int pos) {
   assert(0 <= pos && pos < get_region_n_ins(region));
-  return (get_region_attr(region)->in_array)[pos];
+  return ((get_region_attr(region)->in_array)[pos]);
 }
 
 void add_region_in (void *region, void *in) {
@@ -93,7 +117,7 @@ void inc_region_n_exc_outs(void *region) {
 
 void *get_loop_cfop(void *region, int pos) {
   assert(0 <= pos && pos < get_region_n_ins(region));
-  return (get_region_attr(region)->op_array)[pos];
+  return ((get_region_attr(region)->op_array)[pos]);
 }
 
 void add_loop_cfop (void *region, void *cfop) {
@@ -102,7 +126,8 @@ void add_loop_cfop (void *region, void *cfop) {
 }
 
 static INLINE void exc_outs(void *reg, ir_node *cfop) {
-  if (is_fragile_op(cfop)) inc_region_n_exc_outs(reg);
+  if (is_fragile_op(cfop) || (is_fragile_Proj(cfop)))
+    inc_region_n_exc_outs(reg);
 }
 
 /*------------------------------------------------------------------*/
@@ -110,15 +135,15 @@ static INLINE void exc_outs(void *reg, ir_node *cfop) {
 /* Walk a loop and add all edges.  Walk inner loops by recursion. */
 /*------------------------------------------------------------------*/
 
-/* return true if outer can be reached from inner via the outer loop relation */
+/* return non-zero if outer can be reached from inner via the outer loop relation */
 static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *b, ir_node *cfop) {
   if (get_loop_outer_loop(inner) == outer) {
     add_region_in(inner, b);
     add_loop_cfop(inner, cfop);
     exc_outs(b, cfop);
-    return true;
+    return 1;
   }
-  return false;
+  return 0;
 }
 
 static int test_loop_nest(ir_node *pred_b, ir_loop *nest) {
@@ -128,34 +153,34 @@ static int test_loop_nest(ir_node *pred_b, ir_loop *nest) {
     loop_element e = get_loop_element(nest, i);
     switch (*e.kind) {
     case k_ir_node: {
-      if (e.node == pred_b) return true;
+      if (e.node == pred_b) return 1;
     } break;
     case k_ir_loop: {
-      if (test_loop_nest(pred_b, e.son)) return true;
+      if (test_loop_nest(pred_b, e.son)) return 1;
     } break;
     default: break;
     }
   }
-  return false;
+  return 0;
 }
 
 static int find_inner_loop(ir_node *b, ir_loop *l, ir_node *pred, ir_node *cfop) {
   int i, n_elems = get_loop_n_elements(l);
-  int found = false;
+  int found = 0;
 
   for (i = 0; (i < n_elems) && !found; ++i) {
     loop_element e = get_loop_element(l, i);
     switch (*e.kind) {
     case k_ir_node: {
-      if (e.node == b) return false;
+      if (e.node == b) return 0;
     } break;
     case k_ir_loop: {
       found = test_loop_nest(pred, e.son);
       if (found) {
-	add_region_in(b, e.son);
-	exc_outs(e.son, cfop);
-	//if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
-	return found;
+        add_region_in(b, e.son);
+        exc_outs(e.son, cfop);
+        //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
+        return found;
       }
     } break;
     default: break;
@@ -172,16 +197,16 @@ static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b, ir_node *
   assert(l_pos > -1);
   assert(l_pos > 0 && "Is this a necessary condition?  There could be a perfect nest ...");
 
-  for (i = l_pos -1, found = false; i > -1 && !found; --i) {
+  for (i = l_pos -1, found = 0; i > -1 && !found; --i) {
     ir_loop *k = get_loop_element(outer, i).son;
     if (is_ir_loop(k)) {
       found = test_loop_nest(pred_b, k);
       if (found) {
-	add_region_in(l, k);
-	//if (is_fragile_op(cfop)) inc_region_n_exc_outs(k);
-	exc_outs(k, cfop);
-	add_loop_cfop(l, cfop);
-	add_region_in(b, NULL);
+        add_region_in(l, k);
+        //if (is_fragile_op(cfop)) inc_region_n_exc_outs(k);
+        exc_outs(k, cfop);
+        add_loop_cfop(l, cfop);
+        add_region_in(b, NULL);
       }
     }
   }
@@ -198,9 +223,10 @@ static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b, ir_node *
 }
 
 
-/* Compute the edges for the interval graph.
+/**
+ * Compute the edges for the interval graph.
  *
- * @param b The block for which to constuct the edges.
+ * @param b The block for which to construct the edges.
  * @param l The loop of b.
  *
  * There are four cases:
@@ -226,17 +252,25 @@ static void construct_interval_block(ir_node *b, ir_loop *l) {
 
     if (is_backedge(b, i)) {
       if (b != get_loop_element(l, 0).node) {
-	    if (get_firm_verbosity()) {
-	      printf("Loophead not at loop position 0. "); DDMN(b);
-	    }
+        if (get_firm_verbosity()) {
+	        printf("Loophead not at loop position 0. "); DDMN(b);
+        }
       }
       /* There are no backedges in the interval decomposition. */
       add_region_in(b, NULL);
       continue;
     }
 
-    cfop = skip_Proj(get_Block_cfgpred(b, i));
-    pred = get_nodes_block(cfop);
+    cfop = get_Block_cfgpred(b, i);
+    if (is_Proj(cfop)) {
+      if (get_irn_op(get_Proj_pred(cfop)) != op_Cond) {
+        cfop = skip_Proj(cfop);
+      } else {
+        assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop)));
+      }
+    }
+
+    pred = skip_Proj(get_nodes_block(cfop));
     /* We want nice blocks. */
     assert(   get_irn_op(pred) != op_Bad
            && get_irn_op(skip_Proj(get_Block_cfgpred(b, i))) != op_Bad);
@@ -338,9 +372,9 @@ void dump_region_edges(FILE *F, void *reg) {
   if (is_ir_node(reg) && get_Block_n_cfgpreds((ir_node *)reg) > get_region_n_ins(reg)) {
     for (i = n_ins; i < get_Block_n_cfgpreds((ir_node *)reg); ++i) {
       if (is_backedge((ir_node *)reg, i))
-	fprintf (F, "backedge: { sourcename: \"");
+        fprintf (F, "backedge: { sourcename: \"");
       else
-	fprintf (F, "edge: { sourcename: \"");
+        fprintf (F, "edge: { sourcename: \"");
       PRINT_NODEID(((ir_node *)reg));
       fprintf (F, "\" targetname: \"");
       PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
@@ -353,17 +387,17 @@ void dump_region_edges(FILE *F, void *reg) {
 
     if (is_ir_node(reg)) {
       if (get_Block_n_cfgpreds((ir_node *)reg) != get_region_n_ins(reg)) {
-	printf("n_cfgpreds = %d, n_ins = %d\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg));
-	DDMN((ir_node *)reg);
+        printf("n_cfgpreds = %d, n_ins = %d\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg));
+        DDMN((ir_node *)reg);
       }
     }
 
     if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) {
       assert(is_ir_node(reg));
       if (is_backedge((ir_node *)reg, i))
-	fprintf (F, "backedge: { sourcename: \"");
+        fprintf (F, "backedge: { sourcename: \"");
       else
-	fprintf (F, "edge: { sourcename: \"");
+        fprintf (F, "edge: { sourcename: \"");
       PRINT_NODEID(((ir_node *)reg));
       fprintf (F, "\" targetname: \"");
       PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
@@ -419,7 +453,7 @@ void dump_interval_block(FILE *F, ir_node *block) {
     ir_node *pred = get_Block_cfgpred(block, i);
     if (is_Bad(pred)) {
       if (! fl)
-	fprintf(F, "Bad pred at pos: ");
+        fprintf(F, "Bad pred at pos: ");
       fprintf(F, "%d ", i);
       fl = 1;
     }