LLVM 19.0.0git
JumpThreading.cpp
Go to the documentation of this file.
1//===- JumpThreading.cpp - Thread control through conditional blocks ------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the Jump Threading pass.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/CFG.h"
30#include "llvm/Analysis/Loads.h"
37#include "llvm/IR/BasicBlock.h"
38#include "llvm/IR/CFG.h"
39#include "llvm/IR/Constant.h"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/DebugInfo.h"
44#include "llvm/IR/Dominators.h"
45#include "llvm/IR/Function.h"
46#include "llvm/IR/InstrTypes.h"
47#include "llvm/IR/Instruction.h"
50#include "llvm/IR/Intrinsics.h"
51#include "llvm/IR/LLVMContext.h"
52#include "llvm/IR/MDBuilder.h"
53#include "llvm/IR/Metadata.h"
54#include "llvm/IR/Module.h"
55#include "llvm/IR/PassManager.h"
58#include "llvm/IR/Type.h"
59#include "llvm/IR/Use.h"
60#include "llvm/IR/Value.h"
65#include "llvm/Support/Debug.h"
72#include <algorithm>
73#include <cassert>
74#include <cstdint>
75#include <iterator>
76#include <memory>
77#include <utility>
78
79using namespace llvm;
80using namespace jumpthreading;
81
82#define DEBUG_TYPE "jump-threading"
83
84STATISTIC(NumThreads, "Number of jumps threaded");
85STATISTIC(NumFolds, "Number of terminators folded");
86STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi");
87
89BBDuplicateThreshold("jump-threading-threshold",
90 cl::desc("Max block size to duplicate for jump threading"),
92
95 "jump-threading-implication-search-threshold",
96 cl::desc("The number of predecessors to search for a stronger "
97 "condition to use to thread over a weaker condition"),
99
101 "jump-threading-phi-threshold",
102 cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76),
103 cl::Hidden);
104
106 "jump-threading-across-loop-headers",
107 cl::desc("Allow JumpThreading to thread across loop headers, for testing"),
108 cl::init(false), cl::Hidden);
109
111 DefaultBBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);
112}
113
114// Update branch probability information according to conditional
115// branch probability. This is usually made possible for cloned branches
116// in inline instances by the context specific profile in the caller.
117// For instance,
118//
119// [Block PredBB]
120// [Branch PredBr]
121// if (t) {
122// Block A;
123// } else {
124// Block B;
125// }
126//
127// [Block BB]
128// cond = PN([true, %A], [..., %B]); // PHI node
129// [Branch CondBr]
130// if (cond) {
131// ... // P(cond == true) = 1%
132// }
133//
134// Here we know that when block A is taken, cond must be true, which means
135// P(cond == true | A) = 1
136//
137// Given that P(cond == true) = P(cond == true | A) * P(A) +
138// P(cond == true | B) * P(B)
139// we get:
140// P(cond == true ) = P(A) + P(cond == true | B) * P(B)
141//
142// which gives us:
143// P(A) is less than P(cond == true), i.e.
144// P(t == true) <= P(cond == true)
145//
146// In other words, if we know P(cond == true) is unlikely, we know
147// that P(t == true) is also unlikely.
148//
150 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
151 if (!CondBr)
152 return;
153
154 uint64_t TrueWeight, FalseWeight;
155 if (!extractBranchWeights(*CondBr, TrueWeight, FalseWeight))
156 return;
157
158 if (TrueWeight + FalseWeight == 0)
159 // Zero branch_weights do not give a hint for getting branch probabilities.
160 // Technically it would result in division by zero denominator, which is
161 // TrueWeight + FalseWeight.
162 return;
163
164 // Returns the outgoing edge of the dominating predecessor block
165 // that leads to the PhiNode's incoming block:
166 auto GetPredOutEdge =
167 [](BasicBlock *IncomingBB,
168 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
169 auto *PredBB = IncomingBB;
170 auto *SuccBB = PhiBB;
172 while (true) {
173 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
174 if (PredBr && PredBr->isConditional())
175 return {PredBB, SuccBB};
176 Visited.insert(PredBB);
177 auto *SinglePredBB = PredBB->getSinglePredecessor();
178 if (!SinglePredBB)
179 return {nullptr, nullptr};
180
181 // Stop searching when SinglePredBB has been visited. It means we see
182 // an unreachable loop.
183 if (Visited.count(SinglePredBB))
184 return {nullptr, nullptr};
185
186 SuccBB = PredBB;
187 PredBB = SinglePredBB;
188 }
189 };
190
191 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
192 Value *PhiOpnd = PN->getIncomingValue(i);
193 ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
194
195 if (!CI || !CI->getType()->isIntegerTy(1))
196 continue;
197
200 TrueWeight, TrueWeight + FalseWeight)
202 FalseWeight, TrueWeight + FalseWeight));
203
204 auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB);
205 if (!PredOutEdge.first)
206 return;
207
208 BasicBlock *PredBB = PredOutEdge.first;
209 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
210 if (!PredBr)
211 return;
212
213 uint64_t PredTrueWeight, PredFalseWeight;
214 // FIXME: We currently only set the profile data when it is missing.
215 // With PGO, this can be used to refine even existing profile data with
216 // context information. This needs to be done after more performance
217 // testing.
218 if (extractBranchWeights(*PredBr, PredTrueWeight, PredFalseWeight))
219 continue;
220
221 // We can not infer anything useful when BP >= 50%, because BP is the
222 // upper bound probability value.
223 if (BP >= BranchProbability(50, 100))
224 continue;
225
226 uint32_t Weights[2];
227 if (PredBr->getSuccessor(0) == PredOutEdge.second) {
228 Weights[0] = BP.getNumerator();
229 Weights[1] = BP.getCompl().getNumerator();
230 } else {
231 Weights[0] = BP.getCompl().getNumerator();
232 Weights[1] = BP.getNumerator();
233 }
234 setBranchWeights(*PredBr, Weights, hasBranchWeightOrigin(*PredBr));
235 }
236}
237
240 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
241 // Jump Threading has no sense for the targets with divergent CF
243 return PreservedAnalyses::all();
244 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
245 auto &LVI = AM.getResult<LazyValueAnalysis>(F);
246 auto &AA = AM.getResult<AAManager>(F);
247 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
248
249 bool Changed =
250 runImpl(F, &AM, &TLI, &TTI, &LVI, &AA,
251 std::make_unique<DomTreeUpdater>(
253 std::nullopt, std::nullopt);
254
255 if (!Changed)
256 return PreservedAnalyses::all();
257
258
260
261#if defined(EXPENSIVE_CHECKS)
262 assert(getDomTreeUpdater()->getDomTree().verify(
263 DominatorTree::VerificationLevel::Full) &&
264 "DT broken after JumpThreading");
265 assert((!getDomTreeUpdater()->hasPostDomTree() ||
266 getDomTreeUpdater()->getPostDomTree().verify(
268 "PDT broken after JumpThreading");
269#else
270 assert(getDomTreeUpdater()->getDomTree().verify(
271 DominatorTree::VerificationLevel::Fast) &&
272 "DT broken after JumpThreading");
273 assert((!getDomTreeUpdater()->hasPostDomTree() ||
274 getDomTreeUpdater()->getPostDomTree().verify(
276 "PDT broken after JumpThreading");
277#endif
278
279 return getPreservedAnalysis();
280}
281
283 TargetLibraryInfo *TLI_,
285 AliasAnalysis *AA_,
286 std::unique_ptr<DomTreeUpdater> DTU_,
287 std::optional<BlockFrequencyInfo *> BFI_,
288 std::optional<BranchProbabilityInfo *> BPI_) {
289 LLVM_DEBUG(dbgs() << "Jump threading on function '" << F_.getName() << "'\n");
290 F = &F_;
291 FAM = FAM_;
292 TLI = TLI_;
293 TTI = TTI_;
294 LVI = LVI_;
295 AA = AA_;
296 DTU = std::move(DTU_);
297 BFI = BFI_;
298 BPI = BPI_;
299 auto *GuardDecl = F->getParent()->getFunction(
300 Intrinsic::getName(Intrinsic::experimental_guard));
301 HasGuards = GuardDecl && !GuardDecl->use_empty();
302
303 // Reduce the number of instructions duplicated when optimizing strictly for
304 // size.
305 if (BBDuplicateThreshold.getNumOccurrences())
306 BBDupThreshold = BBDuplicateThreshold;
307 else if (F->hasFnAttribute(Attribute::MinSize))
308 BBDupThreshold = 3;
309 else
310 BBDupThreshold = DefaultBBDupThreshold;
311
312 // JumpThreading must not processes blocks unreachable from entry. It's a
313 // waste of compute time and can potentially lead to hangs.
315 assert(DTU && "DTU isn't passed into JumpThreading before using it.");
316 assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
317 DominatorTree &DT = DTU->getDomTree();
318 for (auto &BB : *F)
319 if (!DT.isReachableFromEntry(&BB))
320 Unreachable.insert(&BB);
321
324
325 bool EverChanged = false;
326 bool Changed;
327 do {
328 Changed = false;
329 for (auto &BB : *F) {
330 if (Unreachable.count(&BB))
331 continue;
332 while (processBlock(&BB)) // Thread all of the branches we can over BB.
333 Changed = ChangedSinceLastAnalysisUpdate = true;
334
335 // Jump threading may have introduced redundant debug values into BB
336 // which should be removed.
337 if (Changed)
339
340 // Stop processing BB if it's the entry or is now deleted. The following
341 // routines attempt to eliminate BB and locating a suitable replacement
342 // for the entry is non-trivial.
343 if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
344 continue;
345
346 if (pred_empty(&BB)) {
347 // When processBlock makes BB unreachable it doesn't bother to fix up
348 // the instructions in it. We must remove BB to prevent invalid IR.
349 LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName()
350 << "' with terminator: " << *BB.getTerminator()
351 << '\n');
352 LoopHeaders.erase(&BB);
353 LVI->eraseBlock(&BB);
354 DeleteDeadBlock(&BB, DTU.get());
355 Changed = ChangedSinceLastAnalysisUpdate = true;
356 continue;
357 }
358
359 // processBlock doesn't thread BBs with unconditional TIs. However, if BB
360 // is "almost empty", we attempt to merge BB with its sole successor.
361 auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
362 if (BI && BI->isUnconditional()) {
363 BasicBlock *Succ = BI->getSuccessor(0);
364 if (
365 // The terminator must be the only non-phi instruction in BB.
366 BB.getFirstNonPHIOrDbg(true)->isTerminator() &&
367 // Don't alter Loop headers and latches to ensure another pass can
368 // detect and transform nested loops later.
369 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
372 // BB is valid for cleanup here because we passed in DTU. F remains
373 // BB's parent until a DTU->getDomTree() event.
374 LVI->eraseBlock(&BB);
375 Changed = ChangedSinceLastAnalysisUpdate = true;
376 }
377 }
378 }
379 EverChanged |= Changed;
380 } while (Changed);
381
382 LoopHeaders.clear();
383 return EverChanged;
384}
385
386// Replace uses of Cond with ToVal when safe to do so. If all uses are
387// replaced, we can remove Cond. We cannot blindly replace all uses of Cond
388// because we may incorrectly replace uses when guards/assumes are uses of
389// of `Cond` and we used the guards/assume to reason about the `Cond` value
390// at the end of block. RAUW unconditionally replaces all uses
391// including the guards/assumes themselves and the uses before the
392// guard/assume.
394 BasicBlock *KnownAtEndOfBB) {
395 bool Changed = false;
396 assert(Cond->getType() == ToVal->getType());
397 // We can unconditionally replace all uses in non-local blocks (i.e. uses
398 // strictly dominated by BB), since LVI information is true from the
399 // terminator of BB.
400 if (Cond->getParent() == KnownAtEndOfBB)
401 Changed |= replaceNonLocalUsesWith(Cond, ToVal);
402 for (Instruction &I : reverse(*KnownAtEndOfBB)) {
403 // Replace any debug-info record users of Cond with ToVal.
404 for (DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange()))
405 DVR.replaceVariableLocationOp(Cond, ToVal, true);
406
407 // Reached the Cond whose uses we are trying to replace, so there are no
408 // more uses.
409 if (&I == Cond)
410 break;
411 // We only replace uses in instructions that are guaranteed to reach the end
412 // of BB, where we know Cond is ToVal.
414 break;
415 Changed |= I.replaceUsesOfWith(Cond, ToVal);
416 }
417 if (Cond->use_empty() && !Cond->mayHaveSideEffects()) {
418 Cond->eraseFromParent();
419 Changed = true;
420 }
421 return Changed;
422}
423
424/// Return the cost of duplicating a piece of this block from first non-phi
425/// and before StopAt instruction to thread across it. Stop scanning the block
426/// when exceeding the threshold. If duplication is impossible, returns ~0U.
428 BasicBlock *BB,
429 Instruction *StopAt,
430 unsigned Threshold) {
431 assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
432
433 // Do not duplicate the BB if it has a lot of PHI nodes.
434 // If a threadable chain is too long then the number of PHI nodes can add up,
435 // leading to a substantial increase in compile time when rewriting the SSA.
436 unsigned PhiCount = 0;
437 Instruction *FirstNonPHI = nullptr;
438 for (Instruction &I : *BB) {
439 if (!isa<PHINode>(&I)) {
440 FirstNonPHI = &I;
441 break;
442 }
443 if (++PhiCount > PhiDuplicateThreshold)
444 return ~0U;
445 }
446
447 /// Ignore PHI nodes, these will be flattened when duplication happens.
448 BasicBlock::const_iterator I(FirstNonPHI);
449
450 // FIXME: THREADING will delete values that are just used to compute the
451 // branch, so they shouldn't count against the duplication cost.
452
453 unsigned Bonus = 0;
454 if (BB->getTerminator() == StopAt) {
455 // Threading through a switch statement is particularly profitable. If this
456 // block ends in a switch, decrease its cost to make it more likely to
457 // happen.
458 if (isa<SwitchInst>(StopAt))
459 Bonus = 6;
460
461 // The same holds for indirect branches, but slightly more so.
462 if (isa<IndirectBrInst>(StopAt))
463 Bonus = 8;
464 }
465
466 // Bump the threshold up so the early exit from the loop doesn't skip the
467 // terminator-based Size adjustment at the end.
468 Threshold += Bonus;
469
470 // Sum up the cost of each instruction until we get to the terminator. Don't
471 // include the terminator because the copy won't include it.
472 unsigned Size = 0;
473 for (; &*I != StopAt; ++I) {
474
475 // Stop scanning the block if we've reached the threshold.
476 if (Size > Threshold)
477 return Size;
478
479 // Bail out if this instruction gives back a token type, it is not possible
480 // to duplicate it if it is used outside this BB.
481 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
482 return ~0U;
483
484 // Blocks with NoDuplicate are modelled as having infinite cost, so they
485 // are never duplicated.
486 if (const CallInst *CI = dyn_cast<CallInst>(I))
487 if (CI->cannotDuplicate() || CI->isConvergent())
488 return ~0U;
489
492 continue;
493
494 // All other instructions count for at least one unit.
495 ++Size;
496
497 // Calls are more expensive. If they are non-intrinsic calls, we model them
498 // as having cost of 4. If they are a non-vector intrinsic, we model them
499 // as having cost of 2 total, and if they are a vector intrinsic, we model
500 // them as having cost 1.
501 if (const CallInst *CI = dyn_cast<CallInst>(I)) {
502 if (!isa<IntrinsicInst>(CI))
503 Size += 3;
504 else if (!CI->getType()->isVectorTy())
505 Size += 1;
506 }
507 }
508
509 return Size > Bonus ? Size - Bonus : 0;
510}
511
512/// findLoopHeaders - We do not want jump threading to turn proper loop
513/// structures into irreducible loops. Doing this breaks up the loop nesting
514/// hierarchy and pessimizes later transformations. To prevent this from
515/// happening, we first have to find the loop headers. Here we approximate this
516/// by finding targets of backedges in the CFG.
517///
518/// Note that there definitely are cases when we want to allow threading of
519/// edges across a loop header. For example, threading a jump from outside the
520/// loop (the preheader) to an exit block of the loop is definitely profitable.
521/// It is also almost always profitable to thread backedges from within the loop
522/// to exit blocks, and is often profitable to thread backedges to other blocks
523/// within the loop (forming a nested loop). This simple analysis is not rich
524/// enough to track all of these properties and keep it up-to-date as the CFG
525/// mutates, so we don't allow any of these transformations.
528 FindFunctionBackedges(F, Edges);
529
530 for (const auto &Edge : Edges)
531 LoopHeaders.insert(Edge.second);
532}
533
534/// getKnownConstant - Helper method to determine if we can thread over a
535/// terminator with the given value as its condition, and if so what value to
536/// use for that. What kind of value this is depends on whether we want an
537/// integer or a block address, but an undef is always accepted.
538/// Returns null if Val is null or not an appropriate constant.
540 if (!Val)
541 return nullptr;
542
543 // Undef is "known" enough.
544 if (UndefValue *U = dyn_cast<UndefValue>(Val))
545 return U;
546
547 if (Preference == WantBlockAddress)
548 return dyn_cast<BlockAddress>(Val->stripPointerCasts());
549
550 return dyn_cast<ConstantInt>(Val);
551}
552
553/// computeValueKnownInPredecessors - Given a basic block BB and a value V, see
554/// if we can infer that the value is a known ConstantInt/BlockAddress or undef
555/// in any of our predecessors. If so, return the known list of value and pred
556/// BB in the result vector.
557///
558/// This returns true if there were any known values.
560 Value *V, BasicBlock *BB, PredValueInfo &Result,
561 ConstantPreference Preference, SmallPtrSet<Value *, 4> &RecursionSet,
562 Instruction *CxtI) {
563 const DataLayout &DL = BB->getModule()->getDataLayout();
564
565 // This method walks up use-def chains recursively. Because of this, we could
566 // get into an infinite loop going around loops in the use-def chain. To
567 // prevent this, keep track of what (value, block) pairs we've already visited
568 // and terminate the search if we loop back to them
569 if (!RecursionSet.insert(V).second)
570 return false;
571
572 // If V is a constant, then it is known in all predecessors.
573 if (Constant *KC = getKnownConstant(V, Preference)) {
574 for (BasicBlock *Pred : predecessors(BB))
575 Result.emplace_back(KC, Pred);
576
577 return !Result.empty();
578 }
579
580 // If V is a non-instruction value, or an instruction in a different block,
581 // then it can't be derived from a PHI.
582 Instruction *I = dyn_cast<Instruction>(V);
583 if (!I || I->getParent() != BB) {
584
585 // Okay, if this is a live-in value, see if it has a known value at the any
586 // edge from our predecessors.
587 for (BasicBlock *P : predecessors(BB)) {
588 using namespace PatternMatch;
589 // If the value is known by LazyValueInfo to be a constant in a
590 // predecessor, use that information to try to thread this block.
591 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);
592 // If I is a non-local compare-with-constant instruction, use more-rich
593 // 'getPredicateOnEdge' method. This would be able to handle value
594 // inequalities better, for example if the compare is "X < 4" and "X < 3"
595 // is known true but "X < 4" itself is not available.
597 Value *Val;
598 Constant *Cst;
599 if (!PredCst && match(V, m_Cmp(Pred, m_Value(Val), m_Constant(Cst)))) {
600 auto Res = LVI->getPredicateOnEdge(Pred, Val, Cst, P, BB, CxtI);
601 if (Res != LazyValueInfo::Unknown)
602 PredCst = ConstantInt::getBool(V->getContext(), Res);
603 }
604 if (Constant *KC = getKnownConstant(PredCst, Preference))
605 Result.emplace_back(KC, P);
606 }
607
608 return !Result.empty();
609 }
610
611 /// If I is a PHI node, then we know the incoming values for any constants.
612 if (PHINode *PN = dyn_cast<PHINode>(I)) {
613 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
614 Value *InVal = PN->getIncomingValue(i);
615 if (Constant *KC = getKnownConstant(InVal, Preference)) {
616 Result.emplace_back(KC, PN->getIncomingBlock(i));
617 } else {
618 Constant *CI = LVI->getConstantOnEdge(InVal,
619 PN->getIncomingBlock(i),
620 BB, CxtI);
621 if (Constant *KC = getKnownConstant(CI, Preference))
622 Result.emplace_back(KC, PN->getIncomingBlock(i));
623 }
624 }
625
626 return !Result.empty();
627 }
628
629 // Handle Cast instructions.
630 if (CastInst *CI = dyn_cast<CastInst>(I)) {
631 Value *Source = CI->getOperand(0);
632 PredValueInfoTy Vals;
633 computeValueKnownInPredecessorsImpl(Source, BB, Vals, Preference,
634 RecursionSet, CxtI);
635 if (Vals.empty())
636 return false;
637
638 // Convert the known values.
639 for (auto &Val : Vals)
640 if (Constant *Folded = ConstantFoldCastOperand(CI->getOpcode(), Val.first,
641 CI->getType(), DL))
642 Result.emplace_back(Folded, Val.second);
643
644 return !Result.empty();
645 }
646
647 if (FreezeInst *FI = dyn_cast<FreezeInst>(I)) {
648 Value *Source = FI->getOperand(0);
649 computeValueKnownInPredecessorsImpl(Source, BB, Result, Preference,
650 RecursionSet, CxtI);
651
652 erase_if(Result, [](auto &Pair) {
653 return !isGuaranteedNotToBeUndefOrPoison(Pair.first);
654 });
655
656 return !Result.empty();
657 }
658
659 // Handle some boolean conditions.
660 if (I->getType()->getPrimitiveSizeInBits() == 1) {
661 using namespace PatternMatch;
662 if (Preference != WantInteger)
663 return false;
664 // X | true -> true
665 // X & false -> false
666 Value *Op0, *Op1;
667 if (match(I, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
668 match(I, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
669 PredValueInfoTy LHSVals, RHSVals;
670
672 RecursionSet, CxtI);
674 RecursionSet, CxtI);
675
676 if (LHSVals.empty() && RHSVals.empty())
677 return false;
678
679 ConstantInt *InterestingVal;
680 if (match(I, m_LogicalOr()))
681 InterestingVal = ConstantInt::getTrue(I->getContext());
682 else
683 InterestingVal = ConstantInt::getFalse(I->getContext());
684
685 SmallPtrSet<BasicBlock*, 4> LHSKnownBBs;
686
687 // Scan for the sentinel. If we find an undef, force it to the
688 // interesting value: x|undef -> true and x&undef -> false.
689 for (const auto &LHSVal : LHSVals)
690 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
691 Result.emplace_back(InterestingVal, LHSVal.second);
692 LHSKnownBBs.insert(LHSVal.second);
693 }
694 for (const auto &RHSVal : RHSVals)
695 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
696 // If we already inferred a value for this block on the LHS, don't
697 // re-add it.
698 if (!LHSKnownBBs.count(RHSVal.second))
699 Result.emplace_back(InterestingVal, RHSVal.second);
700 }
701
702 return !Result.empty();
703 }
704
705 // Handle the NOT form of XOR.
706 if (I->getOpcode() == Instruction::Xor &&
707 isa<ConstantInt>(I->getOperand(1)) &&
708 cast<ConstantInt>(I->getOperand(1))->isOne()) {
709 computeValueKnownInPredecessorsImpl(I->getOperand(0), BB, Result,
710 WantInteger, RecursionSet, CxtI);
711 if (Result.empty())
712 return false;
713
714 // Invert the known values.
715 for (auto &R : Result)
716 R.first = ConstantExpr::getNot(R.first);
717
718 return true;
719 }
720
721 // Try to simplify some other binary operator values.
722 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
723 if (Preference != WantInteger)
724 return false;
725 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
726 PredValueInfoTy LHSVals;
727 computeValueKnownInPredecessorsImpl(BO->getOperand(0), BB, LHSVals,
728 WantInteger, RecursionSet, CxtI);
729
730 // Try to use constant folding to simplify the binary operator.
731 for (const auto &LHSVal : LHSVals) {
732 Constant *V = LHSVal.first;
733 Constant *Folded =
734 ConstantFoldBinaryOpOperands(BO->getOpcode(), V, CI, DL);
735
736 if (Constant *KC = getKnownConstant(Folded, WantInteger))
737 Result.emplace_back(KC, LHSVal.second);
738 }
739 }
740
741 return !Result.empty();
742 }
743
744 // Handle compare with phi operand, where the PHI is defined in this block.
745 if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
746 if (Preference != WantInteger)
747 return false;
748 Type *CmpType = Cmp->getType();
749 Value *CmpLHS = Cmp->getOperand(0);
750 Value *CmpRHS = Cmp->getOperand(1);
751 CmpInst::Predicate Pred = Cmp->getPredicate();
752
753 PHINode *PN = dyn_cast<PHINode>(CmpLHS);
754 if (!PN)
755 PN = dyn_cast<PHINode>(CmpRHS);
756 // Do not perform phi translation across a loop header phi, because this
757 // may result in comparison of values from two different loop iterations.
758 // FIXME: This check is broken if LoopHeaders is not populated.
759 if (PN && PN->getParent() == BB && !LoopHeaders.contains(BB)) {
760 const DataLayout &DL = PN->getModule()->getDataLayout();
761 // We can do this simplification if any comparisons fold to true or false.
762 // See if any do.
763 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
764 BasicBlock *PredBB = PN->getIncomingBlock(i);
765 Value *LHS, *RHS;
766 if (PN == CmpLHS) {
767 LHS = PN->getIncomingValue(i);
768 RHS = CmpRHS->DoPHITranslation(BB, PredBB);
769 } else {
770 LHS = CmpLHS->DoPHITranslation(BB, PredBB);
771 RHS = PN->getIncomingValue(i);
772 }
773 Value *Res = simplifyCmpInst(Pred, LHS, RHS, {DL});
774 if (!Res) {
775 if (!isa<Constant>(RHS))
776 continue;
777
778 // getPredicateOnEdge call will make no sense if LHS is defined in BB.
779 auto LHSInst = dyn_cast<Instruction>(LHS);
780 if (LHSInst && LHSInst->getParent() == BB)
781 continue;
782
784 ResT = LVI->getPredicateOnEdge(Pred, LHS,
785 cast<Constant>(RHS), PredBB, BB,
786 CxtI ? CxtI : Cmp);
787 if (ResT == LazyValueInfo::Unknown)
788 continue;
789 Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT);
790 }
791
792 if (Constant *KC = getKnownConstant(Res, WantInteger))
793 Result.emplace_back(KC, PredBB);
794 }
795
796 return !Result.empty();
797 }
798
799 // If comparing a live-in value against a constant, see if we know the
800 // live-in value on any predecessors.
801 if (isa<Constant>(CmpRHS) && !CmpType->isVectorTy()) {
802 Constant *CmpConst = cast<Constant>(CmpRHS);
803
804 if (!isa<Instruction>(CmpLHS) ||
805 cast<Instruction>(CmpLHS)->getParent() != BB) {
806 for (BasicBlock *P : predecessors(BB)) {
807 // If the value is known by LazyValueInfo to be a constant in a
808 // predecessor, use that information to try to thread this block.
810 LVI->getPredicateOnEdge(Pred, CmpLHS,
811 CmpConst, P, BB, CxtI ? CxtI : Cmp);
812 if (Res == LazyValueInfo::Unknown)
813 continue;
814
815 Constant *ResC = ConstantInt::get(CmpType, Res);
816 Result.emplace_back(ResC, P);
817 }
818
819 return !Result.empty();
820 }
821
822 // InstCombine can fold some forms of constant range checks into
823 // (icmp (add (x, C1)), C2). See if we have we have such a thing with
824 // x as a live-in.
825 {
826 using namespace PatternMatch;
827
828 Value *AddLHS;
829 ConstantInt *AddConst;
830 if (isa<ConstantInt>(CmpConst) &&
831 match(CmpLHS, m_Add(m_Value(AddLHS), m_ConstantInt(AddConst)))) {
832 if (!isa<Instruction>(AddLHS) ||
833 cast<Instruction>(AddLHS)->getParent() != BB) {
834 for (BasicBlock *P : predecessors(BB)) {
835 // If the value is known by LazyValueInfo to be a ConstantRange in
836 // a predecessor, use that information to try to thread this
837 // block.
839 AddLHS, P, BB, CxtI ? CxtI : cast<Instruction>(CmpLHS));
840 // Propagate the range through the addition.
841 CR = CR.add(AddConst->getValue());
842
843 // Get the range where the compare returns true.
845 Pred, cast<ConstantInt>(CmpConst)->getValue());
846
847 Constant *ResC;
848 if (CmpRange.contains(CR))
849 ResC = ConstantInt::getTrue(CmpType);
850 else if (CmpRange.inverse().contains(CR))
851 ResC = ConstantInt::getFalse(CmpType);
852 else
853 continue;
854
855 Result.emplace_back(ResC, P);
856 }
857
858 return !Result.empty();
859 }
860 }
861 }
862
863 // Try to find a constant value for the LHS of a comparison,
864 // and evaluate it statically if we can.
865 PredValueInfoTy LHSVals;
866 computeValueKnownInPredecessorsImpl(I->getOperand(0), BB, LHSVals,
867 WantInteger, RecursionSet, CxtI);
868
869 for (const auto &LHSVal : LHSVals) {
870 Constant *V = LHSVal.first;
871 Constant *Folded =
872 ConstantFoldCompareInstOperands(Pred, V, CmpConst, DL);
873 if (Constant *KC = getKnownConstant(Folded, WantInteger))
874 Result.emplace_back(KC, LHSVal.second);
875 }
876
877 return !Result.empty();
878 }
879 }
880
881 if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
882 // Handle select instructions where at least one operand is a known constant
883 // and we can figure out the condition value for any predecessor block.
884 Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference);
885 Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference);
886 PredValueInfoTy Conds;
887 if ((TrueVal || FalseVal) &&
888 computeValueKnownInPredecessorsImpl(SI->getCondition(), BB, Conds,
889 WantInteger, RecursionSet, CxtI)) {
890 for (auto &C : Conds) {
891 Constant *Cond = C.first;
892
893 // Figure out what value to use for the condition.
894 bool KnownCond;
895 if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) {
896 // A known boolean.
897 KnownCond = CI->isOne();
898 } else {
899 assert(isa<UndefValue>(Cond) && "Unexpected condition value");
900 // Either operand will do, so be sure to pick the one that's a known
901 // constant.
902 // FIXME: Do this more cleverly if both values are known constants?
903 KnownCond = (TrueVal != nullptr);
904 }
905
906 // See if the select has a known constant value for this predecessor.
907 if (Constant *Val = KnownCond ? TrueVal : FalseVal)
908 Result.emplace_back(Val, C.second);
909 }
910
911 return !Result.empty();
912 }
913 }
914
915 // If all else fails, see if LVI can figure out a constant value for us.
916 assert(CxtI->getParent() == BB && "CxtI should be in BB");
917 Constant *CI = LVI->getConstant(V, CxtI);
918 if (Constant *KC = getKnownConstant(CI, Preference)) {
919 for (BasicBlock *Pred : predecessors(BB))
920 Result.emplace_back(KC, Pred);
921 }
922
923 return !Result.empty();
924}
925
926/// GetBestDestForBranchOnUndef - If we determine that the specified block ends
927/// in an undefined jump, decide which block is best to revector to.
928///
929/// Since we can pick an arbitrary destination, we pick the successor with the
930/// fewest predecessors. This should reduce the in-degree of the others.
932 Instruction *BBTerm = BB->getTerminator();
933 unsigned MinSucc = 0;
934 BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
935 // Compute the successor with the minimum number of predecessors.
936 unsigned MinNumPreds = pred_size(TestBB);
937 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
938 TestBB = BBTerm->getSuccessor(i);
939 unsigned NumPreds = pred_size(TestBB);
940 if (NumPreds < MinNumPreds) {
941 MinSucc = i;
942 MinNumPreds = NumPreds;
943 }
944 }
945
946 return MinSucc;
947}
948
950 if (!BB->hasAddressTaken()) return false;
951
952 // If the block has its address taken, it may be a tree of dead constants
953 // hanging off of it. These shouldn't keep the block alive.
956 return !BA->use_empty();
957}
958
959/// processBlock - If there are any predecessors whose control can be threaded
960/// through to a successor, transform them now.
962 // If the block is trivially dead, just return and let the caller nuke it.
963 // This simplifies other transformations.
964 if (DTU->isBBPendingDeletion(BB) ||
965 (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
966 return false;
967
968 // If this block has a single predecessor, and if that pred has a single
969 // successor, merge the blocks. This encourages recursive jump threading
970 // because now the condition in this block can be threaded through
971 // predecessors of our predecessor block.
973 return true;
974
976 return true;
977
978 // Look if we can propagate guards to predecessors.
979 if (HasGuards && processGuards(BB))
980 return true;
981
982 // What kind of constant we're looking for.
983 ConstantPreference Preference = WantInteger;
984
985 // Look to see if the terminator is a conditional branch, switch or indirect
986 // branch, if not we can't thread it.
987 Value *Condition;
988 Instruction *Terminator = BB->getTerminator();
989 if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
990 // Can't thread an unconditional jump.
991 if (BI->isUnconditional()) return false;
992 Condition = BI->getCondition();
993 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
994 Condition = SI->getCondition();
995 } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
996 // Can't thread indirect branch with no successors.
997 if (IB->getNumSuccessors() == 0) return false;
998 Condition = IB->getAddress()->stripPointerCasts();
999 Preference = WantBlockAddress;
1000 } else {
1001 return false; // Must be an invoke or callbr.
1002 }
1003
1004 // Keep track if we constant folded the condition in this invocation.
1005 bool ConstantFolded = false;
1006
1007 // Run constant folding to see if we can reduce the condition to a simple
1008 // constant.
1009 if (Instruction *I = dyn_cast<Instruction>(Condition)) {
1010 Value *SimpleVal =
1012 if (SimpleVal) {
1013 I->replaceAllUsesWith(SimpleVal);
1014 if (isInstructionTriviallyDead(I, TLI))
1015 I->eraseFromParent();
1016 Condition = SimpleVal;
1017 ConstantFolded = true;
1018 }
1019 }
1020
1021 // If the terminator is branching on an undef or freeze undef, we can pick any
1022 // of the successors to branch to. Let getBestDestForJumpOnUndef decide.
1023 auto *FI = dyn_cast<FreezeInst>(Condition);
1024 if (isa<UndefValue>(Condition) ||
1025 (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
1026 unsigned BestSucc = getBestDestForJumpOnUndef(BB);
1027 std::vector<DominatorTree::UpdateType> Updates;
1028
1029 // Fold the branch/switch.
1030 Instruction *BBTerm = BB->getTerminator();
1031 Updates.reserve(BBTerm->getNumSuccessors());
1032 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
1033 if (i == BestSucc) continue;
1034 BasicBlock *Succ = BBTerm->getSuccessor(i);
1035 Succ->removePredecessor(BB, true);
1036 Updates.push_back({DominatorTree::Delete, BB, Succ});
1037 }
1038
1039 LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
1040 << "' folding undef terminator: " << *BBTerm << '\n');
1041 BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm->getIterator());
1042 ++NumFolds;
1043 BBTerm->eraseFromParent();
1044 DTU->applyUpdatesPermissive(Updates);
1045 if (FI)
1046 FI->eraseFromParent();
1047 return true;
1048 }
1049
1050 // If the terminator of this block is branching on a constant, simplify the
1051 // terminator to an unconditional branch. This can occur due to threading in
1052 // other blocks.
1053 if (getKnownConstant(Condition, Preference)) {
1054 LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
1055 << "' folding terminator: " << *BB->getTerminator()
1056 << '\n');
1057 ++NumFolds;
1058 ConstantFoldTerminator(BB, true, nullptr, DTU.get());
1059 if (auto *BPI = getBPI())
1060 BPI->eraseBlock(BB);
1061 return true;
1062 }
1063
1064 Instruction *CondInst = dyn_cast<Instruction>(Condition);
1065
1066 // All the rest of our checks depend on the condition being an instruction.
1067 if (!CondInst) {
1068 // FIXME: Unify this with code below.
1069 if (processThreadableEdges(Condition, BB, Preference, Terminator))
1070 return true;
1071 return ConstantFolded;
1072 }
1073
1074 // Some of the following optimization can safely work on the unfrozen cond.
1075 Value *CondWithoutFreeze = CondInst;
1076 if (auto *FI = dyn_cast<FreezeInst>(CondInst))
1077 CondWithoutFreeze = FI->getOperand(0);
1078
1079 if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondWithoutFreeze)) {
1080 // If we're branching on a conditional, LVI might be able to determine
1081 // it's value at the branch instruction. We only handle comparisons
1082 // against a constant at this time.
1083 if (Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1))) {
1085 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1086 CondConst, BB->getTerminator(),
1087 /*UseBlockValue=*/false);
1088 if (Ret != LazyValueInfo::Unknown) {
1089 // We can safely replace *some* uses of the CondInst if it has
1090 // exactly one value as returned by LVI. RAUW is incorrect in the
1091 // presence of guards and assumes, that have the `Cond` as the use. This
1092 // is because we use the guards/assume to reason about the `Cond` value
1093 // at the end of block, but RAUW unconditionally replaces all uses
1094 // including the guards/assumes themselves and the uses before the
1095 // guard/assume.
1096 auto *CI = Ret == LazyValueInfo::True ?
1097 ConstantInt::getTrue(CondCmp->getType()) :
1098 ConstantInt::getFalse(CondCmp->getType());
1099 if (replaceFoldableUses(CondCmp, CI, BB))
1100 return true;
1101 }
1102
1103 // We did not manage to simplify this branch, try to see whether
1104 // CondCmp depends on a known phi-select pattern.
1105 if (tryToUnfoldSelect(CondCmp, BB))
1106 return true;
1107 }
1108 }
1109
1110 if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
1111 if (tryToUnfoldSelect(SI, BB))
1112 return true;
1113
1114 // Check for some cases that are worth simplifying. Right now we want to look
1115 // for loads that are used by a switch or by the condition for the branch. If
1116 // we see one, check to see if it's partially redundant. If so, insert a PHI
1117 // which can then be used to thread the values.
1118 Value *SimplifyValue = CondWithoutFreeze;
1119
1120 if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
1121 if (isa<Constant>(CondCmp->getOperand(1)))
1122 SimplifyValue = CondCmp->getOperand(0);
1123
1124 // TODO: There are other places where load PRE would be profitable, such as
1125 // more complex comparisons.
1126 if (LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
1128 return true;
1129
1130 // Before threading, try to propagate profile data backwards:
1131 if (PHINode *PN = dyn_cast<PHINode>(CondInst))
1132 if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1134
1135 // Handle a variety of cases where we are branching on something derived from
1136 // a PHI node in the current block. If we can prove that any predecessors
1137 // compute a predictable value based on a PHI node, thread those predecessors.
1138 if (processThreadableEdges(CondInst, BB, Preference, Terminator))
1139 return true;
1140
1141 // If this is an otherwise-unfoldable branch on a phi node or freeze(phi) in
1142 // the current block, see if we can simplify.
1143 PHINode *PN = dyn_cast<PHINode>(CondWithoutFreeze);
1144 if (PN && PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1145 return processBranchOnPHI(PN);
1146
1147 // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify.
1148 if (CondInst->getOpcode() == Instruction::Xor &&
1149 CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1150 return processBranchOnXOR(cast<BinaryOperator>(CondInst));
1151
1152 // Search for a stronger dominating condition that can be used to simplify a
1153 // conditional branch leaving BB.
1155 return true;
1156
1157 return false;
1158}
1159
1161 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
1162 if (!BI || !BI->isConditional())
1163 return false;
1164
1165 Value *Cond = BI->getCondition();
1166 // Assuming that predecessor's branch was taken, if pred's branch condition
1167 // (V) implies Cond, Cond can be either true, undef, or poison. In this case,
1168 // freeze(Cond) is either true or a nondeterministic value.
1169 // If freeze(Cond) has only one use, we can freely fold freeze(Cond) to true
1170 // without affecting other instructions.
1171 auto *FICond = dyn_cast<FreezeInst>(Cond);
1172 if (FICond && FICond->hasOneUse())
1173 Cond = FICond->getOperand(0);
1174 else
1175 FICond = nullptr;
1176
1177 BasicBlock *CurrentBB = BB;
1178 BasicBlock *CurrentPred = BB->getSinglePredecessor();
1179 unsigned Iter = 0;
1180
1181 auto &DL = BB->getModule()->getDataLayout();
1182
1183 while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
1184 auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
1185 if (!PBI || !PBI->isConditional())
1186 return false;
1187 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1188 return false;
1189
1190 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1191 std::optional<bool> Implication =
1192 isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
1193
1194 // If the branch condition of BB (which is Cond) and CurrentPred are
1195 // exactly the same freeze instruction, Cond can be folded into CondIsTrue.
1196 if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
1197 if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
1198 FICond->getOperand(0))
1199 Implication = CondIsTrue;
1200 }
1201
1202 if (Implication) {
1203 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1204 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1205 RemoveSucc->removePredecessor(BB);
1206 BranchInst *UncondBI = BranchInst::Create(KeepSucc, BI->getIterator());
1207 UncondBI->setDebugLoc(BI->getDebugLoc());
1208 ++NumFolds;
1209 BI->eraseFromParent();
1210 if (FICond)
1211 FICond->eraseFromParent();
1212
1213 DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
1214 if (auto *BPI = getBPI())
1215 BPI->eraseBlock(BB);
1216 return true;
1217 }
1218 CurrentBB = CurrentPred;
1219 CurrentPred = CurrentBB->getSinglePredecessor();
1220 }
1221
1222 return false;
1223}
1224
1225/// Return true if Op is an instruction defined in the given block.
1227 if (Instruction *OpInst = dyn_cast<Instruction>(Op))
1228 if (OpInst->getParent() == BB)
1229 return true;
1230 return false;
1231}
1232
1233/// simplifyPartiallyRedundantLoad - If LoadI is an obviously partially
1234/// redundant load instruction, eliminate it by replacing it with a PHI node.
1235/// This is an important optimization that encourages jump threading, and needs
1236/// to be run interlaced with other jump threading tasks.
1238 // Don't hack volatile and ordered loads.
1239 if (!LoadI->isUnordered()) return false;
1240
1241 // If the load is defined in a block with exactly one predecessor, it can't be
1242 // partially redundant.
1243 BasicBlock *LoadBB = LoadI->getParent();
1244 if (LoadBB->getSinglePredecessor())
1245 return false;
1246
1247 // If the load is defined in an EH pad, it can't be partially redundant,
1248 // because the edges between the invoke and the EH pad cannot have other
1249 // instructions between them.
1250 if (LoadBB->isEHPad())
1251 return false;
1252
1253 Value *LoadedPtr = LoadI->getOperand(0);
1254
1255 // If the loaded operand is defined in the LoadBB and its not a phi,
1256 // it can't be available in predecessors.
1257 if (isOpDefinedInBlock(LoadedPtr, LoadBB) && !isa<PHINode>(LoadedPtr))
1258 return false;
1259
1260 // Scan a few instructions up from the load, to see if it is obviously live at
1261 // the entry to its block.
1262 BasicBlock::iterator BBIt(LoadI);
1263 bool IsLoadCSE;
1264 BatchAAResults BatchAA(*AA);
1265 // The dominator tree is updated lazily and may not be valid at this point.
1266 BatchAA.disableDominatorTree();
1267 if (Value *AvailableVal = FindAvailableLoadedValue(
1268 LoadI, LoadBB, BBIt, DefMaxInstsToScan, &BatchAA, &IsLoadCSE)) {
1269 // If the value of the load is locally available within the block, just use
1270 // it. This frequently occurs for reg2mem'd allocas.
1271
1272 if (IsLoadCSE) {
1273 LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1274 combineMetadataForCSE(NLoadI, LoadI, false);
1275 LVI->forgetValue(NLoadI);
1276 };
1277
1278 // If the returned value is the load itself, replace with poison. This can
1279 // only happen in dead loops.
1280 if (AvailableVal == LoadI)
1281 AvailableVal = PoisonValue::get(LoadI->getType());
1282 if (AvailableVal->getType() != LoadI->getType()) {
1283 AvailableVal = CastInst::CreateBitOrPointerCast(
1284 AvailableVal, LoadI->getType(), "", LoadI->getIterator());
1285 cast<Instruction>(AvailableVal)->setDebugLoc(LoadI->getDebugLoc());
1286 }
1287 LoadI->replaceAllUsesWith(AvailableVal);
1288 LoadI->eraseFromParent();
1289 return true;
1290 }
1291
1292 // Otherwise, if we scanned the whole block and got to the top of the block,
1293 // we know the block is locally transparent to the load. If not, something
1294 // might clobber its value.
1295 if (BBIt != LoadBB->begin())
1296 return false;
1297
1298 // If all of the loads and stores that feed the value have the same AA tags,
1299 // then we can propagate them onto any newly inserted loads.
1300 AAMDNodes AATags = LoadI->getAAMetadata();
1301
1302 SmallPtrSet<BasicBlock*, 8> PredsScanned;
1303
1304 using AvailablePredsTy = SmallVector<std::pair<BasicBlock *, Value *>, 8>;
1305
1306 AvailablePredsTy AvailablePreds;
1307 BasicBlock *OneUnavailablePred = nullptr;
1309
1310 // If we got here, the loaded value is transparent through to the start of the
1311 // block. Check to see if it is available in any of the predecessor blocks.
1312 for (BasicBlock *PredBB : predecessors(LoadBB)) {
1313 // If we already scanned this predecessor, skip it.
1314 if (!PredsScanned.insert(PredBB).second)
1315 continue;
1316
1317 BBIt = PredBB->end();
1318 unsigned NumScanedInst = 0;
1319 Value *PredAvailable = nullptr;
1320 // NOTE: We don't CSE load that is volatile or anything stronger than
1321 // unordered, that should have been checked when we entered the function.
1322 assert(LoadI->isUnordered() &&
1323 "Attempting to CSE volatile or atomic loads");
1324 // If this is a load on a phi pointer, phi-translate it and search
1325 // for available load/store to the pointer in predecessors.
1326 Type *AccessTy = LoadI->getType();
1327 const auto &DL = LoadI->getModule()->getDataLayout();
1328 MemoryLocation Loc(LoadedPtr->DoPHITranslation(LoadBB, PredBB),
1329 LocationSize::precise(DL.getTypeStoreSize(AccessTy)),
1330 AATags);
1331 PredAvailable = findAvailablePtrLoadStore(
1332 Loc, AccessTy, LoadI->isAtomic(), PredBB, BBIt, DefMaxInstsToScan,
1333 &BatchAA, &IsLoadCSE, &NumScanedInst);
1334
1335 // If PredBB has a single predecessor, continue scanning through the
1336 // single predecessor.
1337 BasicBlock *SinglePredBB = PredBB;
1338 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
1339 NumScanedInst < DefMaxInstsToScan) {
1340 SinglePredBB = SinglePredBB->getSinglePredecessor();
1341 if (SinglePredBB) {
1342 BBIt = SinglePredBB->end();
1343 PredAvailable = findAvailablePtrLoadStore(
1344 Loc, AccessTy, LoadI->isAtomic(), SinglePredBB, BBIt,
1345 (DefMaxInstsToScan - NumScanedInst), &BatchAA, &IsLoadCSE,
1346 &NumScanedInst);
1347 }
1348 }
1349
1350 if (!PredAvailable) {
1351 OneUnavailablePred = PredBB;
1352 continue;
1353 }
1354
1355 if (IsLoadCSE)
1356 CSELoads.push_back(cast<LoadInst>(PredAvailable));
1357
1358 // If so, this load is partially redundant. Remember this info so that we
1359 // can create a PHI node.
1360 AvailablePreds.emplace_back(PredBB, PredAvailable);
1361 }
1362
1363 // If the loaded value isn't available in any predecessor, it isn't partially
1364 // redundant.
1365 if (AvailablePreds.empty()) return false;
1366
1367 // Okay, the loaded value is available in at least one (and maybe all!)
1368 // predecessors. If the value is unavailable in more than one unique
1369 // predecessor, we want to insert a merge block for those common predecessors.
1370 // This ensures that we only have to insert one reload, thus not increasing
1371 // code size.
1372 BasicBlock *UnavailablePred = nullptr;
1373
1374 // If the value is unavailable in one of predecessors, we will end up
1375 // inserting a new instruction into them. It is only valid if all the
1376 // instructions before LoadI are guaranteed to pass execution to its
1377 // successor, or if LoadI is safe to speculate.
1378 // TODO: If this logic becomes more complex, and we will perform PRE insertion
1379 // farther than to a predecessor, we need to reuse the code from GVN's PRE.
1380 // It requires domination tree analysis, so for this simple case it is an
1381 // overkill.
1382 if (PredsScanned.size() != AvailablePreds.size() &&
1384 for (auto I = LoadBB->begin(); &*I != LoadI; ++I)
1386 return false;
1387
1388 // If there is exactly one predecessor where the value is unavailable, the
1389 // already computed 'OneUnavailablePred' block is it. If it ends in an
1390 // unconditional branch, we know that it isn't a critical edge.
1391 if (PredsScanned.size() == AvailablePreds.size()+1 &&
1392 OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
1393 UnavailablePred = OneUnavailablePred;
1394 } else if (PredsScanned.size() != AvailablePreds.size()) {
1395 // Otherwise, we had multiple unavailable predecessors or we had a critical
1396 // edge from the one.
1397 SmallVector<BasicBlock*, 8> PredsToSplit;
1398 SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
1399
1400 for (const auto &AvailablePred : AvailablePreds)
1401 AvailablePredSet.insert(AvailablePred.first);
1402
1403 // Add all the unavailable predecessors to the PredsToSplit list.
1404 for (BasicBlock *P : predecessors(LoadBB)) {
1405 // If the predecessor is an indirect goto, we can't split the edge.
1406 if (isa<IndirectBrInst>(P->getTerminator()))
1407 return false;
1408
1409 if (!AvailablePredSet.count(P))
1410 PredsToSplit.push_back(P);
1411 }
1412
1413 // Split them out to their own block.
1414 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split");
1415 }
1416
1417 // If the value isn't available in all predecessors, then there will be
1418 // exactly one where it isn't available. Insert a load on that edge and add
1419 // it to the AvailablePreds list.
1420 if (UnavailablePred) {
1421 assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
1422 "Can't handle critical edge here!");
1423 LoadInst *NewVal = new LoadInst(
1424 LoadI->getType(), LoadedPtr->DoPHITranslation(LoadBB, UnavailablePred),
1425 LoadI->getName() + ".pr", false, LoadI->getAlign(),
1426 LoadI->getOrdering(), LoadI->getSyncScopeID(),
1427 UnavailablePred->getTerminator()->getIterator());
1428 NewVal->setDebugLoc(LoadI->getDebugLoc());
1429 if (AATags)
1430 NewVal->setAAMetadata(AATags);
1431
1432 AvailablePreds.emplace_back(UnavailablePred, NewVal);
1433 }
1434
1435 // Now we know that each predecessor of this block has a value in
1436 // AvailablePreds, sort them for efficient access as we're walking the preds.
1437 array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
1438
1439 // Create a PHI node at the start of the block for the PRE'd load value.
1440 PHINode *PN = PHINode::Create(LoadI->getType(), pred_size(LoadBB), "");
1441 PN->insertBefore(LoadBB->begin());
1442 PN->takeName(LoadI);
1443 PN->setDebugLoc(LoadI->getDebugLoc());
1444
1445 // Insert new entries into the PHI for each predecessor. A single block may
1446 // have multiple entries here.
1447 for (BasicBlock *P : predecessors(LoadBB)) {
1448 AvailablePredsTy::iterator I =
1449 llvm::lower_bound(AvailablePreds, std::make_pair(P, (Value *)nullptr));
1450
1451 assert(I != AvailablePreds.end() && I->first == P &&
1452 "Didn't find entry for predecessor!");
1453
1454 // If we have an available predecessor but it requires casting, insert the
1455 // cast in the predecessor and use the cast. Note that we have to update the
1456 // AvailablePreds vector as we go so that all of the PHI entries for this
1457 // predecessor use the same bitcast.
1458 Value *&PredV = I->second;
1459 if (PredV->getType() != LoadI->getType())
1461 PredV, LoadI->getType(), "", P->getTerminator()->getIterator());
1462
1463 PN->addIncoming(PredV, I->first);
1464 }
1465
1466 for (LoadInst *PredLoadI : CSELoads) {
1467 combineMetadataForCSE(PredLoadI, LoadI, true);
1468 LVI->forgetValue(PredLoadI);
1469 }
1470
1471 LoadI->replaceAllUsesWith(PN);
1472 LoadI->eraseFromParent();
1473
1474 return true;
1475}
1476
1477/// findMostPopularDest - The specified list contains multiple possible
1478/// threadable destinations. Pick the one that occurs the most frequently in
1479/// the list.
1480static BasicBlock *
1482 const SmallVectorImpl<std::pair<BasicBlock *,
1483 BasicBlock *>> &PredToDestList) {
1484 assert(!PredToDestList.empty());
1485
1486 // Determine popularity. If there are multiple possible destinations, we
1487 // explicitly choose to ignore 'undef' destinations. We prefer to thread
1488 // blocks with known and real destinations to threading undef. We'll handle
1489 // them later if interesting.
1490 MapVector<BasicBlock *, unsigned> DestPopularity;
1491
1492 // Populate DestPopularity with the successors in the order they appear in the
1493 // successor list. This way, we ensure determinism by iterating it in the
1494 // same order in llvm::max_element below. We map nullptr to 0 so that we can
1495 // return nullptr when PredToDestList contains nullptr only.
1496 DestPopularity[nullptr] = 0;
1497 for (auto *SuccBB : successors(BB))
1498 DestPopularity[SuccBB] = 0;
1499
1500 for (const auto &PredToDest : PredToDestList)
1501 if (PredToDest.second)
1502 DestPopularity[PredToDest.second]++;
1503
1504 // Find the most popular dest.
1505 auto MostPopular = llvm::max_element(DestPopularity, llvm::less_second());
1506
1507 // Okay, we have finally picked the most popular destination.
1508 return MostPopular->first;
1509}
1510
1511// Try to evaluate the value of V when the control flows from PredPredBB to
1512// BB->getSinglePredecessor() and then on to BB.
1514 BasicBlock *PredPredBB,
1515 Value *V,
1516 const DataLayout &DL) {
1517 BasicBlock *PredBB = BB->getSinglePredecessor();
1518 assert(PredBB && "Expected a single predecessor");
1519
1520 if (Constant *Cst = dyn_cast<Constant>(V)) {
1521 return Cst;
1522 }
1523
1524 // Consult LVI if V is not an instruction in BB or PredBB.
1525 Instruction *I = dyn_cast<Instruction>(V);
1526 if (!I || (I->getParent() != BB && I->getParent() != PredBB)) {
1527 return LVI->getConstantOnEdge(V, PredPredBB, PredBB, nullptr);
1528 }
1529
1530 // Look into a PHI argument.
1531 if (PHINode *PHI = dyn_cast<PHINode>(V)) {
1532 if (PHI->getParent() == PredBB)
1533 return dyn_cast<Constant>(PHI->getIncomingValueForBlock(PredPredBB));
1534 return nullptr;
1535 }
1536
1537 // If we have a CmpInst, try to fold it for each incoming edge into PredBB.
1538 if (CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1539 if (CondCmp->getParent() == BB) {
1540 Constant *Op0 =
1541 evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(0), DL);
1542 Constant *Op1 =
1543 evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(1), DL);
1544 if (Op0 && Op1) {
1545 return ConstantFoldCompareInstOperands(CondCmp->getPredicate(), Op0,
1546 Op1, DL);
1547 }
1548 }
1549 return nullptr;
1550 }
1551
1552 return nullptr;
1553}
1554
1556 ConstantPreference Preference,
1557 Instruction *CxtI) {
1558 // If threading this would thread across a loop header, don't even try to
1559 // thread the edge.
1560 if (LoopHeaders.count(BB))
1561 return false;
1562
1563 PredValueInfoTy PredValues;
1564 if (!computeValueKnownInPredecessors(Cond, BB, PredValues, Preference,
1565 CxtI)) {
1566 // We don't have known values in predecessors. See if we can thread through
1567 // BB and its sole predecessor.
1569 }
1570
1571 assert(!PredValues.empty() &&
1572 "computeValueKnownInPredecessors returned true with no values");
1573
1574 LLVM_DEBUG(dbgs() << "IN BB: " << *BB;
1575 for (const auto &PredValue : PredValues) {
1576 dbgs() << " BB '" << BB->getName()
1577 << "': FOUND condition = " << *PredValue.first
1578 << " for pred '" << PredValue.second->getName() << "'.\n";
1579 });
1580
1581 // Decide what we want to thread through. Convert our list of known values to
1582 // a list of known destinations for each pred. This also discards duplicate
1583 // predecessors and keeps track of the undefined inputs (which are represented
1584 // as a null dest in the PredToDestList).
1587
1588 BasicBlock *OnlyDest = nullptr;
1589 BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL;
1590 Constant *OnlyVal = nullptr;
1591 Constant *MultipleVal = (Constant *)(intptr_t)~0ULL;
1592
1593 for (const auto &PredValue : PredValues) {
1594 BasicBlock *Pred = PredValue.second;
1595 if (!SeenPreds.insert(Pred).second)
1596 continue; // Duplicate predecessor entry.
1597
1598 Constant *Val = PredValue.first;
1599
1600 BasicBlock *DestBB;
1601 if (isa<UndefValue>(Val))
1602 DestBB = nullptr;
1603 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
1604 assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
1605 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
1606 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
1607 assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
1608 DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1609 } else {
1610 assert(isa<IndirectBrInst>(BB->getTerminator())
1611 && "Unexpected terminator");
1612 assert(isa<BlockAddress>(Val) && "Expecting a constant blockaddress");
1613 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1614 }
1615
1616 // If we have exactly one destination, remember it for efficiency below.
1617 if (PredToDestList.empty()) {
1618 OnlyDest = DestBB;
1619 OnlyVal = Val;
1620 } else {
1621 if (OnlyDest != DestBB)
1622 OnlyDest = MultipleDestSentinel;
1623 // It possible we have same destination, but different value, e.g. default
1624 // case in switchinst.
1625 if (Val != OnlyVal)
1626 OnlyVal = MultipleVal;
1627 }
1628
1629 // If the predecessor ends with an indirect goto, we can't change its
1630 // destination.
1631 if (isa<IndirectBrInst>(Pred->getTerminator()))
1632 continue;
1633
1634 PredToDestList.emplace_back(Pred, DestBB);
1635 }
1636
1637 // If all edges were unthreadable, we fail.
1638 if (PredToDestList.empty())
1639 return false;
1640
1641 // If all the predecessors go to a single known successor, we want to fold,
1642 // not thread. By doing so, we do not need to duplicate the current block and
1643 // also miss potential opportunities in case we dont/cant duplicate.
1644 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1645 if (BB->hasNPredecessors(PredToDestList.size())) {
1646 bool SeenFirstBranchToOnlyDest = false;
1647 std::vector <DominatorTree::UpdateType> Updates;
1648 Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
1649 for (BasicBlock *SuccBB : successors(BB)) {
1650 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1651 SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
1652 } else {
1653 SuccBB->removePredecessor(BB, true); // This is unreachable successor.
1654 Updates.push_back({DominatorTree::Delete, BB, SuccBB});
1655 }
1656 }
1657
1658 // Finally update the terminator.
1659 Instruction *Term = BB->getTerminator();
1660 BranchInst::Create(OnlyDest, Term->getIterator());
1661 ++NumFolds;
1662 Term->eraseFromParent();
1663 DTU->applyUpdatesPermissive(Updates);
1664 if (auto *BPI = getBPI())
1665 BPI->eraseBlock(BB);
1666
1667 // If the condition is now dead due to the removal of the old terminator,
1668 // erase it.
1669 if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
1670 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1671 CondInst->eraseFromParent();
1672 // We can safely replace *some* uses of the CondInst if it has
1673 // exactly one value as returned by LVI. RAUW is incorrect in the
1674 // presence of guards and assumes, that have the `Cond` as the use. This
1675 // is because we use the guards/assume to reason about the `Cond` value
1676 // at the end of block, but RAUW unconditionally replaces all uses
1677 // including the guards/assumes themselves and the uses before the
1678 // guard/assume.
1679 else if (OnlyVal && OnlyVal != MultipleVal)
1680 replaceFoldableUses(CondInst, OnlyVal, BB);
1681 }
1682 return true;
1683 }
1684 }
1685
1686 // Determine which is the most common successor. If we have many inputs and
1687 // this block is a switch, we want to start by threading the batch that goes
1688 // to the most popular destination first. If we only know about one
1689 // threadable destination (the common case) we can avoid this.
1690 BasicBlock *MostPopularDest = OnlyDest;
1691
1692 if (MostPopularDest == MultipleDestSentinel) {
1693 // Remove any loop headers from the Dest list, threadEdge conservatively
1694 // won't process them, but we might have other destination that are eligible
1695 // and we still want to process.
1696 erase_if(PredToDestList,
1697 [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1698 return LoopHeaders.contains(PredToDest.second);
1699 });
1700
1701 if (PredToDestList.empty())
1702 return false;
1703
1704 MostPopularDest = findMostPopularDest(BB, PredToDestList);
1705 }
1706
1707 // Now that we know what the most popular destination is, factor all
1708 // predecessors that will jump to it into a single predecessor.
1709 SmallVector<BasicBlock*, 16> PredsToFactor;
1710 for (const auto &PredToDest : PredToDestList)
1711 if (PredToDest.second == MostPopularDest) {
1712 BasicBlock *Pred = PredToDest.first;
1713
1714 // This predecessor may be a switch or something else that has multiple
1715 // edges to the block. Factor each of these edges by listing them
1716 // according to # occurrences in PredsToFactor.
1717 for (BasicBlock *Succ : successors(Pred))
1718 if (Succ == BB)
1719 PredsToFactor.push_back(Pred);
1720 }
1721
1722 // If the threadable edges are branching on an undefined value, we get to pick
1723 // the destination that these predecessors should get to.
1724 if (!MostPopularDest)
1725 MostPopularDest = BB->getTerminator()->
1726 getSuccessor(getBestDestForJumpOnUndef(BB));
1727
1728 // Ok, try to thread it!
1729 return tryThreadEdge(BB, PredsToFactor, MostPopularDest);
1730}
1731
1732/// processBranchOnPHI - We have an otherwise unthreadable conditional branch on
1733/// a PHI node (or freeze PHI) in the current block. See if there are any
1734/// simplifications we can do based on inputs to the phi node.
1736 BasicBlock *BB = PN->getParent();
1737
1738 // TODO: We could make use of this to do it once for blocks with common PHI
1739 // values.
1741 PredBBs.resize(1);
1742
1743 // If any of the predecessor blocks end in an unconditional branch, we can
1744 // *duplicate* the conditional branch into that block in order to further
1745 // encourage jump threading and to eliminate cases where we have branch on a
1746 // phi of an icmp (branch on icmp is much better).
1747 // This is still beneficial when a frozen phi is used as the branch condition
1748 // because it allows CodeGenPrepare to further canonicalize br(freeze(icmp))
1749 // to br(icmp(freeze ...)).
1750 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1751 BasicBlock *PredBB = PN->getIncomingBlock(i);
1752 if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator()))
1753 if (PredBr->isUnconditional()) {
1754 PredBBs[0] = PredBB;
1755 // Try to duplicate BB into PredBB.
1756 if (duplicateCondBranchOnPHIIntoPred(BB, PredBBs))
1757 return true;
1758 }
1759 }
1760
1761 return false;
1762}
1763
1764/// processBranchOnXOR - We have an otherwise unthreadable conditional branch on
1765/// a xor instruction in the current block. See if there are any
1766/// simplifications we can do based on inputs to the xor.
1768 BasicBlock *BB = BO->getParent();
1769
1770 // If either the LHS or RHS of the xor is a constant, don't do this
1771 // optimization.
1772 if (isa<ConstantInt>(BO->getOperand(0)) ||
1773 isa<ConstantInt>(BO->getOperand(1)))
1774 return false;
1775
1776 // If the first instruction in BB isn't a phi, we won't be able to infer
1777 // anything special about any particular predecessor.
1778 if (!isa<PHINode>(BB->front()))
1779 return false;
1780
1781 // If this BB is a landing pad, we won't be able to split the edge into it.
1782 if (BB->isEHPad())
1783 return false;
1784
1785 // If we have a xor as the branch input to this block, and we know that the
1786 // LHS or RHS of the xor in any predecessor is true/false, then we can clone
1787 // the condition into the predecessor and fix that value to true, saving some
1788 // logical ops on that path and encouraging other paths to simplify.
1789 //
1790 // This copies something like this:
1791 //
1792 // BB:
1793 // %X = phi i1 [1], [%X']
1794 // %Y = icmp eq i32 %A, %B
1795 // %Z = xor i1 %X, %Y
1796 // br i1 %Z, ...
1797 //
1798 // Into:
1799 // BB':
1800 // %Y = icmp ne i32 %A, %B
1801 // br i1 %Y, ...
1802
1803 PredValueInfoTy XorOpValues;
1804 bool isLHS = true;
1805 if (!computeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues,
1806 WantInteger, BO)) {
1807 assert(XorOpValues.empty());
1808 if (!computeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues,
1809 WantInteger, BO))
1810 return false;
1811 isLHS = false;
1812 }
1813
1814 assert(!XorOpValues.empty() &&
1815 "computeValueKnownInPredecessors returned true with no values");
1816
1817 // Scan the information to see which is most popular: true or false. The
1818 // predecessors can be of the set true, false, or undef.
1819 unsigned NumTrue = 0, NumFalse = 0;
1820 for (const auto &XorOpValue : XorOpValues) {
1821 if (isa<UndefValue>(XorOpValue.first))
1822 // Ignore undefs for the count.
1823 continue;
1824 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1825 ++NumFalse;
1826 else
1827 ++NumTrue;
1828 }
1829
1830 // Determine which value to split on, true, false, or undef if neither.
1831 ConstantInt *SplitVal = nullptr;
1832 if (NumTrue > NumFalse)
1833 SplitVal = ConstantInt::getTrue(BB->getContext());
1834 else if (NumTrue != 0 || NumFalse != 0)
1835 SplitVal = ConstantInt::getFalse(BB->getContext());
1836
1837 // Collect all of the blocks that this can be folded into so that we can
1838 // factor this once and clone it once.
1839 SmallVector<BasicBlock*, 8> BlocksToFoldInto;
1840 for (const auto &XorOpValue : XorOpValues) {
1841 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1842 continue;
1843
1844 BlocksToFoldInto.push_back(XorOpValue.second);
1845 }
1846
1847 // If we inferred a value for all of the predecessors, then duplication won't
1848 // help us. However, we can just replace the LHS or RHS with the constant.
1849 if (BlocksToFoldInto.size() ==
1850 cast<PHINode>(BB->front()).getNumIncomingValues()) {
1851 if (!SplitVal) {
1852 // If all preds provide undef, just nuke the xor, because it is undef too.
1854 BO->eraseFromParent();
1855 } else if (SplitVal->isZero() && BO != BO->getOperand(isLHS)) {
1856 // If all preds provide 0, replace the xor with the other input.
1857 BO->replaceAllUsesWith(BO->getOperand(isLHS));
1858 BO->eraseFromParent();
1859 } else {
1860 // If all preds provide 1, set the computed value to 1.
1861 BO->setOperand(!isLHS, SplitVal);
1862 }
1863
1864 return true;
1865 }
1866
1867 // If any of predecessors end with an indirect goto, we can't change its
1868 // destination.
1869 if (any_of(BlocksToFoldInto, [](BasicBlock *Pred) {
1870 return isa<IndirectBrInst>(Pred->getTerminator());
1871 }))
1872 return false;
1873
1874 // Try to duplicate BB into PredBB.
1875 return duplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
1876}
1877
1878/// addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
1879/// predecessor to the PHIBB block. If it has PHI nodes, add entries for
1880/// NewPred using the entries from OldPred (suitably mapped).
1882 BasicBlock *OldPred,
1883 BasicBlock *NewPred,
1885 for (PHINode &PN : PHIBB->phis()) {
1886 // Ok, we have a PHI node. Figure out what the incoming value was for the
1887 // DestBlock.
1888 Value *IV = PN.getIncomingValueForBlock(OldPred);
1889
1890 // Remap the value if necessary.
1891 if (Instruction *Inst = dyn_cast<Instruction>(IV)) {
1893 if (I != ValueMap.end())
1894 IV = I->second;
1895 }
1896
1897 PN.addIncoming(IV, NewPred);
1898 }
1899}
1900
1901/// Merge basic block BB into its sole predecessor if possible.
1903 BasicBlock *SinglePred = BB->getSinglePredecessor();
1904 if (!SinglePred)
1905 return false;
1906
1907 const Instruction *TI = SinglePred->getTerminator();
1908 if (TI->isSpecialTerminator() || TI->getNumSuccessors() != 1 ||
1909 SinglePred == BB || hasAddressTakenAndUsed(BB))
1910 return false;
1911
1912 // If SinglePred was a loop header, BB becomes one.
1913 if (LoopHeaders.erase(SinglePred))
1914 LoopHeaders.insert(BB);
1915
1916 LVI->eraseBlock(SinglePred);
1917 MergeBasicBlockIntoOnlyPred(BB, DTU.get());
1918
1919 // Now that BB is merged into SinglePred (i.e. SinglePred code followed by
1920 // BB code within one basic block `BB`), we need to invalidate the LVI
1921 // information associated with BB, because the LVI information need not be
1922 // true for all of BB after the merge. For example,
1923 // Before the merge, LVI info and code is as follows:
1924 // SinglePred: <LVI info1 for %p val>
1925 // %y = use of %p
1926 // call @exit() // need not transfer execution to successor.
1927 // assume(%p) // from this point on %p is true
1928 // br label %BB
1929 // BB: <LVI info2 for %p val, i.e. %p is true>
1930 // %x = use of %p
1931 // br label exit
1932 //
1933 // Note that this LVI info for blocks BB and SinglPred is correct for %p
1934 // (info2 and info1 respectively). After the merge and the deletion of the
1935 // LVI info1 for SinglePred. We have the following code:
1936 // BB: <LVI info2 for %p val>
1937 // %y = use of %p
1938 // call @exit()
1939 // assume(%p)
1940 // %x = use of %p <-- LVI info2 is correct from here onwards.
1941 // br label exit
1942 // LVI info2 for BB is incorrect at the beginning of BB.
1943
1944 // Invalidate LVI information for BB if the LVI is not provably true for
1945 // all of BB.
1947 LVI->eraseBlock(BB);
1948 return true;
1949}
1950
1951/// Update the SSA form. NewBB contains instructions that are copied from BB.
1952/// ValueMapping maps old values in BB to new ones in NewBB.
1954 ValueToValueMapTy &ValueMapping) {
1955 // If there were values defined in BB that are used outside the block, then we
1956 // now have to update all uses of the value to use either the original value,
1957 // the cloned value, or some PHI derived value. This can require arbitrary
1958 // PHI insertion, of which we are prepared to do, clean these up now.
1959 SSAUpdater SSAUpdate;
1960 SmallVector<Use *, 16> UsesToRename;
1962 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;
1963
1964 for (Instruction &I : *BB) {
1965 // Scan all uses of this instruction to see if it is used outside of its
1966 // block, and if so, record them in UsesToRename.
1967 for (Use &U : I.uses()) {
1968 Instruction *User = cast<Instruction>(U.getUser());
1969 if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
1970 if (UserPN->getIncomingBlock(U) == BB)
1971 continue;
1972 } else if (User->getParent() == BB)
1973 continue;
1974
1975 UsesToRename.push_back(&U);
1976 }
1977
1978 // Find debug values outside of the block
1979 findDbgValues(DbgValues, &I, &DbgVariableRecords);
1980 llvm::erase_if(DbgValues, [&](const DbgValueInst *DbgVal) {
1981 return DbgVal->getParent() == BB;
1982 });
1983 llvm::erase_if(DbgVariableRecords, [&](const DbgVariableRecord *DbgVarRec) {
1984 return DbgVarRec->getParent() == BB;
1985 });
1986
1987 // If there are no uses outside the block, we're done with this instruction.
1988 if (UsesToRename.empty() && DbgValues.empty() && DbgVariableRecords.empty())
1989 continue;
1990 LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
1991
1992 // We found a use of I outside of BB. Rename all uses of I that are outside
1993 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
1994 // with the two values we know.
1995 SSAUpdate.Initialize(I.getType(), I.getName());
1996 SSAUpdate.AddAvailableValue(BB, &I);
1997 SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]);
1998
1999 while (!UsesToRename.empty())
2000 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
2001 if (!DbgValues.empty() || !DbgVariableRecords.empty()) {
2002 SSAUpdate.UpdateDebugValues(&I, DbgValues);
2003 SSAUpdate.UpdateDebugValues(&I, DbgVariableRecords);
2004 DbgValues.clear();
2005 DbgVariableRecords.clear();
2006 }
2007
2008 LLVM_DEBUG(dbgs() << "\n");
2009 }
2010}
2011
2012/// Clone instructions in range [BI, BE) to NewBB. For PHI nodes, we only clone
2013/// arguments that come from PredBB. Return the map from the variables in the
2014/// source basic block to the variables in the newly created basic block.
2015
2019 BasicBlock *NewBB,
2020 BasicBlock *PredBB) {
2021 // We are going to have to map operands from the source basic block to the new
2022 // copy of the block 'NewBB'. If there are PHI nodes in the source basic
2023 // block, evaluate them to account for entry from PredBB.
2024
2025 // Retargets llvm.dbg.value to any renamed variables.
2026 auto RetargetDbgValueIfPossible = [&](Instruction *NewInst) -> bool {
2027 auto DbgInstruction = dyn_cast<DbgValueInst>(NewInst);
2028 if (!DbgInstruction)
2029 return false;
2030
2031 SmallSet<std::pair<Value *, Value *>, 16> OperandsToRemap;
2032 for (auto DbgOperand : DbgInstruction->location_ops()) {
2033 auto DbgOperandInstruction = dyn_cast<Instruction>(DbgOperand);
2034 if (!DbgOperandInstruction)
2035 continue;
2036
2037 auto I = ValueMapping.find(DbgOperandInstruction);
2038 if (I != ValueMapping.end()) {
2039 OperandsToRemap.insert(
2040 std::pair<Value *, Value *>(DbgOperand, I->second));
2041 }
2042 }
2043
2044 for (auto &[OldOp, MappedOp] : OperandsToRemap)
2045 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2046 return true;
2047 };
2048
2049 // Duplicate implementation of the above dbg.value code, using
2050 // DbgVariableRecords instead.
2051 auto RetargetDbgVariableRecordIfPossible = [&](DbgVariableRecord *DVR) {
2052 SmallSet<std::pair<Value *, Value *>, 16> OperandsToRemap;
2053 for (auto *Op : DVR->location_ops()) {
2054 Instruction *OpInst = dyn_cast<Instruction>(Op);
2055 if (!OpInst)
2056 continue;
2057
2058 auto I = ValueMapping.find(OpInst);
2059 if (I != ValueMapping.end())
2060 OperandsToRemap.insert({OpInst, I->second});
2061 }
2062
2063 for (auto &[OldOp, MappedOp] : OperandsToRemap)
2064 DVR->replaceVariableLocationOp(OldOp, MappedOp);
2065 };
2066
2067 BasicBlock *RangeBB = BI->getParent();
2068
2069 // Clone the phi nodes of the source basic block into NewBB. The resulting
2070 // phi nodes are trivial since NewBB only has one predecessor, but SSAUpdater
2071 // might need to rewrite the operand of the cloned phi.
2072 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2073 PHINode *NewPN = PHINode::Create(PN->getType(), 1, PN->getName(), NewBB);
2074 NewPN->addIncoming(PN->getIncomingValueForBlock(PredBB), PredBB);
2075 ValueMapping[PN] = NewPN;
2076 }
2077
2078 // Clone noalias scope declarations in the threaded block. When threading a
2079 // loop exit, we would otherwise end up with two idential scope declarations
2080 // visible at the same time.
2081 SmallVector<MDNode *> NoAliasScopes;
2082 DenseMap<MDNode *, MDNode *> ClonedScopes;
2083 LLVMContext &Context = PredBB->getContext();
2084 identifyNoAliasScopesToClone(BI, BE, NoAliasScopes);
2085 cloneNoAliasScopes(NoAliasScopes, ClonedScopes, "thread", Context);
2086
2087 auto CloneAndRemapDbgInfo = [&](Instruction *NewInst, Instruction *From) {
2088 auto DVRRange = NewInst->cloneDebugInfoFrom(From);
2089 for (DbgVariableRecord &DVR : filterDbgVars(DVRRange))
2090 RetargetDbgVariableRecordIfPossible(&DVR);
2091 };
2092
2093 // Clone the non-phi instructions of the source basic block into NewBB,
2094 // keeping track of the mapping and using it to remap operands in the cloned
2095 // instructions.
2096 for (; BI != BE; ++BI) {
2097 Instruction *New = BI->clone();
2098 New->setName(BI->getName());
2099 New->insertInto(NewBB, NewBB->end());
2100 ValueMapping[&*BI] = New;
2101 adaptNoAliasScopes(New, ClonedScopes, Context);
2102
2103 CloneAndRemapDbgInfo(New, &*BI);
2104
2105 if (RetargetDbgValueIfPossible(New))
2106 continue;
2107
2108 // Remap operands to patch up intra-block references.
2109 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2110 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2111 ValueToValueMapTy::iterator I = ValueMapping.find(Inst);
2112 if (I != ValueMapping.end())
2113 New->setOperand(i, I->second);
2114 }
2115 }
2116
2117 // There may be DbgVariableRecords on the terminator, clone directly from
2118 // marker to marker as there isn't an instruction there.
2119 if (BE != RangeBB->end() && BE->hasDbgRecords()) {
2120 // Dump them at the end.
2121 DbgMarker *Marker = RangeBB->getMarker(BE);
2122 DbgMarker *EndMarker = NewBB->createMarker(NewBB->end());
2123 auto DVRRange = EndMarker->cloneDebugInfoFrom(Marker, std::nullopt);
2124 for (DbgVariableRecord &DVR : filterDbgVars(DVRRange))
2125 RetargetDbgVariableRecordIfPossible(&DVR);
2126 }
2127
2128 return;
2129}
2130
2131/// Attempt to thread through two successive basic blocks.
2133 Value *Cond) {
2134 // Consider:
2135 //
2136 // PredBB:
2137 // %var = phi i32* [ null, %bb1 ], [ @a, %bb2 ]
2138 // %tobool = icmp eq i32 %cond, 0
2139 // br i1 %tobool, label %BB, label ...
2140 //
2141 // BB:
2142 // %cmp = icmp eq i32* %var, null
2143 // br i1 %cmp, label ..., label ...
2144 //
2145 // We don't know the value of %var at BB even if we know which incoming edge
2146 // we take to BB. However, once we duplicate PredBB for each of its incoming
2147 // edges (say, PredBB1 and PredBB2), we know the value of %var in each copy of
2148 // PredBB. Then we can thread edges PredBB1->BB and PredBB2->BB through BB.
2149
2150 // Require that BB end with a Branch for simplicity.
2151 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2152 if (!CondBr)
2153 return false;
2154
2155 // BB must have exactly one predecessor.
2156 BasicBlock *PredBB = BB->getSinglePredecessor();
2157 if (!PredBB)
2158 return false;
2159
2160 // Require that PredBB end with a conditional Branch. If PredBB ends with an
2161 // unconditional branch, we should be merging PredBB and BB instead. For
2162 // simplicity, we don't deal with a switch.
2163 BranchInst *PredBBBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2164 if (!PredBBBranch || PredBBBranch->isUnconditional())
2165 return false;
2166
2167 // If PredBB has exactly one incoming edge, we don't gain anything by copying
2168 // PredBB.
2169 if (PredBB->getSinglePredecessor())
2170 return false;
2171
2172 // Don't thread through PredBB if it contains a successor edge to itself, in
2173 // which case we would infinite loop. Suppose we are threading an edge from
2174 // PredPredBB through PredBB and BB to SuccBB with PredBB containing a
2175 // successor edge to itself. If we allowed jump threading in this case, we
2176 // could duplicate PredBB and BB as, say, PredBB.thread and BB.thread. Since
2177 // PredBB.thread has a successor edge to PredBB, we would immediately come up
2178 // with another jump threading opportunity from PredBB.thread through PredBB
2179 // and BB to SuccBB. This jump threading would repeatedly occur. That is, we
2180 // would keep peeling one iteration from PredBB.
2181 if (llvm::is_contained(successors(PredBB), PredBB))
2182 return false;
2183
2184 // Don't thread across a loop header.
2185 if (LoopHeaders.count(PredBB))
2186 return false;
2187
2188 // Avoid complication with duplicating EH pads.
2189 if (PredBB->isEHPad())
2190 return false;
2191
2192 // Find a predecessor that we can thread. For simplicity, we only consider a
2193 // successor edge out of BB to which we thread exactly one incoming edge into
2194 // PredBB.
2195 unsigned ZeroCount = 0;
2196 unsigned OneCount = 0;
2197 BasicBlock *ZeroPred = nullptr;
2198 BasicBlock *OnePred = nullptr;
2199 const DataLayout &DL = BB->getModule()->getDataLayout();
2200 for (BasicBlock *P : predecessors(PredBB)) {
2201 // If PredPred ends with IndirectBrInst, we can't handle it.
2202 if (isa<IndirectBrInst>(P->getTerminator()))
2203 continue;
2204 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2206 if (CI->isZero()) {
2207 ZeroCount++;
2208 ZeroPred = P;
2209 } else if (CI->isOne()) {
2210 OneCount++;
2211 OnePred = P;
2212 }
2213 }
2214 }
2215
2216 // Disregard complicated cases where we have to thread multiple edges.
2217 BasicBlock *PredPredBB;
2218 if (ZeroCount == 1) {
2219 PredPredBB = ZeroPred;
2220 } else if (OneCount == 1) {
2221 PredPredBB = OnePred;
2222 } else {
2223 return false;
2224 }
2225
2226 BasicBlock *SuccBB = CondBr->getSuccessor(PredPredBB == ZeroPred);
2227
2228 // If threading to the same block as we come from, we would infinite loop.
2229 if (SuccBB == BB) {
2230 LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
2231 << "' - would thread to self!\n");
2232 return false;
2233 }
2234
2235 // If threading this would thread across a loop header, don't thread the edge.
2236 // See the comments above findLoopHeaders for justifications and caveats.
2237 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2238 LLVM_DEBUG({
2239 bool BBIsHeader = LoopHeaders.count(BB);
2240 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2241 dbgs() << " Not threading across "
2242 << (BBIsHeader ? "loop header BB '" : "block BB '")
2243 << BB->getName() << "' to dest "
2244 << (SuccIsHeader ? "loop header BB '" : "block BB '")
2245 << SuccBB->getName()
2246 << "' - it might create an irreducible loop!\n";
2247 });
2248 return false;
2249 }
2250
2251 // Compute the cost of duplicating BB and PredBB.
2252 unsigned BBCost = getJumpThreadDuplicationCost(
2253 TTI, BB, BB->getTerminator(), BBDupThreshold);
2254 unsigned PredBBCost = getJumpThreadDuplicationCost(
2255 TTI, PredBB, PredBB->getTerminator(), BBDupThreshold);
2256
2257 // Give up if costs are too high. We need to check BBCost and PredBBCost
2258 // individually before checking their sum because getJumpThreadDuplicationCost
2259 // return (unsigned)~0 for those basic blocks that cannot be duplicated.
2260 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2261 BBCost + PredBBCost > BBDupThreshold) {
2262 LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
2263 << "' - Cost is too high: " << PredBBCost
2264 << " for PredBB, " << BBCost << "for BB\n");
2265 return false;
2266 }
2267
2268 // Now we are ready to duplicate PredBB.
2269 threadThroughTwoBasicBlocks(PredPredBB, PredBB, BB, SuccBB);
2270 return true;
2271}
2272
2274 BasicBlock *PredBB,
2275 BasicBlock *BB,
2276 BasicBlock *SuccBB) {
2277 LLVM_DEBUG(dbgs() << " Threading through '" << PredBB->getName() << "' and '"
2278 << BB->getName() << "'\n");
2279
2280 // Build BPI/BFI before any changes are made to IR.
2281 bool HasProfile = doesBlockHaveProfileData(BB);
2282 auto *BFI = getOrCreateBFI(HasProfile);
2283 auto *BPI = getOrCreateBPI(BFI != nullptr);
2284
2285 BranchInst *CondBr = cast<BranchInst>(BB->getTerminator());
2286 BranchInst *PredBBBranch = cast<BranchInst>(PredBB->getTerminator());
2287
2288 BasicBlock *NewBB =
2289 BasicBlock::Create(PredBB->getContext(), PredBB->getName() + ".thread",
2290 PredBB->getParent(), PredBB);
2291 NewBB->moveAfter(PredBB);
2292
2293 // Set the block frequency of NewBB.
2294 if (BFI) {
2295 assert(BPI && "It's expected BPI to exist along with BFI");
2296 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2297 BPI->getEdgeProbability(PredPredBB, PredBB);
2298 BFI->setBlockFreq(NewBB, NewBBFreq);
2299 }
2300
2301 // We are going to have to map operands from the original BB block to the new
2302 // copy of the block 'NewBB'. If there are PHI nodes in PredBB, evaluate them
2303 // to account for entry from PredPredBB.
2304 ValueToValueMapTy ValueMapping;
2305 cloneInstructions(ValueMapping, PredBB->begin(), PredBB->end(), NewBB,
2306 PredPredBB);
2307
2308 // Copy the edge probabilities from PredBB to NewBB.
2309 if (BPI)
2310 BPI->copyEdgeProbabilities(PredBB, NewBB);
2311
2312 // Update the terminator of PredPredBB to jump to NewBB instead of PredBB.
2313 // This eliminates predecessors from PredPredBB, which requires us to simplify
2314 // any PHI nodes in PredBB.
2315 Instruction *PredPredTerm = PredPredBB->getTerminator();
2316 for (unsigned i = 0, e = PredPredTerm->getNumSuccessors(); i != e; ++i)
2317 if (PredPredTerm->getSuccessor(i) == PredBB) {
2318 PredBB->removePredecessor(PredPredBB, true);
2319 PredPredTerm->setSuccessor(i, NewBB);
2320 }
2321
2322 addPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(0), PredBB, NewBB,
2323 ValueMapping);
2324 addPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(1), PredBB, NewBB,
2325 ValueMapping);
2326
2327 DTU->applyUpdatesPermissive(
2328 {{DominatorTree::Insert, NewBB, CondBr->getSuccessor(0)},
2329 {DominatorTree::Insert, NewBB, CondBr->getSuccessor(1)},
2330 {DominatorTree::Insert, PredPredBB, NewBB},
2331 {DominatorTree::Delete, PredPredBB, PredBB}});
2332
2333 updateSSA(PredBB, NewBB, ValueMapping);
2334
2335 // Clean up things like PHI nodes with single operands, dead instructions,
2336 // etc.
2337 SimplifyInstructionsInBlock(NewBB, TLI);
2338 SimplifyInstructionsInBlock(PredBB, TLI);
2339
2340 SmallVector<BasicBlock *, 1> PredsToFactor;
2341 PredsToFactor.push_back(NewBB);
2342 threadEdge(BB, PredsToFactor, SuccBB);
2343}
2344
2345/// tryThreadEdge - Thread an edge if it's safe and profitable to do so.
2347 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
2348 BasicBlock *SuccBB) {
2349 // If threading to the same block as we come from, we would infinite loop.
2350 if (SuccBB == BB) {
2351 LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
2352 << "' - would thread to self!\n");
2353 return false;
2354 }
2355
2356 // If threading this would thread across a loop header, don't thread the edge.
2357 // See the comments above findLoopHeaders for justifications and caveats.
2358 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2359 LLVM_DEBUG({
2360 bool BBIsHeader = LoopHeaders.count(BB);
2361 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2362 dbgs() << " Not threading across "
2363 << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
2364 << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")
2365 << SuccBB->getName() << "' - it might create an irreducible loop!\n";
2366 });
2367 return false;
2368 }
2369
2370 unsigned JumpThreadCost = getJumpThreadDuplicationCost(
2371 TTI, BB, BB->getTerminator(), BBDupThreshold);
2372 if (JumpThreadCost > BBDupThreshold) {
2373 LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
2374 << "' - Cost is too high: " << JumpThreadCost << "\n");
2375 return false;
2376 }
2377
2378 threadEdge(BB, PredBBs, SuccBB);
2379 return true;
2380}
2381
2382/// threadEdge - We have decided that it is safe and profitable to factor the
2383/// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB
2384/// across BB. Transform the IR to reflect this change.
2386 const SmallVectorImpl<BasicBlock *> &PredBBs,
2387 BasicBlock *SuccBB) {
2388 assert(SuccBB != BB && "Don't create an infinite loop");
2389
2390 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2391 "Don't thread across loop headers");
2392
2393 // Build BPI/BFI before any changes are made to IR.
2394 bool HasProfile = doesBlockHaveProfileData(BB);
2395 auto *BFI = getOrCreateBFI(HasProfile);
2396 auto *BPI = getOrCreateBPI(BFI != nullptr);
2397
2398 // And finally, do it! Start by factoring the predecessors if needed.
2399 BasicBlock *PredBB;
2400 if (PredBBs.size() == 1)
2401 PredBB = PredBBs[0];
2402 else {
2403 LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size()
2404 << " common predecessors.\n");
2405 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");
2406 }
2407
2408 // And finally, do it!
2409 LLVM_DEBUG(dbgs() << " Threading edge from '" << PredBB->getName()
2410 << "' to '" << SuccBB->getName()
2411 << ", across block:\n " << *BB << "\n");
2412
2413 LVI->threadEdge(PredBB, BB, SuccBB);
2414
2416 BB->getName()+".thread",
2417 BB->getParent(), BB);
2418 NewBB->moveAfter(PredBB);
2419
2420 // Set the block frequency of NewBB.
2421 if (BFI) {
2422 assert(BPI && "It's expected BPI to exist along with BFI");
2423 auto NewBBFreq =
2424 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2425 BFI->setBlockFreq(NewBB, NewBBFreq);
2426 }
2427
2428 // Copy all the instructions from BB to NewBB except the terminator.
2429 ValueToValueMapTy ValueMapping;
2430 cloneInstructions(ValueMapping, BB->begin(), std::prev(BB->end()), NewBB,
2431 PredBB);
2432
2433 // We didn't copy the terminator from BB over to NewBB, because there is now
2434 // an unconditional jump to SuccBB. Insert the unconditional jump.
2435 BranchInst *NewBI = BranchInst::Create(SuccBB, NewBB);
2436 NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc());
2437
2438 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
2439 // PHI nodes for NewBB now.
2440 addPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping);
2441
2442 // Update the terminator of PredBB to jump to NewBB instead of BB. This
2443 // eliminates predecessors from BB, which requires us to simplify any PHI
2444 // nodes in BB.
2445 Instruction *PredTerm = PredBB->getTerminator();
2446 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
2447 if (PredTerm->getSuccessor(i) == BB) {
2448 BB->removePredecessor(PredBB, true);
2449 PredTerm->setSuccessor(i, NewBB);
2450 }
2451
2452 // Enqueue required DT updates.
2453 DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB},
2454 {DominatorTree::Insert, PredBB, NewBB},
2455 {DominatorTree::Delete, PredBB, BB}});
2456
2457 updateSSA(BB, NewBB, ValueMapping);
2458
2459 // At this point, the IR is fully up to date and consistent. Do a quick scan
2460 // over the new instructions and zap any that are constants or dead. This
2461 // frequently happens because of phi translation.
2462 SimplifyInstructionsInBlock(NewBB, TLI);
2463
2464 // Update the edge weight from BB to SuccBB, which should be less than before.
2465 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
2466
2467 // Threaded an edge!
2468 ++NumThreads;
2469}
2470
2471/// Create a new basic block that will be the predecessor of BB and successor of
2472/// all blocks in Preds. When profile data is available, update the frequency of
2473/// this new block.
2474BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB,
2476 const char *Suffix) {
2478
2479 // Collect the frequencies of all predecessors of BB, which will be used to
2480 // update the edge weight of the result of splitting predecessors.
2482 auto *BFI = getBFI();
2483 if (BFI) {
2484 auto *BPI = getOrCreateBPI(true);
2485 for (auto *Pred : Preds)
2486 FreqMap.insert(std::make_pair(
2487 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2488 }
2489
2490 // In the case when BB is a LandingPad block we create 2 new predecessors
2491 // instead of just one.
2492 if (BB->isLandingPad()) {
2493 std::string NewName = std::string(Suffix) + ".split-lp";
2494 SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs);
2495 } else {
2496 NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
2497 }
2498
2499 std::vector<DominatorTree::UpdateType> Updates;
2500 Updates.reserve((2 * Preds.size()) + NewBBs.size());
2501 for (auto *NewBB : NewBBs) {
2502 BlockFrequency NewBBFreq(0);
2503 Updates.push_back({DominatorTree::Insert, NewBB, BB});
2504 for (auto *Pred : predecessors(NewBB)) {
2505 Updates.push_back({DominatorTree::Delete, Pred, BB});
2506 Updates.push_back({DominatorTree::Insert, Pred, NewBB});
2507 if (BFI) // Update frequencies between Pred -> NewBB.
2508 NewBBFreq += FreqMap.lookup(Pred);
2509 }
2510 if (BFI) // Apply the summed frequency to NewBB.
2511 BFI->setBlockFreq(NewBB, NewBBFreq);
2512 }
2513
2514 DTU->applyUpdatesPermissive(Updates);
2515 return NewBBs[0];
2516}
2517
2518bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
2519 const Instruction *TI = BB->getTerminator();
2520 if (!TI || TI->getNumSuccessors() < 2)
2521 return false;
2522
2523 return hasValidBranchWeightMD(*TI);
2524}
2525
2526/// Update the block frequency of BB and branch weight and the metadata on the
2527/// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 -
2528/// Freq(PredBB->BB) / Freq(BB->SuccBB).
2529void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
2530 BasicBlock *BB,
2531 BasicBlock *NewBB,
2532 BasicBlock *SuccBB,
2533 BlockFrequencyInfo *BFI,
2535 bool HasProfile) {
2536 assert(((BFI && BPI) || (!BFI && !BFI)) &&
2537 "Both BFI & BPI should either be set or unset");
2538
2539 if (!BFI) {
2540 assert(!HasProfile &&
2541 "It's expected to have BFI/BPI when profile info exists");
2542 return;
2543 }
2544
2545 // As the edge from PredBB to BB is deleted, we have to update the block
2546 // frequency of BB.
2547 auto BBOrigFreq = BFI->getBlockFreq(BB);
2548 auto NewBBFreq = BFI->getBlockFreq(NewBB);
2549 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);
2550 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2551 BFI->setBlockFreq(BB, BBNewFreq);
2552
2553 // Collect updated outgoing edges' frequencies from BB and use them to update
2554 // edge probabilities.
2555 SmallVector<uint64_t, 4> BBSuccFreq;
2556 for (BasicBlock *Succ : successors(BB)) {
2557 auto SuccFreq = (Succ == SuccBB)
2558 ? BB2SuccBBFreq - NewBBFreq
2559 : BBOrigFreq * BPI->getEdgeProbability(BB, Succ);
2560 BBSuccFreq.push_back(SuccFreq.getFrequency());
2561 }
2562
2563 uint64_t MaxBBSuccFreq = *llvm::max_element(BBSuccFreq);
2564
2566 if (MaxBBSuccFreq == 0)
2567 BBSuccProbs.assign(BBSuccFreq.size(),
2568 {1, static_cast<unsigned>(BBSuccFreq.size())});
2569 else {
2570 for (uint64_t Freq : BBSuccFreq)
2571 BBSuccProbs.push_back(
2572 BranchProbability::getBranchProbability(Freq, MaxBBSuccFreq));
2573 // Normalize edge probabilities so that they sum up to one.
2575 BBSuccProbs.end());
2576 }
2577
2578 // Update edge probabilities in BPI.
2579 BPI->setEdgeProbability(BB, BBSuccProbs);
2580
2581 // Update the profile metadata as well.
2582 //
2583 // Don't do this if the profile of the transformed blocks was statically
2584 // estimated. (This could occur despite the function having an entry
2585 // frequency in completely cold parts of the CFG.)
2586 //
2587 // In this case we don't want to suggest to subsequent passes that the
2588 // calculated weights are fully consistent. Consider this graph:
2589 //
2590 // check_1
2591 // 50% / |
2592 // eq_1 | 50%
2593 // \ |
2594 // check_2
2595 // 50% / |
2596 // eq_2 | 50%
2597 // \ |
2598 // check_3
2599 // 50% / |
2600 // eq_3 | 50%
2601 // \ |
2602 //
2603 // Assuming the blocks check_* all compare the same value against 1, 2 and 3,
2604 // the overall probabilities are inconsistent; the total probability that the
2605 // value is either 1, 2 or 3 is 150%.
2606 //
2607 // As a consequence if we thread eq_1 -> check_2 to check_3, check_2->check_3
2608 // becomes 0%. This is even worse if the edge whose probability becomes 0% is
2609 // the loop exit edge. Then based solely on static estimation we would assume
2610 // the loop was extremely hot.
2611 //
2612 // FIXME this locally as well so that BPI and BFI are consistent as well. We
2613 // shouldn't make edges extremely likely or unlikely based solely on static
2614 // estimation.
2615 if (BBSuccProbs.size() >= 2 && HasProfile) {
2617 for (auto Prob : BBSuccProbs)
2618 Weights.push_back(Prob.getNumerator());
2619
2620 auto TI = BB->getTerminator();
2621 setBranchWeights(*TI, Weights, hasBranchWeightOrigin(*TI));
2622 }
2623}
2624
2625/// duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch
2626/// to BB which contains an i1 PHI node and a conditional branch on that PHI.
2627/// If we can duplicate the contents of BB up into PredBB do so now, this
2628/// improves the odds that the branch will be on an analyzable instruction like
2629/// a compare.
2631 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) {
2632 assert(!PredBBs.empty() && "Can't handle an empty set");
2633
2634 // If BB is a loop header, then duplicating this block outside the loop would
2635 // cause us to transform this into an irreducible loop, don't do this.
2636 // See the comments above findLoopHeaders for justifications and caveats.
2637 if (LoopHeaders.count(BB)) {
2638 LLVM_DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName()
2639 << "' into predecessor block '" << PredBBs[0]->getName()
2640 << "' - it might create an irreducible loop!\n");
2641 return false;
2642 }
2643
2644 unsigned DuplicationCost = getJumpThreadDuplicationCost(
2645 TTI, BB, BB->getTerminator(), BBDupThreshold);
2646 if (DuplicationCost > BBDupThreshold) {
2647 LLVM_DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
2648 << "' - Cost is too high: " << DuplicationCost << "\n");
2649 return false;
2650 }
2651
2652 // And finally, do it! Start by factoring the predecessors if needed.
2653 std::vector<DominatorTree::UpdateType> Updates;
2654 BasicBlock *PredBB;
2655 if (PredBBs.size() == 1)
2656 PredBB = PredBBs[0];
2657 else {
2658 LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size()
2659 << " common predecessors.\n");
2660 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");
2661 }
2662 Updates.push_back({DominatorTree::Delete, PredBB, BB});
2663
2664 // Okay, we decided to do this! Clone all the instructions in BB onto the end
2665 // of PredBB.
2666 LLVM_DEBUG(dbgs() << " Duplicating block '" << BB->getName()
2667 << "' into end of '" << PredBB->getName()
2668 << "' to eliminate branch on phi. Cost: "
2669 << DuplicationCost << " block is:" << *BB << "\n");
2670
2671 // Unless PredBB ends with an unconditional branch, split the edge so that we
2672 // can just clone the bits from BB into the end of the new PredBB.
2673 BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2674
2675 if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
2676 BasicBlock *OldPredBB = PredBB;
2677 PredBB = SplitEdge(OldPredBB, BB);
2678 Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB});
2679 Updates.push_back({DominatorTree::Insert, PredBB, BB});
2680 Updates.push_back({DominatorTree::Delete, OldPredBB, BB});
2681 OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
2682 }
2683
2684 // We are going to have to map operands from the original BB block into the
2685 // PredBB block. Evaluate PHI nodes in BB.
2686 ValueToValueMapTy ValueMapping;
2687
2688 BasicBlock::iterator BI = BB->begin();
2689 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2690 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
2691 // Clone the non-phi instructions of BB into PredBB, keeping track of the
2692 // mapping and using it to remap operands in the cloned instructions.
2693 for (; BI != BB->end(); ++BI) {
2694 Instruction *New = BI->clone();
2695 New->insertInto(PredBB, OldPredBranch->getIterator());
2696
2697 // Remap operands to patch up intra-block references.
2698 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2699 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2700 ValueToValueMapTy::iterator I = ValueMapping.find(Inst);
2701 if (I != ValueMapping.end())
2702 New->setOperand(i, I->second);
2703 }
2704
2705 // Remap debug variable operands.
2706 remapDebugVariable(ValueMapping, New);
2707
2708 // If this instruction can be simplified after the operands are updated,
2709 // just use the simplified value instead. This frequently happens due to
2710 // phi translation.
2712 New,
2713 {BB->getModule()->getDataLayout(), TLI, nullptr, nullptr, New})) {
2714 ValueMapping[&*BI] = IV;
2715 if (!New->mayHaveSideEffects()) {
2716 New->eraseFromParent();
2717 New = nullptr;
2718 // Clone debug-info on the elided instruction to the destination
2719 // position.
2720 OldPredBranch->cloneDebugInfoFrom(&*BI, std::nullopt, true);
2721 }
2722 } else {
2723 ValueMapping[&*BI] = New;
2724 }
2725 if (New) {
2726 // Otherwise, insert the new instruction into the block.
2727 New->setName(BI->getName());
2728 // Clone across any debug-info attached to the old instruction.
2729 New->cloneDebugInfoFrom(&*BI);
2730 // Update Dominance from simplified New instruction operands.
2731 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2732 if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2733 Updates.push_back({DominatorTree::Insert, PredBB, SuccBB});
2734 }
2735 }
2736
2737 // Check to see if the targets of the branch had PHI nodes. If so, we need to
2738 // add entries to the PHI nodes for branch from PredBB now.
2739 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
2740 addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
2741 ValueMapping);
2742 addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB,
2743 ValueMapping);
2744
2745 updateSSA(BB, PredBB, ValueMapping);
2746
2747 // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
2748 // that we nuked.
2749 BB->removePredecessor(PredBB, true);
2750
2751 // Remove the unconditional branch at the end of the PredBB block.
2752 OldPredBranch->eraseFromParent();
2753 if (auto *BPI = getBPI())
2754 BPI->copyEdgeProbabilities(BB, PredBB);
2755 DTU->applyUpdatesPermissive(Updates);
2756
2757 ++NumDupes;
2758 return true;
2759}
2760
2761// Pred is a predecessor of BB with an unconditional branch to BB. SI is
2762// a Select instruction in Pred. BB has other predecessors and SI is used in
2763// a PHI node in BB. SI has no other use.
2764// A new basic block, NewBB, is created and SI is converted to compare and
2765// conditional branch. SI is erased from parent.
2767 SelectInst *SI, PHINode *SIUse,
2768 unsigned Idx) {
2769 // Expand the select.
2770 //
2771 // Pred --
2772 // | v
2773 // | NewBB
2774 // | |
2775 // |-----
2776 // v
2777 // BB
2778 BranchInst *PredTerm = cast<BranchInst>(Pred->getTerminator());
2779 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
2780 BB->getParent(), BB);
2781 // Move the unconditional branch to NewBB.
2782 PredTerm->removeFromParent();
2783 PredTerm->insertInto(NewBB, NewBB->end());
2784 // Create a conditional branch and update PHI nodes.
2785 auto *BI = BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
2786 BI->applyMergedLocation(PredTerm->getDebugLoc(), SI->getDebugLoc());
2787 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2788 SIUse->setIncomingValue(Idx, SI->getFalseValue());
2789 SIUse->addIncoming(SI->getTrueValue(), NewBB);
2790
2791 uint64_t TrueWeight = 1;
2792 uint64_t FalseWeight = 1;
2793 // Copy probabilities from 'SI' to created conditional branch in 'Pred'.
2794 if (extractBranchWeights(*SI, TrueWeight, FalseWeight) &&
2795 (TrueWeight + FalseWeight) != 0) {
2798 TrueWeight, TrueWeight + FalseWeight));
2800 FalseWeight, TrueWeight + FalseWeight));
2801 // Update BPI if exists.
2802 if (auto *BPI = getBPI())
2803 BPI->setEdgeProbability(Pred, BP);
2804 }
2805 // Set the block frequency of NewBB.
2806 if (auto *BFI = getBFI()) {
2807 if ((TrueWeight + FalseWeight) == 0) {
2808 TrueWeight = 1;
2809 FalseWeight = 1;
2810 }
2812 TrueWeight, TrueWeight + FalseWeight);
2813 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2814 BFI->setBlockFreq(NewBB, NewBBFreq);
2815 }
2816
2817 // The select is now dead.
2818 SI->eraseFromParent();
2819 DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB},
2820 {DominatorTree::Insert, Pred, NewBB}});
2821
2822 // Update any other PHI nodes in BB.
2823 for (BasicBlock::iterator BI = BB->begin();
2824 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2825 if (Phi != SIUse)
2826 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2827}
2828
2830 PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2831
2832 if (!CondPHI || CondPHI->getParent() != BB)
2833 return false;
2834
2835 for (unsigned I = 0, E = CondPHI->getNumIncomingValues(); I != E; ++I) {
2836 BasicBlock *Pred = CondPHI->getIncomingBlock(I);
2837 SelectInst *PredSI = dyn_cast<SelectInst>(CondPHI->getIncomingValue(I));
2838
2839 // The second and third condition can be potentially relaxed. Currently
2840 // the conditions help to simplify the code and allow us to reuse existing
2841 // code, developed for tryToUnfoldSelect(CmpInst *, BasicBlock *)
2842 if (!PredSI || PredSI->getParent() != Pred || !PredSI->hasOneUse())
2843 continue;
2844
2845 BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2846 if (!PredTerm || !PredTerm->isUnconditional())
2847 continue;
2848
2849 unfoldSelectInstr(Pred, BB, PredSI, CondPHI, I);
2850 return true;
2851 }
2852 return false;
2853}
2854
2855/// tryToUnfoldSelect - Look for blocks of the form
2856/// bb1:
2857/// %a = select
2858/// br bb2
2859///
2860/// bb2:
2861/// %p = phi [%a, %bb1] ...
2862/// %c = icmp %p
2863/// br i1 %c
2864///
2865/// And expand the select into a branch structure if one of its arms allows %c
2866/// to be folded. This later enables threading from bb1 over bb2.
2868 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2869 PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0));
2870 Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1));
2871
2872 if (!CondBr || !CondBr->isConditional() || !CondLHS ||
2873 CondLHS->getParent() != BB)
2874 return false;
2875
2876 for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
2877 BasicBlock *Pred = CondLHS->getIncomingBlock(I);
2878 SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I));
2879
2880 // Look if one of the incoming values is a select in the corresponding
2881 // predecessor.
2882 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2883 continue;
2884
2885 BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2886 if (!PredTerm || !PredTerm->isUnconditional())
2887 continue;
2888
2889 // Now check if one of the select values would allow us to constant fold the
2890 // terminator in BB. We don't do the transform if both sides fold, those
2891 // cases will be threaded in any case.
2892 LazyValueInfo::Tristate LHSFolds =
2893 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),
2894 CondRHS, Pred, BB, CondCmp);
2895 LazyValueInfo::Tristate RHSFolds =
2896 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),
2897 CondRHS, Pred, BB, CondCmp);
2898 if ((LHSFolds != LazyValueInfo::Unknown ||
2899 RHSFolds != LazyValueInfo::Unknown) &&
2900 LHSFolds != RHSFolds) {
2901 unfoldSelectInstr(Pred, BB, SI, CondLHS, I);
2902 return true;
2903 }
2904 }
2905 return false;
2906}
2907
2908/// tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the
2909/// same BB in the form
2910/// bb:
2911/// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ...
2912/// %s = select %p, trueval, falseval
2913///
2914/// or
2915///
2916/// bb:
2917/// %p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ...
2918/// %c = cmp %p, 0
2919/// %s = select %c, trueval, falseval
2920///
2921/// And expand the select into a branch structure. This later enables
2922/// jump-threading over bb in this pass.
2923///
2924/// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
2925/// select if the associated PHI has at least one constant. If the unfolded
2926/// select is not jump-threaded, it will be folded again in the later
2927/// optimizations.
2929 // This transform would reduce the quality of msan diagnostics.
2930 // Disable this transform under MemorySanitizer.
2931 if (BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
2932 return false;
2933
2934 // If threading this would thread across a loop header, don't thread the edge.
2935 // See the comments above findLoopHeaders for justifications and caveats.
2936 if (LoopHeaders.count(BB))
2937 return false;
2938
2939 for (BasicBlock::iterator BI = BB->begin();
2940 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2941 // Look for a Phi having at least one constant incoming value.
2942 if (llvm::all_of(PN->incoming_values(),
2943 [](Value *V) { return !isa<ConstantInt>(V); }))
2944 continue;
2945
2946 auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) {
2947 using namespace PatternMatch;
2948
2949 // Check if SI is in BB and use V as condition.
2950 if (SI->getParent() != BB)
2951 return false;
2952 Value *Cond = SI->getCondition();
2953 bool IsAndOr = match(SI, m_CombineOr(m_LogicalAnd(), m_LogicalOr()));
2954 return Cond && Cond == V && Cond->getType()->isIntegerTy(1) && !IsAndOr;
2955 };
2956
2957 SelectInst *SI = nullptr;
2958 for (Use &U : PN->uses()) {
2959 if (ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2960 // Look for a ICmp in BB that compares PN with a constant and is the
2961 // condition of a Select.
2962 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2963 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2964 if (SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2965 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2966 SI = SelectI;
2967 break;
2968 }
2969 } else if (SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2970 // Look for a Select in BB that uses PN as condition.
2971 if (isUnfoldCandidate(SelectI, U.get())) {
2972 SI = SelectI;
2973 break;
2974 }
2975 }
2976 }
2977
2978 if (!SI)
2979 continue;
2980 // Expand the select.
2981 Value *Cond = SI->getCondition();
2982 if (!isGuaranteedNotToBeUndefOrPoison(Cond, nullptr, SI))
2983 Cond = new FreezeInst(Cond, "cond.fr", SI->getIterator());
2984 MDNode *BranchWeights = getBranchWeightMDNode(*SI);
2985 Instruction *Term =
2986 SplitBlockAndInsertIfThen(Cond, SI, false, BranchWeights);
2987 BasicBlock *SplitBB = SI->getParent();
2988 BasicBlock *NewBB = Term->getParent();
2989 PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI->getIterator());
2990 NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
2991 NewPN->addIncoming(SI->getFalseValue(), BB);
2992 NewPN->setDebugLoc(SI->getDebugLoc());
2993 SI->replaceAllUsesWith(NewPN);
2994 SI->eraseFromParent();
2995 // NewBB and SplitBB are newly created blocks which require insertion.
2996 std::vector<DominatorTree::UpdateType> Updates;
2997 Updates.reserve((2 * SplitBB->getTerminator()->getNumSuccessors()) + 3);
2998 Updates.push_back({DominatorTree::Insert, BB, SplitBB});
2999 Updates.push_back({DominatorTree::Insert, BB, NewBB});
3000 Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
3001 // BB's successors were moved to SplitBB, update DTU accordingly.
3002 for (auto *Succ : successors(SplitBB)) {
3003 Updates.push_back({DominatorTree::Delete, BB, Succ});
3004 Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
3005 }
3006 DTU->applyUpdatesPermissive(Updates);
3007 return true;
3008 }
3009 return false;
3010}
3011
3012/// Try to propagate a guard from the current BB into one of its predecessors
3013/// in case if another branch of execution implies that the condition of this
3014/// guard is always true. Currently we only process the simplest case that
3015/// looks like:
3016///
3017/// Start:
3018/// %cond = ...
3019/// br i1 %cond, label %T1, label %F1
3020/// T1:
3021/// br label %Merge
3022/// F1:
3023/// br label %Merge
3024/// Merge:
3025/// %condGuard = ...
3026/// call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
3027///
3028/// And cond either implies condGuard or !condGuard. In this case all the
3029/// instructions before the guard can be duplicated in both branches, and the
3030/// guard is then threaded to one of them.
3032 using namespace PatternMatch;
3033
3034 // We only want to deal with two predecessors.
3035 BasicBlock *Pred1, *Pred2;
3036 auto PI = pred_begin(BB), PE = pred_end(BB);
3037 if (PI == PE)
3038 return false;
3039 Pred1 = *PI++;
3040 if (PI == PE)
3041 return false;
3042 Pred2 = *PI++;
3043 if (PI != PE)
3044 return false;
3045 if (Pred1 == Pred2)
3046 return false;
3047
3048 // Try to thread one of the guards of the block.
3049 // TODO: Look up deeper than to immediate predecessor?
3050 auto *Parent = Pred1->getSinglePredecessor();
3051 if (!Parent || Parent != Pred2->getSinglePredecessor())
3052 return false;
3053
3054 if (auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
3055 for (auto &I : *BB)
3056 if (isGuard(&I) && threadGuard(BB, cast<IntrinsicInst>(&I), BI))
3057 return true;
3058
3059 return false;
3060}
3061
3062/// Try to propagate the guard from BB which is the lower block of a diamond
3063/// to one of its branches, in case if diamond's condition implies guard's
3064/// condition.
3066 BranchInst *BI) {
3067 assert(BI->getNumSuccessors() == 2 && "Wrong number of successors?");
3068 assert(BI->isConditional() && "Unconditional branch has 2 successors?");
3069 Value *GuardCond = Guard->getArgOperand(0);
3070 Value *BranchCond = BI->getCondition();
3071 BasicBlock *TrueDest = BI->getSuccessor(0);
3072 BasicBlock *FalseDest = BI->getSuccessor(1);
3073
3074 auto &DL = BB->getModule()->getDataLayout();
3075 bool TrueDestIsSafe = false;
3076 bool FalseDestIsSafe = false;
3077
3078 // True dest is safe if BranchCond => GuardCond.
3079 auto Impl = isImpliedCondition(BranchCond, GuardCond, DL);
3080 if (Impl && *Impl)
3081 TrueDestIsSafe = true;
3082 else {
3083 // False dest is safe if !BranchCond => GuardCond.
3084 Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
3085 if (Impl && *Impl)
3086 FalseDestIsSafe = true;
3087 }
3088
3089 if (!TrueDestIsSafe && !FalseDestIsSafe)
3090 return false;
3091
3092 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3093 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3094
3095 ValueToValueMapTy UnguardedMapping, GuardedMapping;
3096 Instruction *AfterGuard = Guard->getNextNode();
3097 unsigned Cost =
3098 getJumpThreadDuplicationCost(TTI, BB, AfterGuard, BBDupThreshold);
3099 if (Cost > BBDupThreshold)
3100 return false;
3101 // Duplicate all instructions before the guard and the guard itself to the
3102 // branch where implication is not proved.
3104 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3105 assert(GuardedBlock && "Could not create the guarded block?");
3106 // Duplicate all instructions before the guard in the unguarded branch.
3107 // Since we have successfully duplicated the guarded block and this block
3108 // has fewer instructions, we expect it to succeed.
3110 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3111 assert(UnguardedBlock && "Could not create the unguarded block?");
3112 LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
3113 << GuardedBlock->getName() << "\n");
3114 // Some instructions before the guard may still have uses. For them, we need
3115 // to create Phi nodes merging their copies in both guarded and unguarded
3116 // branches. Those instructions that have no uses can be just removed.
3118 for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
3119 if (!isa<PHINode>(&*BI))
3120 ToRemove.push_back(&*BI);
3121
3122 BasicBlock::iterator InsertionPoint = BB->getFirstInsertionPt();
3123 assert(InsertionPoint != BB->end() && "Empty block?");
3124 // Substitute with Phis & remove.
3125 for (auto *Inst : reverse(ToRemove)) {
3126 if (!Inst->use_empty()) {
3127 PHINode *NewPN = PHINode::Create(Inst->getType(), 2);
3128 NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3129 NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
3130 NewPN->setDebugLoc(Inst->getDebugLoc());
3131 NewPN->insertBefore(InsertionPoint);
3132 Inst->replaceAllUsesWith(NewPN);
3133 }
3134 Inst->dropDbgRecords();
3135 Inst->eraseFromParent();
3136 }
3137 return true;
3138}
3139
3140PreservedAnalyses JumpThreadingPass::getPreservedAnalysis() const {
3144
3145 // TODO: We would like to preserve BPI/BFI. Enable once all paths update them.
3146 // TODO: Would be nice to verify BPI/BFI consistency as well.
3147 return PA;
3148}
3149
3150template <typename AnalysisT>
3151typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
3152 assert(FAM && "Can't run external analysis without FunctionAnalysisManager");
3153
3154 // If there were no changes since last call to 'runExternalAnalysis' then all
3155 // analysis is either up to date or explicitly invalidated. Just go ahead and
3156 // run the "external" analysis.
3157 if (!ChangedSinceLastAnalysisUpdate) {
3158 assert(!DTU->hasPendingUpdates() &&
3159 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
3160 // Run the "external" analysis.
3161 return &FAM->getResult<AnalysisT>(*F);
3162 }
3163 ChangedSinceLastAnalysisUpdate = false;
3164
3165 auto PA = getPreservedAnalysis();
3166 // TODO: This shouldn't be needed once 'getPreservedAnalysis' reports BPI/BFI
3167 // as preserved.
3168 PA.preserve<BranchProbabilityAnalysis>();
3169 PA.preserve<BlockFrequencyAnalysis>();
3170 // Report everything except explicitly preserved as invalid.
3171 FAM->invalidate(*F, PA);
3172 // Update DT/PDT.
3173 DTU->flush();
3174 // Make sure DT/PDT are valid before running "external" analysis.
3175 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3176 assert((!DTU->hasPostDomTree() ||
3177 DTU->getPostDomTree().verify(
3179 // Run the "external" analysis.
3180 auto *Result = &FAM->getResult<AnalysisT>(*F);
3181 // Update analysis JumpThreading depends on and not explicitly preserved.
3182 TTI = &FAM->getResult<TargetIRAnalysis>(*F);
3183 TLI = &FAM->getResult<TargetLibraryAnalysis>(*F);
3184 AA = &FAM->getResult<AAManager>(*F);
3185
3186 return Result;
3187}
3188
3189BranchProbabilityInfo *JumpThreadingPass::getBPI() {
3190 if (!BPI) {
3191 assert(FAM && "Can't create BPI without FunctionAnalysisManager");
3193 }
3194 return *BPI;
3195}
3196
3197BlockFrequencyInfo *JumpThreadingPass::getBFI() {
3198 if (!BFI) {
3199 assert(FAM && "Can't create BFI without FunctionAnalysisManager");
3201 }
3202 return *BFI;
3203}
3204
3205// Important note on validity of BPI/BFI. JumpThreading tries to preserve
3206// BPI/BFI as it goes. Thus if cached instance exists it will be updated.
3207// Otherwise, new instance of BPI/BFI is created (up to date by definition).
3208BranchProbabilityInfo *JumpThreadingPass::getOrCreateBPI(bool Force) {
3209 auto *Res = getBPI();
3210 if (Res)
3211 return Res;
3212
3213 if (Force)
3214 BPI = runExternalAnalysis<BranchProbabilityAnalysis>();
3215
3216 return *BPI;
3217}
3218
3219BlockFrequencyInfo *JumpThreadingPass::getOrCreateBFI(bool Force) {
3220 auto *Res = getBFI();
3221 if (Res)
3222 return Res;
3223
3224 if (Force)
3225 BFI = runExternalAnalysis<BlockFrequencyAnalysis>();
3226
3227 return *BFI;
3228}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
ReachingDefAnalysis InstSet & ToRemove
static const Function * getParent(const Value *V)
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
uint64_t Size
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static unsigned getBestDestForJumpOnUndef(BasicBlock *BB)
GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump,...
static cl::opt< unsigned > PhiDuplicateThreshold("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden)
static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)
static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
static cl::opt< bool > ThreadAcrossLoopHeaders("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden)
static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI, BasicBlock *BB, Instruction *StopAt, unsigned Threshold)
Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction...
static void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, ValueToValueMapTy &ValueMap)
addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.
static BasicBlock * findMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)
findMostPopularDest - The specified list contains multiple possible threadable destinations.
static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)
getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...
static cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)
static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
Return true if Op is an instruction defined in the given block.
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)
static bool hasAddressTakenAndUsed(BasicBlock *BB)
See the comments on JumpThreadingPass.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:528
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
This file contains the declarations for metadata subclasses.
Module.h This file contains the declarations for the Module class.
#define P(N)
ppc ctr loops verify
This header defines various interfaces for pass management in LLVM.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
This defines the Use class.
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:78
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:492
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:443
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:430
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:499
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:409
DbgMarker * createMarker(Instruction *I)
Attach a DbgMarker to the given instruction.
Definition: BasicBlock.cpp:52
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:640
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:166
const Instruction & front() const
Definition: BasicBlock.h:453
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:199
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:284
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:474
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:452
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
DbgMarker * getMarker(InstListType::iterator It)
Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:672
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:657
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:221
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:289
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:509
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
void disableDominatorTree()
Disable the use of the dominator tree during alias analysis queries.
The address of a basic block.
Definition: Constants.h:890
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1833
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
uint32_t getNumerator() const
BranchProbability getCompl() const
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1695
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:601
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:983
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:993
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:1105
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2561
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:212
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:850
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:206
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:857
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:864
This class represents a range of values.
Definition: ConstantRange.h:47
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This is an important base class in LLVM.
Definition: Constant.h:41
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:723
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Per-instruction record of debug-info.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(DbgMarker *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere, bool InsertAtHead=false)
Clone all DbgMarkers from From into this marker.
const BasicBlock * getParent() const
This represents the llvm.dbg.value instruction.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
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:202
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
This class represents a freeze function that returns random concrete value if an operand is either a ...
const BasicBlock & getEntryBlock() const
Definition: Function.h:790
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:680
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:655
This instruction compares its operands according to the predicate given to the constructor.
Indirect Branch Instruction.
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: Instruction.cpp:91
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:454
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:83
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1720
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
Definition: Metadata.cpp:1706
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:252
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:451
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
bool isSpecialTerminator() const
Definition: Instruction.h:262
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:48
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)
Update the SSA form.
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, std::optional< BlockFrequencyInfo * > BFI, std::optional< BranchProbabilityInfo * > BPI)
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value *, 4 > &RecursionSet, Instruction *CxtI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
bool processImpliedCondition(BasicBlock *BB)
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
void threadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...
bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Analysis to compute lazy value information.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:61
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
void forgetValue(Value *V)
Remove information related to this value from the cache.
An instruction for reading from memory.
Definition: Instructions.h:185
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:246
bool isUnordered() const
Definition: Instructions.h:275
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Definition: Instructions.h:256
Align getAlign() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:237
static LocationSize precise(uint64_t Value)
Metadata node.
Definition: Metadata.h:1067
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
Representation for a specific memory location.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:193
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:293
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1814
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:40
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:188
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
void UpdateDebugValues(Instruction *I)
Rewrite debug value intrinsics to conform to a new SSA form.
Definition: SSAUpdater.cpp:200
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
This class represents the LLVM 'select' instruction.
size_type size() const
Definition: SmallPtrSet.h:94
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:717
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void resize(size_type N)
Definition: SmallVector.h:651
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Multiway switch.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool hasBranchDivergence(const Function *F=nullptr) const
Return true if branch divergence exists.
@ TCK_SizeAndLatency
The weighted sum of size and latency.
@ TCC_Free
Expected to fold away in lowering.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
'undef' values are things that do not have specified contents.
Definition: Constants.h:1395
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1795
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Value * getOperand(unsigned i) const
Definition: User.h:169
iterator find(const KeyT &Val)
Definition: ValueMap.h:155
iterator end()
Definition: ValueMap.h:135
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Definition: Value.cpp:1066
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:693
bool use_empty() const
Definition: Value.h:344
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
self_iterator getIterator()
Definition: ilist_node.h:109
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:316
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:1032
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:165
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:168
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:105
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:239
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
pred_iterator pred_end(BasicBlock *BB)
Definition: CFG.h:114
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:130
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:3470
auto successors(const MachineBasicBlock *BB)
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
Definition: Loads.cpp:584
void remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst)
Remap the operands of the debug records attached to Inst, and the operands of Inst itself if it's a d...
Definition: Local.cpp:3692
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:731
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, BatchAAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:455
bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:138
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:400
pred_iterator pred_begin(BasicBlock *BB)
Definition: CFG.h:110
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
Definition: GuardUtils.cpp:18
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
Definition: Local.cpp:1120
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
bool hasValidBranchWeightMD(const Instruction &I)
Checks if an instructions has valid Branch Weight Metadata.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
void cloneNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, DenseMap< MDNode *, MDNode * > &ClonedScopes, StringRef Ext, LLVMContext &Context)
Duplicate the specified list of noalias decl scopes.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:3345
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
Definition: Local.cpp:771
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1954
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
void adaptNoAliasScopes(llvm::Instruction *I, const DenseMap< MDNode *, MDNode * > &ClonedScopes, LLVMContext &Context)
Adapt the metadata for the specified instruction according to the provided mapping.
auto max_element(R &&Range)
Definition: STLExtras.h:1986
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2051
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1607
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
unsigned pred_size(const MachineBasicBlock *BB)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
Definition: CFG.cpp:34
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:760
Function object to check whether the second component of a container supported by std::get (like std:...
Definition: STLExtras.h:1459