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