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