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