Merging r258406:

[oota-llvm.git] / lib / Analysis / SparsePropagation.cpp

diff --git a/lib/Analysis/SparsePropagation.cpp b/lib/Analysis/SparsePropagation.cpp
index 8f042c278392f6645bab6954233de8be3200b361..f5a927b805258d6f7815131dffc8d520a8e26288 100644 (file)
--- a/lib/Analysis/SparsePropagation.cpp
+++ b/lib/Analysis/SparsePropagation.cpp
@@ -12,14 +12,16 @@
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "sparseprop"
 #include "llvm/Analysis/SparsePropagation.h"
-#include "llvm/Constants.h"
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
+#define DEBUG_TYPE "sparseprop"
+
 //===----------------------------------------------------------------------===//
 //                  AbstractLatticeFunction Implementation
 //===----------------------------------------------------------------------===//
@@ -27,7 +29,7 @@ using namespace llvm;
 AbstractLatticeFunction::~AbstractLatticeFunction() {}
 
 /// PrintValue - Render the specified lattice value to the specified stream.
-void AbstractLatticeFunction::PrintValue(LatticeVal V, std::ostream &OS) {
+void AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) {
   if (V == UndefVal)
     OS << "undefined";
   else if (V == OverdefinedVal)
@@ -87,7 +89,7 @@ void SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) {
 /// MarkBlockExecutable - This method can be used by clients to mark all of
 /// the blocks that are known to be intrinsically live in the processed unit.
 void SparseSolver::MarkBlockExecutable(BasicBlock *BB) {
-  DOUT << "Marking Block Executable: " << BB->getNameStart() << "\n";
+  DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
   BBExecutable.insert(BB);   // Basic block is executable!
   BBWorkList.push_back(BB);  // Add the block to the work list!
 }
@@ -98,8 +100,8 @@ void SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
   if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
     return;  // This edge is already known to be executable!
   
-  DOUT << "Marking Edge Executable: " << Source->getNameStart()
-       << " -> " << Dest->getNameStart() << "\n";
+  DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
+        << " -> " << Dest->getName() << "\n");
 
   if (BBExecutable.count(Dest)) {
     // The destination is already executable, but we just made an edge
@@ -146,14 +148,14 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI,
       return;
 
     Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this);
-    if (C == 0 || !isa<ConstantInt>(C)) {
+    if (!C || !isa<ConstantInt>(C)) {
       // Non-constant values can go either way.
       Succs[0] = Succs[1] = true;
       return;
     }
 
     // Constant condition variables mean the branch can only go a single way
-    Succs[C == ConstantInt::getFalse()] = true;
+    Succs[C->isNullValue()] = true;
     return;
   }
   
@@ -164,6 +166,11 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI,
     return;
   }
   
+  if (isa<IndirectBrInst>(TI)) {
+    Succs.assign(Succs.size(), true);
+    return;
+  }
+  
   SwitchInst &SI = cast<SwitchInst>(TI);
   LatticeVal SCValue;
   if (AggressiveUndef)
@@ -183,13 +190,13 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI,
     return;
   
   Constant *C = LatticeFunc->GetConstant(SCValue, SI.getCondition(), *this);
-  if (C == 0 || !isa<ConstantInt>(C)) {
+  if (!C || !isa<ConstantInt>(C)) {
     // All destinations are executable!
     Succs.assign(TI.getNumSuccessors(), true);
     return;
   }
-  
-  Succs[SI.findCaseValue(cast<ConstantInt>(C))] = true;
+  SwitchInst::CaseIt Case = SI.findCaseValue(cast<ConstantInt>(C));
+  Succs[Case.getSuccessorIndex()] = true;
 }
 
 
@@ -221,6 +228,16 @@ void SparseSolver::visitTerminatorInst(TerminatorInst &TI) {
 }
 
 void SparseSolver::visitPHINode(PHINode &PN) {
+  // The lattice function may store more information on a PHINode than could be
+  // computed from its incoming values.  For example, SSI form stores its sigma
+  // functions as PHINodes with a single incoming value.
+  if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
+    LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this);
+    if (IV != LatticeFunc->getUntrackedVal())
+      UpdateState(PN, IV);
+    return;
+  }
+
   LatticeVal PNIV = getOrInitValueState(&PN);
   LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
   
@@ -283,15 +300,14 @@ void SparseSolver::Solve(Function &F) {
       Instruction *I = InstWorkList.back();
       InstWorkList.pop_back();
 
-      DOUT << "\nPopped off I-WL: " << *I;
+      DEBUG(dbgs() << "\nPopped off I-WL: " << *I << "\n");
 
       // "I" got into the work list because it made a transition.  See if any
       // users are both live and in need of updating.
-      for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
-           UI != E; ++UI) {
-        Instruction *U = cast<Instruction>(*UI);
-        if (BBExecutable.count(U->getParent()))   // Inst is executable?
-          visitInst(*U);
+      for (User *U : I->users()) {
+        Instruction *UI = cast<Instruction>(U);
+        if (BBExecutable.count(UI->getParent()))   // Inst is executable?
+          visitInst(*UI);
       }
     }
 
@@ -300,7 +316,7 @@ void SparseSolver::Solve(Function &F) {
       BasicBlock *BB = BBWorkList.back();
       BBWorkList.pop_back();
 
-      DOUT << "\nPopped off BBWL: " << *BB;
+      DEBUG(dbgs() << "\nPopped off BBWL: " << *BB);
 
       // Notify all instructions in this basic block that they are newly
       // executable.
@@ -310,19 +326,19 @@ void SparseSolver::Solve(Function &F) {
   }
 }
 
-void SparseSolver::Print(Function &F, std::ostream &OS) {
-  OS << "\nFUNCTION: " << F.getNameStr() << "\n";
-  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
-    if (!BBExecutable.count(BB))
+void SparseSolver::Print(Function &F, raw_ostream &OS) const {
+  OS << "\nFUNCTION: " << F.getName() << "\n";
+  for (auto &BB : F) {
+    if (!BBExecutable.count(&BB))
       OS << "INFEASIBLE: ";
     OS << "\t";
-    if (BB->hasName())
-      OS << BB->getNameStr() << ":\n";
+    if (BB.hasName())
+      OS << BB.getName() << ":\n";
     else
       OS << "; anon bb\n";
-    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
-      LatticeFunc->PrintValue(getLatticeState(I), OS);
-      OS << *I;
+    for (auto &I : BB) {
+      LatticeFunc->PrintValue(getLatticeState(&I), OS);
+      OS << I << "\n";
     }
     
     OS << "\n";