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