Index: include/llvm/Analysis/SparsePropagation.h =================================================================== --- include/llvm/Analysis/SparsePropagation.h +++ include/llvm/Analysis/SparsePropagation.h @@ -17,6 +17,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/Instruction.h" #include #include #include @@ -27,7 +28,6 @@ class BasicBlock; class Constant; class Function; -class Instruction; class PHINode; class raw_ostream; class SparseSolver; @@ -44,7 +44,8 @@ /// class AbstractLatticeFunction { public: - using LatticeVal = void *; + using LatticeVal = const void *; + using StateTy = DenseMap; private: LatticeVal UndefVal, OverdefinedVal, UntrackedVal; @@ -63,11 +64,22 @@ LatticeVal getOverdefinedVal() const { return OverdefinedVal; } LatticeVal getUntrackedVal() const { return UntrackedVal; } - /// IsUntrackedValue - If the specified Value is something that is obviously - /// uninteresting to the analysis (and would always return UntrackedVal), - /// this function can return true to avoid pointless work. + /// IsUntrackedValue - If the specified value is obviously uninteresting to + /// the analysis (i.e., it would always return UntrackedVal), this function + /// can return true to avoid pointless work. virtual bool IsUntrackedValue(Value *V) { return false; } + /// IsUntrackedGlobalVariable - If the specified global variable holds values + /// that are obviously uninteresting to the analysis (i.e., they would always + /// return UntrackedVal), this function can return true to avoid pointless + /// work. + virtual bool IsUntrackedGlobalVariable(GlobalVariable *V) { return false; } + + /// IsUntrackedFunction - If the specified function returns values that are + /// obviously uninteresting to the analysis (i.e., they would always return + /// UntrackedVal), this function can return true to avoid pointless work. + virtual bool IsUntrackedFunction(Function *V) { return false; } + /// ComputeConstant - Given a constant value, compute and return a lattice /// value corresponding to the specified constant. virtual LatticeVal ComputeConstant(Constant *C) { @@ -91,6 +103,18 @@ return getOverdefinedVal(); // always safe } + /// ComputeGlobalVariable - Given a global variable, compute and return a + /// lattice value corresponding to the value stored in the global. + virtual LatticeVal ComputeGlobalVariable(GlobalVariable *GV) { + return getOverdefinedVal(); // always safe + } + + /// ComputeFunction - Given a function, compute and return a lattice value + /// corresponding to the function's return value. + virtual LatticeVal ComputeFunction(Function *F) { + return getOverdefinedVal(); // always safe + } + /// MergeValues - Compute and return the merge of the two specified lattice /// values. Merging should only move one direction down the lattice to /// guarantee convergence (toward overdefined). @@ -98,10 +122,12 @@ return getOverdefinedVal(); // always safe, never useful. } - /// ComputeInstructionState - Given an instruction and a vector of its operand - /// values, compute the result value of the instruction. - virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) { - return getOverdefinedVal(); // always safe, never useful. + /// ComputeInstructionState - Compute the lattice values that change as a + /// result of executing instruction \p I. The changed values are store in \p + /// CV. + virtual void ComputeInstructionState(Instruction &I, StateTy &CV, + SparseSolver &S) { + CV[&I] = getOverdefinedVal(); // always safe, never useful. } /// PrintValue - Render the specified lattice value to the specified stream. @@ -112,17 +138,40 @@ /// Propagation with a programmable lattice function. class SparseSolver { using LatticeVal = AbstractLatticeFunction::LatticeVal; + using StateTy = AbstractLatticeFunction::StateTy; /// LatticeFunc - This is the object that knows the lattice and how to do /// compute transfer functions. AbstractLatticeFunction *LatticeFunc; - DenseMap ValueState; // The state each value is in. - SmallPtrSet BBExecutable; // The bbs that are executable. + /// ValueState - Holds the lattice state associated with LLVM values. + StateTy ValueState; + + /// FunctionState - Holds the lattice state for function return values. We + /// maintain a separate map for returns because functions can return more + /// than one value (i.e., there's no key with which to associate the return + /// lattice state other than the function itself). LLVM functions can also be + /// tracked independently in the ValueState map, so we need a separate one + /// for returns. + StateTy FunctionState; + + /// GlobalVariableState - Holds the lattice state for values stored in global + /// variables. Similar to function returns, we maintain a separate map for + /// global variables because a global variable is the only key with which to + /// associate the values stored at its location. Additionally, LLVM global + /// variables can also be tracked independently in the ValueState map. This + /// map maintains the state of in-memory values, not their addresses. + StateTy GlobalVariableState; + + /// BBWorkList - Holds basic blocks that should be processed. + std::vector BBWorkList; - std::vector InstWorkList; // Worklist of insts to process. + /// ValueWorkList - Holds values (i.e., instructions and global variables) + /// that should be processed. + std::vector ValueWorkList; - std::vector BBWorkList; // The BasicBlock work list + /// BBExecutable - Holds the basic blocks that are executable. + SmallPtrSet BBExecutable; /// KnownFeasibleEdges - Entries in this set are edges which have already had /// PHI nodes retriggered. @@ -134,28 +183,43 @@ : LatticeFunc(Lattice) {} SparseSolver(const SparseSolver &) = delete; SparseSolver &operator=(const SparseSolver &) = delete; - ~SparseSolver() { delete LatticeFunc; } /// Solve - Solve for constants and executable blocks. - void Solve(Function &F); + void Solve(); - void Print(Function &F, raw_ostream &OS) const; + /// Print - Print the contents of each of the states maps. + void Print(raw_ostream &OS) const; - /// getLatticeState - Return the LatticeVal object that corresponds to the - /// value. If an value is not in the map, it is returned as untracked, - /// unlike the getOrInitValueState method. - LatticeVal getLatticeState(Value *V) const { - DenseMap::const_iterator I = ValueState.find(V); - return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal(); - } + /// getValueState - Return the LatticeVal object corresponding to the given + /// value from the ValueState map. If the value is not in the map, + /// UntrackedVal is returned. + LatticeVal getValueState(Value *V) const; + + /// getGlobalVariableState - Return the LatticeVal object corresponding to + /// the given global variable from the GlobalVariableState map. If the global + /// variable is not in the map, UntrackedVal is returned. + LatticeVal getGlobalVariableState(GlobalVariable *GV) const; + + /// getFunctionState - Return the LatticeVal object corresponding to the + /// given function from the FunctionState map. If the function is not in the + /// map, UntrackedVal is returned. + LatticeVal getFunctionState(Function *F) const; - /// getOrInitValueState - Return the LatticeVal object that corresponds to the - /// value, initializing the value's state if it hasn't been entered into the - /// map yet. This function is necessary because not all values should start - /// out in the underdefined state... Arguments should be overdefined, and - /// constants should be marked as constants. + /// getOrInitValueState - Return the LatticeVal object corresponding to the + /// given value from the ValueState map. If the value is not in the map, its + /// state is initialized. LatticeVal getOrInitValueState(Value *V); + /// getOrInitGlobalVariableState - Return the LatticeVal object corresponding + /// to the given global variable from the GlobalVariableState map. If the + /// global variable is not in the map, its state is initialized. + LatticeVal getOrInitGlobalVariableState(GlobalVariable *GV); + + /// getOrInitFunctionState - Return the LatticeVal object corresponding to + /// the given function from the FunctionState map. If the function is not in + /// the map, its state is initialized. + LatticeVal getOrInitFunctionState(Function *F); + /// isEdgeFeasible - Return true if the control flow edge from the 'From' /// basic block to the 'To' basic block is currently feasible. If /// AggressiveUndef is true, then this treats values with unknown lattice @@ -171,15 +235,22 @@ return BBExecutable.count(BB); } -private: - /// UpdateState - When the state for some instruction is potentially updated, - /// this function notices and adds I to the worklist if needed. - void 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 MarkBlockExecutable(BasicBlock *BB); +private: + /// UpdateState - When the state for some value is potentially updated, this + /// function notices and adds V to the worklist if needed. + void UpdateState(Value &V, LatticeVal LV, StateTy &State); + + /// getStateMapForInstruction - Return a reference to the state map + /// appropriate for the given instruction. + StateTy &getStateMapForInstruction(Instruction &I); + + /// printStateMap - Print the contents of the given state map. + void printStateMap(const StateTy &State, raw_ostream &OS) const; + /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB /// work list if it is not already executable. void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest); Index: lib/Analysis/SparsePropagation.cpp =================================================================== --- lib/Analysis/SparsePropagation.cpp +++ lib/Analysis/SparsePropagation.cpp @@ -20,8 +20,8 @@ #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" +#include "llvm/IR/GlobalVariable.h" #include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/User.h" #include "llvm/Support/Casting.h" @@ -54,13 +54,25 @@ // SparseSolver Implementation //===----------------------------------------------------------------------===// -/// getOrInitValueState - Return the LatticeVal object that corresponds to the -/// value, initializing the value's state if it hasn't been entered into the -/// map yet. This function is necessary because not all values should start -/// out in the underdefined state... Arguments should be overdefined, and -/// constants should be marked as constants. +SparseSolver::LatticeVal SparseSolver::getValueState(Value *V) const { + StateTy::const_iterator I = ValueState.find(V); + return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal(); +} + +SparseSolver::LatticeVal +SparseSolver::getGlobalVariableState(GlobalVariable *GV) const { + StateTy::const_iterator I = GlobalVariableState.find(GV); + return I != GlobalVariableState.end() ? I->second + : LatticeFunc->getUntrackedVal(); +} + +SparseSolver::LatticeVal SparseSolver::getFunctionState(Function *F) const { + StateTy::const_iterator I = FunctionState.find(F); + return I != FunctionState.end() ? I->second : LatticeFunc->getUntrackedVal(); +} + SparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) { - DenseMap::iterator I = ValueState.find(V); + StateTy::iterator I = ValueState.find(V); if (I != ValueState.end()) return I->second; // Common case, in the map LatticeVal LV; @@ -83,23 +95,43 @@ return ValueState[V] = LV; } +SparseSolver::LatticeVal +SparseSolver::getOrInitGlobalVariableState(GlobalVariable *GV) { + StateTy::iterator I = GlobalVariableState.find(GV); + if (I != GlobalVariableState.end()) + return I->second; + if (LatticeFunc->IsUntrackedGlobalVariable(GV)) + return LatticeFunc->getUntrackedVal(); + return GlobalVariableState[GV] = LatticeFunc->ComputeGlobalVariable(GV); +} + +SparseSolver::LatticeVal SparseSolver::getOrInitFunctionState(Function *F) { + StateTy::iterator I = FunctionState.find(F); + if (I != FunctionState.end()) + return I->second; + if (LatticeFunc->IsUntrackedFunction(F)) + return LatticeFunc->getUntrackedVal(); + return FunctionState[F] = LatticeFunc->ComputeFunction(F); +} + /// UpdateState - When the state for some instruction is potentially updated, /// this function notices and adds I to the worklist if needed. -void SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) { - DenseMap::iterator I = ValueState.find(&Inst); - if (I != ValueState.end() && I->second == V) +void SparseSolver::UpdateState(Value &V, LatticeVal LV, StateTy &State) { + StateTy::iterator I = State.find(&V); + if (I != State.end() && I->second == LV) return; // No change. // An update. Visit uses of I. - ValueState[&Inst] = V; - InstWorkList.push_back(&Inst); + State[&V] = LV; + ValueWorkList.push_back(&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) { + if (!BBExecutable.insert(BB).second) + return; 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! } @@ -141,7 +173,7 @@ if (AggressiveUndef) BCValue = getOrInitValueState(BI->getCondition()); else - BCValue = getLatticeState(BI->getCondition()); + BCValue = getValueState(BI->getCondition()); if (BCValue == LatticeFunc->getOverdefinedVal() || BCValue == LatticeFunc->getUntrackedVal()) { @@ -166,10 +198,8 @@ return; } - if (isa(TI)) { - // Invoke instructions successors are always executable. - // TODO: Could ask the lattice function if the value can throw. - Succs[0] = Succs[1] = true; + if (TI.isExceptional()) { + Succs.assign(Succs.size(), true); return; } @@ -183,7 +213,7 @@ if (AggressiveUndef) SCValue = getOrInitValueState(SI.getCondition()); else - SCValue = getLatticeState(SI.getCondition()); + SCValue = getValueState(SI.getCondition()); if (SCValue == LatticeFunc->getOverdefinedVal() || SCValue == LatticeFunc->getUntrackedVal()) { @@ -238,9 +268,12 @@ // 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); + StateTy ChangedValues; + LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this); + for (auto &ChangedValue : ChangedValues) { + if (ChangedValue.second != LatticeFunc->getUntrackedVal()) + UpdateState(*ChangedValue.first, ChangedValue.second, ValueState); + } return; } @@ -254,7 +287,7 @@ // Super-extra-high-degree PHI nodes are unlikely to ever be interesting, // and slow us down a lot. Just mark them overdefined. if (PN.getNumIncomingValues() > 64) { - UpdateState(PN, Overdefined); + UpdateState(PN, Overdefined, ValueState); return; } @@ -276,7 +309,15 @@ } // Update the PHI with the compute value, which is the merge of the inputs. - UpdateState(PN, PNIV); + UpdateState(PN, PNIV, ValueState); +} + +SparseSolver::StateTy &SparseSolver::getStateMapForInstruction(Instruction &I) { + switch (I.getOpcode()) { + case Instruction::Ret: return FunctionState; + case Instruction::Store: return GlobalVariableState; + default: return ValueState; + } } void SparseSolver::visitInst(Instruction &I) { @@ -287,32 +328,35 @@ // Otherwise, ask the transfer function what the result is. If this is // something that we care about, remember it. - LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this); - if (IV != LatticeFunc->getUntrackedVal()) - UpdateState(I, IV); - + StateTy ChangedValues; + LatticeFunc->ComputeInstructionState(I, ChangedValues, *this); + for (auto &ChangedValue : ChangedValues) { + if (ChangedValue.second != LatticeFunc->getUntrackedVal()) + UpdateState(*ChangedValue.first, ChangedValue.second, + getStateMapForInstruction(I)); + } + if (TerminatorInst *TI = dyn_cast(&I)) visitTerminatorInst(*TI); } -void SparseSolver::Solve(Function &F) { - MarkBlockExecutable(&F.getEntryBlock()); - +void SparseSolver::Solve() { + // Process the work lists until they are empty! - while (!BBWorkList.empty() || !InstWorkList.empty()) { + while (!BBWorkList.empty() || !ValueWorkList.empty()) { // Process the instruction work list. - while (!InstWorkList.empty()) { - Instruction *I = InstWorkList.back(); - InstWorkList.pop_back(); + while (!ValueWorkList.empty()) { + Value *I = ValueWorkList.back(); + ValueWorkList.pop_back(); 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 (User *U : I->users()) { - Instruction *UI = cast(U); - if (BBExecutable.count(UI->getParent())) // Inst is executable? - visitInst(*UI); + if (Instruction *UI = dyn_cast(U)) + if (BBExecutable.count(UI->getParent())) // Inst is executable? + visitInst(*UI); } } @@ -331,21 +375,39 @@ } } -void SparseSolver::Print(Function &F, raw_ostream &OS) const { - OS << "\nFUNCTION: " << F.getName() << "\n"; - for (auto &BB : F) { - if (!BBExecutable.count(&BB)) - OS << "INFEASIBLE: "; +void SparseSolver::printStateMap(const StateTy &State, raw_ostream &OS) const { + if (State.empty()) + return; + + LatticeVal LV; + Value *V; + + if (&State == &FunctionState) + OS << "FunctionState:\n"; + else if (&State == &GlobalVariableState) + OS << "GlobalVariableState:\n"; + else if (&State == &ValueState) + OS << "ValueState:\n"; + else + llvm_unreachable("Unknown state map"); + + for (auto &StateEntry : State) { + std::tie(V, LV) = StateEntry; + if (LV == LatticeFunc->getUntrackedVal()) + continue; OS << "\t"; - if (BB.hasName()) - OS << BB.getName() << ":\n"; + LatticeFunc->PrintValue(LV, OS); + OS << ": "; + if (isa(V)) + OS << V->getName() << "\n"; else - OS << "; anon bb\n"; - for (auto &I : BB) { - LatticeFunc->PrintValue(getLatticeState(&I), OS); - OS << I << "\n"; - } - - OS << "\n"; + OS << *V << "\n"; } + OS << "\n"; +} + +void SparseSolver::Print(raw_ostream &OS) const { + printStateMap(FunctionState, OS); + printStateMap(GlobalVariableState, OS); + printStateMap(ValueState, OS); }