llvm/lib/Transforms/Utils/PredicateInfo.cpp

   1 //===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
   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 the PredicateInfo class.
  10 //
  11 //===----------------------------------------------------------------===//
  12
  13 #include "llvm/Transforms/Utils/PredicateInfo.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/DepthFirstIterator.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/SmallPtrSet.h"
  18 #include "llvm/Analysis/AssumptionCache.h"
  19 #include "llvm/IR/AssemblyAnnotationWriter.h"
  20 #include "llvm/IR/Dominators.h"
  21 #include "llvm/IR/IRBuilder.h"
  22 #include "llvm/IR/InstIterator.h"
  23 #include "llvm/IR/IntrinsicInst.h"
  24 #include "llvm/IR/Module.h"
  25 #include "llvm/IR/PatternMatch.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/DebugCounter.h"
  29 #include "llvm/Support/FormattedStream.h"
  30 #define DEBUG_TYPE "predicateinfo"
  31 using namespace llvm;
  32 using namespace PatternMatch;
  33
  34 static cl::opt<bool> VerifyPredicateInfo(
  35     "verify-predicateinfo", cl::init(false), cl::Hidden,
  36     cl::desc("Verify PredicateInfo in legacy printer pass."));
  37 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
  38               "Controls which variables are renamed with predicateinfo");
  39
  40 // Maximum number of conditions considered for renaming for each branch/assume.
  41 // This limits renaming of deep and/or chains.
  42 static const unsigned MaxCondsPerBranch = 8;
  43
  44 namespace {
  45 // Given a predicate info that is a type of branching terminator, get the
  46 // branching block.
  47 const BasicBlock *getBranchBlock(const PredicateBase *PB) {
  48   assert(isa<PredicateWithEdge>(PB) &&
  49          "Only branches and switches should have PHIOnly defs that "
  50          "require branch blocks.");
  51   return cast<PredicateWithEdge>(PB)->From;
  52 }
  53
  54 // Given a predicate info that is a type of branching terminator, get the
  55 // branching terminator.
  56 static Instruction *getBranchTerminator(const PredicateBase *PB) {
  57   assert(isa<PredicateWithEdge>(PB) &&
  58          "Not a predicate info type we know how to get a terminator from.");
  59   return cast<PredicateWithEdge>(PB)->From->getTerminator();
  60 }
  61
  62 // Given a predicate info that is a type of branching terminator, get the
  63 // edge this predicate info represents
  64 std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const PredicateBase *PB) {
  65   assert(isa<PredicateWithEdge>(PB) &&
  66          "Not a predicate info type we know how to get an edge from.");
  67   const auto *PEdge = cast<PredicateWithEdge>(PB);
  68   return std::make_pair(PEdge->From, PEdge->To);
  69 }
  70 }
  71
  72 namespace llvm {
  73 enum LocalNum {
  74   // Operations that must appear first in the block.
  75   LN_First,
  76   // Operations that are somewhere in the middle of the block, and are sorted on
  77   // demand.
  78   LN_Middle,
  79   // Operations that must appear last in a block, like successor phi node uses.
  80   LN_Last
  81 };
  82
  83 // Associate global and local DFS info with defs and uses, so we can sort them
  84 // into a global domination ordering.
  85 struct ValueDFS {
  86   int DFSIn = 0;
  87   int DFSOut = 0;
  88   unsigned int LocalNum = LN_Middle;
  89   // Only one of Def or Use will be set.
  90   Value *Def = nullptr;
  91   Use *U = nullptr;
  92   // Neither PInfo nor EdgeOnly participate in the ordering
  93   PredicateBase *PInfo = nullptr;
  94   bool EdgeOnly = false;
  95 };
  96
  97 // Perform a strict weak ordering on instructions and arguments.
  98 static bool valueComesBefore(const Value *A, const Value *B) {
  99   auto *ArgA = dyn_cast_or_null<Argument>(A);
 100   auto *ArgB = dyn_cast_or_null<Argument>(B);
 101   if (ArgA && !ArgB)
 102     return true;
 103   if (ArgB && !ArgA)
 104     return false;
 105   if (ArgA && ArgB)
 106     return ArgA->getArgNo() < ArgB->getArgNo();
 107   return cast<Instruction>(A)->comesBefore(cast<Instruction>(B));
 108 }
 109
 110 // This compares ValueDFS structures. Doing so allows us to walk the minimum
 111 // number of instructions necessary to compute our def/use ordering.
 112 struct ValueDFS_Compare {
 113   DominatorTree &DT;
 114   ValueDFS_Compare(DominatorTree &DT) : DT(DT) {}
 115
 116   bool operator()(const ValueDFS &A, const ValueDFS &B) const {
 117     if (&A == &B)
 118       return false;
 119     // The only case we can't directly compare them is when they in the same
 120     // block, and both have localnum == middle.  In that case, we have to use
 121     // comesbefore to see what the real ordering is, because they are in the
 122     // same basic block.
 123
 124     assert((A.DFSIn != B.DFSIn || A.DFSOut == B.DFSOut) &&
 125            "Equal DFS-in numbers imply equal out numbers");
 126     bool SameBlock = A.DFSIn == B.DFSIn;
 127
 128     // We want to put the def that will get used for a given set of phi uses,
 129     // before those phi uses.
 130     // So we sort by edge, then by def.
 131     // Note that only phi nodes uses and defs can come last.
 132     if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
 133       return comparePHIRelated(A, B);
 134
 135     bool isADef = A.Def;
 136     bool isBDef = B.Def;
 137     if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
 138       return std::tie(A.DFSIn, A.LocalNum, isADef) <
 139              std::tie(B.DFSIn, B.LocalNum, isBDef);
 140     return localComesBefore(A, B);
 141   }
 142
 143   // For a phi use, or a non-materialized def, return the edge it represents.
 144   std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const ValueDFS &VD) const {
 145     if (!VD.Def && VD.U) {
 146       auto *PHI = cast<PHINode>(VD.U->getUser());
 147       return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
 148     }
 149     // This is really a non-materialized def.
 150     return ::getBlockEdge(VD.PInfo);
 151   }
 152
 153   // For two phi related values, return the ordering.
 154   bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
 155     BasicBlock *ASrc, *ADest, *BSrc, *BDest;
 156     std::tie(ASrc, ADest) = getBlockEdge(A);
 157     std::tie(BSrc, BDest) = getBlockEdge(B);
 158
 159 #ifndef NDEBUG
 160     // This function should only be used for values in the same BB, check that.
 161     DomTreeNode *DomASrc = DT.getNode(ASrc);
 162     DomTreeNode *DomBSrc = DT.getNode(BSrc);
 163     assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn &&
 164            "DFS numbers for A should match the ones of the source block");
 165     assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn &&
 166            "DFS numbers for B should match the ones of the source block");
 167     assert(A.DFSIn == B.DFSIn && "Values must be in the same block");
 168 #endif
 169     (void)ASrc;
 170     (void)BSrc;
 171
 172     // Use DFS numbers to compare destination blocks, to guarantee a
 173     // deterministic order.
 174     DomTreeNode *DomADest = DT.getNode(ADest);
 175     DomTreeNode *DomBDest = DT.getNode(BDest);
 176     unsigned AIn = DomADest->getDFSNumIn();
 177     unsigned BIn = DomBDest->getDFSNumIn();
 178     bool isADef = A.Def;
 179     bool isBDef = B.Def;
 180     assert((!A.Def || !A.U) && (!B.Def || !B.U) &&
 181            "Def and U cannot be set at the same time");
 182     // Now sort by edge destination and then defs before uses.
 183     return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
 184   }
 185
 186   // Get the definition of an instruction that occurs in the middle of a block.
 187   Value *getMiddleDef(const ValueDFS &VD) const {
 188     if (VD.Def)
 189       return VD.Def;
 190     // It's possible for the defs and uses to be null.  For branches, the local
 191     // numbering will say the placed predicaeinfos should go first (IE
 192     // LN_beginning), so we won't be in this function. For assumes, we will end
 193     // up here, beause we need to order the def we will place relative to the
 194     // assume.  So for the purpose of ordering, we pretend the def is right
 195     // after the assume, because that is where we will insert the info.
 196     if (!VD.U) {
 197       assert(VD.PInfo &&
 198              "No def, no use, and no predicateinfo should not occur");
 199       assert(isa<PredicateAssume>(VD.PInfo) &&
 200              "Middle of block should only occur for assumes");
 201       return cast<PredicateAssume>(VD.PInfo)->AssumeInst->getNextNode();
 202     }
 203     return nullptr;
 204   }
 205
 206   // Return either the Def, if it's not null, or the user of the Use, if the def
 207   // is null.
 208   const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
 209     if (Def)
 210       return cast<Instruction>(Def);
 211     return cast<Instruction>(U->getUser());
 212   }
 213
 214   // This performs the necessary local basic block ordering checks to tell
 215   // whether A comes before B, where both are in the same basic block.
 216   bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
 217     auto *ADef = getMiddleDef(A);
 218     auto *BDef = getMiddleDef(B);
 219
 220     // See if we have real values or uses. If we have real values, we are
 221     // guaranteed they are instructions or arguments. No matter what, we are
 222     // guaranteed they are in the same block if they are instructions.
 223     auto *ArgA = dyn_cast_or_null<Argument>(ADef);
 224     auto *ArgB = dyn_cast_or_null<Argument>(BDef);
 225
 226     if (ArgA || ArgB)
 227       return valueComesBefore(ArgA, ArgB);
 228
 229     auto *AInst = getDefOrUser(ADef, A.U);
 230     auto *BInst = getDefOrUser(BDef, B.U);
 231     return valueComesBefore(AInst, BInst);
 232   }
 233 };
 234
 235 class PredicateInfoBuilder {
 236   // Used to store information about each value we might rename.
 237   struct ValueInfo {
 238     SmallVector<PredicateBase *, 4> Infos;
 239   };
 240
 241   PredicateInfo &PI;
 242   Function &F;
 243   DominatorTree &DT;
 244   AssumptionCache &AC;
 245
 246   // This stores info about each operand or comparison result we make copies
 247   // of. The real ValueInfos start at index 1, index 0 is unused so that we
 248   // can more easily detect invalid indexing.
 249   SmallVector<ValueInfo, 32> ValueInfos;
 250
 251   // This gives the index into the ValueInfos array for a given Value. Because
 252   // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell
 253   // whether it returned a valid result.
 254   DenseMap<Value *, unsigned int> ValueInfoNums;
 255
 256   // The set of edges along which we can only handle phi uses, due to critical
 257   // edges.
 258   DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
 259
 260   ValueInfo &getOrCreateValueInfo(Value *);
 261   const ValueInfo &getValueInfo(Value *) const;
 262
 263   void processAssume(IntrinsicInst *, BasicBlock *,
 264                      SmallVectorImpl<Value *> &OpsToRename);
 265   void processBranch(BranchInst *, BasicBlock *,
 266                      SmallVectorImpl<Value *> &OpsToRename);
 267   void processSwitch(SwitchInst *, BasicBlock *,
 268                      SmallVectorImpl<Value *> &OpsToRename);
 269   void renameUses(SmallVectorImpl<Value *> &OpsToRename);
 270   void addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op,
 271                   PredicateBase *PB);
 272
 273   typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
 274   void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
 275   Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
 276   bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
 277   void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
 278
 279 public:
 280   PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT,
 281                        AssumptionCache &AC)
 282       : PI(PI), F(F), DT(DT), AC(AC) {
 283     // Push an empty operand info so that we can detect 0 as not finding one
 284     ValueInfos.resize(1);
 285   }
 286
 287   void buildPredicateInfo();
 288 };
 289
 290 bool PredicateInfoBuilder::stackIsInScope(const ValueDFSStack &Stack,
 291                                           const ValueDFS &VDUse) const {
 292   if (Stack.empty())
 293     return false;
 294   // If it's a phi only use, make sure it's for this phi node edge, and that the
 295   // use is in a phi node.  If it's anything else, and the top of the stack is
 296   // EdgeOnly, we need to pop the stack.  We deliberately sort phi uses next to
 297   // the defs they must go with so that we can know it's time to pop the stack
 298   // when we hit the end of the phi uses for a given def.
 299   if (Stack.back().EdgeOnly) {
 300     if (!VDUse.U)
 301       return false;
 302     auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
 303     if (!PHI)
 304       return false;
 305     // Check edge
 306     BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
 307     if (EdgePred != getBranchBlock(Stack.back().PInfo))
 308       return false;
 309
 310     // Use dominates, which knows how to handle edge dominance.
 311     return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
 312   }
 313
 314   return (VDUse.DFSIn >= Stack.back().DFSIn &&
 315           VDUse.DFSOut <= Stack.back().DFSOut);
 316 }
 317
 318 void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,
 319                                                  const ValueDFS &VD) {
 320   while (!Stack.empty() && !stackIsInScope(Stack, VD))
 321     Stack.pop_back();
 322 }
 323
 324 // Convert the uses of Op into a vector of uses, associating global and local
 325 // DFS info with each one.
 326 void PredicateInfoBuilder::convertUsesToDFSOrdered(
 327     Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
 328   for (auto &U : Op->uses()) {
 329     if (auto *I = dyn_cast<Instruction>(U.getUser())) {
 330       ValueDFS VD;
 331       // Put the phi node uses in the incoming block.
 332       BasicBlock *IBlock;
 333       if (auto *PN = dyn_cast<PHINode>(I)) {
 334         IBlock = PN->getIncomingBlock(U);
 335         // Make phi node users appear last in the incoming block
 336         // they are from.
 337         VD.LocalNum = LN_Last;
 338       } else {
 339         // If it's not a phi node use, it is somewhere in the middle of the
 340         // block.
 341         IBlock = I->getParent();
 342         VD.LocalNum = LN_Middle;
 343       }
 344       DomTreeNode *DomNode = DT.getNode(IBlock);
 345       // It's possible our use is in an unreachable block. Skip it if so.
 346       if (!DomNode)
 347         continue;
 348       VD.DFSIn = DomNode->getDFSNumIn();
 349       VD.DFSOut = DomNode->getDFSNumOut();
 350       VD.U = &U;
 351       DFSOrderedSet.push_back(VD);
 352     }
 353   }
 354 }
 355
 356 bool shouldRename(Value *V) {
 357   // Only want real values, not constants.  Additionally, operands with one use
 358   // are only being used in the comparison, which means they will not be useful
 359   // for us to consider for predicateinfo.
 360   return (isa<Instruction>(V) || isa<Argument>(V)) && !V->hasOneUse();
 361 }
 362
 363 // Collect relevant operations from Comparison that we may want to insert copies
 364 // for.
 365 void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
 366   auto *Op0 = Comparison->getOperand(0);
 367   auto *Op1 = Comparison->getOperand(1);
 368   if (Op0 == Op1)
 369     return;
 370
 371   CmpOperands.push_back(Op0);
 372   CmpOperands.push_back(Op1);
 373 }
 374
 375 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
 376 void PredicateInfoBuilder::addInfoFor(SmallVectorImpl<Value *> &OpsToRename,
 377                                       Value *Op, PredicateBase *PB) {
 378   auto &OperandInfo = getOrCreateValueInfo(Op);
 379   if (OperandInfo.Infos.empty())
 380     OpsToRename.push_back(Op);
 381   PI.AllInfos.push_back(PB);
 382   OperandInfo.Infos.push_back(PB);
 383 }
 384
 385 // Process an assume instruction and place relevant operations we want to rename
 386 // into OpsToRename.
 387 void PredicateInfoBuilder::processAssume(
 388     IntrinsicInst *II, BasicBlock *AssumeBB,
 389     SmallVectorImpl<Value *> &OpsToRename) {
 390   SmallVector<Value *, 4> Worklist;
 391   SmallPtrSet<Value *, 4> Visited;
 392   Worklist.push_back(II->getOperand(0));
 393   while (!Worklist.empty()) {
 394     Value *Cond = Worklist.pop_back_val();
 395     if (!Visited.insert(Cond).second)
 396       continue;
 397     if (Visited.size() > MaxCondsPerBranch)
 398       break;
 399
 400     Value *Op0, *Op1;
 401     if (match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
 402       Worklist.push_back(Op1);
 403       Worklist.push_back(Op0);
 404     }
 405
 406     SmallVector<Value *, 4> Values;
 407     Values.push_back(Cond);
 408     if (auto *Cmp = dyn_cast<CmpInst>(Cond))
 409       collectCmpOps(Cmp, Values);
 410
 411     for (Value *V : Values) {
 412       if (shouldRename(V)) {
 413         auto *PA = new PredicateAssume(V, II, Cond);
 414         addInfoFor(OpsToRename, V, PA);
 415       }
 416     }
 417   }
 418 }
 419
 420 // Process a block terminating branch, and place relevant operations to be
 421 // renamed into OpsToRename.
 422 void PredicateInfoBuilder::processBranch(
 423     BranchInst *BI, BasicBlock *BranchBB,
 424     SmallVectorImpl<Value *> &OpsToRename) {
 425   BasicBlock *FirstBB = BI->getSuccessor(0);
 426   BasicBlock *SecondBB = BI->getSuccessor(1);
 427
 428   for (BasicBlock *Succ : {FirstBB, SecondBB}) {
 429     bool TakenEdge = Succ == FirstBB;
 430     // Don't try to insert on a self-edge. This is mainly because we will
 431     // eliminate during renaming anyway.
 432     if (Succ == BranchBB)
 433       continue;
 434
 435     SmallVector<Value *, 4> Worklist;
 436     SmallPtrSet<Value *, 4> Visited;
 437     Worklist.push_back(BI->getCondition());
 438     while (!Worklist.empty()) {
 439       Value *Cond = Worklist.pop_back_val();
 440       if (!Visited.insert(Cond).second)
 441         continue;
 442       if (Visited.size() > MaxCondsPerBranch)
 443         break;
 444
 445       Value *Op0, *Op1;
 446       if (TakenEdge ? match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))
 447                     : match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
 448         Worklist.push_back(Op1);
 449         Worklist.push_back(Op0);
 450       }
 451
 452       SmallVector<Value *, 4> Values;
 453       Values.push_back(Cond);
 454       if (auto *Cmp = dyn_cast<CmpInst>(Cond))
 455         collectCmpOps(Cmp, Values);
 456
 457       for (Value *V : Values) {
 458         if (shouldRename(V)) {
 459           PredicateBase *PB =
 460               new PredicateBranch(V, BranchBB, Succ, Cond, TakenEdge);
 461           addInfoFor(OpsToRename, V, PB);
 462           if (!Succ->getSinglePredecessor())
 463             EdgeUsesOnly.insert({BranchBB, Succ});
 464         }
 465       }
 466     }
 467   }
 468 }
 469 // Process a block terminating switch, and place relevant operations to be
 470 // renamed into OpsToRename.
 471 void PredicateInfoBuilder::processSwitch(
 472     SwitchInst *SI, BasicBlock *BranchBB,
 473     SmallVectorImpl<Value *> &OpsToRename) {
 474   Value *Op = SI->getCondition();
 475   if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
 476     return;
 477
 478   // Remember how many outgoing edges there are to every successor.
 479   SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
 480   for (BasicBlock *TargetBlock : successors(BranchBB))
 481     ++SwitchEdges[TargetBlock];
 482
 483   // Now propagate info for each case value
 484   for (auto C : SI->cases()) {
 485     BasicBlock *TargetBlock = C.getCaseSuccessor();
 486     if (SwitchEdges.lookup(TargetBlock) == 1) {
 487       PredicateSwitch *PS = new PredicateSwitch(
 488           Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
 489       addInfoFor(OpsToRename, Op, PS);
 490       if (!TargetBlock->getSinglePredecessor())
 491         EdgeUsesOnly.insert({BranchBB, TargetBlock});
 492     }
 493   }
 494 }
 495
 496 // Build predicate info for our function
 497 void PredicateInfoBuilder::buildPredicateInfo() {
 498   DT.updateDFSNumbers();
 499   // Collect operands to rename from all conditional branch terminators, as well
 500   // as assume statements.
 501   SmallVector<Value *, 8> OpsToRename;
 502   for (auto *DTN : depth_first(DT.getRootNode())) {
 503     BasicBlock *BranchBB = DTN->getBlock();
 504     if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
 505       if (!BI->isConditional())
 506         continue;
 507       // Can't insert conditional information if they all go to the same place.
 508       if (BI->getSuccessor(0) == BI->getSuccessor(1))
 509         continue;
 510       processBranch(BI, BranchBB, OpsToRename);
 511     } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
 512       processSwitch(SI, BranchBB, OpsToRename);
 513     }
 514   }
 515   for (auto &Assume : AC.assumptions()) {
 516     if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
 517       if (DT.isReachableFromEntry(II->getParent()))
 518         processAssume(II, II->getParent(), OpsToRename);
 519   }
 520   // Now rename all our operations.
 521   renameUses(OpsToRename);
 522 }
 523
 524 // Given the renaming stack, make all the operands currently on the stack real
 525 // by inserting them into the IR.  Return the last operation's value.
 526 Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,
 527                                              ValueDFSStack &RenameStack,
 528                                              Value *OrigOp) {
 529   // Find the first thing we have to materialize
 530   auto RevIter = RenameStack.rbegin();
 531   for (; RevIter != RenameStack.rend(); ++RevIter)
 532     if (RevIter->Def)
 533       break;
 534
 535   size_t Start = RevIter - RenameStack.rbegin();
 536   // The maximum number of things we should be trying to materialize at once
 537   // right now is 4, depending on if we had an assume, a branch, and both used
 538   // and of conditions.
 539   for (auto RenameIter = RenameStack.end() - Start;
 540        RenameIter != RenameStack.end(); ++RenameIter) {
 541     auto *Op =
 542         RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
 543     ValueDFS &Result = *RenameIter;
 544     auto *ValInfo = Result.PInfo;
 545     ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
 546                              ? OrigOp
 547                              : (RenameStack.end() - Start - 1)->Def;
 548     // For edge predicates, we can just place the operand in the block before
 549     // the terminator.  For assume, we have to place it right before the assume
 550     // to ensure we dominate all of our uses.  Always insert right before the
 551     // relevant instruction (terminator, assume), so that we insert in proper
 552     // order in the case of multiple predicateinfo in the same block.
 553     // The number of named values is used to detect if a new declaration was
 554     // added. If so, that declaration is tracked so that it can be removed when
 555     // the analysis is done. The corner case were a new declaration results in
 556     // a name clash and the old name being renamed is not considered as that
 557     // represents an invalid module.
 558     if (isa<PredicateWithEdge>(ValInfo)) {
 559       IRBuilder<> B(getBranchTerminator(ValInfo));
 560       auto NumDecls = F.getParent()->getNumNamedValues();
 561       Function *IF = Intrinsic::getOrInsertDeclaration(
 562           F.getParent(), Intrinsic::ssa_copy, Op->getType());
 563       if (NumDecls != F.getParent()->getNumNamedValues())
 564         PI.CreatedDeclarations.insert(IF);
 565       CallInst *PIC =
 566           B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
 567       PI.PredicateMap.insert({PIC, ValInfo});
 568       Result.Def = PIC;
 569     } else {
 570       auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
 571       assert(PAssume &&
 572              "Should not have gotten here without it being an assume");
 573       // Insert the predicate directly after the assume. While it also holds
 574       // directly before it, assume(i1 true) is not a useful fact.
 575       IRBuilder<> B(PAssume->AssumeInst->getNextNode());
 576       auto NumDecls = F.getParent()->getNumNamedValues();
 577       Function *IF = Intrinsic::getOrInsertDeclaration(
 578           F.getParent(), Intrinsic::ssa_copy, Op->getType());
 579       if (NumDecls != F.getParent()->getNumNamedValues())
 580         PI.CreatedDeclarations.insert(IF);
 581       CallInst *PIC = B.CreateCall(IF, Op);
 582       PI.PredicateMap.insert({PIC, ValInfo});
 583       Result.Def = PIC;
 584     }
 585   }
 586   return RenameStack.back().Def;
 587 }
 588
 589 // Instead of the standard SSA renaming algorithm, which is O(Number of
 590 // instructions), and walks the entire dominator tree, we walk only the defs +
 591 // uses.  The standard SSA renaming algorithm does not really rely on the
 592 // dominator tree except to order the stack push/pops of the renaming stacks, so
 593 // that defs end up getting pushed before hitting the correct uses.  This does
 594 // not require the dominator tree, only the *order* of the dominator tree. The
 595 // complete and correct ordering of the defs and uses, in dominator tree is
 596 // contained in the DFS numbering of the dominator tree. So we sort the defs and
 597 // uses into the DFS ordering, and then just use the renaming stack as per
 598 // normal, pushing when we hit a def (which is a predicateinfo instruction),
 599 // popping when we are out of the dfs scope for that def, and replacing any uses
 600 // with top of stack if it exists.  In order to handle liveness without
 601 // propagating liveness info, we don't actually insert the predicateinfo
 602 // instruction def until we see a use that it would dominate.  Once we see such
 603 // a use, we materialize the predicateinfo instruction in the right place and
 604 // use it.
 605 //
 606 // TODO: Use this algorithm to perform fast single-variable renaming in
 607 // promotememtoreg and memoryssa.
 608 void PredicateInfoBuilder::renameUses(SmallVectorImpl<Value *> &OpsToRename) {
 609   ValueDFS_Compare Compare(DT);
 610   // Compute liveness, and rename in O(uses) per Op.
 611   for (auto *Op : OpsToRename) {
 612     LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
 613     unsigned Counter = 0;
 614     SmallVector<ValueDFS, 16> OrderedUses;
 615     const auto &ValueInfo = getValueInfo(Op);
 616     // Insert the possible copies into the def/use list.
 617     // They will become real copies if we find a real use for them, and never
 618     // created otherwise.
 619     for (const auto &PossibleCopy : ValueInfo.Infos) {
 620       ValueDFS VD;
 621       // Determine where we are going to place the copy by the copy type.
 622       // The predicate info for branches always come first, they will get
 623       // materialized in the split block at the top of the block.
 624       // The predicate info for assumes will be somewhere in the middle,
 625       // it will get materialized in front of the assume.
 626       if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
 627         VD.LocalNum = LN_Middle;
 628         DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
 629         if (!DomNode)
 630           continue;
 631         VD.DFSIn = DomNode->getDFSNumIn();
 632         VD.DFSOut = DomNode->getDFSNumOut();
 633         VD.PInfo = PossibleCopy;
 634         OrderedUses.push_back(VD);
 635       } else if (isa<PredicateWithEdge>(PossibleCopy)) {
 636         // If we can only do phi uses, we treat it like it's in the branch
 637         // block, and handle it specially. We know that it goes last, and only
 638         // dominate phi uses.
 639         auto BlockEdge = getBlockEdge(PossibleCopy);
 640         if (EdgeUsesOnly.count(BlockEdge)) {
 641           VD.LocalNum = LN_Last;
 642           auto *DomNode = DT.getNode(BlockEdge.first);
 643           if (DomNode) {
 644             VD.DFSIn = DomNode->getDFSNumIn();
 645             VD.DFSOut = DomNode->getDFSNumOut();
 646             VD.PInfo = PossibleCopy;
 647             VD.EdgeOnly = true;
 648             OrderedUses.push_back(VD);
 649           }
 650         } else {
 651           // Otherwise, we are in the split block (even though we perform
 652           // insertion in the branch block).
 653           // Insert a possible copy at the split block and before the branch.
 654           VD.LocalNum = LN_First;
 655           auto *DomNode = DT.getNode(BlockEdge.second);
 656           if (DomNode) {
 657             VD.DFSIn = DomNode->getDFSNumIn();
 658             VD.DFSOut = DomNode->getDFSNumOut();
 659             VD.PInfo = PossibleCopy;
 660             OrderedUses.push_back(VD);
 661           }
 662         }
 663       }
 664     }
 665
 666     convertUsesToDFSOrdered(Op, OrderedUses);
 667     // Here we require a stable sort because we do not bother to try to
 668     // assign an order to the operands the uses represent. Thus, two
 669     // uses in the same instruction do not have a strict sort order
 670     // currently and will be considered equal. We could get rid of the
 671     // stable sort by creating one if we wanted.
 672     llvm::stable_sort(OrderedUses, Compare);
 673     SmallVector<ValueDFS, 8> RenameStack;
 674     // For each use, sorted into dfs order, push values and replaces uses with
 675     // top of stack, which will represent the reaching def.
 676     for (auto &VD : OrderedUses) {
 677       // We currently do not materialize copy over copy, but we should decide if
 678       // we want to.
 679       bool PossibleCopy = VD.PInfo != nullptr;
 680       if (RenameStack.empty()) {
 681         LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
 682       } else {
 683         LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
 684                           << RenameStack.back().DFSIn << ","
 685                           << RenameStack.back().DFSOut << ")\n");
 686       }
 687
 688       LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
 689                         << VD.DFSOut << ")\n");
 690
 691       bool ShouldPush = (VD.Def || PossibleCopy);
 692       bool OutOfScope = !stackIsInScope(RenameStack, VD);
 693       if (OutOfScope || ShouldPush) {
 694         // Sync to our current scope.
 695         popStackUntilDFSScope(RenameStack, VD);
 696         if (ShouldPush) {
 697           RenameStack.push_back(VD);
 698         }
 699       }
 700       // If we get to this point, and the stack is empty we must have a use
 701       // with no renaming needed, just skip it.
 702       if (RenameStack.empty())
 703         continue;
 704       // Skip values, only want to rename the uses
 705       if (VD.Def || PossibleCopy)
 706         continue;
 707       if (!DebugCounter::shouldExecute(RenameCounter)) {
 708         LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
 709         continue;
 710       }
 711       ValueDFS &Result = RenameStack.back();
 712
 713       // If the possible copy dominates something, materialize our stack up to
 714       // this point. This ensures every comparison that affects our operation
 715       // ends up with predicateinfo.
 716       if (!Result.Def)
 717         Result.Def = materializeStack(Counter, RenameStack, Op);
 718
 719       LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
 720                         << *VD.U->get() << " in " << *(VD.U->getUser())
 721                         << "\n");
 722       assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
 723              "Predicateinfo def should have dominated this use");
 724       VD.U->set(Result.Def);
 725     }
 726   }
 727 }
 728
 729 PredicateInfoBuilder::ValueInfo &
 730 PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) {
 731   auto OIN = ValueInfoNums.find(Operand);
 732   if (OIN == ValueInfoNums.end()) {
 733     // This will grow it
 734     ValueInfos.resize(ValueInfos.size() + 1);
 735     // This will use the new size and give us a 0 based number of the info
 736     auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
 737     assert(InsertResult.second && "Value info number already existed?");
 738     return ValueInfos[InsertResult.first->second];
 739   }
 740   return ValueInfos[OIN->second];
 741 }
 742
 743 const PredicateInfoBuilder::ValueInfo &
 744 PredicateInfoBuilder::getValueInfo(Value *Operand) const {
 745   auto OINI = ValueInfoNums.lookup(Operand);
 746   assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
 747   assert(OINI < ValueInfos.size() &&
 748          "Value Info Number greater than size of Value Info Table");
 749   return ValueInfos[OINI];
 750 }
 751
 752 PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
 753                              AssumptionCache &AC)
 754     : F(F) {
 755   PredicateInfoBuilder Builder(*this, F, DT, AC);
 756   Builder.buildPredicateInfo();
 757 }
 758
 759 // Remove all declarations we created . The PredicateInfo consumers are
 760 // responsible for remove the ssa_copy calls created.
 761 PredicateInfo::~PredicateInfo() {
 762   // Collect function pointers in set first, as SmallSet uses a SmallVector
 763   // internally and we have to remove the asserting value handles first.
 764   SmallPtrSet<Function *, 20> FunctionPtrs;
 765   for (const auto &F : CreatedDeclarations)
 766     FunctionPtrs.insert(&*F);
 767   CreatedDeclarations.clear();
 768
 769   for (Function *F : FunctionPtrs) {
 770     assert(F->user_begin() == F->user_end() &&
 771            "PredicateInfo consumer did not remove all SSA copies.");
 772     F->eraseFromParent();
 773   }
 774 }
 775
 776 std::optional<PredicateConstraint> PredicateBase::getConstraint() const {
 777   switch (Type) {
 778   case PT_Assume:
 779   case PT_Branch: {
 780     bool TrueEdge = true;
 781     if (auto *PBranch = dyn_cast<PredicateBranch>(this))
 782       TrueEdge = PBranch->TrueEdge;
 783
 784     if (Condition == RenamedOp) {
 785       return {{CmpInst::ICMP_EQ,
 786                TrueEdge ? ConstantInt::getTrue(Condition->getType())
 787                         : ConstantInt::getFalse(Condition->getType())}};
 788     }
 789
 790     CmpInst *Cmp = dyn_cast<CmpInst>(Condition);
 791     if (!Cmp) {
 792       // TODO: Make this an assertion once RenamedOp is fully accurate.
 793       return std::nullopt;
 794     }
 795
 796     CmpInst::Predicate Pred;
 797     Value *OtherOp;
 798     if (Cmp->getOperand(0) == RenamedOp) {
 799       Pred = Cmp->getPredicate();
 800       OtherOp = Cmp->getOperand(1);
 801     } else if (Cmp->getOperand(1) == RenamedOp) {
 802       Pred = Cmp->getSwappedPredicate();
 803       OtherOp = Cmp->getOperand(0);
 804     } else {
 805       // TODO: Make this an assertion once RenamedOp is fully accurate.
 806       return std::nullopt;
 807     }
 808
 809     // Invert predicate along false edge.
 810     if (!TrueEdge)
 811       Pred = CmpInst::getInversePredicate(Pred);
 812
 813     return {{Pred, OtherOp}};
 814   }
 815   case PT_Switch:
 816     if (Condition != RenamedOp) {
 817       // TODO: Make this an assertion once RenamedOp is fully accurate.
 818       return std::nullopt;
 819     }
 820
 821     return {{CmpInst::ICMP_EQ, cast<PredicateSwitch>(this)->CaseValue}};
 822   }
 823   llvm_unreachable("Unknown predicate type");
 824 }
 825
 826 void PredicateInfo::verifyPredicateInfo() const {}
 827
 828 // Replace ssa_copy calls created by PredicateInfo with their operand.
 829 static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
 830   for (Instruction &Inst : llvm::make_early_inc_range(instructions(F))) {
 831     const auto *PI = PredInfo.getPredicateInfoFor(&Inst);
 832     auto *II = dyn_cast<IntrinsicInst>(&Inst);
 833     if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy)
 834       continue;
 835
 836     Inst.replaceAllUsesWith(II->getOperand(0));
 837     Inst.eraseFromParent();
 838   }
 839 }
 840
 841 PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
 842                                                 FunctionAnalysisManager &AM) {
 843   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 844   auto &AC = AM.getResult<AssumptionAnalysis>(F);
 845   OS << "PredicateInfo for function: " << F.getName() << "\n";
 846   auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
 847   PredInfo->print(OS);
 848
 849   replaceCreatedSSACopys(*PredInfo, F);
 850   return PreservedAnalyses::all();
 851 }
 852
 853 /// An assembly annotator class to print PredicateInfo information in
 854 /// comments.
 855 class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
 856   friend class PredicateInfo;
 857   const PredicateInfo *PredInfo;
 858
 859 public:
 860   PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
 861
 862   void emitBasicBlockStartAnnot(const BasicBlock *BB,
 863                                 formatted_raw_ostream &OS) override {}
 864
 865   void emitInstructionAnnot(const Instruction *I,
 866                             formatted_raw_ostream &OS) override {
 867     if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
 868       OS << "; Has predicate info\n";
 869       if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
 870         OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
 871            << " Comparison:" << *PB->Condition << " Edge: [";
 872         PB->From->printAsOperand(OS);
 873         OS << ",";
 874         PB->To->printAsOperand(OS);
 875         OS << "]";
 876       } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
 877         OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
 878            << " Switch:" << *PS->Switch << " Edge: [";
 879         PS->From->printAsOperand(OS);
 880         OS << ",";
 881         PS->To->printAsOperand(OS);
 882         OS << "]";
 883       } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
 884         OS << "; assume predicate info {"
 885            << " Comparison:" << *PA->Condition;
 886       }
 887       OS << ", RenamedOp: ";
 888       PI->RenamedOp->printAsOperand(OS, false);
 889       OS << " }\n";
 890     }
 891   }
 892 };
 893
 894 void PredicateInfo::print(raw_ostream &OS) const {
 895   PredicateInfoAnnotatedWriter Writer(this);
 896   F.print(OS, &Writer);
 897 }
 898
 899 void PredicateInfo::dump() const {
 900   PredicateInfoAnnotatedWriter Writer(this);
 901   F.print(dbgs(), &Writer);
 902 }
 903
 904 PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
 905                                                  FunctionAnalysisManager &AM) {
 906   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 907   auto &AC = AM.getResult<AssumptionAnalysis>(F);
 908   std::make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
 909
 910   return PreservedAnalyses::all();
 911 }
 912 }