LLVM  9.0.0svn
PredicateInfo.cpp
Go to the documentation of this file.
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 
14 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/CFG.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/GlobalVariable.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/Support/Debug.h"
36 #include "llvm/Transforms/Utils.h"
37 #include <algorithm>
38 #define DEBUG_TYPE "predicateinfo"
39 using namespace llvm;
40 using namespace PatternMatch;
41 using namespace llvm::PredicateInfoClasses;
42 
44  "PredicateInfo Printer", false, false)
48  "PredicateInfo Printer", false, false)
49 static cl::opt<bool> VerifyPredicateInfo(
50  "verify-predicateinfo", cl::init(false), cl::Hidden,
51  cl::desc("Verify PredicateInfo in legacy printer pass."));
52 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
53  "Controls which variables are renamed with predicateinfo");
54 
55 namespace {
56 // Given a predicate info that is a type of branching terminator, get the
57 // branching block.
58 const BasicBlock *getBranchBlock(const PredicateBase *PB) {
59  assert(isa<PredicateWithEdge>(PB) &&
60  "Only branches and switches should have PHIOnly defs that "
61  "require branch blocks.");
62  return cast<PredicateWithEdge>(PB)->From;
63 }
64 
65 // Given a predicate info that is a type of branching terminator, get the
66 // branching terminator.
67 static Instruction *getBranchTerminator(const PredicateBase *PB) {
68  assert(isa<PredicateWithEdge>(PB) &&
69  "Not a predicate info type we know how to get a terminator from.");
70  return cast<PredicateWithEdge>(PB)->From->getTerminator();
71 }
72 
73 // Given a predicate info that is a type of branching terminator, get the
74 // edge this predicate info represents
75 const std::pair<BasicBlock *, BasicBlock *>
76 getBlockEdge(const PredicateBase *PB) {
77  assert(isa<PredicateWithEdge>(PB) &&
78  "Not a predicate info type we know how to get an edge from.");
79  const auto *PEdge = cast<PredicateWithEdge>(PB);
80  return std::make_pair(PEdge->From, PEdge->To);
81 }
82 }
83 
84 namespace llvm {
85 namespace PredicateInfoClasses {
86 enum LocalNum {
87  // Operations that must appear first in the block.
89  // Operations that are somewhere in the middle of the block, and are sorted on
90  // demand.
92  // Operations that must appear last in a block, like successor phi node uses.
94 };
95 
96 // Associate global and local DFS info with defs and uses, so we can sort them
97 // into a global domination ordering.
98 struct ValueDFS {
99  int DFSIn = 0;
100  int DFSOut = 0;
101  unsigned int LocalNum = LN_Middle;
102  // Only one of Def or Use will be set.
103  Value *Def = nullptr;
104  Use *U = nullptr;
105  // Neither PInfo nor EdgeOnly participate in the ordering
106  PredicateBase *PInfo = nullptr;
107  bool EdgeOnly = false;
108 };
109 
110 // Perform a strict weak ordering on instructions and arguments.
111 static bool valueComesBefore(OrderedInstructions &OI, const Value *A,
112  const Value *B) {
113  auto *ArgA = dyn_cast_or_null<Argument>(A);
114  auto *ArgB = dyn_cast_or_null<Argument>(B);
115  if (ArgA && !ArgB)
116  return true;
117  if (ArgB && !ArgA)
118  return false;
119  if (ArgA && ArgB)
120  return ArgA->getArgNo() < ArgB->getArgNo();
121  return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
122 }
123 
124 // This compares ValueDFS structures, creating OrderedBasicBlocks where
125 // necessary to compare uses/defs in the same block. Doing so allows us to walk
126 // the minimum number of instructions necessary to compute our def/use ordering.
130 
131  bool operator()(const ValueDFS &A, const ValueDFS &B) const {
132  if (&A == &B)
133  return false;
134  // The only case we can't directly compare them is when they in the same
135  // block, and both have localnum == middle. In that case, we have to use
136  // comesbefore to see what the real ordering is, because they are in the
137  // same basic block.
138 
139  bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
140 
141  // We want to put the def that will get used for a given set of phi uses,
142  // before those phi uses.
143  // So we sort by edge, then by def.
144  // Note that only phi nodes uses and defs can come last.
145  if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
146  return comparePHIRelated(A, B);
147 
148  if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
149  return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) <
150  std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U);
151  return localComesBefore(A, B);
152  }
153 
154  // For a phi use, or a non-materialized def, return the edge it represents.
155  const std::pair<BasicBlock *, BasicBlock *>
156  getBlockEdge(const ValueDFS &VD) const {
157  if (!VD.Def && VD.U) {
158  auto *PHI = cast<PHINode>(VD.U->getUser());
159  return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
160  }
161  // This is really a non-materialized def.
162  return ::getBlockEdge(VD.PInfo);
163  }
164 
165  // For two phi related values, return the ordering.
166  bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
167  auto &ABlockEdge = getBlockEdge(A);
168  auto &BBlockEdge = getBlockEdge(B);
169  // Now sort by block edge and then defs before uses.
170  return std::tie(ABlockEdge, A.Def, A.U) < std::tie(BBlockEdge, B.Def, B.U);
171  }
172 
173  // Get the definition of an instruction that occurs in the middle of a block.
174  Value *getMiddleDef(const ValueDFS &VD) const {
175  if (VD.Def)
176  return VD.Def;
177  // It's possible for the defs and uses to be null. For branches, the local
178  // numbering will say the placed predicaeinfos should go first (IE
179  // LN_beginning), so we won't be in this function. For assumes, we will end
180  // up here, beause we need to order the def we will place relative to the
181  // assume. So for the purpose of ordering, we pretend the def is the assume
182  // because that is where we will insert the info.
183  if (!VD.U) {
184  assert(VD.PInfo &&
185  "No def, no use, and no predicateinfo should not occur");
186  assert(isa<PredicateAssume>(VD.PInfo) &&
187  "Middle of block should only occur for assumes");
188  return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
189  }
190  return nullptr;
191  }
192 
193  // Return either the Def, if it's not null, or the user of the Use, if the def
194  // is null.
195  const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
196  if (Def)
197  return cast<Instruction>(Def);
198  return cast<Instruction>(U->getUser());
199  }
200 
201  // This performs the necessary local basic block ordering checks to tell
202  // whether A comes before B, where both are in the same basic block.
203  bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
204  auto *ADef = getMiddleDef(A);
205  auto *BDef = getMiddleDef(B);
206 
207  // See if we have real values or uses. If we have real values, we are
208  // guaranteed they are instructions or arguments. No matter what, we are
209  // guaranteed they are in the same block if they are instructions.
210  auto *ArgA = dyn_cast_or_null<Argument>(ADef);
211  auto *ArgB = dyn_cast_or_null<Argument>(BDef);
212 
213  if (ArgA || ArgB)
214  return valueComesBefore(OI, ArgA, ArgB);
215 
216  auto *AInst = getDefOrUser(ADef, A.U);
217  auto *BInst = getDefOrUser(BDef, B.U);
218  return valueComesBefore(OI, AInst, BInst);
219  }
220 };
221 
222 } // namespace PredicateInfoClasses
223 
224 bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
225  const ValueDFS &VDUse) const {
226  if (Stack.empty())
227  return false;
228  // If it's a phi only use, make sure it's for this phi node edge, and that the
229  // use is in a phi node. If it's anything else, and the top of the stack is
230  // EdgeOnly, we need to pop the stack. We deliberately sort phi uses next to
231  // the defs they must go with so that we can know it's time to pop the stack
232  // when we hit the end of the phi uses for a given def.
233  if (Stack.back().EdgeOnly) {
234  if (!VDUse.U)
235  return false;
236  auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
237  if (!PHI)
238  return false;
239  // Check edge
240  BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
241  if (EdgePred != getBranchBlock(Stack.back().PInfo))
242  return false;
243 
244  // Use dominates, which knows how to handle edge dominance.
245  return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
246  }
247 
248  return (VDUse.DFSIn >= Stack.back().DFSIn &&
249  VDUse.DFSOut <= Stack.back().DFSOut);
250 }
251 
252 void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
253  const ValueDFS &VD) {
254  while (!Stack.empty() && !stackIsInScope(Stack, VD))
255  Stack.pop_back();
256 }
257 
258 // Convert the uses of Op into a vector of uses, associating global and local
259 // DFS info with each one.
260 void PredicateInfo::convertUsesToDFSOrdered(
261  Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
262  for (auto &U : Op->uses()) {
263  if (auto *I = dyn_cast<Instruction>(U.getUser())) {
264  ValueDFS VD;
265  // Put the phi node uses in the incoming block.
266  BasicBlock *IBlock;
267  if (auto *PN = dyn_cast<PHINode>(I)) {
268  IBlock = PN->getIncomingBlock(U);
269  // Make phi node users appear last in the incoming block
270  // they are from.
271  VD.LocalNum = LN_Last;
272  } else {
273  // If it's not a phi node use, it is somewhere in the middle of the
274  // block.
275  IBlock = I->getParent();
276  VD.LocalNum = LN_Middle;
277  }
278  DomTreeNode *DomNode = DT.getNode(IBlock);
279  // It's possible our use is in an unreachable block. Skip it if so.
280  if (!DomNode)
281  continue;
282  VD.DFSIn = DomNode->getDFSNumIn();
283  VD.DFSOut = DomNode->getDFSNumOut();
284  VD.U = &U;
285  DFSOrderedSet.push_back(VD);
286  }
287  }
288 }
289 
290 // Collect relevant operations from Comparison that we may want to insert copies
291 // for.
292 void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
293  auto *Op0 = Comparison->getOperand(0);
294  auto *Op1 = Comparison->getOperand(1);
295  if (Op0 == Op1)
296  return;
297  CmpOperands.push_back(Comparison);
298  // Only want real values, not constants. Additionally, operands with one use
299  // are only being used in the comparison, which means they will not be useful
300  // for us to consider for predicateinfo.
301  //
302  if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse())
303  CmpOperands.push_back(Op0);
304  if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse())
305  CmpOperands.push_back(Op1);
306 }
307 
308 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
309 void PredicateInfo::addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
310  PredicateBase *PB) {
311  OpsToRename.insert(Op);
312  auto &OperandInfo = getOrCreateValueInfo(Op);
313  AllInfos.push_back(PB);
314  OperandInfo.Infos.push_back(PB);
315 }
316 
317 // Process an assume instruction and place relevant operations we want to rename
318 // into OpsToRename.
319 void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
320  SmallPtrSetImpl<Value *> &OpsToRename) {
321  // See if we have a comparison we support
322  SmallVector<Value *, 8> CmpOperands;
323  SmallVector<Value *, 2> ConditionsToProcess;
324  CmpInst::Predicate Pred;
325  Value *Operand = II->getOperand(0);
326  if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
327  m_Cmp(Pred, m_Value(), m_Value()))
328  .match(II->getOperand(0))) {
329  ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
330  ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
331  ConditionsToProcess.push_back(Operand);
332  } else if (isa<CmpInst>(Operand)) {
333 
334  ConditionsToProcess.push_back(Operand);
335  }
336  for (auto Cond : ConditionsToProcess) {
337  if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
338  collectCmpOps(Cmp, CmpOperands);
339  // Now add our copy infos for our operands
340  for (auto *Op : CmpOperands) {
341  auto *PA = new PredicateAssume(Op, II, Cmp);
342  addInfoFor(OpsToRename, Op, PA);
343  }
344  CmpOperands.clear();
345  } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
346  // Otherwise, it should be an AND.
347  assert(BinOp->getOpcode() == Instruction::And &&
348  "Should have been an AND");
349  auto *PA = new PredicateAssume(BinOp, II, BinOp);
350  addInfoFor(OpsToRename, BinOp, PA);
351  } else {
352  llvm_unreachable("Unknown type of condition");
353  }
354  }
355 }
356 
357 // Process a block terminating branch, and place relevant operations to be
358 // renamed into OpsToRename.
359 void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
360  SmallPtrSetImpl<Value *> &OpsToRename) {
361  BasicBlock *FirstBB = BI->getSuccessor(0);
362  BasicBlock *SecondBB = BI->getSuccessor(1);
363  SmallVector<BasicBlock *, 2> SuccsToProcess;
364  SuccsToProcess.push_back(FirstBB);
365  SuccsToProcess.push_back(SecondBB);
366  SmallVector<Value *, 2> ConditionsToProcess;
367 
368  auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
369  for (auto *Succ : SuccsToProcess) {
370  // Don't try to insert on a self-edge. This is mainly because we will
371  // eliminate during renaming anyway.
372  if (Succ == BranchBB)
373  continue;
374  bool TakenEdge = (Succ == FirstBB);
375  // For and, only insert on the true edge
376  // For or, only insert on the false edge
377  if ((isAnd && !TakenEdge) || (isOr && TakenEdge))
378  continue;
379  PredicateBase *PB =
380  new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
381  addInfoFor(OpsToRename, Op, PB);
382  if (!Succ->getSinglePredecessor())
383  EdgeUsesOnly.insert({BranchBB, Succ});
384  }
385  };
386 
387  // Match combinations of conditions.
388  CmpInst::Predicate Pred;
389  bool isAnd = false;
390  bool isOr = false;
391  SmallVector<Value *, 8> CmpOperands;
392  if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
393  m_Cmp(Pred, m_Value(), m_Value()))) ||
394  match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
395  m_Cmp(Pred, m_Value(), m_Value())))) {
396  auto *BinOp = cast<BinaryOperator>(BI->getCondition());
397  if (BinOp->getOpcode() == Instruction::And)
398  isAnd = true;
399  else if (BinOp->getOpcode() == Instruction::Or)
400  isOr = true;
401  ConditionsToProcess.push_back(BinOp->getOperand(0));
402  ConditionsToProcess.push_back(BinOp->getOperand(1));
403  ConditionsToProcess.push_back(BI->getCondition());
404  } else if (isa<CmpInst>(BI->getCondition())) {
405  ConditionsToProcess.push_back(BI->getCondition());
406  }
407  for (auto Cond : ConditionsToProcess) {
408  if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
409  collectCmpOps(Cmp, CmpOperands);
410  // Now add our copy infos for our operands
411  for (auto *Op : CmpOperands)
412  InsertHelper(Op, isAnd, isOr, Cmp);
413  } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
414  // This must be an AND or an OR.
415  assert((BinOp->getOpcode() == Instruction::And ||
416  BinOp->getOpcode() == Instruction::Or) &&
417  "Should have been an AND or an OR");
418  // The actual value of the binop is not subject to the same restrictions
419  // as the comparison. It's either true or false on the true/false branch.
420  InsertHelper(BinOp, false, false, BinOp);
421  } else {
422  llvm_unreachable("Unknown type of condition");
423  }
424  CmpOperands.clear();
425  }
426 }
427 // Process a block terminating switch, and place relevant operations to be
428 // renamed into OpsToRename.
429 void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
430  SmallPtrSetImpl<Value *> &OpsToRename) {
431  Value *Op = SI->getCondition();
432  if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
433  return;
434 
435  // Remember how many outgoing edges there are to every successor.
437  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
438  BasicBlock *TargetBlock = SI->getSuccessor(i);
439  ++SwitchEdges[TargetBlock];
440  }
441 
442  // Now propagate info for each case value
443  for (auto C : SI->cases()) {
444  BasicBlock *TargetBlock = C.getCaseSuccessor();
445  if (SwitchEdges.lookup(TargetBlock) == 1) {
447  Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
448  addInfoFor(OpsToRename, Op, PS);
449  if (!TargetBlock->getSinglePredecessor())
450  EdgeUsesOnly.insert({BranchBB, TargetBlock});
451  }
452  }
453 }
454 
455 // Build predicate info for our function
456 void PredicateInfo::buildPredicateInfo() {
457  DT.updateDFSNumbers();
458  // Collect operands to rename from all conditional branch terminators, as well
459  // as assume statements.
460  SmallPtrSet<Value *, 8> OpsToRename;
461  for (auto DTN : depth_first(DT.getRootNode())) {
462  BasicBlock *BranchBB = DTN->getBlock();
463  if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
464  if (!BI->isConditional())
465  continue;
466  // Can't insert conditional information if they all go to the same place.
467  if (BI->getSuccessor(0) == BI->getSuccessor(1))
468  continue;
469  processBranch(BI, BranchBB, OpsToRename);
470  } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
471  processSwitch(SI, BranchBB, OpsToRename);
472  }
473  }
474  for (auto &Assume : AC.assumptions()) {
475  if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
476  if (DT.isReachableFromEntry(II->getParent()))
477  processAssume(II, II->getParent(), OpsToRename);
478  }
479  // Now rename all our operations.
480  renameUses(OpsToRename);
481 }
482 
483 // Create a ssa_copy declaration with custom mangling, because
484 // Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
485 // all unnamed types get mangled to the same string. We use the pointer
486 // to the type as name here, as it guarantees unique names for different
487 // types and we remove the declarations when destroying PredicateInfo.
488 // It is a workaround for PR38117, because solving it in a fully general way is
489 // tricky (FIXME).
491  std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty);
492  return cast<Function>(
493  M->getOrInsertFunction(Name,
494  getType(M->getContext(), Intrinsic::ssa_copy, Ty))
495  .getCallee());
496 }
497 
498 // Given the renaming stack, make all the operands currently on the stack real
499 // by inserting them into the IR. Return the last operation's value.
500 Value *PredicateInfo::materializeStack(unsigned int &Counter,
501  ValueDFSStack &RenameStack,
502  Value *OrigOp) {
503  // Find the first thing we have to materialize
504  auto RevIter = RenameStack.rbegin();
505  for (; RevIter != RenameStack.rend(); ++RevIter)
506  if (RevIter->Def)
507  break;
508 
509  size_t Start = RevIter - RenameStack.rbegin();
510  // The maximum number of things we should be trying to materialize at once
511  // right now is 4, depending on if we had an assume, a branch, and both used
512  // and of conditions.
513  for (auto RenameIter = RenameStack.end() - Start;
514  RenameIter != RenameStack.end(); ++RenameIter) {
515  auto *Op =
516  RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
517  ValueDFS &Result = *RenameIter;
518  auto *ValInfo = Result.PInfo;
519  // For edge predicates, we can just place the operand in the block before
520  // the terminator. For assume, we have to place it right before the assume
521  // to ensure we dominate all of our uses. Always insert right before the
522  // relevant instruction (terminator, assume), so that we insert in proper
523  // order in the case of multiple predicateinfo in the same block.
524  if (isa<PredicateWithEdge>(ValInfo)) {
525  IRBuilder<> B(getBranchTerminator(ValInfo));
526  Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
527  if (empty(IF->users()))
528  CreatedDeclarations.insert(IF);
529  CallInst *PIC =
530  B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
531  PredicateMap.insert({PIC, ValInfo});
532  Result.Def = PIC;
533  } else {
534  auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
535  assert(PAssume &&
536  "Should not have gotten here without it being an assume");
537  IRBuilder<> B(PAssume->AssumeInst);
538  Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
539  if (empty(IF->users()))
540  CreatedDeclarations.insert(IF);
541  CallInst *PIC = B.CreateCall(IF, Op);
542  PredicateMap.insert({PIC, ValInfo});
543  Result.Def = PIC;
544  }
545  }
546  return RenameStack.back().Def;
547 }
548 
549 // Instead of the standard SSA renaming algorithm, which is O(Number of
550 // instructions), and walks the entire dominator tree, we walk only the defs +
551 // uses. The standard SSA renaming algorithm does not really rely on the
552 // dominator tree except to order the stack push/pops of the renaming stacks, so
553 // that defs end up getting pushed before hitting the correct uses. This does
554 // not require the dominator tree, only the *order* of the dominator tree. The
555 // complete and correct ordering of the defs and uses, in dominator tree is
556 // contained in the DFS numbering of the dominator tree. So we sort the defs and
557 // uses into the DFS ordering, and then just use the renaming stack as per
558 // normal, pushing when we hit a def (which is a predicateinfo instruction),
559 // popping when we are out of the dfs scope for that def, and replacing any uses
560 // with top of stack if it exists. In order to handle liveness without
561 // propagating liveness info, we don't actually insert the predicateinfo
562 // instruction def until we see a use that it would dominate. Once we see such
563 // a use, we materialize the predicateinfo instruction in the right place and
564 // use it.
565 //
566 // TODO: Use this algorithm to perform fast single-variable renaming in
567 // promotememtoreg and memoryssa.
568 void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
569  // Sort OpsToRename since we are going to iterate it.
570  SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
571  auto Comparator = [&](const Value *A, const Value *B) {
572  return valueComesBefore(OI, A, B);
573  };
574  llvm::sort(OpsToRename, Comparator);
576  // Compute liveness, and rename in O(uses) per Op.
577  for (auto *Op : OpsToRename) {
578  LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
579  unsigned Counter = 0;
580  SmallVector<ValueDFS, 16> OrderedUses;
581  const auto &ValueInfo = getValueInfo(Op);
582  // Insert the possible copies into the def/use list.
583  // They will become real copies if we find a real use for them, and never
584  // created otherwise.
585  for (auto &PossibleCopy : ValueInfo.Infos) {
586  ValueDFS VD;
587  // Determine where we are going to place the copy by the copy type.
588  // The predicate info for branches always come first, they will get
589  // materialized in the split block at the top of the block.
590  // The predicate info for assumes will be somewhere in the middle,
591  // it will get materialized in front of the assume.
592  if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
593  VD.LocalNum = LN_Middle;
594  DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
595  if (!DomNode)
596  continue;
597  VD.DFSIn = DomNode->getDFSNumIn();
598  VD.DFSOut = DomNode->getDFSNumOut();
599  VD.PInfo = PossibleCopy;
600  OrderedUses.push_back(VD);
601  } else if (isa<PredicateWithEdge>(PossibleCopy)) {
602  // If we can only do phi uses, we treat it like it's in the branch
603  // block, and handle it specially. We know that it goes last, and only
604  // dominate phi uses.
605  auto BlockEdge = getBlockEdge(PossibleCopy);
606  if (EdgeUsesOnly.count(BlockEdge)) {
607  VD.LocalNum = LN_Last;
608  auto *DomNode = DT.getNode(BlockEdge.first);
609  if (DomNode) {
610  VD.DFSIn = DomNode->getDFSNumIn();
611  VD.DFSOut = DomNode->getDFSNumOut();
612  VD.PInfo = PossibleCopy;
613  VD.EdgeOnly = true;
614  OrderedUses.push_back(VD);
615  }
616  } else {
617  // Otherwise, we are in the split block (even though we perform
618  // insertion in the branch block).
619  // Insert a possible copy at the split block and before the branch.
620  VD.LocalNum = LN_First;
621  auto *DomNode = DT.getNode(BlockEdge.second);
622  if (DomNode) {
623  VD.DFSIn = DomNode->getDFSNumIn();
624  VD.DFSOut = DomNode->getDFSNumOut();
625  VD.PInfo = PossibleCopy;
626  OrderedUses.push_back(VD);
627  }
628  }
629  }
630  }
631 
632  convertUsesToDFSOrdered(Op, OrderedUses);
633  // Here we require a stable sort because we do not bother to try to
634  // assign an order to the operands the uses represent. Thus, two
635  // uses in the same instruction do not have a strict sort order
636  // currently and will be considered equal. We could get rid of the
637  // stable sort by creating one if we wanted.
638  llvm::stable_sort(OrderedUses, Compare);
639  SmallVector<ValueDFS, 8> RenameStack;
640  // For each use, sorted into dfs order, push values and replaces uses with
641  // top of stack, which will represent the reaching def.
642  for (auto &VD : OrderedUses) {
643  // We currently do not materialize copy over copy, but we should decide if
644  // we want to.
645  bool PossibleCopy = VD.PInfo != nullptr;
646  if (RenameStack.empty()) {
647  LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
648  } else {
649  LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
650  << RenameStack.back().DFSIn << ","
651  << RenameStack.back().DFSOut << ")\n");
652  }
653 
654  LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
655  << VD.DFSOut << ")\n");
656 
657  bool ShouldPush = (VD.Def || PossibleCopy);
658  bool OutOfScope = !stackIsInScope(RenameStack, VD);
659  if (OutOfScope || ShouldPush) {
660  // Sync to our current scope.
661  popStackUntilDFSScope(RenameStack, VD);
662  if (ShouldPush) {
663  RenameStack.push_back(VD);
664  }
665  }
666  // If we get to this point, and the stack is empty we must have a use
667  // with no renaming needed, just skip it.
668  if (RenameStack.empty())
669  continue;
670  // Skip values, only want to rename the uses
671  if (VD.Def || PossibleCopy)
672  continue;
673  if (!DebugCounter::shouldExecute(RenameCounter)) {
674  LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
675  continue;
676  }
677  ValueDFS &Result = RenameStack.back();
678 
679  // If the possible copy dominates something, materialize our stack up to
680  // this point. This ensures every comparison that affects our operation
681  // ends up with predicateinfo.
682  if (!Result.Def)
683  Result.Def = materializeStack(Counter, RenameStack, Op);
684 
685  LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
686  << *VD.U->get() << " in " << *(VD.U->getUser())
687  << "\n");
688  assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
689  "Predicateinfo def should have dominated this use");
690  VD.U->set(Result.Def);
691  }
692  }
693 }
694 
695 PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
696  auto OIN = ValueInfoNums.find(Operand);
697  if (OIN == ValueInfoNums.end()) {
698  // This will grow it
699  ValueInfos.resize(ValueInfos.size() + 1);
700  // This will use the new size and give us a 0 based number of the info
701  auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
702  assert(InsertResult.second && "Value info number already existed?");
703  return ValueInfos[InsertResult.first->second];
704  }
705  return ValueInfos[OIN->second];
706 }
707 
708 const PredicateInfo::ValueInfo &
709 PredicateInfo::getValueInfo(Value *Operand) const {
710  auto OINI = ValueInfoNums.lookup(Operand);
711  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
712  assert(OINI < ValueInfos.size() &&
713  "Value Info Number greater than size of Value Info Table");
714  return ValueInfos[OINI];
715 }
716 
718  AssumptionCache &AC)
719  : F(F), DT(DT), AC(AC), OI(&DT) {
720  // Push an empty operand info so that we can detect 0 as not finding one
721  ValueInfos.resize(1);
722  buildPredicateInfo();
723 }
724 
725 // Remove all declarations we created . The PredicateInfo consumers are
726 // responsible for remove the ssa_copy calls created.
728  // Collect function pointers in set first, as SmallSet uses a SmallVector
729  // internally and we have to remove the asserting value handles first.
730  SmallPtrSet<Function *, 20> FunctionPtrs;
731  for (auto &F : CreatedDeclarations)
732  FunctionPtrs.insert(&*F);
733  CreatedDeclarations.clear();
734 
735  for (Function *F : FunctionPtrs) {
736  assert(F->user_begin() == F->user_end() &&
737  "PredicateInfo consumer did not remove all SSA copies.");
738  F->eraseFromParent();
739  }
740 }
741 
743 
745 
747  : FunctionPass(ID) {
750 }
751 
753  AU.setPreservesAll();
756 }
757 
758 // Replace ssa_copy calls created by PredicateInfo with their operand.
759 static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
760  for (auto I = inst_begin(F), E = inst_end(F); I != E;) {
761  Instruction *Inst = &*I++;
762  const auto *PI = PredInfo.getPredicateInfoFor(Inst);
763  auto *II = dyn_cast<IntrinsicInst>(Inst);
764  if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy)
765  continue;
766 
767  Inst->replaceAllUsesWith(II->getOperand(0));
768  Inst->eraseFromParent();
769  }
770 }
771 
773  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
774  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
775  auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
776  PredInfo->print(dbgs());
778  PredInfo->verifyPredicateInfo();
779 
780  replaceCreatedSSACopys(*PredInfo, F);
781  return false;
782 }
783 
786  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
787  auto &AC = AM.getResult<AssumptionAnalysis>(F);
788  OS << "PredicateInfo for function: " << F.getName() << "\n";
789  auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
790  PredInfo->print(OS);
791 
792  replaceCreatedSSACopys(*PredInfo, F);
793  return PreservedAnalyses::all();
794 }
795 
796 /// An assembly annotator class to print PredicateInfo information in
797 /// comments.
799  friend class PredicateInfo;
800  const PredicateInfo *PredInfo;
801 
802 public:
803  PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
804 
805  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
806  formatted_raw_ostream &OS) {}
807 
808  virtual void emitInstructionAnnot(const Instruction *I,
809  formatted_raw_ostream &OS) {
810  if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
811  OS << "; Has predicate info\n";
812  if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
813  OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
814  << " Comparison:" << *PB->Condition << " Edge: [";
815  PB->From->printAsOperand(OS);
816  OS << ",";
817  PB->To->printAsOperand(OS);
818  OS << "] }\n";
819  } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
820  OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
821  << " Switch:" << *PS->Switch << " Edge: [";
822  PS->From->printAsOperand(OS);
823  OS << ",";
824  PS->To->printAsOperand(OS);
825  OS << "] }\n";
826  } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
827  OS << "; assume predicate info {"
828  << " Comparison:" << *PA->Condition << " }\n";
829  }
830  }
831  }
832 };
833 
835  PredicateInfoAnnotatedWriter Writer(this);
836  F.print(OS, &Writer);
837 }
838 
839 void PredicateInfo::dump() const {
840  PredicateInfoAnnotatedWriter Writer(this);
841  F.print(dbgs(), &Writer);
842 }
843 
846  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
847  auto &AC = AM.getResult<AssumptionAnalysis>(F);
848  make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
849 
850  return PreservedAnalyses::all();
851 }
852 }
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:756
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
Safe Stack instrumentation pass
Definition: SafeStack.cpp:907
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:699
iterator_range< use_iterator > uses()
Definition: Value.h:354
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:78
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
bool operator()(const ValueDFS &A, const ValueDFS &B) const
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static Function * getCopyDeclaration(Module *M, Type *Ty)
void verifyPredicateInfo() const
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
Value * getCondition() const
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl< Value *> &CmpOperands)
A cache of @llvm.assume calls within a function.
const std::pair< BasicBlock *, BasicBlock * > getBlockEdge(const ValueDFS &VD) const
BasicBlock * getSuccessor(unsigned i) const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
virtual void emitBasicBlockStartAnnot(const BasicBlock *BB, formatted_raw_ostream &OS)
emitBasicBlockStartAnnot - This may be implemented to emit a string right after the basic block label...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool valueComesBefore(OrderedInstructions &OI, const Value *A, const Value *B)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
This file provides an implementation of debug counters.
PredicateInfoAnnotatedWriter(const PredicateInfo *M)
void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
ppc ctr loops PowerPC CTR Loops Verify
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
print PredicateInfo static false cl::opt< bool > VerifyPredicateInfo("verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass."))
unsigned getNumSuccessors() const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
BasicBlock * getSuccessor(unsigned idx) const
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const
bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
print predicateinfo
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:762
Conditional or Unconditional Branch instruction.
INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo", "PredicateInfo Printer", false, false) INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
bool dfsBefore(const Instruction *, const Instruction *) const
Return true if the first instruction comes before the second in the dominator tree DFS traversal if t...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:709
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
unsigned getDFSNumOut() const
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
static wasm::ValType getType(const TargetRegisterClass *RC)
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
Struct that holds a reference to a particular GUID in a global value summary.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:209
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:50
A function analysis which provides an AssumptionCache.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
Module.h This file contains the declarations for the Module class.
bool isConditional() const
FunctionCallee getOrInsertFunction(StringRef Name, FunctionType *T, AttributeList AttributeList)
Look up the specified function in the module symbol table.
Definition: Module.cpp:143
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:223
static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Encapsulates PredicateInfo, including all data associated with memory accesses.
const PredicateBase * getPredicateInfoFor(const Value *V) const
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:399
print PredicateInfo Printer
iterator begin() const
Definition: SmallPtrSet.h:396
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
static void rename(GlobalValue *GV)
Definition: AutoUpgrade.cpp:33
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2009
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Function.cpp:217
An assembly annotator class to print PredicateInfo information in comments.
AnalysisUsage & addRequiredTransitive()
iterator end() const
Definition: SmallPtrSet.h:401
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:211
iterator_range< df_iterator< T > > depth_first(const T &G)
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
void stable_sort(R &&Range)
Definition: STLExtras.h:1309
LLVM Value Representation.
Definition: Value.h:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
hexagon cext opt
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
A container for analyses that lazily runs them and caches their results.
void print(raw_ostream &) const
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DEBUG_COUNTER(RenameCounter, "predicateinfo-rename", "Controls which variables are renamed with predicateinfo")
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Value * getMiddleDef(const ValueDFS &VD) const
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66
const Instruction * getDefOrUser(const Value *Def, const Use *U) const
virtual void emitInstructionAnnot(const Instruction *I, formatted_raw_ostream &OS)
emitInstructionAnnot - This may be implemented to emit a string right before an instruction is emitte...
void resize(size_type N)
Definition: SmallVector.h:344
user_iterator user_end()
Definition: Value.h:383