X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FSparsePropagation.cpp;h=edd82f5fe296081f635da4713ac27b0043f14d59;hb=bb660fc192c341012f5f1686b6792be807a6d38b;hp=9c18751ed6f855787393fa52b9f6c7f3654de758;hpb=ab7d9ccf188da6b07977e3a003a0fe6a07b07e81;p=oota-llvm.git diff --git a/lib/Analysis/SparsePropagation.cpp b/lib/Analysis/SparsePropagation.cpp index 9c18751ed6f..edd82f5fe29 100644 --- a/lib/Analysis/SparsePropagation.cpp +++ b/lib/Analysis/SparsePropagation.cpp @@ -12,17 +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/Module.h" -#include "llvm/Pass.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/Streams.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; +#define DEBUG_TYPE "sparseprop" + //===----------------------------------------------------------------------===// // AbstractLatticeFunction Implementation //===----------------------------------------------------------------------===// @@ -30,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) @@ -60,8 +59,10 @@ SparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) { return LatticeFunc->getUntrackedVal(); else if (Constant *C = dyn_cast(V)) LV = LatticeFunc->ComputeConstant(C); + else if (Argument *A = dyn_cast(V)) + LV = LatticeFunc->ComputeArgument(A); else if (!isa(V)) - // Non-instructions (e.g. formal arguments) are overdefined. + // All other non-instructions are overdefined. LV = LatticeFunc->getOverdefinedVal(); else // All instructions are underdefined by default. @@ -88,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! } @@ -99,10 +100,10 @@ void SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) return; // This edge is already known to be executable! + DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() + << " -> " << Dest->getName() << "\n"); + if (BBExecutable.count(Dest)) { - DOUT << "Marking Edge Executable: " << Source->getNameStart() - << " -> " << Dest->getNameStart() << "\n"; - // The destination is already executable, but we just made an edge // feasible that wasn't before. Revisit the PHI nodes in the block // because they have potentially new operands. @@ -118,7 +119,8 @@ void SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { /// getFeasibleSuccessors - Return a vector of booleans to indicate which /// successors are reachable from a given terminator instruction. void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, - SmallVectorImpl &Succs) { + SmallVectorImpl &Succs, + bool AggressiveUndef) { Succs.resize(TI.getNumSuccessors()); if (TI.getNumSuccessors() == 0) return; @@ -128,7 +130,12 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, return; } - LatticeVal BCValue = getOrInitValueState(BI->getCondition()); + LatticeVal BCValue; + if (AggressiveUndef) + BCValue = getOrInitValueState(BI->getCondition()); + else + BCValue = getLatticeState(BI->getCondition()); + if (BCValue == LatticeFunc->getOverdefinedVal() || BCValue == LatticeFunc->getUntrackedVal()) { // Overdefined condition variables can branch either way. @@ -141,14 +148,14 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, return; Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this); - if (C == 0 || !isa(C)) { + if (!C || !isa(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; } @@ -159,8 +166,18 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, return; } + if (isa(TI)) { + Succs.assign(Succs.size(), true); + return; + } + SwitchInst &SI = cast(TI); - LatticeVal SCValue = getOrInitValueState(SI.getCondition()); + LatticeVal SCValue; + if (AggressiveUndef) + SCValue = getOrInitValueState(SI.getCondition()); + else + SCValue = getLatticeState(SI.getCondition()); + if (SCValue == LatticeFunc->getOverdefinedVal() || SCValue == LatticeFunc->getUntrackedVal()) { // All destinations are executable! @@ -173,22 +190,23 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, return; Constant *C = LatticeFunc->GetConstant(SCValue, SI.getCondition(), *this); - if (C == 0 || !isa(C)) { + if (!C || !isa(C)) { // All destinations are executable! Succs.assign(TI.getNumSuccessors(), true); return; } - - Succs[SI.findCaseValue(cast(C))] = true; + SwitchInst::CaseIt Case = SI.findCaseValue(cast(C)); + Succs[Case.getSuccessorIndex()] = true; } /// isEdgeFeasible - Return true if the control flow edge from the 'From' /// basic block to the 'To' basic block is currently feasible... -bool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { +bool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To, + bool AggressiveUndef) { SmallVector SuccFeasible; TerminatorInst *TI = From->getTerminator(); - getFeasibleSuccessors(*TI, SuccFeasible); + getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef); for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) if (TI->getSuccessor(i) == To && SuccFeasible[i]) @@ -199,7 +217,7 @@ bool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { void SparseSolver::visitTerminatorInst(TerminatorInst &TI) { SmallVector SuccFeasible; - getFeasibleSuccessors(TI, SuccFeasible); + getFeasibleSuccessors(TI, SuccFeasible, true); BasicBlock *BB = TI.getParent(); @@ -210,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(); @@ -229,7 +257,7 @@ void SparseSolver::visitPHINode(PHINode &PN) { // transfer function to give us the merge of the incoming values. for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { // If the edge is not yet known to be feasible, it doesn't impact the PHI. - if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) + if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true)) continue; // Merge in this value. @@ -263,7 +291,7 @@ void SparseSolver::visitInst(Instruction &I) { } void SparseSolver::Solve(Function &F) { - MarkBlockExecutable(F.begin()); + MarkBlockExecutable(&F.getEntryBlock()); // Process the work lists until they are empty! while (!BBWorkList.empty() || !InstWorkList.empty()) { @@ -272,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(*UI); - if (BBExecutable.count(U->getParent())) // Inst is executable? - visitInst(*U); + for (User *U : I->users()) { + Instruction *UI = cast(U); + if (BBExecutable.count(UI->getParent())) // Inst is executable? + visitInst(*UI); } } @@ -289,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. @@ -299,19 +326,19 @@ void SparseSolver::Solve(Function &F) { } } -void SparseSolver::Print(Function &F, std::ostream &OS) { - OS << "\nFUNCTION: " << F.getNameStr() << "\n"; +void SparseSolver::Print(Function &F, raw_ostream &OS) const { + OS << "\nFUNCTION: " << F.getName() << "\n"; for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!BBExecutable.count(BB)) OS << "INFEASIBLE: "; OS << "\t"; if (BB->hasName()) - OS << BB->getNameStr() << ":\n"; + 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; + OS << *I << "\n"; } OS << "\n";