1 //===- SpeculateAroundPHIs.cpp --------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
11 #include "llvm/ADT/PostOrderIterator.h"
12 #include "llvm/ADT/Sequence.h"
13 #include "llvm/ADT/SetVector.h"
14 #include "llvm/ADT/Statistic.h"
15 #include "llvm/Analysis/TargetTransformInfo.h"
16 #include "llvm/Analysis/ValueTracking.h"
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/IRBuilder.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/IntrinsicInst.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
26 #define DEBUG_TYPE "spec-phis"
28 STATISTIC(NumPHIsSpeculated, "Number of PHI nodes we speculated around");
29 STATISTIC(NumEdgesSplit,
30 "Number of critical edges which were split for speculation");
31 STATISTIC(NumSpeculatedInstructions,
32 "Number of instructions we speculated around the PHI nodes");
33 STATISTIC(NumNewRedundantInstructions,
34 "Number of new, redundant instructions inserted");
36 /// Check wether speculating the users of a PHI node around the PHI
39 /// This checks both that all of the users are safe and also that all of their
40 /// operands are either recursively safe or already available along an incoming
43 /// This routine caches both all the safe nodes explored in `PotentialSpecSet`
44 /// and the chain of nodes that definitively reach any unsafe node in
45 /// `UnsafeSet`. By preserving these between repeated calls to this routine for
46 /// PHIs in the same basic block, the exploration here can be reused. However,
47 /// these caches must no be reused for PHIs in a different basic block as they
48 /// reflect what is available along incoming edges.
50 isSafeToSpeculatePHIUsers(PHINode &PN, DominatorTree &DT,
51 SmallPtrSetImpl<Instruction *> &PotentialSpecSet,
52 SmallPtrSetImpl<Instruction *> &UnsafeSet) {
53 auto *PhiBB = PN.getParent();
54 SmallPtrSet<Instruction *, 4> Visited;
55 SmallVector<std::pair<Instruction *, User::value_op_iterator>, 16> DFSStack;
57 // Walk each user of the PHI node.
58 for (Use &U : PN.uses()) {
59 auto *UI = cast<Instruction>(U.getUser());
61 // Ensure the use post-dominates the PHI node. This ensures that, in the
62 // absence of unwinding, the use will actually be reached.
63 // FIXME: We use a blunt hammer of requiring them to be in the same basic
64 // block. We should consider using actual post-dominance here in the
66 if (UI->getParent() != PhiBB) {
67 DEBUG(dbgs() << " Unsafe: use in a different BB: " << *UI << "\n");
71 // FIXME: This check is much too conservative. We're not going to move these
72 // instructions onto new dynamic paths through the program unless there is
73 // a call instruction between the use and the PHI node. And memory isn't
74 // changing unless there is a store in that same sequence. We should
75 // probably change this to do at least a limited scan of the intervening
76 // instructions and allow handling stores in easily proven safe cases.
77 if (mayBeMemoryDependent(*UI)) {
78 DEBUG(dbgs() << " Unsafe: can't speculate use: " << *UI << "\n");
82 // Now do a depth-first search of everything these users depend on to make
83 // sure they are transitively safe. This is a depth-first search, but we
84 // check nodes in preorder to minimize the amount of checking.
86 DFSStack.push_back({UI, UI->value_op_begin()});
88 User::value_op_iterator OpIt;
89 std::tie(UI, OpIt) = DFSStack.pop_back_val();
91 while (OpIt != UI->value_op_end()) {
92 auto *OpI = dyn_cast<Instruction>(*OpIt);
93 // Increment to the next operand for whenever we continue.
95 // No need to visit non-instructions, which can't form dependencies.
99 // Now do the main pre-order checks that this operand is a viable
100 // dependency of something we want to speculate.
102 // First do a few checks for instructions that won't require
103 // speculation at all because they are trivially available on the
104 // incoming edge (either through dominance or through an incoming value
107 // The cases in the current block will be trivially dominated by the
109 auto *ParentBB = OpI->getParent();
110 if (ParentBB == PhiBB) {
111 if (isa<PHINode>(OpI)) {
112 // We can trivially map through phi nodes in the same block.
115 } else if (DT.dominates(ParentBB, PhiBB)) {
116 // Instructions from dominating blocks are already available.
120 // Once we know that we're considering speculating the operand, check
121 // if we've already explored this subgraph and found it to be safe.
122 if (PotentialSpecSet.count(OpI))
125 // If we've already explored this subgraph and found it unsafe, bail.
126 // If when we directly test whether this is safe it fails, bail.
127 if (UnsafeSet.count(OpI) || ParentBB != PhiBB ||
128 mayBeMemoryDependent(*OpI)) {
129 DEBUG(dbgs() << " Unsafe: can't speculate transitive use: " << *OpI
131 // Record the stack of instructions which reach this node as unsafe
132 // so we prune subsequent searches.
133 UnsafeSet.insert(OpI);
134 for (auto &StackPair : DFSStack) {
135 Instruction *I = StackPair.first;
141 // Skip any operands we're already recursively checking.
142 if (!Visited.insert(OpI).second)
145 // Push onto the stack and descend. We can directly continue this
146 // loop when ascending.
147 DFSStack.push_back({UI, OpIt});
149 OpIt = OpI->value_op_begin();
152 // This node and all its operands are safe. Go ahead and cache that for
154 PotentialSpecSet.insert(UI);
156 // Continue with the next node on the stack.
157 } while (!DFSStack.empty());
161 // Every visited operand should have been marked as safe for speculation at
162 // this point. Verify this and return success.
163 for (auto *I : Visited)
164 assert(PotentialSpecSet.count(I) &&
165 "Failed to mark a visited instruction as safe!");
170 /// Check whether, in isolation, a given PHI node is both safe and profitable
171 /// to speculate users around.
173 /// This handles checking whether there are any constant operands to a PHI
174 /// which could represent a useful speculation candidate, whether the users of
175 /// the PHI are safe to speculate including all their transitive dependencies,
176 /// and whether after speculation there will be some cost savings (profit) to
177 /// folding the operands into the users of the PHI node. Returns true if both
178 /// safe and profitable with relevant cost savings updated in the map and with
179 /// an update to the `PotentialSpecSet`. Returns false if either safety or
180 /// profitability are absent. Some new entries may be made to the
181 /// `PotentialSpecSet` even when this routine returns false, but they remain
182 /// conservatively correct.
184 /// The profitability check here is a local one, but it checks this in an
185 /// interesting way. Beyond checking that the total cost of materializing the
186 /// constants will be less than the cost of folding them into their users, it
187 /// also checks that no one incoming constant will have a higher cost when
188 /// folded into its users rather than materialized. This higher cost could
189 /// result in a dynamic *path* that is more expensive even when the total cost
190 /// is lower. Currently, all of the interesting cases where this optimization
191 /// should fire are ones where it is a no-loss operation in this sense. If we
192 /// ever want to be more aggressive here, we would need to balance the
193 /// different incoming edges' cost by looking at their respective
195 static bool isSafeAndProfitableToSpeculateAroundPHI(
196 PHINode &PN, SmallDenseMap<PHINode *, int, 16> &CostSavingsMap,
197 SmallPtrSetImpl<Instruction *> &PotentialSpecSet,
198 SmallPtrSetImpl<Instruction *> &UnsafeSet, DominatorTree &DT,
199 TargetTransformInfo &TTI) {
200 // First see whether there is any cost savings to speculating around this
201 // PHI, and build up a map of the constant inputs to how many times they
203 bool NonFreeMat = false;
204 struct CostsAndCount {
205 int MatCost = TargetTransformInfo::TCC_Free;
206 int FoldedCost = TargetTransformInfo::TCC_Free;
209 SmallDenseMap<ConstantInt *, CostsAndCount, 16> CostsAndCounts;
210 SmallPtrSet<BasicBlock *, 16> IncomingConstantBlocks;
211 for (int i : llvm::seq<int>(0, PN.getNumIncomingValues())) {
212 auto *IncomingC = dyn_cast<ConstantInt>(PN.getIncomingValue(i));
216 // Only visit each incoming edge with a constant input once.
217 if (!IncomingConstantBlocks.insert(PN.getIncomingBlock(i)).second)
220 auto InsertResult = CostsAndCounts.insert({IncomingC, {}});
221 // Count how many edges share a given incoming costant.
222 ++InsertResult.first->second.Count;
223 // Only compute the cost the first time we see a particular constant.
224 if (!InsertResult.second)
227 int &MatCost = InsertResult.first->second.MatCost;
228 MatCost = TTI.getIntImmCost(IncomingC->getValue(), IncomingC->getType());
229 NonFreeMat |= MatCost != TTI.TCC_Free;
232 DEBUG(dbgs() << " Free: " << PN << "\n");
233 // No profit in free materialization.
237 // Now check that the uses of this PHI can actually be speculated,
238 // otherwise we'll still have to materialize the PHI value.
239 if (!isSafeToSpeculatePHIUsers(PN, DT, PotentialSpecSet, UnsafeSet)) {
240 DEBUG(dbgs() << " Unsafe PHI: " << PN << "\n");
244 // Compute how much (if any) savings are available by speculating around this
246 for (Use &U : PN.uses()) {
247 auto *UserI = cast<Instruction>(U.getUser());
248 // Now check whether there is any savings to folding the incoming constants
250 unsigned Idx = U.getOperandNo();
252 // If we have a binary operator that is commutative, an actual constant
253 // operand would end up on the RHS, so pretend the use of the PHI is on the
256 // Technically, this is a bit weird if *both* operands are PHIs we're
257 // speculating. But if that is the case, giving an "optimistic" cost isn't
258 // a bad thing because after speculation it will constant fold. And
259 // moreover, such cases should likely have been constant folded already by
260 // some other pass, so we shouldn't worry about "modeling" them terribly
261 // accurately here. Similarly, if the other operand is a constant, it still
262 // seems fine to be "optimistic" in our cost modeling, because when the
263 // incoming operand from the PHI node is also a constant, we will end up
265 if (UserI->isBinaryOp() && UserI->isCommutative() && Idx != 1)
266 // Assume we will commute the constant to the RHS to be canonical.
269 // Get the intrinsic ID if this user is an instrinsic.
270 Intrinsic::ID IID = Intrinsic::not_intrinsic;
271 if (auto *UserII = dyn_cast<IntrinsicInst>(UserI))
272 IID = UserII->getIntrinsicID();
274 for (auto &IncomingConstantAndCostsAndCount : CostsAndCounts) {
275 ConstantInt *IncomingC = IncomingConstantAndCostsAndCount.first;
276 int MatCost = IncomingConstantAndCostsAndCount.second.MatCost;
277 int &FoldedCost = IncomingConstantAndCostsAndCount.second.FoldedCost;
279 FoldedCost += TTI.getIntImmCost(IID, Idx, IncomingC->getValue(),
280 IncomingC->getType());
283 TTI.getIntImmCost(UserI->getOpcode(), Idx, IncomingC->getValue(),
284 IncomingC->getType());
286 // If we accumulate more folded cost for this incoming constant than
287 // materialized cost, then we'll regress any edge with this constant so
288 // just bail. We're only interested in cases where folding the incoming
289 // constants is at least break-even on all paths.
290 if (FoldedCost > MatCost) {
291 DEBUG(dbgs() << " Not profitable to fold imm: " << *IncomingC << "\n"
292 " Materializing cost: " << MatCost << "\n"
293 " Accumulated folded cost: " << FoldedCost << "\n");
299 // Compute the total cost savings afforded by this PHI node.
300 int TotalMatCost = TTI.TCC_Free, TotalFoldedCost = TTI.TCC_Free;
301 for (auto IncomingConstantAndCostsAndCount : CostsAndCounts) {
302 int MatCost = IncomingConstantAndCostsAndCount.second.MatCost;
303 int FoldedCost = IncomingConstantAndCostsAndCount.second.FoldedCost;
304 int Count = IncomingConstantAndCostsAndCount.second.Count;
306 TotalMatCost += MatCost * Count;
307 TotalFoldedCost += FoldedCost * Count;
309 assert(TotalFoldedCost <= TotalMatCost && "If each constant's folded cost is "
310 "less that its materialized cost, "
311 "the sum must be as well.");
313 DEBUG(dbgs() << " Cost savings " << (TotalMatCost - TotalFoldedCost)
314 << ": " << PN << "\n");
315 CostSavingsMap[&PN] = TotalMatCost - TotalFoldedCost;
319 /// Simple helper to walk all the users of a list of phis depth first, and call
320 /// a visit function on each one in post-order.
322 /// All of the PHIs should be in the same basic block, and this is primarily
323 /// used to make a single depth-first walk across their collective users
324 /// without revisiting any subgraphs. Callers should provide a fast, idempotent
325 /// callable to test whether a node has been visited and the more important
326 /// callable to actually visit a particular node.
328 /// Depth-first and postorder here refer to the *operand* graph -- we start
329 /// from a collection of users of PHI nodes and walk "up" the operands
331 template <typename IsVisitedT, typename VisitT>
332 static void visitPHIUsersAndDepsInPostOrder(ArrayRef<PHINode *> PNs,
333 IsVisitedT IsVisited,
335 SmallVector<std::pair<Instruction *, User::value_op_iterator>, 16> DFSStack;
337 for (Use &U : PN->uses()) {
338 auto *UI = cast<Instruction>(U.getUser());
340 // Already visited this user, continue across the roots.
343 // Otherwise, walk the operand graph depth-first and visit each
344 // dependency in postorder.
345 DFSStack.push_back({UI, UI->value_op_begin()});
347 User::value_op_iterator OpIt;
348 std::tie(UI, OpIt) = DFSStack.pop_back_val();
349 while (OpIt != UI->value_op_end()) {
350 auto *OpI = dyn_cast<Instruction>(*OpIt);
351 // Increment to the next operand for whenever we continue.
353 // No need to visit non-instructions, which can't form dependencies,
354 // or instructions outside of our potential dependency set that we
355 // were given. Finally, if we've already visited the node, continue
357 if (!OpI || IsVisited(OpI))
360 // Push onto the stack and descend. We can directly continue this
361 // loop when ascending.
362 DFSStack.push_back({UI, OpIt});
364 OpIt = OpI->value_op_begin();
367 // Finished visiting children, visit this node.
368 assert(!IsVisited(UI) && "Should not have already visited a node!");
370 } while (!DFSStack.empty());
374 /// Find profitable PHIs to speculate.
376 /// For a PHI node to be profitable, we need the cost of speculating its users
377 /// (and their dependencies) to not exceed the savings of folding the PHI's
378 /// constant operands into the speculated users.
380 /// Computing this is surprisingly challenging. Because users of two different
381 /// PHI nodes can depend on each other or on common other instructions, it may
382 /// be profitable to speculate two PHI nodes together even though neither one
383 /// in isolation is profitable. The straightforward way to find all the
384 /// profitable PHIs would be to check each combination of PHIs' cost, but this
385 /// is exponential in complexity.
387 /// Even if we assume that we only care about cases where we can consider each
388 /// PHI node in isolation (rather than considering cases where none are
389 /// profitable in isolation but some subset are profitable as a set), we still
390 /// have a challenge. The obvious way to find all individually profitable PHIs
391 /// is to iterate until reaching a fixed point, but this will be quadratic in
394 /// This code currently uses a linear-to-compute order for a greedy approach.
395 /// It won't find cases where a set of PHIs must be considered together, but it
396 /// handles most cases of order dependence without quadratic iteration. The
397 /// specific order used is the post-order across the operand DAG. When the last
398 /// user of a PHI is visited in this postorder walk, we check it for
401 /// There is an orthogonal extra complexity to all of this: computing the cost
402 /// itself can easily become a linear computation making everything again (at
403 /// best) quadratic. Using a postorder over the operand graph makes it
404 /// particularly easy to avoid this through dynamic programming. As we do the
405 /// postorder walk, we build the transitive cost of that subgraph. It is also
406 /// straightforward to then update these costs when we mark a PHI for
407 /// speculation so that subsequent PHIs don't re-pay the cost of already
408 /// speculated instructions.
409 static SmallVector<PHINode *, 16>
410 findProfitablePHIs(ArrayRef<PHINode *> PNs,
411 const SmallDenseMap<PHINode *, int, 16> &CostSavingsMap,
412 const SmallPtrSetImpl<Instruction *> &PotentialSpecSet,
413 int NumPreds, DominatorTree &DT, TargetTransformInfo &TTI) {
414 SmallVector<PHINode *, 16> SpecPNs;
416 // First, establish a reverse mapping from immediate users of the PHI nodes
417 // to the nodes themselves, and count how many users each PHI node has in
418 // a way we can update while processing them.
419 SmallDenseMap<Instruction *, TinyPtrVector<PHINode *>, 16> UserToPNMap;
420 SmallDenseMap<PHINode *, int, 16> PNUserCountMap;
421 SmallPtrSet<Instruction *, 16> UserSet;
422 for (auto *PN : PNs) {
423 assert(UserSet.empty() && "Must start with an empty user set!");
424 for (Use &U : PN->uses())
425 UserSet.insert(cast<Instruction>(U.getUser()));
426 PNUserCountMap[PN] = UserSet.size();
427 for (auto *UI : UserSet)
428 UserToPNMap.insert({UI, {}}).first->second.push_back(PN);
432 // Now do a DFS across the operand graph of the users, computing cost as we
433 // go and when all costs for a given PHI are known, checking that PHI for
435 SmallDenseMap<Instruction *, int, 16> SpecCostMap;
436 visitPHIUsersAndDepsInPostOrder(
439 [&](Instruction *I) {
440 // We consider anything that isn't potentially speculated to be
441 // "visited" as it is already handled. Similarly, anything that *is*
442 // potentially speculated but for which we have an entry in our cost
444 return !PotentialSpecSet.count(I) || SpecCostMap.count(I);
447 [&](Instruction *I) {
448 // We've fully visited the operands, so sum their cost with this node
449 // and update the cost map.
450 int Cost = TTI.TCC_Free;
451 for (Value *OpV : I->operand_values())
452 if (auto *OpI = dyn_cast<Instruction>(OpV)) {
453 auto CostMapIt = SpecCostMap.find(OpI);
454 if (CostMapIt != SpecCostMap.end())
455 Cost += CostMapIt->second;
457 Cost += TTI.getUserCost(I);
458 bool Inserted = SpecCostMap.insert({I, Cost}).second;
460 assert(Inserted && "Must not re-insert a cost during the DFS!");
462 // Now check if this node had a corresponding PHI node using it. If so,
463 // we need to decrement the outstanding user count for it.
464 auto UserPNsIt = UserToPNMap.find(I);
465 if (UserPNsIt == UserToPNMap.end())
467 auto &UserPNs = UserPNsIt->second;
468 auto UserPNsSplitIt = std::stable_partition(
469 UserPNs.begin(), UserPNs.end(), [&](PHINode *UserPN) {
470 int &PNUserCount = PNUserCountMap.find(UserPN)->second;
473 "Should never re-visit a PN after its user count hits zero!");
475 return PNUserCount != 0;
478 // FIXME: Rather than one at a time, we should sum the savings as the
479 // cost will be completely shared.
480 SmallVector<Instruction *, 16> SpecWorklist;
481 for (auto *PN : llvm::make_range(UserPNsSplitIt, UserPNs.end())) {
482 int SpecCost = TTI.TCC_Free;
483 for (Use &U : PN->uses())
485 SpecCostMap.find(cast<Instruction>(U.getUser()))->second;
486 SpecCost *= (NumPreds - 1);
487 // When the user count of a PHI node hits zero, we should check its
488 // profitability. If profitable, we should mark it for speculation
489 // and zero out the cost of everything it depends on.
490 int CostSavings = CostSavingsMap.find(PN)->second;
491 if (SpecCost > CostSavings) {
492 DEBUG(dbgs() << " Not profitable, speculation cost: " << *PN << "\n"
493 " Cost savings: " << CostSavings << "\n"
494 " Speculation cost: " << SpecCost << "\n");
498 // We're going to speculate this user-associated PHI. Copy it out and
499 // add its users to the worklist to update their cost.
500 SpecPNs.push_back(PN);
501 for (Use &U : PN->uses()) {
502 auto *UI = cast<Instruction>(U.getUser());
503 auto CostMapIt = SpecCostMap.find(UI);
504 if (CostMapIt->second == 0)
506 // Zero out this cost entry to avoid duplicates.
507 CostMapIt->second = 0;
508 SpecWorklist.push_back(UI);
512 // Now walk all the operands of the users in the worklist transitively
513 // to zero out all the memoized costs.
514 while (!SpecWorklist.empty()) {
515 Instruction *SpecI = SpecWorklist.pop_back_val();
516 assert(SpecCostMap.find(SpecI)->second == 0 &&
517 "Didn't zero out a cost!");
519 // Walk the operands recursively to zero out their cost as well.
520 for (auto *OpV : SpecI->operand_values()) {
521 auto *OpI = dyn_cast<Instruction>(OpV);
524 auto CostMapIt = SpecCostMap.find(OpI);
525 if (CostMapIt == SpecCostMap.end() || CostMapIt->second == 0)
527 CostMapIt->second = 0;
528 SpecWorklist.push_back(OpI);
536 /// Speculate users around a set of PHI nodes.
538 /// This routine does the actual speculation around a set of PHI nodes where we
539 /// have determined this to be both safe and profitable.
541 /// This routine handles any spliting of critical edges necessary to create
542 /// a safe block to speculate into as well as cloning the instructions and
543 /// rewriting all uses.
544 static void speculatePHIs(ArrayRef<PHINode *> SpecPNs,
545 SmallPtrSetImpl<Instruction *> &PotentialSpecSet,
546 SmallSetVector<BasicBlock *, 16> &PredSet,
548 DEBUG(dbgs() << " Speculating around " << SpecPNs.size() << " PHIs!\n");
549 NumPHIsSpeculated += SpecPNs.size();
551 // Split any critical edges so that we have a block to hoist into.
552 auto *ParentBB = SpecPNs[0]->getParent();
553 SmallVector<BasicBlock *, 16> SpecPreds;
554 SpecPreds.reserve(PredSet.size());
555 for (auto *PredBB : PredSet) {
556 auto *NewPredBB = SplitCriticalEdge(
558 CriticalEdgeSplittingOptions(&DT).setMergeIdenticalEdges());
561 DEBUG(dbgs() << " Split critical edge from: " << PredBB->getName()
563 SpecPreds.push_back(NewPredBB);
565 assert(PredBB->getSingleSuccessor() == ParentBB &&
566 "We need a non-critical predecessor to speculate into.");
567 assert(!isa<InvokeInst>(PredBB->getTerminator()) &&
568 "Cannot have a non-critical invoke!");
570 // Already non-critical, use existing pred.
571 SpecPreds.push_back(PredBB);
575 SmallPtrSet<Instruction *, 16> SpecSet;
576 SmallVector<Instruction *, 16> SpecList;
577 visitPHIUsersAndDepsInPostOrder(SpecPNs,
579 [&](Instruction *I) {
580 // This is visited if we don't need to
581 // speculate it or we already have
583 return !PotentialSpecSet.count(I) ||
587 [&](Instruction *I) {
588 // All operands scheduled, schedule this
591 SpecList.push_back(I);
594 int NumSpecInsts = SpecList.size() * SpecPreds.size();
595 int NumRedundantInsts = NumSpecInsts - SpecList.size();
596 DEBUG(dbgs() << " Inserting " << NumSpecInsts << " speculated instructions, "
597 << NumRedundantInsts << " redundancies\n");
598 NumSpeculatedInstructions += NumSpecInsts;
599 NumNewRedundantInstructions += NumRedundantInsts;
601 // Each predecessor is numbered by its index in `SpecPreds`, so for each
602 // instruction we speculate, the speculated instruction is stored in that
603 // index of the vector asosciated with the original instruction. We also
604 // store the incoming values for each predecessor from any PHIs used.
605 SmallDenseMap<Instruction *, SmallVector<Value *, 2>, 16> SpeculatedValueMap;
607 // Inject the synthetic mappings to rewrite PHIs to the appropriate incoming
608 // value. This handles both the PHIs we are speculating around and any other
609 // PHIs that happen to be used.
610 for (auto *OrigI : SpecList)
611 for (auto *OpV : OrigI->operand_values()) {
612 auto *OpPN = dyn_cast<PHINode>(OpV);
613 if (!OpPN || OpPN->getParent() != ParentBB)
616 auto InsertResult = SpeculatedValueMap.insert({OpPN, {}});
617 if (!InsertResult.second)
620 auto &SpeculatedVals = InsertResult.first->second;
622 // Populating our structure for mapping is particularly annoying because
623 // finding an incoming value for a particular predecessor block in a PHI
624 // node is a linear time operation! To avoid quadratic behavior, we build
625 // a map for this PHI node's incoming values and then translate it into
626 // the more compact representation used below.
627 SmallDenseMap<BasicBlock *, Value *, 16> IncomingValueMap;
628 for (int i : llvm::seq<int>(0, OpPN->getNumIncomingValues()))
629 IncomingValueMap[OpPN->getIncomingBlock(i)] = OpPN->getIncomingValue(i);
631 for (auto *PredBB : SpecPreds)
632 SpeculatedVals.push_back(IncomingValueMap.find(PredBB)->second);
635 // Speculate into each predecessor.
636 for (int PredIdx : llvm::seq<int>(0, SpecPreds.size())) {
637 auto *PredBB = SpecPreds[PredIdx];
638 assert(PredBB->getSingleSuccessor() == ParentBB &&
639 "We need a non-critical predecessor to speculate into.");
641 for (auto *OrigI : SpecList) {
642 auto *NewI = OrigI->clone();
643 NewI->setName(Twine(OrigI->getName()) + "." + Twine(PredIdx));
644 NewI->insertBefore(PredBB->getTerminator());
646 // Rewrite all the operands to the previously speculated instructions.
647 // Because we're walking in-order, the defs must precede the uses and we
648 // should already have these mappings.
649 for (Use &U : NewI->operands()) {
650 auto *OpI = dyn_cast<Instruction>(U.get());
653 auto MapIt = SpeculatedValueMap.find(OpI);
654 if (MapIt == SpeculatedValueMap.end())
656 const auto &SpeculatedVals = MapIt->second;
657 assert(SpeculatedVals[PredIdx] &&
658 "Must have a speculated value for this predecessor!");
659 assert(SpeculatedVals[PredIdx]->getType() == OpI->getType() &&
660 "Speculated value has the wrong type!");
662 // Rewrite the use to this predecessor's speculated instruction.
663 U.set(SpeculatedVals[PredIdx]);
666 // Commute instructions which now have a constant in the LHS but not the
668 if (NewI->isBinaryOp() && NewI->isCommutative() &&
669 isa<Constant>(NewI->getOperand(0)) &&
670 !isa<Constant>(NewI->getOperand(1)))
671 NewI->getOperandUse(0).swap(NewI->getOperandUse(1));
673 SpeculatedValueMap[OrigI].push_back(NewI);
674 assert(SpeculatedValueMap[OrigI][PredIdx] == NewI &&
675 "Mismatched speculated instruction index!");
679 // Walk the speculated instruction list and if they have uses, insert a PHI
680 // for them from the speculated versions, and replace the uses with the PHI.
681 // Then erase the instructions as they have been fully speculated. The walk
682 // needs to be in reverse so that we don't think there are users when we'll
683 // actually eventually remove them later.
684 IRBuilder<> IRB(SpecPNs[0]);
685 for (auto *OrigI : llvm::reverse(SpecList)) {
686 // Check if we need a PHI for any remaining users and if so, insert it.
687 if (!OrigI->use_empty()) {
688 auto *SpecIPN = IRB.CreatePHI(OrigI->getType(), SpecPreds.size(),
689 Twine(OrigI->getName()) + ".phi");
690 // Add the incoming values we speculated.
691 auto &SpeculatedVals = SpeculatedValueMap.find(OrigI)->second;
692 for (int PredIdx : llvm::seq<int>(0, SpecPreds.size()))
693 SpecIPN->addIncoming(SpeculatedVals[PredIdx], SpecPreds[PredIdx]);
695 // And replace the uses with the PHI node.
696 OrigI->replaceAllUsesWith(SpecIPN);
699 // It is important to immediately erase this so that it stops using other
700 // instructions. This avoids inserting needless PHIs of them.
701 OrigI->eraseFromParent();
704 // All of the uses of the speculated phi nodes should be removed at this
705 // point, so erase them.
706 for (auto *SpecPN : SpecPNs) {
707 assert(SpecPN->use_empty() && "All users should have been speculated!");
708 SpecPN->eraseFromParent();
712 /// Try to speculate around a series of PHIs from a single basic block.
714 /// This routine checks whether any of these PHIs are profitable to speculate
715 /// users around. If safe and profitable, it does the speculation. It returns
716 /// true when at least some speculation occurs.
717 static bool tryToSpeculatePHIs(SmallVectorImpl<PHINode *> &PNs,
718 DominatorTree &DT, TargetTransformInfo &TTI) {
719 DEBUG(dbgs() << "Evaluating phi nodes for speculation:\n");
721 // Savings in cost from speculating around a PHI node.
722 SmallDenseMap<PHINode *, int, 16> CostSavingsMap;
724 // Remember the set of instructions that are candidates for speculation so
725 // that we can quickly walk things within that space. This prunes out
726 // instructions already available along edges, etc.
727 SmallPtrSet<Instruction *, 16> PotentialSpecSet;
729 // Remember the set of instructions that are (transitively) unsafe to
730 // speculate into the incoming edges of this basic block. This avoids
731 // recomputing them for each PHI node we check. This set is specific to this
732 // block though as things are pruned out of it based on what is available
733 // along incoming edges.
734 SmallPtrSet<Instruction *, 16> UnsafeSet;
736 // For each PHI node in this block, check whether there are immediate folding
737 // opportunities from speculation, and whether that speculation will be
738 // valid. This determise the set of safe PHIs to speculate.
739 PNs.erase(llvm::remove_if(PNs,
741 return !isSafeAndProfitableToSpeculateAroundPHI(
742 *PN, CostSavingsMap, PotentialSpecSet,
746 // If no PHIs were profitable, skip.
748 DEBUG(dbgs() << " No safe and profitable PHIs found!\n");
752 // We need to know how much speculation will cost which is determined by how
753 // many incoming edges will need a copy of each speculated instruction.
754 SmallSetVector<BasicBlock *, 16> PredSet;
755 for (auto *PredBB : PNs[0]->blocks()) {
756 if (!PredSet.insert(PredBB))
759 // We cannot speculate when a predecessor is an indirect branch.
760 // FIXME: We also can't reliably create a non-critical edge block for
761 // speculation if the predecessor is an invoke. This doesn't seem
762 // fundamental and we should probably be splitting critical edges
764 if (isa<IndirectBrInst>(PredBB->getTerminator()) ||
765 isa<InvokeInst>(PredBB->getTerminator())) {
766 DEBUG(dbgs() << " Invalid: predecessor terminator: " << PredBB->getName()
771 if (PredSet.size() < 2) {
772 DEBUG(dbgs() << " Unimportant: phi with only one predecessor\n");
776 SmallVector<PHINode *, 16> SpecPNs = findProfitablePHIs(
777 PNs, CostSavingsMap, PotentialSpecSet, PredSet.size(), DT, TTI);
782 speculatePHIs(SpecPNs, PotentialSpecSet, PredSet, DT);
786 PreservedAnalyses SpeculateAroundPHIsPass::run(Function &F,
787 FunctionAnalysisManager &AM) {
788 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
789 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
791 bool Changed = false;
792 for (auto *BB : ReversePostOrderTraversal<Function *>(&F)) {
793 SmallVector<PHINode *, 16> PNs;
794 auto BBI = BB->begin();
795 while (auto *PN = dyn_cast<PHINode>(&*BBI)) {
803 Changed |= tryToSpeculatePHIs(PNs, DT, TTI);
807 return PreservedAnalyses::all();
809 PreservedAnalyses PA;