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