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/BundleAttributes.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/InstIterator.h"
24#include "llvm/IR/IntrinsicInst.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(AssumeInst *, BasicBlock *,
223 SmallVectorImpl<Value *> &OpsToRename);
224 void processBranch(CondBrInst *, 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 assert(Top.PInfo && "RenameStack should only contain predicate infos (defs)");
266 if (Top.LocalNum == LN_Last) {
267 if (!VDUse.U) {
268 assert(VDUse.PInfo && "A non-use VDUse should have a predicate info");
269 // We should reserve adjacent LN_Last defs for the same phi use.
270 return VDUse.LocalNum == LN_Last &&
271 // If the two phi defs have the same edge, they must be designated
272 // for the same succ BB.
273 getBlockEdge(PB: Top.PInfo) == getBlockEdge(PB: VDUse.PInfo);
274 }
275 auto *PHI = dyn_cast<PHINode>(Val: VDUse.U->getUser());
276 if (!PHI)
277 return false;
278 // Check edge
279 BasicBlock *EdgePred = PHI->getIncomingBlock(U: *VDUse.U);
280 if (EdgePred != getBranchBlock(PB: Top.PInfo))
281 return false;
282
283 // Use dominates, which knows how to handle edge dominance.
284 return DT.dominates(BBE: getBlockEdge(PB: Top.PInfo), U: *VDUse.U);
285 }
286
287 return VDUse.DFSIn >= Top.DFSIn && VDUse.DFSOut <= Top.DFSOut;
288}
289
290void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,
291 const ValueDFS &VD) {
292 while (!Stack.empty() && !stackIsInScope(Stack, VDUse: VD))
293 Stack.pop_back();
294}
295
296// Convert the uses of Op into a vector of uses, associating global and local
297// DFS info with each one.
298void PredicateInfoBuilder::convertUsesToDFSOrdered(
299 Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
300 for (auto &U : Op->uses()) {
301 if (auto *I = dyn_cast<Instruction>(Val: U.getUser())) {
302 // Lifetime intrinsics must work directly on alloca, do not replace them
303 // with a predicated copy.
304 if (I->isLifetimeStartOrEnd())
305 continue;
306
307 ValueDFS VD;
308 // Put the phi node uses in the incoming block.
309 BasicBlock *IBlock;
310 if (auto *PN = dyn_cast<PHINode>(Val: I)) {
311 IBlock = PN->getIncomingBlock(U);
312 // Make phi node users appear last in the incoming block
313 // they are from.
314 VD.LocalNum = LN_Last;
315 } else {
316 // If it's not a phi node use, it is somewhere in the middle of the
317 // block.
318 IBlock = I->getParent();
319 VD.LocalNum = LN_Middle;
320 }
321 DomTreeNode *DomNode = DT.getNode(BB: IBlock);
322 // It's possible our use is in an unreachable block. Skip it if so.
323 if (!DomNode)
324 continue;
325 VD.DFSIn = DomNode->getDFSNumIn();
326 VD.DFSOut = DomNode->getDFSNumOut();
327 VD.U = &U;
328 DFSOrderedSet.push_back(Elt: VD);
329 }
330 }
331}
332
333bool shouldRename(Value *V) {
334 // Only want real values, not constants. Additionally, operands with one use
335 // are only being used in the comparison, which means they will not be useful
336 // for us to consider for predicateinfo.
337 return (isa<Instruction>(Val: V) || isa<Argument>(Val: V)) && !V->hasOneUse();
338}
339
340// Collect relevant operations from Comparison that we may want to insert copies
341// for.
342void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
343 auto *Op0 = Comparison->getOperand(i_nocapture: 0);
344 auto *Op1 = Comparison->getOperand(i_nocapture: 1);
345 if (Op0 == Op1)
346 return;
347
348 CmpOperands.push_back(Elt: Op0);
349 CmpOperands.push_back(Elt: Op1);
350}
351
352// Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
353void PredicateInfoBuilder::addInfoFor(SmallVectorImpl<Value *> &OpsToRename,
354 Value *Op, PredicateBase *PB) {
355 auto &OperandInfo = getOrCreateValueInfo(Op);
356 if (OperandInfo.Infos.empty())
357 OpsToRename.push_back(Elt: Op);
358 OperandInfo.Infos.push_back(Elt: PB);
359}
360
361// Process an assume instruction and place relevant operations we want to rename
362// into OpsToRename.
363void PredicateInfoBuilder::processAssume(
364 AssumeInst *II, BasicBlock *AssumeBB,
365 SmallVectorImpl<Value *> &OpsToRename) {
366 if (II->hasOperandBundles()) {
367 for (auto OBU : II->operand_bundles()) {
368 if (getBundleAttrFromOBU(OBU) == BundleAttr::NonNull) {
369 if (auto [Ptr] = getAssumeNonNullInfo(OBU); shouldRename(V: Ptr))
370 addInfoFor(OpsToRename, Op: Ptr,
371 PB: new (Allocator)
372 PredicateBundleAssume(Ptr, II, BundleAttr::NonNull));
373 }
374 }
375 return;
376 }
377
378 SmallVector<Value *, 4> Worklist;
379 SmallPtrSet<Value *, 4> Visited;
380 Worklist.push_back(Elt: II->getOperand(i_nocapture: 0));
381 while (!Worklist.empty()) {
382 Value *Cond = Worklist.pop_back_val();
383 if (!Visited.insert(Ptr: Cond).second)
384 continue;
385 if (Visited.size() > MaxCondsPerBranch)
386 break;
387
388 Value *Op0, *Op1;
389 if (match(V: Cond, P: m_LogicalAnd(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
390 Worklist.push_back(Elt: Op1);
391 Worklist.push_back(Elt: Op0);
392 }
393
394 SmallVector<Value *, 4> Values;
395 Values.push_back(Elt: Cond);
396 if (auto *Cmp = dyn_cast<CmpInst>(Val: Cond))
397 collectCmpOps(Comparison: Cmp, CmpOperands&: Values);
398 else if (match(V: Cond, P: m_NUWTrunc(Op: m_Value(V&: Op0))))
399 Values.push_back(Elt: Op0);
400
401 for (Value *V : Values) {
402 if (shouldRename(V)) {
403 auto *PA = new (Allocator) PredicateConditionAssume(V, II, Cond);
404 addInfoFor(OpsToRename, Op: V, PB: PA);
405 }
406 }
407 }
408}
409
410// Process a block terminating branch, and place relevant operations to be
411// renamed into OpsToRename.
412void PredicateInfoBuilder::processBranch(
413 CondBrInst *BI, BasicBlock *BranchBB,
414 SmallVectorImpl<Value *> &OpsToRename) {
415 BasicBlock *FirstBB = BI->getSuccessor(i: 0);
416 BasicBlock *SecondBB = BI->getSuccessor(i: 1);
417
418 for (BasicBlock *Succ : {FirstBB, SecondBB}) {
419 bool TakenEdge = Succ == FirstBB;
420 // Don't try to insert on a self-edge. This is mainly because we will
421 // eliminate during renaming anyway.
422 if (Succ == BranchBB)
423 continue;
424
425 SmallVector<Value *, 4> Worklist;
426 SmallPtrSet<Value *, 4> Visited;
427 Worklist.push_back(Elt: BI->getCondition());
428 while (!Worklist.empty()) {
429 Value *Cond = Worklist.pop_back_val();
430 if (!Visited.insert(Ptr: Cond).second)
431 continue;
432 if (Visited.size() > MaxCondsPerBranch)
433 break;
434
435 Value *Op0, *Op1;
436 if (TakenEdge ? match(V: Cond, P: m_LogicalAnd(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))
437 : match(V: Cond, P: m_LogicalOr(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
438 Worklist.push_back(Elt: Op1);
439 Worklist.push_back(Elt: Op0);
440 }
441
442 SmallVector<Value *, 4> Values;
443 Values.push_back(Elt: Cond);
444 if (auto *Cmp = dyn_cast<CmpInst>(Val: Cond))
445 collectCmpOps(Comparison: Cmp, CmpOperands&: Values);
446 else if (match(V: Cond, P: m_NUWTrunc(Op: m_Value(V&: Op0))))
447 Values.push_back(Elt: Op0);
448
449 for (Value *V : Values) {
450 if (shouldRename(V)) {
451 PredicateBase *PB = new (Allocator)
452 PredicateBranch(V, BranchBB, Succ, Cond, TakenEdge);
453 addInfoFor(OpsToRename, Op: V, PB);
454 }
455 }
456 }
457 }
458}
459// Process a block terminating switch, and place relevant operations to be
460// renamed into OpsToRename.
461void PredicateInfoBuilder::processSwitch(
462 SwitchInst *SI, BasicBlock *BranchBB,
463 SmallVectorImpl<Value *> &OpsToRename) {
464 Value *Op = SI->getCondition();
465 if ((!isa<Instruction>(Val: Op) && !isa<Argument>(Val: Op)) || Op->hasOneUse())
466 return;
467
468 // Remember how many outgoing edges there are to every successor.
469 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
470 for (BasicBlock *TargetBlock : successors(BB: BranchBB))
471 ++SwitchEdges[TargetBlock];
472
473 // Now propagate info for each case value
474 for (auto C : SI->cases()) {
475 BasicBlock *TargetBlock = C.getCaseSuccessor();
476 if (SwitchEdges.lookup(Val: TargetBlock) == 1) {
477 PredicateSwitch *PS = new (Allocator) PredicateSwitch(
478 Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
479 addInfoFor(OpsToRename, Op, PB: PS);
480 }
481 }
482}
483
484// Build predicate info for our function
485void PredicateInfoBuilder::buildPredicateInfo() {
486 DT.updateDFSNumbers();
487 // Collect operands to rename from all conditional branch terminators, as well
488 // as assume statements.
489 SmallVector<Value *, 8> OpsToRename;
490 for (BasicBlock &BB : F) {
491 if (!DT.isReachableFromEntry(A: &BB))
492 continue;
493
494 if (auto *BI = dyn_cast<CondBrInst>(Val: BB.getTerminator())) {
495 // Can't insert conditional information if they all go to the same place.
496 if (BI->getSuccessor(i: 0) == BI->getSuccessor(i: 1))
497 continue;
498 processBranch(BI, BranchBB: &BB, OpsToRename);
499 } else if (auto *SI = dyn_cast<SwitchInst>(Val: BB.getTerminator())) {
500 processSwitch(SI, BranchBB: &BB, OpsToRename);
501 }
502 }
503 for (auto &Assume : AC.assumptions()) {
504 if (auto *II = cast_or_null<AssumeInst>(Val&: Assume))
505 if (DT.isReachableFromEntry(A: II->getParent()))
506 processAssume(II, AssumeBB: II->getParent(), OpsToRename);
507 }
508 // Now rename all our operations.
509 renameUses(OpsToRename);
510}
511
512// Given the renaming stack, make all the operands currently on the stack real
513// by inserting them into the IR. Return the last operation's value.
514Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,
515 ValueDFSStack &RenameStack,
516 Value *OrigOp) {
517 // Find the first thing we have to materialize
518 auto RevIter = RenameStack.rbegin();
519 for (; RevIter != RenameStack.rend(); ++RevIter)
520 if (RevIter->Def)
521 break;
522
523 size_t Start = RevIter - RenameStack.rbegin();
524 // The maximum number of things we should be trying to materialize at once
525 // right now is 4, depending on if we had an assume, a branch, and both used
526 // and of conditions.
527 for (auto RenameIter = RenameStack.end() - Start;
528 RenameIter != RenameStack.end(); ++RenameIter) {
529 auto *Op =
530 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
531 StackEntry &Result = *RenameIter;
532 auto *ValInfo = Result.V->PInfo;
533 ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
534 ? OrigOp
535 : (RenameStack.end() - Start - 1)->Def;
536 auto CreateSSACopy = [](Instruction *InsertPt, Value *Op,
537 const Twine &Name = "") {
538 // Use a no-op bitcast to represent ssa copy.
539 return new BitCastInst(Op, Op->getType(), Name, InsertPt->getIterator());
540 };
541 // For edge predicates, we can just place the operand in the block before
542 // the terminator. For assume, we have to place it right after the assume
543 // to ensure we dominate all uses except assume itself. Always insert
544 // right before the terminator or after the assume, so that we insert in
545 // proper order in the case of multiple predicateinfo in the same block.
546 if (isa<PredicateWithEdge>(Val: ValInfo)) {
547 BitCastInst *PIC = CreateSSACopy(getBranchTerminator(PB: ValInfo), Op,
548 Op->getName() + "." + Twine(Counter++));
549 PI.PredicateMap.insert(KV: {PIC, ValInfo});
550 Result.Def = PIC;
551 } else {
552 auto *PAssume = dyn_cast<PredicateAssume>(Val: ValInfo);
553 assert(PAssume &&
554 "Should not have gotten here without it being an assume");
555 // Insert the predicate directly after the assume. While it also holds
556 // directly before it, assume(i1 true) is not a useful fact.
557 BitCastInst *PIC = CreateSSACopy(PAssume->AssumeInst->getNextNode(), Op);
558 PI.PredicateMap.insert(KV: {PIC, ValInfo});
559 Result.Def = PIC;
560 }
561 }
562 return RenameStack.back().Def;
563}
564
565// Instead of the standard SSA renaming algorithm, which is O(Number of
566// instructions), and walks the entire dominator tree, we walk only the defs +
567// uses. The standard SSA renaming algorithm does not really rely on the
568// dominator tree except to order the stack push/pops of the renaming stacks, so
569// that defs end up getting pushed before hitting the correct uses. This does
570// not require the dominator tree, only the *order* of the dominator tree. The
571// complete and correct ordering of the defs and uses, in dominator tree is
572// contained in the DFS numbering of the dominator tree. So we sort the defs and
573// uses into the DFS ordering, and then just use the renaming stack as per
574// normal, pushing when we hit a def (which is a predicateinfo instruction),
575// popping when we are out of the dfs scope for that def, and replacing any uses
576// with top of stack if it exists. In order to handle liveness without
577// propagating liveness info, we don't actually insert the predicateinfo
578// instruction def until we see a use that it would dominate. Once we see such
579// a use, we materialize the predicateinfo instruction in the right place and
580// use it.
581//
582// TODO: Use this algorithm to perform fast single-variable renaming in
583// promotememtoreg and memoryssa.
584void PredicateInfoBuilder::renameUses(SmallVectorImpl<Value *> &OpsToRename) {
585 ValueDFS_Compare Compare(DT);
586 // Compute liveness, and rename in O(uses) per Op.
587 for (auto *Op : OpsToRename) {
588 LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
589 unsigned Counter = 0;
590 SmallVector<ValueDFS, 16> OrderedUses;
591 const auto &ValueInfo = getValueInfo(Op);
592 // Insert the possible copies into the def/use list.
593 // They will become real copies if we find a real use for them, and never
594 // created otherwise.
595 for (const auto &PossibleCopy : ValueInfo.Infos) {
596 ValueDFS VD;
597 // Determine where we are going to place the copy by the copy type.
598 // The predicate info for branches always come first, they will get
599 // materialized in the split block at the top of the block.
600 // The predicate info for assumes will be somewhere in the middle,
601 // it will get materialized right after the assume.
602 if (const auto *PAssume = dyn_cast<PredicateAssume>(Val: PossibleCopy)) {
603 VD.LocalNum = LN_Middle;
604 DomTreeNode *DomNode = DT.getNode(BB: PAssume->AssumeInst->getParent());
605 if (!DomNode)
606 continue;
607 VD.DFSIn = DomNode->getDFSNumIn();
608 VD.DFSOut = DomNode->getDFSNumOut();
609 VD.PInfo = PossibleCopy;
610 OrderedUses.push_back(Elt: VD);
611 } else if (isa<PredicateWithEdge>(Val: PossibleCopy)) {
612 // If we can only do phi uses, we treat it like it's in the branch
613 // block, and handle it specially. We know that it goes last, and only
614 // dominate phi uses.
615 auto BlockEdge = getBlockEdge(PB: PossibleCopy);
616 if (!BlockEdge.second->getSinglePredecessor()) {
617 VD.LocalNum = LN_Last;
618 auto *DomNode = DT.getNode(BB: BlockEdge.first);
619 if (DomNode) {
620 VD.DFSIn = DomNode->getDFSNumIn();
621 VD.DFSOut = DomNode->getDFSNumOut();
622 VD.PInfo = PossibleCopy;
623 OrderedUses.push_back(Elt: VD);
624 }
625 } else {
626 // Otherwise, we are in the split block (even though we perform
627 // insertion in the branch block).
628 // Insert a possible copy at the split block and before the branch.
629 VD.LocalNum = LN_First;
630 auto *DomNode = DT.getNode(BB: BlockEdge.second);
631 if (DomNode) {
632 VD.DFSIn = DomNode->getDFSNumIn();
633 VD.DFSOut = DomNode->getDFSNumOut();
634 VD.PInfo = PossibleCopy;
635 OrderedUses.push_back(Elt: VD);
636 }
637 }
638 }
639 }
640
641 convertUsesToDFSOrdered(Op, DFSOrderedSet&: OrderedUses);
642 // Here we require a stable sort because we do not bother to try to
643 // assign an order to the operands the uses represent. Thus, two
644 // uses in the same instruction do not have a strict sort order
645 // currently and will be considered equal. We could get rid of the
646 // stable sort by creating one if we wanted.
647 llvm::stable_sort(Range&: OrderedUses, C: Compare);
648 SmallVector<StackEntry, 8> RenameStack;
649 // For each use, sorted into dfs order, push values and replaces uses with
650 // top of stack, which will represent the reaching def.
651 for (const ValueDFS &VD : OrderedUses) {
652 // We currently do not materialize copy over copy, but we should decide if
653 // we want to.
654 if (RenameStack.empty()) {
655 LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
656 } else {
657 LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
658 << RenameStack.back().V->DFSIn << ","
659 << RenameStack.back().V->DFSOut << ")\n");
660 }
661
662 LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
663 << VD.DFSOut << ")\n");
664
665 // Sync to our current scope.
666 popStackUntilDFSScope(Stack&: RenameStack, VD);
667
668 if (VD.PInfo) {
669 RenameStack.push_back(Elt: &VD);
670 continue;
671 }
672
673 // If we get to this point, and the stack is empty we must have a use
674 // with no renaming needed, just skip it.
675 if (RenameStack.empty())
676 continue;
677 if (!DebugCounter::shouldExecute(Counter&: RenameCounter)) {
678 LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
679 continue;
680 }
681 StackEntry &Result = RenameStack.back();
682
683 // If the possible copy dominates something, materialize our stack up to
684 // this point. This ensures every comparison that affects our operation
685 // ends up with predicateinfo.
686 if (!Result.Def)
687 Result.Def = materializeStack(Counter, RenameStack, OrigOp: Op);
688
689 LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
690 << *VD.U->get() << " in " << *(VD.U->getUser())
691 << "\n");
692 assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
693 "Predicateinfo def should have dominated this use");
694 VD.U->set(Result.Def);
695 }
696 }
697}
698
699PredicateInfoBuilder::ValueInfo &
700PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) {
701 auto Res = ValueInfoNums.try_emplace(Key: Operand, Args: ValueInfos.size());
702 if (Res.second) {
703 // Allocate space for new ValueInfo.
704 ValueInfos.resize(N: ValueInfos.size() + 1);
705 }
706 return ValueInfos[Res.first->second];
707}
708
709const PredicateInfoBuilder::ValueInfo &
710PredicateInfoBuilder::getValueInfo(Value *Operand) const {
711 auto OINI = ValueInfoNums.lookup(Val: Operand);
712 assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
713 assert(OINI < ValueInfos.size() &&
714 "Value Info Number greater than size of Value Info Table");
715 return ValueInfos[OINI];
716}
717
718PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
719 AssumptionCache &AC, BumpPtrAllocator &Allocator)
720 : F(F) {
721 PredicateInfoBuilder Builder(*this, F, DT, AC, Allocator);
722 Builder.buildPredicateInfo();
723}
724
725std::optional<PredicateConstraint> PredicateBase::getConstraint() const {
726 switch (Type) {
727 case PT_BundleAssume: {
728 assert(cast<PredicateBundleAssume>(this)->AttrKind == BundleAttr::NonNull &&
729 "Cannot handle anything other than NonNull");
730 return {{.Predicate: CmpInst::ICMP_NE, .OtherOp: ConstantPointerNull::get(
731 T: cast<PointerType>(Val: OriginalOp->getType()))}};
732 }
733
734 case PT_ConditionAssume:
735 case PT_Branch: {
736 bool TrueEdge = true;
737 if (auto *PBranch = dyn_cast<PredicateBranch>(Val: this))
738 TrueEdge = PBranch->TrueEdge;
739
740 if (Condition == RenamedOp) {
741 return {{.Predicate: CmpInst::ICMP_EQ,
742 .OtherOp: TrueEdge ? ConstantInt::getTrue(Ty: Condition->getType())
743 : ConstantInt::getFalse(Ty: Condition->getType())}};
744 }
745
746 if (match(V: Condition, P: m_NUWTrunc(Op: m_Specific(V: RenamedOp)))) {
747 return {{.Predicate: TrueEdge ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ,
748 .OtherOp: ConstantInt::getNullValue(Ty: RenamedOp->getType())}};
749 }
750
751 CmpInst *Cmp = dyn_cast<CmpInst>(Val: Condition);
752 if (!Cmp) {
753 // TODO: Make this an assertion once RenamedOp is fully accurate.
754 return std::nullopt;
755 }
756
757 CmpInst::Predicate Pred;
758 Value *OtherOp;
759 if (Cmp->getOperand(i_nocapture: 0) == RenamedOp) {
760 Pred = Cmp->getPredicate();
761 OtherOp = Cmp->getOperand(i_nocapture: 1);
762 } else if (Cmp->getOperand(i_nocapture: 1) == RenamedOp) {
763 Pred = Cmp->getSwappedPredicate();
764 OtherOp = Cmp->getOperand(i_nocapture: 0);
765 } else {
766 // TODO: Make this an assertion once RenamedOp is fully accurate.
767 return std::nullopt;
768 }
769
770 // Invert predicate along false edge.
771 if (!TrueEdge)
772 Pred = CmpInst::getInversePredicate(pred: Pred);
773
774 return {{.Predicate: Pred, .OtherOp: OtherOp}};
775 }
776 case PT_Switch:
777 if (Condition != RenamedOp) {
778 // TODO: Make this an assertion once RenamedOp is fully accurate.
779 return std::nullopt;
780 }
781
782 return {{.Predicate: CmpInst::ICMP_EQ, .OtherOp: cast<PredicateSwitch>(Val: this)->CaseValue}};
783 }
784 llvm_unreachable("Unknown predicate type");
785}
786
787void PredicateInfo::verifyPredicateInfo() const {}
788
789// Replace bitcasts created by PredicateInfo with their operand.
790static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
791 for (Instruction &Inst : llvm::make_early_inc_range(Range: instructions(F))) {
792 const auto *PI = PredInfo.getPredicateInfoFor(V: &Inst);
793 if (!PI)
794 continue;
795
796 assert(isa<BitCastInst>(Inst) &&
797 Inst.getType() == Inst.getOperand(0)->getType());
798 Inst.replaceAllUsesWith(V: Inst.getOperand(i: 0));
799 Inst.eraseFromParent();
800 }
801}
802
803PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
804 FunctionAnalysisManager &AM) {
805 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
806 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
807 OS << "PredicateInfo for function: " << F.getName() << "\n";
808 BumpPtrAllocator Allocator;
809 auto PredInfo = std::make_unique<PredicateInfo>(args&: F, args&: DT, args&: AC, args&: Allocator);
810 PredInfo->print(OS);
811
812 replaceCreatedSSACopys(PredInfo&: *PredInfo, F);
813 return PreservedAnalyses::all();
814}
815
816/// An assembly annotator class to print PredicateInfo information in
817/// comments.
818class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
819 friend class PredicateInfo;
820 const PredicateInfo *PredInfo;
821
822public:
823 PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
824
825 void emitBasicBlockStartAnnot(const BasicBlock *BB,
826 formatted_raw_ostream &OS) override {}
827
828 void emitInstructionAnnot(const Instruction *I,
829 formatted_raw_ostream &OS) override {
830 if (const auto *PI = PredInfo->getPredicateInfoFor(V: I)) {
831 if (const auto *PB = dyn_cast<PredicateBranch>(Val: PI)) {
832 OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
833 << " Comparison:" << *PB->Condition << " Edge: [";
834 PB->From->printAsOperand(O&: OS);
835 OS << ",";
836 PB->To->printAsOperand(O&: OS);
837 OS << "]";
838 } else if (const auto *PS = dyn_cast<PredicateSwitch>(Val: PI)) {
839 OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
840 << " Edge: [";
841 PS->From->printAsOperand(O&: OS);
842 OS << ",";
843 PS->To->printAsOperand(O&: OS);
844 OS << "]";
845 } else if (const auto *PA = dyn_cast<PredicateAssume>(Val: PI)) {
846 OS << "; assume predicate info {";
847 if (auto *PBA = dyn_cast<PredicateBundleAssume>(Val: PA)) {
848 OS << " Attribute: " << getNameFromBundleAttr(PBA->AttrKind);
849 } else {
850 assert(isa<PredicateConditionAssume>(PA));
851 OS << " Comparison:" << *PA->Condition;
852 }
853 }
854 OS << ", RenamedOp: ";
855 PI->RenamedOp->printAsOperand(O&: OS, PrintType: false);
856 OS << " }\n";
857 }
858 }
859};
860
861void PredicateInfo::print(raw_ostream &OS) const {
862 PredicateInfoAnnotatedWriter Writer(this);
863 F.print(OS, AAW: &Writer);
864}
865
866void PredicateInfo::dump() const {
867 PredicateInfoAnnotatedWriter Writer(this);
868 F.print(OS&: dbgs(), AAW: &Writer);
869}
870
871PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
872 FunctionAnalysisManager &AM) {
873 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
874 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
875 BumpPtrAllocator Allocator;
876 std::make_unique<PredicateInfo>(args&: F, args&: DT, args&: AC, args&: Allocator)->verifyPredicateInfo();
877
878 return PreservedAnalyses::all();
879}
880}
881