From da956802bd8b789f0769960083f718bface44f6f Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Thu, 21 Jun 2001 05:27:22 +0000
Subject: [PATCH] Moved printing code to the Assembly/Writer library. Code now
 detects looping intervals

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/Writer.cpp                 | 28 +++++++++++
 lib/Transforms/Scalar/InductionVars.cpp | 66 +++++++++++++++----------
 2 files changed, 67 insertions(+), 27 deletions(-)
 create mode 100644 lib/Analysis/Writer.cpp

diff --git a/lib/Analysis/Writer.cpp b/lib/Analysis/Writer.cpp
new file mode 100644
index 00000000000..3abe70a7dfb
--- /dev/null
+++ b/lib/Analysis/Writer.cpp
@@ -0,0 +1,28 @@
+//===-- IntervalWriter.cpp - Library for printing Intervals ------*- C++ -*--=//
+//
+// This library implements the interval printing functionality defined in 
+// llvm/Assembly/Writer.h
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Assembly/Writer.h"
+#include "llvm/Analysis/Intervals.h"
+#include <iterator>
+#include <algorithm>
+
+void cfg::WriteToOutput(const Interval *I, ostream &o) {
+  o << "-------------------------------------------------------------\n"
+       << "Interval Contents:\n";
+  
+  // Print out all of the basic blocks in the interval...
+  copy(I->Nodes.begin(), I->Nodes.end(), 
+       ostream_iterator<BasicBlock*>(o, "\n"));
+
+  o << "Interval Predecessors:\n";
+  copy(I->Predecessors.begin(), I->Predecessors.end(), 
+       ostream_iterator<BasicBlock*>(o, "\n"));
+  
+  o << "Interval Successors:\n";
+  copy(I->Successors.begin(), I->Successors.end(), 
+       ostream_iterator<BasicBlock*>(o, "\n"));
+}
diff --git a/lib/Transforms/Scalar/InductionVars.cpp b/lib/Transforms/Scalar/InductionVars.cpp
index e2f2ad90e67..a9e4c5b5cb0 100644
--- a/lib/Transforms/Scalar/InductionVars.cpp
+++ b/lib/Transforms/Scalar/InductionVars.cpp
@@ -14,40 +14,52 @@
 #include "llvm/Analysis/Intervals.h"
 #include "llvm/Opt/AllOpts.h"
 #include "llvm/Assembly/Writer.h"
+#include "llvm/Tools/STLExtras.h"
 
-static void PrintIntervalInfo(cfg::Interval *I) {
-  cerr << "-------------------------------------------------------------\n"
-       << "Interval Contents:\n";
-  
-  // Print out all of the basic blocks in the interval...
-  copy(I->Nodes.begin(), I->Nodes.end(), 
-       ostream_iterator<BasicBlock*>(cerr, "\n"));
-
-  cerr << "Interval Predecessors:\n";
-  copy(I->Predecessors.begin(), I->Predecessors.end(), 
-       ostream_iterator<BasicBlock*>(cerr, "\n"));
-  
-  cerr << "Interval Successors:\n";
-  copy(I->Successors.begin(), I->Successors.end(), 
-       ostream_iterator<BasicBlock*>(cerr, "\n"));
+static bool ProcessInterval(cfg::Interval *Int) {
+  if (!Int->isLoop()) return false;  // Not a loop?  Ignore it!
+
+  cerr << "Found Looping Interval: " << Int; //->HeaderNode;
+  return false;
+}
+
+static bool ProcessIntervalPartition(cfg::IntervalPartition &IP) {
+  // This currently just prints out information about the interval structure
+  // of the method...
+  static unsigned N = 0;
+  cerr << "\n***********Interval Partition #" << (++N) << "************\n\n";
+  copy(IP.begin(), IP.end(), ostream_iterator<cfg::Interval*>(cerr, "\n"));
+
+  cerr << "\n*********** PERFORMING WORK ************\n\n";
+
+  // Loop over all of the intervals in the partition and look for induction
+  // variables in intervals that represent loops.
+  //
+  return reduce_apply(IP.begin(), IP.end(), bitwise_or<bool>(), false,
+		      ptr_fun(ProcessInterval));
 }
 
 // DoInductionVariableCannonicalize - Simplify induction variables in loops
 //
 bool DoInductionVariableCannonicalize(Method *M) {
-  cfg::IntervalPartition Intervals(M);
+  cfg::IntervalPartition *IP = new cfg::IntervalPartition(M);
+  bool Changed = false;
 
-  // This currently just prints out information about the interval structure
-  // of the method...
-  for_each(Intervals.begin(), Intervals.end(), PrintIntervalInfo);
+  while (!IP->isDegeneratePartition()) {
+    Changed |= ProcessIntervalPartition(*IP);
 
-  cerr << "*************Reduced Interval**************\n\n";
+    // Calculate the reduced version of this graph until we get to an 
+    // irreducible graph or a degenerate graph...
+    //
+    cfg::IntervalPartition *NewIP = new cfg::IntervalPartition(*IP, false);
+    if (NewIP->size() == IP->size()) {
+      cerr << "IRREDUCIBLE GRAPH FOUND!!!\n";
+      return Changed;
+    }
+    delete IP;
+    IP = NewIP;
+  }
 
-  cfg::IntervalPartition Intervals2(Intervals, false);
-  
-  // This currently just prints out information about the interval structure
-  // of the method...
-  for_each(Intervals2.begin(), Intervals2.end(), PrintIntervalInfo);
-
-  return false;
+  delete IP;
+  return Changed;
 }
-- 
2.34.1