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