include/llvm/Analysis/SparsePropagation.h

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