contrib/llvm/lib/Transforms/Utils/PredicateInfo.cpp

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