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