X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FSparsePropagation.cpp;h=c819666ee44445780b975edd2810b3bba4f253f6;hb=d6fc26217e194372cabe4ef9e2514beac511a943;hp=c5d99d49e131a1aabf2d2d088ba1a0b1eadf6237;hpb=4651f3de3489bc82e0fe4a3df14d493148e68fca;p=oota-llvm.git diff --git a/lib/Analysis/SparsePropagation.cpp b/lib/Analysis/SparsePropagation.cpp index c5d99d49e13..c819666ee44 100644 --- a/lib/Analysis/SparsePropagation.cpp +++ b/lib/Analysis/SparsePropagation.cpp @@ -18,6 +18,7 @@ #include "llvm/Function.h" #include "llvm/Instructions.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; //===----------------------------------------------------------------------===// @@ -27,7 +28,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) @@ -57,8 +58,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. @@ -85,7 +88,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! } @@ -96,10 +99,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. @@ -115,7 +118,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; @@ -125,7 +129,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. @@ -145,7 +154,7 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, } // Constant condition variables mean the branch can only go a single way - Succs[C == ConstantInt::getFalse()] = true; + Succs[C->isNullValue()] = true; return; } @@ -156,8 +165,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! @@ -175,17 +194,18 @@ void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, 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]) @@ -196,7 +216,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(); @@ -207,6 +227,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(); @@ -226,7 +256,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. @@ -260,7 +290,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()) { @@ -269,7 +299,7 @@ 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. @@ -286,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. @@ -296,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";