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