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