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