LCOV - code coverage report
Current view: top level - include/llvm/Analysis - SparsePropagation.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 108 140 77.1 %
Date: 2018-10-17 09:37:48 Functions: 24 43 55.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements an abstract sparse conditional propagation algorithm,
      11             : // modeled after SCCP, but with a customizable lattice function.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
      16             : #define LLVM_ANALYSIS_SPARSEPROPAGATION_H
      17             : 
      18             : #include "llvm/IR/Instructions.h"
      19             : #include "llvm/Support/Debug.h"
      20             : #include <set>
      21             : 
      22             : #define DEBUG_TYPE "sparseprop"
      23             : 
      24             : namespace llvm {
      25             : 
      26             : /// A template for translating between LLVM Values and LatticeKeys. Clients must
      27             : /// provide a specialization of LatticeKeyInfo for their LatticeKey type.
      28             : template <class LatticeKey> struct LatticeKeyInfo {
      29             :   // static inline Value *getValueFromLatticeKey(LatticeKey Key);
      30             :   // static inline LatticeKey getLatticeKeyFromValue(Value *V);
      31             : };
      32             : 
      33             : template <class LatticeKey, class LatticeVal,
      34             :           class KeyInfo = LatticeKeyInfo<LatticeKey>>
      35             : class SparseSolver;
      36             : 
      37             : /// AbstractLatticeFunction - This class is implemented by the dataflow instance
      38             : /// to specify what the lattice values are and how they handle merges etc.  This
      39             : /// gives the client the power to compute lattice values from instructions,
      40             : /// constants, etc.  The current requirement is that lattice values must be
      41             : /// copyable.  At the moment, nothing tries to avoid copying.  Additionally,
      42             : /// lattice keys must be able to be used as keys of a mapping data structure.
      43             : /// Internally, the generic solver currently uses a DenseMap to map lattice keys
      44             : /// to lattice values.  If the lattice key is a non-standard type, a
      45             : /// specialization of DenseMapInfo must be provided.
      46             : template <class LatticeKey, class LatticeVal> class AbstractLatticeFunction {
      47             : private:
      48             :   LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
      49             : 
      50             : public:
      51        1788 :   AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
      52        1781 :                           LatticeVal untrackedVal) {
      53           7 :     UndefVal = undefVal;
      54           7 :     OverdefinedVal = overdefinedVal;
      55           7 :     UntrackedVal = untrackedVal;
      56        1781 :   }
      57             : 
      58        1781 :   virtual ~AbstractLatticeFunction() = default;
      59             : 
      60           0 :   LatticeVal getUndefVal()       const { return UndefVal; }
      61           0 :   LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
      62           0 :   LatticeVal getUntrackedVal()   const { return UntrackedVal; }
      63             : 
      64             :   /// IsUntrackedValue - If the specified LatticeKey is obviously uninteresting
      65             :   /// to the analysis (i.e., it would always return UntrackedVal), this
      66             :   /// function can return true to avoid pointless work.
      67           0 :   virtual bool IsUntrackedValue(LatticeKey Key) { return false; }
      68             : 
      69             :   /// ComputeLatticeVal - Compute and return a LatticeVal corresponding to the
      70             :   /// given LatticeKey.
      71           0 :   virtual LatticeVal ComputeLatticeVal(LatticeKey Key) {
      72           0 :     return getOverdefinedVal();
      73             :   }
      74             : 
      75             :   /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
      76             :   /// one that the we want to handle through ComputeInstructionState.
      77           0 :   virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
      78             : 
      79             :   /// MergeValues - Compute and return the merge of the two specified lattice
      80             :   /// values.  Merging should only move one direction down the lattice to
      81             :   /// guarantee convergence (toward overdefined).
      82           0 :   virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
      83           0 :     return getOverdefinedVal(); // always safe, never useful.
      84             :   }
      85             : 
      86             :   /// ComputeInstructionState - Compute the LatticeKeys that change as a result
      87             :   /// of executing instruction \p I. Their associated LatticeVals are store in
      88             :   /// \p ChangedValues.
      89             :   virtual void
      90             :   ComputeInstructionState(Instruction &I,
      91             :                           DenseMap<LatticeKey, LatticeVal> &ChangedValues,
      92             :                           SparseSolver<LatticeKey, LatticeVal> &SS) = 0;
      93             : 
      94             :   /// PrintLatticeVal - Render the given LatticeVal to the specified stream.
      95             :   virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS);
      96             : 
      97             :   /// PrintLatticeKey - Render the given LatticeKey to the specified stream.
      98             :   virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS);
      99             : 
     100             :   /// GetValueFromLatticeVal - If the given LatticeVal is representable as an
     101             :   /// LLVM value, return it; otherwise, return nullptr. If a type is given, the
     102             :   /// returned value must have the same type. This function is used by the
     103             :   /// generic solver in attempting to resolve branch and switch conditions.
     104           0 :   virtual Value *GetValueFromLatticeVal(LatticeVal LV, Type *Ty = nullptr) {
     105           0 :     return nullptr;
     106             :   }
     107             : };
     108             : 
     109             : /// SparseSolver - This class is a general purpose solver for Sparse Conditional
     110             : /// Propagation with a programmable lattice function.
     111             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     112             : class SparseSolver {
     113             : 
     114             :   /// LatticeFunc - This is the object that knows the lattice and how to
     115             :   /// compute transfer functions.
     116             :   AbstractLatticeFunction<LatticeKey, LatticeVal> *LatticeFunc;
     117             : 
     118             :   /// ValueState - Holds the LatticeVals associated with LatticeKeys.
     119             :   DenseMap<LatticeKey, LatticeVal> ValueState;
     120             : 
     121             :   /// BBExecutable - Holds the basic blocks that are executable.
     122             :   SmallPtrSet<BasicBlock *, 16> BBExecutable;
     123             : 
     124             :   /// ValueWorkList - Holds values that should be processed.
     125             :   SmallVector<Value *, 64> ValueWorkList;
     126             : 
     127             :   /// BBWorkList - Holds basic blocks that should be processed.
     128             :   SmallVector<BasicBlock *, 64> BBWorkList;
     129             : 
     130             :   using Edge = std::pair<BasicBlock *, BasicBlock *>;
     131             : 
     132             :   /// KnownFeasibleEdges - Entries in this set are edges which have already had
     133             :   /// PHI nodes retriggered.
     134             :   std::set<Edge> KnownFeasibleEdges;
     135             : 
     136             : public:
     137        1788 :   explicit SparseSolver(
     138             :       AbstractLatticeFunction<LatticeKey, LatticeVal> *Lattice)
     139        1788 :       : LatticeFunc(Lattice) {}
     140             :   SparseSolver(const SparseSolver &) = delete;
     141             :   SparseSolver &operator=(const SparseSolver &) = delete;
     142             : 
     143             :   /// Solve - Solve for constants and executable blocks.
     144             :   void Solve();
     145             : 
     146             :   void Print(raw_ostream &OS) const;
     147             : 
     148             :   /// getExistingValueState - Return the LatticeVal object corresponding to the
     149             :   /// given value from the ValueState map. If the value is not in the map,
     150             :   /// UntrackedVal is returned, unlike the getValueState method.
     151        4163 :   LatticeVal getExistingValueState(LatticeKey Key) const {
     152        4163 :     auto I = ValueState.find(Key);
     153        4163 :     return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
     154             :   }
     155             : 
     156             :   /// getValueState - Return the LatticeVal object corresponding to the given
     157             :   /// value from the ValueState map. If the value is not in the map, its state
     158             :   /// is initialized.
     159             :   LatticeVal getValueState(LatticeKey Key);
     160             : 
     161             :   /// isEdgeFeasible - Return true if the control flow edge from the 'From'
     162             :   /// basic block to the 'To' basic block is currently feasible.  If
     163             :   /// AggressiveUndef is true, then this treats values with unknown lattice
     164             :   /// values as undefined.  This is generally only useful when solving the
     165             :   /// lattice, not when querying it.
     166             :   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
     167             :                       bool AggressiveUndef = false);
     168             : 
     169             :   /// isBlockExecutable - Return true if there are any known feasible
     170             :   /// edges into the basic block.  This is generally only useful when
     171             :   /// querying the lattice.
     172             :   bool isBlockExecutable(BasicBlock *BB) const {
     173           4 :     return BBExecutable.count(BB);
     174             :   }
     175             : 
     176             :   /// MarkBlockExecutable - This method can be used by clients to mark all of
     177             :   /// the blocks that are known to be intrinsically live in the processed unit.
     178             :   void MarkBlockExecutable(BasicBlock *BB);
     179             : 
     180             : private:
     181             :   /// UpdateState - When the state of some LatticeKey is potentially updated to
     182             :   /// the given LatticeVal, this function notices and adds the LLVM value
     183             :   /// corresponding the key to the work list, if needed.
     184             :   void UpdateState(LatticeKey Key, LatticeVal LV);
     185             : 
     186             :   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
     187             :   /// work list if it is not already executable.
     188             :   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
     189             : 
     190             :   /// getFeasibleSuccessors - Return a vector of booleans to indicate which
     191             :   /// successors are reachable from a given terminator instruction.
     192             :   void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs,
     193             :                              bool AggressiveUndef);
     194             : 
     195             :   void visitInst(Instruction &I);
     196             :   void visitPHINode(PHINode &I);
     197             :   void visitTerminator(Instruction &TI);
     198             : };
     199             : 
     200             : //===----------------------------------------------------------------------===//
     201             : //                  AbstractLatticeFunction Implementation
     202             : //===----------------------------------------------------------------------===//
     203             : 
     204             : template <class LatticeKey, class LatticeVal>
     205           0 : void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeVal(
     206             :     LatticeVal V, raw_ostream &OS) {
     207           0 :   if (V == UndefVal)
     208           0 :     OS << "undefined";
     209           0 :   else if (V == OverdefinedVal)
     210           0 :     OS << "overdefined";
     211           0 :   else if (V == UntrackedVal)
     212           0 :     OS << "untracked";
     213             :   else
     214           0 :     OS << "unknown lattice value";
     215           0 : }
     216             : 
     217             : template <class LatticeKey, class LatticeVal>
     218           0 : void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeKey(
     219             :     LatticeKey Key, raw_ostream &OS) {
     220           0 :   OS << "unknown lattice key";
     221           0 : }
     222             : 
     223             : //===----------------------------------------------------------------------===//
     224             : //                          SparseSolver Implementation
     225             : //===----------------------------------------------------------------------===//
     226             : 
     227             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     228             : LatticeVal
     229      677960 : SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getValueState(LatticeKey Key) {
     230      677960 :   auto I = ValueState.find(Key);
     231      677960 :   if (I != ValueState.end())
     232          27 :     return I->second; // Common case, in the map
     233             : 
     234      184852 :   if (LatticeFunc->IsUntrackedValue(Key))
     235             :     return LatticeFunc->getUntrackedVal();
     236      184852 :   LatticeVal LV = LatticeFunc->ComputeLatticeVal(Key);
     237             : 
     238             :   // If this value is untracked, don't add it to the map.
     239      369704 :   if (LV == LatticeFunc->getUntrackedVal())
     240           0 :     return LV;
     241          21 :   return ValueState[Key] = std::move(LV);
     242             : }
     243             : 
     244             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     245     1249110 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::UpdateState(LatticeKey Key,
     246             :                                                                 LatticeVal LV) {
     247     1249110 :   auto I = ValueState.find(Key);
     248     1249110 :   if (I != ValueState.end() && I->second == LV)
     249      551436 :     return; // No change.
     250             : 
     251             :   // Update the state of the given LatticeKey and add its corresponding LLVM
     252             :   // value to the work list.
     253          17 :   ValueState[Key] = std::move(LV);
     254      697674 :   if (Value *V = KeyInfo::getValueFromLatticeKey(Key))
     255      697674 :     ValueWorkList.push_back(V);
     256             : }
     257             : 
     258             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     259      207333 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::MarkBlockExecutable(
     260             :     BasicBlock *BB) {
     261      207333 :   if (!BBExecutable.insert(BB).second)
     262             :     return;
     263             :   LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
     264      183258 :   BBWorkList.push_back(BB); // Add the block to the work list!
     265             : }
     266             : 
     267             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     268      325071 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::markEdgeExecutable(
     269             :     BasicBlock *Source, BasicBlock *Dest) {
     270      325071 :   if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
     271             :     return; // This edge is already known to be executable!
     272             : 
     273             :   LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
     274             :                     << " -> " << Dest->getName() << "\n");
     275             : 
     276      184517 :   if (BBExecutable.count(Dest)) {
     277             :     // The destination is already executable, but we just made an edge
     278             :     // feasible that wasn't before.  Revisit the PHI nodes in the block
     279             :     // because they have potentially new operands.
     280      122575 :     for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
     281       77009 :       visitPHINode(*cast<PHINode>(I));
     282             :   } else {
     283      138951 :     MarkBlockExecutable(Dest);
     284             :   }
     285             : }
     286             : 
     287             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     288      371484 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
     289             :     Instruction &TI, SmallVectorImpl<bool> &Succs, bool AggressiveUndef) {
     290      371484 :   Succs.resize(TI.getNumSuccessors());
     291      371484 :   if (TI.getNumSuccessors() == 0)
     292      371463 :     return;
     293             : 
     294             :   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
     295      216078 :     if (BI->isUnconditional()) {
     296      162161 :       Succs[0] = true;
     297      162161 :       return;
     298             :     }
     299             : 
     300             :     LatticeVal BCValue;
     301       53917 :     if (AggressiveUndef)
     302      107830 :       BCValue =
     303             :           getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
     304             :     else
     305           0 :       BCValue = getExistingValueState(
     306             :           KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
     307             : 
     308      107830 :     if (BCValue == LatticeFunc->getOverdefinedVal() ||
     309       55964 :         BCValue == LatticeFunc->getUntrackedVal()) {
     310             :       // Overdefined condition variables can branch either way.
     311       51866 :       Succs[0] = Succs[1] = true;
     312       51866 :       return;
     313             :     }
     314             : 
     315             :     // If undefined, neither is feasible yet.
     316        4102 :     if (BCValue == LatticeFunc->getUndefVal())
     317             :       return;
     318             : 
     319             :     Constant *C =
     320             :         dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
     321             :             std::move(BCValue), BI->getCondition()->getType()));
     322             :     if (!C || !isa<ConstantInt>(C)) {
     323             :       // Non-constant values can go either way.
     324           0 :       Succs[0] = Succs[1] = true;
     325           0 :       return;
     326             :     }
     327             : 
     328             :     // Constant condition variables mean the branch can only go a single way
     329             :     Succs[C->isNullValue()] = true;
     330             :     return;
     331             :   }
     332             : 
     333             :   if (TI.isExceptionalTerminator()) {
     334      162078 :     Succs.assign(Succs.size(), true);
     335       81039 :     return;
     336             :   }
     337             : 
     338         828 :   if (isa<IndirectBrInst>(TI)) {
     339          16 :     Succs.assign(Succs.size(), true);
     340           8 :     return;
     341             :   }
     342             : 
     343             :   SwitchInst &SI = cast<SwitchInst>(TI);
     344             :   LatticeVal SCValue;
     345         820 :   if (AggressiveUndef)
     346        1640 :     SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
     347             :   else
     348           0 :     SCValue = getExistingValueState(
     349             :         KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
     350             : 
     351        1640 :   if (SCValue == LatticeFunc->getOverdefinedVal() ||
     352         896 :       SCValue == LatticeFunc->getUntrackedVal()) {
     353             :     // All destinations are executable!
     354         744 :     Succs.assign(TI.getNumSuccessors(), true);
     355         744 :     return;
     356             :   }
     357             : 
     358             :   // If undefined, neither is feasible yet.
     359         152 :   if (SCValue == LatticeFunc->getUndefVal())
     360             :     return;
     361             : 
     362             :   Constant *C = dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
     363             :       std::move(SCValue), SI.getCondition()->getType()));
     364             :   if (!C || !isa<ConstantInt>(C)) {
     365             :     // All destinations are executable!
     366           0 :     Succs.assign(TI.getNumSuccessors(), true);
     367           0 :     return;
     368             :   }
     369             :   SwitchInst::CaseHandle Case = *SI.findCaseValue(cast<ConstantInt>(C));
     370             :   Succs[Case.getSuccessorIndex()] = true;
     371             : }
     372             : 
     373             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     374       97283 : bool SparseSolver<LatticeKey, LatticeVal, KeyInfo>::isEdgeFeasible(
     375             :     BasicBlock *From, BasicBlock *To, bool AggressiveUndef) {
     376             :   SmallVector<bool, 16> SuccFeasible;
     377             :   Instruction *TI = From->getTerminator();
     378       97283 :   getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
     379             : 
     380      108485 :   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     381      106544 :     if (TI->getSuccessor(i) == To && SuccFeasible[i])
     382             :       return true;
     383             : 
     384             :   return false;
     385             : }
     386             : 
     387             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     388      274201 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitTerminator(
     389             :     Instruction &TI) {
     390             :   SmallVector<bool, 16> SuccFeasible;
     391      274201 :   getFeasibleSuccessors(TI, SuccFeasible, true);
     392             : 
     393      274201 :   BasicBlock *BB = TI.getParent();
     394             : 
     395             :   // Mark all feasible successors executable...
     396      599644 :   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
     397      650886 :     if (SuccFeasible[i])
     398      325071 :       markEdgeExecutable(BB, TI.getSuccessor(i));
     399      274201 : }
     400             : 
     401             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     402      208875 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {
     403             :   // The lattice function may store more information on a PHINode than could be
     404             :   // computed from its incoming values.  For example, SSI form stores its sigma
     405             :   // functions as PHINodes with a single incoming value.
     406             :   if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
     407             :     DenseMap<LatticeKey, LatticeVal> ChangedValues;
     408             :     LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);
     409             :     for (auto &ChangedValue : ChangedValues)
     410             :       if (ChangedValue.second != LatticeFunc->getUntrackedVal())
     411             :         UpdateState(std::move(ChangedValue.first),
     412             :                     std::move(ChangedValue.second));
     413             :     return;
     414             :   }
     415             : 
     416      208875 :   LatticeKey Key = KeyInfo::getLatticeKeyFromValue(&PN);
     417      208875 :   LatticeVal PNIV = getValueState(Key);
     418      208875 :   LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
     419             : 
     420             :   // If this value is already overdefined (common) just return.
     421      271932 :   if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal())
     422             :     return; // Quick exit
     423             : 
     424             :   // Super-extra-high-degree PHI nodes are unlikely to ever be interesting,
     425             :   // and slow us down a lot.  Just mark them overdefined.
     426       63057 :   if (PN.getNumIncomingValues() > 64) {
     427           5 :     UpdateState(Key, Overdefined);
     428           5 :     return;
     429             :   }
     430             : 
     431             :   // Look at all of the executable operands of the PHI node.  If any of them
     432             :   // are overdefined, the PHI becomes overdefined as well.  Otherwise, ask the
     433             :   // transfer function to give us the merge of the incoming values.
     434       97872 :   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     435             :     // If the edge is not yet known to be feasible, it doesn't impact the PHI.
     436      194566 :     if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true))
     437        1941 :       continue;
     438             : 
     439             :     // Merge in this value.
     440       95342 :     LatticeVal OpVal =
     441             :         getValueState(KeyInfo::getLatticeKeyFromValue(PN.getIncomingValue(i)));
     442           0 :     if (OpVal != PNIV)
     443      190849 :       PNIV = LatticeFunc->MergeValues(PNIV, OpVal);
     444             : 
     445           0 :     if (PNIV == Overdefined)
     446             :       break; // Rest of input values don't matter.
     447             :   }
     448             : 
     449             :   // Update the PHI with the compute value, which is the merge of the inputs.
     450      126104 :   UpdateState(Key, PNIV);
     451             : }
     452             : 
     453             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     454     2156264 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &I) {
     455             :   // PHIs are handled by the propagation logic, they are never passed into the
     456             :   // transfer functions.
     457             :   if (PHINode *PN = dyn_cast<PHINode>(&I))
     458      131866 :     return visitPHINode(*PN);
     459             : 
     460             :   // Otherwise, ask the transfer function what the result is.  If this is
     461             :   // something that we care about, remember it.
     462             :   DenseMap<LatticeKey, LatticeVal> ChangedValues;
     463     2024398 :   LatticeFunc->ComputeInstructionState(I, ChangedValues, *this);
     464     3210451 :   for (auto &ChangedValue : ChangedValues)
     465     2372106 :     if (ChangedValue.second != LatticeFunc->getUntrackedVal())
     466     2372072 :       UpdateState(ChangedValue.first, ChangedValue.second);
     467             : 
     468     2024398 :   if (I.isTerminator())
     469      274201 :     visitTerminator(I);
     470             : }
     471             : 
     472             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     473        1788 : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Solve() {
     474             :   // Process the work lists until they are empty!
     475        4420 :   while (!BBWorkList.empty() || !ValueWorkList.empty()) {
     476             :     // Process the value work list.
     477      700306 :     while (!ValueWorkList.empty()) {
     478      697674 :       Value *V = ValueWorkList.back();
     479             :       ValueWorkList.pop_back();
     480             : 
     481             :       LLVM_DEBUG(dbgs() << "\nPopped off V-WL: " << *V << "\n");
     482             : 
     483             :       // "V" got into the work list because it made a transition. See if any
     484             :       // users are both live and in need of updating.
     485     1632573 :       for (User *U : V->users())
     486             :         if (Instruction *Inst = dyn_cast<Instruction>(U))
     487      934532 :           if (BBExecutable.count(Inst->getParent())) // Inst is executable?
     488      931804 :             visitInst(*Inst);
     489             :     }
     490             : 
     491             :     // Process the basic block work list.
     492      185890 :     while (!BBWorkList.empty()) {
     493      183258 :       BasicBlock *BB = BBWorkList.back();
     494             :       BBWorkList.pop_back();
     495             : 
     496             :       LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB);
     497             : 
     498             :       // Notify all instructions in this basic block that they are newly
     499             :       // executable.
     500     1407718 :       for (Instruction &I : *BB)
     501     1224460 :         visitInst(I);
     502             :     }
     503             :   }
     504        1788 : }
     505             : 
     506             : template <class LatticeKey, class LatticeVal, class KeyInfo>
     507             : void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Print(
     508             :     raw_ostream &OS) const {
     509             :   if (ValueState.empty())
     510             :     return;
     511             : 
     512             :   LatticeKey Key;
     513             :   LatticeVal LV;
     514             : 
     515             :   OS << "ValueState:\n";
     516             :   for (auto &Entry : ValueState) {
     517             :     std::tie(Key, LV) = Entry;
     518             :     if (LV == LatticeFunc->getUntrackedVal())
     519             :       continue;
     520             :     OS << "\t";
     521             :     LatticeFunc->PrintLatticeVal(LV, OS);
     522             :     OS << ": ";
     523             :     LatticeFunc->PrintLatticeKey(Key, OS);
     524             :     OS << "\n";
     525             :   }
     526             : }
     527             : } // end namespace llvm
     528             : 
     529             : #undef DEBUG_TYPE
     530             : 
     531             : #endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H

Generated by: LCOV version 1.13