From a352dbe57a639b93d07240963f5e345527abfbd8 Mon Sep 17 00:00:00 2001
From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= <goetz@ipd.info.uni-karlsruhe.de>
Date: Fri, 26 Nov 2004 14:21:18 +0000
Subject: [PATCH] added test whether loop invariant

[r4474]
---
 ir/ana/irloop.h | 30 ++++++++++++++++++++++++------
 ir/ana/irscc.c  | 40 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 64 insertions(+), 6 deletions(-)

diff --git a/ir/ana/irloop.h b/ir/ana/irloop.h
index 8ea6e71b2..051c22d95 100644
--- a/ir/ana/irloop.h
+++ b/ir/ana/irloop.h
@@ -27,9 +27,7 @@
 # include "irgraph.h"
 # include "irnode.h"
 
-
-/* @@@ Interprocedural backedges ... ???? */
-
+/* ------------------------------------------------------------------- */
 /*
  * Backedge information.
  *
@@ -39,6 +37,7 @@
  * The backedge information can only be used if the graph is not in
  * phase phase_building.
  */
+/* ------------------------------------------------------------------- */
 
 /** Returns true if the predesessor pos is a backedge. */
 bool is_backedge (ir_node *n, int pos);
@@ -51,6 +50,7 @@ bool has_backedges (ir_node *n);
 /** Sets backedge information to zero. */
 void clear_backedges (ir_node *n);
 
+/* ------------------------------------------------------------------- */
 /**
  * The loops datastructure.
  *
@@ -67,6 +67,7 @@ void clear_backedges (ir_node *n);
  * @todo We could add a field pointing from a node to the containing loop,
  * this would cost a lot of memory, though.
  */
+/* ------------------------------------------------------------------- */
 typedef struct ir_loop ir_loop;
 
 /* Loop elements are loop nodes and ir nodes */
@@ -118,9 +119,9 @@ int get_loop_loop_nr(ir_loop *loop);
 void  set_loop_link (ir_loop *loop, void *link);
 void *get_loop_link (const ir_loop *loop);
 
-/*
- * Constructing and destructing the loop/backedge information.
- */
+/* ------------------------------------------------------------------- */
+/* Constructing and destructing the loop/backedge information.         */
+/* ------------------------------------------------------------------- */
 
 /** Constructs backedge information for irg in intraprocedural view.
  *  @returns Maximal depth of loop tree. */
@@ -145,4 +146,21 @@ int construct_ip_cf_backedges (void);
 void free_loop_information(ir_graph *irg);
 void free_all_loop_information (void);
 
+
+
+
+/* ------------------------------------------------------------------- */
+/* Simple analyses based on the loop information                       */
+/* ------------------------------------------------------------------- */
+
+/** Test whether a value is loop invariant.
+ *
+ * @param n      The node to be tested.
+ * @param block  A block node.
+ *
+ * Returns true, if the node n is not changed in the loop block
+ * belongs to or in inner loops of this block. */
+int is_loop_invariant(ir_node *n, ir_node *block);
+
+
 #endif /* _IRLOOP_H_ */
diff --git a/ir/ana/irscc.c b/ir/ana/irscc.c
index 035258991..6d24951e1 100644
--- a/ir/ana/irscc.c
+++ b/ir/ana/irscc.c
@@ -1422,3 +1422,43 @@ void find_strange_loop_nodes(ir_loop *l) {
   if (found_problem) exit(0);
 
 }
+
+
+
+
+
+
+
+/* ------------------------------------------------------------------- */
+/* Simple analyses based on the loop information                       */
+/* ------------------------------------------------------------------- */
+
+int is_loop_variant(ir_loop *l, ir_loop *b) {
+  int i, n_elems =  get_loop_n_elements (l);
+
+  if (l == b) return true;
+
+  for (i = 0; i < n_elems; ++i) {
+    loop_element e = get_loop_element(l, i);
+    if (is_ir_node (e.kind)) {
+    } else {
+      if (is_loop_variant(e.son), b) return true;
+    }
+  }
+
+  return false;
+}
+
+/* Test whether a value is loop invariant.
+ *
+ * @param n      The node to be tested.
+ * @param block  A block node.  We pass the block, not the loop as we must
+ *               start off with a block loop to find all proper uses.
+ *
+ * Returns true, if the node n is not changed in the loop block
+ * belongs to or in inner loops of this block. */
+int is_loop_invariant(ir_node *n, ir_node *block) {
+  ir_loop *l = get_irn_loop(block);
+  ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
+  return !is_loop_variant(l, get_irn_loop(b));
+}
-- 
2.20.1