blob: 566ebedc917b5ff290813dc8a4c23b3385e9256c [file] [log] [blame]
Chris Lattnerb3b60072008-04-20 20:35:01 +00001//===- JumpThreading.cpp - Thread control through conditional blocks ------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
Chris Lattner21157222008-04-20 21:13:06 +000010// This file implements the Jump Threading pass.
Chris Lattnerb3b60072008-04-20 20:35:01 +000011//
12//===----------------------------------------------------------------------===//
13
Sean Silva46590d52016-06-14 00:51:09 +000014#include "llvm/Transforms/Scalar/JumpThreading.h"
Chris Lattnerb3b60072008-04-20 20:35:01 +000015#include "llvm/Transforms/Scalar.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/STLExtras.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000019#include "llvm/ADT/Statistic.h"
James Molloyefbba722015-09-10 10:22:12 +000020#include "llvm/Analysis/GlobalsModRef.h"
Nick Lewycky0b682452013-07-27 01:24:00 +000021#include "llvm/Analysis/CFG.h"
Manman Ren72d44b12015-10-15 14:59:40 +000022#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
Owen Anderson92651ec2011-04-14 21:35:50 +000023#include "llvm/Analysis/ConstantFolding.h"
Chris Lattner800aad32009-11-09 23:00:14 +000024#include "llvm/Analysis/InstructionSimplify.h"
Dan Gohman826bdf82010-05-28 16:19:17 +000025#include "llvm/Analysis/Loads.h"
Manman Ren72d44b12015-10-15 14:59:40 +000026#include "llvm/Analysis/LoopInfo.h"
Sanjoy Das13e63a22015-10-28 21:27:08 +000027#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000028#include "llvm/IR/DataLayout.h"
29#include "llvm/IR/IntrinsicInst.h"
30#include "llvm/IR/LLVMContext.h"
Manman Ren72d44b12015-10-15 14:59:40 +000031#include "llvm/IR/MDBuilder.h"
Hal Finkelcc39b672014-07-24 12:16:19 +000032#include "llvm/IR/Metadata.h"
Sanjoy Das8b859c22017-02-17 04:21:14 +000033#include "llvm/IR/PatternMatch.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000034#include "llvm/Pass.h"
Chris Lattnerb3b60072008-04-20 20:35:01 +000035#include "llvm/Support/CommandLine.h"
Chris Lattner21157222008-04-20 21:13:06 +000036#include "llvm/Support/Debug.h"
Daniel Dunbar9813b0b2009-07-26 07:49:05 +000037#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000038#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Sanjoy Das8b859c22017-02-17 04:21:14 +000039#include "llvm/Transforms/Utils/Cloning.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000040#include "llvm/Transforms/Utils/Local.h"
41#include "llvm/Transforms/Utils/SSAUpdater.h"
Manman Ren72d44b12015-10-15 14:59:40 +000042#include <algorithm>
43#include <memory>
Chris Lattnerb3b60072008-04-20 20:35:01 +000044using namespace llvm;
Sean Silva46590d52016-06-14 00:51:09 +000045using namespace jumpthreading;
Chris Lattnerb3b60072008-04-20 20:35:01 +000046
Chandler Carruth964daaa2014-04-22 02:55:47 +000047#define DEBUG_TYPE "jump-threading"
48
Chris Lattnerff1c6e32008-04-20 22:39:42 +000049STATISTIC(NumThreads, "Number of jumps threaded");
50STATISTIC(NumFolds, "Number of terminators folded");
Chris Lattner97b14052009-10-11 07:24:57 +000051STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi");
Chris Lattnerb3b60072008-04-20 20:35:01 +000052
Chris Lattner21157222008-04-20 21:13:06 +000053static cl::opt<unsigned>
Michael Liaod1209162014-09-24 04:59:06 +000054BBDuplicateThreshold("jump-threading-threshold",
Chris Lattner21157222008-04-20 21:13:06 +000055 cl::desc("Max block size to duplicate for jump threading"),
56 cl::init(6), cl::Hidden);
57
Sanjoy Das13e63a22015-10-28 21:27:08 +000058static cl::opt<unsigned>
59ImplicationSearchThreshold(
60 "jump-threading-implication-search-threshold",
61 cl::desc("The number of predecessors to search for a stronger "
62 "condition to use to thread over a weaker condition"),
63 cl::init(3), cl::Hidden);
64
Chris Lattnerb3b60072008-04-20 20:35:01 +000065namespace {
Chris Lattnere7f0afe2008-05-09 04:43:13 +000066 /// This pass performs 'jump threading', which looks at blocks that have
67 /// multiple predecessors and multiple successors. If one or more of the
68 /// predecessors of the block can be proven to always jump to one of the
69 /// successors, we forward the edge from the predecessor to the successor by
70 /// duplicating the contents of this block.
71 ///
72 /// An example of when this can occur is code like this:
73 ///
74 /// if () { ...
75 /// X = 4;
76 /// }
77 /// if (X < 3) {
78 ///
79 /// In this case, the unconditional branch at the end of the first if can be
80 /// revectored to the false side of the second if.
81 ///
Chris Lattner2dd09db2009-09-02 06:11:42 +000082 class JumpThreading : public FunctionPass {
Sean Silva46590d52016-06-14 00:51:09 +000083 JumpThreadingPass Impl;
Frits van Bommel5e75ef42010-12-05 19:02:47 +000084
Chris Lattnerb3b60072008-04-20 20:35:01 +000085 public:
86 static char ID; // Pass identification
Sean Silva46590d52016-06-14 00:51:09 +000087 JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
Owen Anderson6c18d1a2010-10-19 17:21:58 +000088 initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
89 }
Chris Lattnerb3b60072008-04-20 20:35:01 +000090
Craig Topper3e4c6972014-03-05 09:10:37 +000091 bool runOnFunction(Function &F) override;
Frits van Bommel5e75ef42010-12-05 19:02:47 +000092
Craig Topper3e4c6972014-03-05 09:10:37 +000093 void getAnalysisUsage(AnalysisUsage &AU) const override {
Sean Silva687019f2016-06-13 22:01:25 +000094 AU.addRequired<LazyValueInfoWrapperPass>();
95 AU.addPreserved<LazyValueInfoWrapperPass>();
James Molloyefbba722015-09-10 10:22:12 +000096 AU.addPreserved<GlobalsAAWrapperPass>();
Chandler Carruthb98f63d2015-01-15 10:41:28 +000097 AU.addRequired<TargetLibraryInfoWrapperPass>();
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000098 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +000099
Sean Silva46590d52016-06-14 00:51:09 +0000100 void releaseMemory() override { Impl.releaseMemory(); }
Chris Lattnerb3b60072008-04-20 20:35:01 +0000101 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000102}
Chris Lattnerb3b60072008-04-20 20:35:01 +0000103
Dan Gohmand78c4002008-05-13 00:00:25 +0000104char JumpThreading::ID = 0;
Owen Anderson8ac477f2010-10-12 19:48:12 +0000105INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
106 "Jump Threading", false, false)
Sean Silva687019f2016-06-13 22:01:25 +0000107INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000108INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
Owen Anderson8ac477f2010-10-12 19:48:12 +0000109INITIALIZE_PASS_END(JumpThreading, "jump-threading",
Owen Andersondf7a4f22010-10-07 22:25:06 +0000110 "Jump Threading", false, false)
Dan Gohmand78c4002008-05-13 00:00:25 +0000111
Chris Lattnerb3b60072008-04-20 20:35:01 +0000112// Public interface to the Jump Threading pass
Michael Liaod1209162014-09-24 04:59:06 +0000113FunctionPass *llvm::createJumpThreadingPass(int Threshold) { return new JumpThreading(Threshold); }
Chris Lattnerb3b60072008-04-20 20:35:01 +0000114
Sean Silva46590d52016-06-14 00:51:09 +0000115JumpThreadingPass::JumpThreadingPass(int T) {
116 BBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);
117}
118
Chris Lattnerb3b60072008-04-20 20:35:01 +0000119/// runOnFunction - Top level algorithm.
120///
121bool JumpThreading::runOnFunction(Function &F) {
Andrew Kayloraa641a52016-04-22 22:06:11 +0000122 if (skipFunction(F))
Paul Robinsonaf4e64d2014-02-06 00:07:05 +0000123 return false;
Sean Silva46590d52016-06-14 00:51:09 +0000124 auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
125 auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
126 std::unique_ptr<BlockFrequencyInfo> BFI;
127 std::unique_ptr<BranchProbabilityInfo> BPI;
128 bool HasProfileData = F.getEntryCount().hasValue();
Sean Silvaf81328d2016-06-13 22:52:52 +0000129 if (HasProfileData) {
Sean Silva7d5a57c2016-06-14 00:26:31 +0000130 LoopInfo LI{DominatorTree(F)};
131 BPI.reset(new BranchProbabilityInfo(F, LI));
132 BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
Sean Silvaf81328d2016-06-13 22:52:52 +0000133 }
Sean Silva46590d52016-06-14 00:51:09 +0000134 return Impl.runImpl(F, TLI, LVI, HasProfileData, std::move(BFI),
135 std::move(BPI));
136}
137
138PreservedAnalyses JumpThreadingPass::run(Function &F,
Sean Silva36e0d012016-08-09 00:28:15 +0000139 FunctionAnalysisManager &AM) {
Sean Silva46590d52016-06-14 00:51:09 +0000140
141 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
142 auto &LVI = AM.getResult<LazyValueAnalysis>(F);
143 std::unique_ptr<BlockFrequencyInfo> BFI;
144 std::unique_ptr<BranchProbabilityInfo> BPI;
145 bool HasProfileData = F.getEntryCount().hasValue();
146 if (HasProfileData) {
147 LoopInfo LI{DominatorTree(F)};
148 BPI.reset(new BranchProbabilityInfo(F, LI));
149 BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
150 }
151 bool Changed =
152 runImpl(F, &TLI, &LVI, HasProfileData, std::move(BFI), std::move(BPI));
Sean Silvaf50d4b62016-07-06 19:05:41 +0000153
Sean Silva46590d52016-06-14 00:51:09 +0000154 if (!Changed)
155 return PreservedAnalyses::all();
156 PreservedAnalyses PA;
Sean Silva46590d52016-06-14 00:51:09 +0000157 PA.preserve<GlobalsAA>();
Sean Silvaf2db01c2016-07-02 16:16:44 +0000158 return PA;
Sean Silva46590d52016-06-14 00:51:09 +0000159}
160
161bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
162 LazyValueInfo *LVI_, bool HasProfileData_,
163 std::unique_ptr<BlockFrequencyInfo> BFI_,
164 std::unique_ptr<BranchProbabilityInfo> BPI_) {
165
166 DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
167 TLI = TLI_;
168 LVI = LVI_;
169 BFI.reset();
170 BPI.reset();
171 // When profile data is available, we need to update edge weights after
172 // successful jump threading, which requires both BPI and BFI being available.
173 HasProfileData = HasProfileData_;
Sanjoy Das8b859c22017-02-17 04:21:14 +0000174 auto *GuardDecl = F.getParent()->getFunction(
175 Intrinsic::getName(Intrinsic::experimental_guard));
176 HasGuards = GuardDecl && !GuardDecl->use_empty();
Sean Silva46590d52016-06-14 00:51:09 +0000177 if (HasProfileData) {
178 BPI = std::move(BPI_);
179 BFI = std::move(BFI_);
180 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000181
Dinesh Dwivedi8bb5fb02014-06-19 14:11:53 +0000182 // Remove unreachable blocks from function as they may result in infinite
183 // loop. We do threading if we found something profitable. Jump threading a
184 // branch can create other opportunities. If these opportunities form a cycle
David L Kreitzerda700ce2015-09-16 13:27:30 +0000185 // i.e. if any jump threading is undoing previous threading in the path, then
Dinesh Dwivedi8bb5fb02014-06-19 14:11:53 +0000186 // we will loop forever. We take care of this issue by not jump threading for
187 // back edges. This works for normal cases but not for unreachable blocks as
188 // they may have cycle with no back edge.
David Majnemerd9833ea2016-01-10 07:13:04 +0000189 bool EverChanged = false;
Igor Laevsky87f0d0e2016-06-16 16:25:53 +0000190 EverChanged |= removeUnreachableBlocks(F, LVI);
Dinesh Dwivedi657105e2014-06-17 14:34:19 +0000191
Chris Lattnerd579cb12009-05-04 02:28:08 +0000192 FindLoopHeaders(F);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000193
David Majnemerd9833ea2016-01-10 07:13:04 +0000194 bool Changed;
Benjamin Kramer76e27662010-01-07 13:50:07 +0000195 do {
196 Changed = false;
Chris Lattner595c7272008-12-03 07:48:08 +0000197 for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +0000198 BasicBlock *BB = &*I;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000199 // Thread all of the branches we can over this block.
Chris Lattner595c7272008-12-03 07:48:08 +0000200 while (ProcessBlock(BB))
Chris Lattnerff1c6e32008-04-20 22:39:42 +0000201 Changed = true;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000202
Chris Lattner595c7272008-12-03 07:48:08 +0000203 ++I;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000204
Chris Lattner595c7272008-12-03 07:48:08 +0000205 // If the block is trivially dead, zap it. This eliminates the successor
206 // edges which simplifies the CFG.
Ramkumar Ramachandra40c3e032015-01-13 03:46:47 +0000207 if (pred_empty(BB) &&
Chris Lattnere5983702008-12-08 22:44:07 +0000208 BB != &BB->getParent()->getEntryBlock()) {
David Greene1efdb452010-01-05 01:27:19 +0000209 DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
Chris Lattner97b14052009-10-11 07:24:57 +0000210 << "' with terminator: " << *BB->getTerminator() << '\n');
Chris Lattnerd579cb12009-05-04 02:28:08 +0000211 LoopHeaders.erase(BB);
Igor Laevsky87f0d0e2016-06-16 16:25:53 +0000212 LVI->eraseBlock(BB);
Chris Lattnerfa552d72009-05-04 16:29:24 +0000213 DeleteDeadBlock(BB);
Chris Lattner595c7272008-12-03 07:48:08 +0000214 Changed = true;
Chris Lattner73a58622010-12-13 02:38:13 +0000215 continue;
216 }
Owen Anderson92651ec2011-04-14 21:35:50 +0000217
Chris Lattner73a58622010-12-13 02:38:13 +0000218 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
Owen Anderson92651ec2011-04-14 21:35:50 +0000219
Chris Lattner73a58622010-12-13 02:38:13 +0000220 // Can't thread an unconditional jump, but if the block is "almost
221 // empty", we can replace uses of it with uses of the successor and make
222 // this dead.
Hyojin Sung4673f102016-03-29 04:08:57 +0000223 // We should not eliminate the loop header either, because eliminating
224 // a loop header might later prevent LoopSimplify from transforming nested
225 // loops into simplified form.
Chris Lattner73a58622010-12-13 02:38:13 +0000226 if (BI && BI->isUnconditional() &&
227 BB != &BB->getParent()->getEntryBlock() &&
Chris Lattner80e7e5a2009-11-10 21:40:01 +0000228 // If the terminator is the only non-phi instruction, try to nuke it.
Hyojin Sung4673f102016-03-29 04:08:57 +0000229 BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB)) {
Chris Lattner73a58622010-12-13 02:38:13 +0000230 // FIXME: It is always conservatively correct to drop the info
231 // for a block even if it doesn't get erased. This isn't totally
232 // awesome, but it allows us to use AssertingVH to prevent nasty
233 // dangling pointer issues within LazyValueInfo.
Igor Laevsky87f0d0e2016-06-16 16:25:53 +0000234 LVI->eraseBlock(BB);
Jun Bum Lim423406fd2017-02-01 19:06:55 +0000235 if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
Chris Lattner73a58622010-12-13 02:38:13 +0000236 Changed = true;
Chris Lattner595c7272008-12-03 07:48:08 +0000237 }
238 }
Chris Lattnerff1c6e32008-04-20 22:39:42 +0000239 EverChanged |= Changed;
Benjamin Kramer76e27662010-01-07 13:50:07 +0000240 } while (Changed);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000241
Chris Lattnerd579cb12009-05-04 02:28:08 +0000242 LoopHeaders.clear();
Chris Lattnerff1c6e32008-04-20 22:39:42 +0000243 return EverChanged;
Chris Lattnerb3b60072008-04-20 20:35:01 +0000244}
Chris Lattner21157222008-04-20 21:13:06 +0000245
Sanjoy Das8b859c22017-02-17 04:21:14 +0000246/// Return the cost of duplicating a piece of this block from first non-phi
247/// and before StopAt instruction to thread across it. Stop scanning the block
248/// when exceeding the threshold. If duplication is impossible, returns ~0U.
249static unsigned getJumpThreadDuplicationCost(BasicBlock *BB,
250 Instruction *StopAt,
Nadav Rotem23495312012-12-03 17:34:44 +0000251 unsigned Threshold) {
Sanjoy Das8b859c22017-02-17 04:21:14 +0000252 assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
Chris Lattner97b14052009-10-11 07:24:57 +0000253 /// Ignore PHI nodes, these will be flattened when duplication happens.
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +0000254 BasicBlock::const_iterator I(BB->getFirstNonPHI());
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000255
Chris Lattner3a2ae902009-11-11 00:21:58 +0000256 // FIXME: THREADING will delete values that are just used to compute the
257 // branch, so they shouldn't count against the duplication cost.
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000258
Geoff Berry43dc2852015-12-29 18:10:16 +0000259 unsigned Bonus = 0;
Sanjoy Das8b859c22017-02-17 04:21:14 +0000260 if (BB->getTerminator() == StopAt) {
261 // Threading through a switch statement is particularly profitable. If this
262 // block ends in a switch, decrease its cost to make it more likely to
263 // happen.
264 if (isa<SwitchInst>(StopAt))
265 Bonus = 6;
Geoff Berry43dc2852015-12-29 18:10:16 +0000266
Sanjoy Das8b859c22017-02-17 04:21:14 +0000267 // The same holds for indirect branches, but slightly more so.
268 if (isa<IndirectBrInst>(StopAt))
269 Bonus = 8;
270 }
Geoff Berry43dc2852015-12-29 18:10:16 +0000271
272 // Bump the threshold up so the early exit from the loop doesn't skip the
273 // terminator-based Size adjustment at the end.
274 Threshold += Bonus;
275
Chris Lattner97b14052009-10-11 07:24:57 +0000276 // Sum up the cost of each instruction until we get to the terminator. Don't
277 // include the terminator because the copy won't include it.
278 unsigned Size = 0;
Sanjoy Das8b859c22017-02-17 04:21:14 +0000279 for (; &*I != StopAt; ++I) {
Nadav Rotem23495312012-12-03 17:34:44 +0000280
281 // Stop scanning the block if we've reached the threshold.
282 if (Size > Threshold)
283 return Size;
284
Chris Lattner97b14052009-10-11 07:24:57 +0000285 // Debugger intrinsics don't incur code size.
286 if (isa<DbgInfoIntrinsic>(I)) continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000287
Chris Lattner97b14052009-10-11 07:24:57 +0000288 // If this is a pointer->pointer bitcast, it is free.
Duncan Sands19d0b472010-02-16 11:11:14 +0000289 if (isa<BitCastInst>(I) && I->getType()->isPointerTy())
Chris Lattner97b14052009-10-11 07:24:57 +0000290 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000291
David Majnemerb611e3f2015-08-14 05:09:07 +0000292 // Bail out if this instruction gives back a token type, it is not possible
David L Kreitzerda700ce2015-09-16 13:27:30 +0000293 // to duplicate it if it is used outside this BB.
David Majnemerb611e3f2015-08-14 05:09:07 +0000294 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
295 return ~0U;
296
Chris Lattner97b14052009-10-11 07:24:57 +0000297 // All other instructions count for at least one unit.
298 ++Size;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000299
Chris Lattner97b14052009-10-11 07:24:57 +0000300 // Calls are more expensive. If they are non-intrinsic calls, we model them
301 // as having cost of 4. If they are a non-vector intrinsic, we model them
302 // as having cost of 2 total, and if they are a vector intrinsic, we model
303 // them as having cost 1.
304 if (const CallInst *CI = dyn_cast<CallInst>(I)) {
Jingyue Wue84f6712015-08-31 06:10:27 +0000305 if (CI->cannotDuplicate() || CI->isConvergent())
James Molloy4f6fb952012-12-20 16:04:27 +0000306 // Blocks with NoDuplicate are modelled as having infinite cost, so they
307 // are never duplicated.
308 return ~0U;
309 else if (!isa<IntrinsicInst>(CI))
Chris Lattner97b14052009-10-11 07:24:57 +0000310 Size += 3;
Duncan Sands19d0b472010-02-16 11:11:14 +0000311 else if (!CI->getType()->isVectorTy())
Chris Lattner97b14052009-10-11 07:24:57 +0000312 Size += 1;
313 }
314 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000315
Geoff Berry43dc2852015-12-29 18:10:16 +0000316 return Size > Bonus ? Size - Bonus : 0;
Chris Lattner97b14052009-10-11 07:24:57 +0000317}
318
Chris Lattnerfa552d72009-05-04 16:29:24 +0000319/// FindLoopHeaders - We do not want jump threading to turn proper loop
Chris Lattnerd579cb12009-05-04 02:28:08 +0000320/// structures into irreducible loops. Doing this breaks up the loop nesting
321/// hierarchy and pessimizes later transformations. To prevent this from
322/// happening, we first have to find the loop headers. Here we approximate this
323/// by finding targets of backedges in the CFG.
324///
325/// Note that there definitely are cases when we want to allow threading of
326/// edges across a loop header. For example, threading a jump from outside the
327/// loop (the preheader) to an exit block of the loop is definitely profitable.
328/// It is also almost always profitable to thread backedges from within the loop
329/// to exit blocks, and is often profitable to thread backedges to other blocks
330/// within the loop (forming a nested loop). This simple analysis is not rich
331/// enough to track all of these properties and keep it up-to-date as the CFG
332/// mutates, so we don't allow any of these transformations.
333///
Sean Silva46590d52016-06-14 00:51:09 +0000334void JumpThreadingPass::FindLoopHeaders(Function &F) {
Chris Lattnerd579cb12009-05-04 02:28:08 +0000335 SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
336 FindFunctionBackedges(F, Edges);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000337
Benjamin Kramer543762d2016-01-09 18:43:01 +0000338 for (const auto &Edge : Edges)
339 LoopHeaders.insert(Edge.second);
Chris Lattnerd579cb12009-05-04 02:28:08 +0000340}
341
Frits van Bommel76244862010-12-05 19:06:41 +0000342/// getKnownConstant - Helper method to determine if we can thread over a
343/// terminator with the given value as its condition, and if so what value to
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000344/// use for that. What kind of value this is depends on whether we want an
345/// integer or a block address, but an undef is always accepted.
Frits van Bommel76244862010-12-05 19:06:41 +0000346/// Returns null if Val is null or not an appropriate constant.
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000347static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) {
Frits van Bommel76244862010-12-05 19:06:41 +0000348 if (!Val)
Craig Topperf40110f2014-04-25 05:29:35 +0000349 return nullptr;
Frits van Bommel76244862010-12-05 19:06:41 +0000350
351 // Undef is "known" enough.
352 if (UndefValue *U = dyn_cast<UndefValue>(Val))
353 return U;
354
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000355 if (Preference == WantBlockAddress)
356 return dyn_cast<BlockAddress>(Val->stripPointerCasts());
357
Frits van Bommel76244862010-12-05 19:06:41 +0000358 return dyn_cast<ConstantInt>(Val);
359}
360
Chris Lattner5ff7f562009-11-07 08:05:03 +0000361/// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000362/// if we can infer that the value is a known ConstantInt/BlockAddress or undef
363/// in any of our predecessors. If so, return the known list of value and pred
364/// BB in the result vector.
Chris Lattner5ff7f562009-11-07 08:05:03 +0000365///
Chris Lattner5ff7f562009-11-07 08:05:03 +0000366/// This returns true if there were any known values.
367///
Sean Silva46590d52016-06-14 00:51:09 +0000368bool JumpThreadingPass::ComputeValueKnownInPredecessors(
369 Value *V, BasicBlock *BB, PredValueInfo &Result,
370 ConstantPreference Preference, Instruction *CxtI) {
Owen Anderson6fdcb1722010-08-31 19:24:27 +0000371 // This method walks up use-def chains recursively. Because of this, we could
372 // get into an infinite loop going around loops in the use-def chain. To
373 // prevent this, keep track of what (value, block) pairs we've already visited
374 // and terminate the search if we loop back to them
Owen Anderson3997a072010-08-31 07:36:34 +0000375 if (!RecursionSet.insert(std::make_pair(V, BB)).second)
376 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000377
Owen Anderson6fdcb1722010-08-31 19:24:27 +0000378 // An RAII help to remove this pair from the recursion set once the recursion
379 // stack pops back out again.
380 RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB));
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000381
Frits van Bommel76244862010-12-05 19:06:41 +0000382 // If V is a constant, then it is known in all predecessors.
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000383 if (Constant *KC = getKnownConstant(V, Preference)) {
Benjamin Kramer543762d2016-01-09 18:43:01 +0000384 for (BasicBlock *Pred : predecessors(BB))
385 Result.push_back(std::make_pair(KC, Pred));
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000386
Haicheng Wub35f7722016-02-08 17:00:39 +0000387 return !Result.empty();
Chris Lattner5ff7f562009-11-07 08:05:03 +0000388 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000389
Chris Lattner5ff7f562009-11-07 08:05:03 +0000390 // If V is a non-instruction value, or an instruction in a different block,
391 // then it can't be derived from a PHI.
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000392 Instruction *I = dyn_cast<Instruction>(V);
Craig Topperf40110f2014-04-25 05:29:35 +0000393 if (!I || I->getParent() != BB) {
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000394
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000395 // Okay, if this is a live-in value, see if it has a known value at the end
396 // of any of our predecessors.
397 //
398 // FIXME: This should be an edge property, not a block end property.
399 /// TODO: Per PR2563, we could infer value range information about a
400 /// predecessor based on its terminator.
401 //
Owen Andersond361aac2010-09-14 20:57:41 +0000402 // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if
403 // "I" is a non-local compare-with-a-constant instruction. This would be
404 // able to handle value inequalities better, for example if the compare is
405 // "X < 4" and "X < 3" is known true but "X < 4" itself is not available.
406 // Perhaps getConstantOnEdge should be smart enough to do this?
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000407
Benjamin Kramer543762d2016-01-09 18:43:01 +0000408 for (BasicBlock *P : predecessors(BB)) {
Owen Andersond361aac2010-09-14 20:57:41 +0000409 // If the value is known by LazyValueInfo to be a constant in a
410 // predecessor, use that information to try to thread this block.
Hal Finkel7e184492014-09-07 20:29:59 +0000411 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000412 if (Constant *KC = getKnownConstant(PredCst, Preference))
Frits van Bommel76244862010-12-05 19:06:41 +0000413 Result.push_back(std::make_pair(KC, P));
Owen Andersond361aac2010-09-14 20:57:41 +0000414 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000415
Owen Andersond361aac2010-09-14 20:57:41 +0000416 return !Result.empty();
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000417 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000418
Chris Lattner5ff7f562009-11-07 08:05:03 +0000419 /// If I is a PHI node, then we know the incoming values for any constants.
420 if (PHINode *PN = dyn_cast<PHINode>(I)) {
421 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
422 Value *InVal = PN->getIncomingValue(i);
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000423 if (Constant *KC = getKnownConstant(InVal, Preference)) {
Frits van Bommel76244862010-12-05 19:06:41 +0000424 Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i)));
Owen Andersond361aac2010-09-14 20:57:41 +0000425 } else {
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000426 Constant *CI = LVI->getConstantOnEdge(InVal,
Hal Finkel7e184492014-09-07 20:29:59 +0000427 PN->getIncomingBlock(i),
428 BB, CxtI);
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000429 if (Constant *KC = getKnownConstant(CI, Preference))
430 Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i)));
Chris Lattner5ff7f562009-11-07 08:05:03 +0000431 }
432 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000433
Chris Lattner5ff7f562009-11-07 08:05:03 +0000434 return !Result.empty();
435 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000436
Haicheng Wu78738572016-03-16 04:52:52 +0000437 // Handle Cast instructions. Only see through Cast when the source operand is
438 // PHI or Cmp and the source type is i1 to save the compilation time.
439 if (CastInst *CI = dyn_cast<CastInst>(I)) {
440 Value *Source = CI->getOperand(0);
441 if (!Source->getType()->isIntegerTy(1))
442 return false;
443 if (!isa<PHINode>(Source) && !isa<CmpInst>(Source))
444 return false;
445 ComputeValueKnownInPredecessors(Source, BB, Result, Preference, CxtI);
446 if (Result.empty())
447 return false;
448
449 // Convert the known values.
450 for (auto &R : Result)
451 R.first = ConstantExpr::getCast(CI->getOpcode(), R.first, CI->getType());
452
453 return true;
454 }
455
Frits van Bommel76244862010-12-05 19:06:41 +0000456 PredValueInfoTy LHSVals, RHSVals;
Chris Lattner5ff7f562009-11-07 08:05:03 +0000457
458 // Handle some boolean conditions.
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000459 if (I->getType()->getPrimitiveSizeInBits() == 1) {
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000460 assert(Preference == WantInteger && "One-bit non-integer type?");
Chris Lattner5ff7f562009-11-07 08:05:03 +0000461 // X | true -> true
462 // X & false -> false
463 if (I->getOpcode() == Instruction::Or ||
464 I->getOpcode() == Instruction::And) {
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000465 ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000466 WantInteger, CxtI);
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000467 ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000468 WantInteger, CxtI);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000469
Owen Anderson6fdcb1722010-08-31 19:24:27 +0000470 if (LHSVals.empty() && RHSVals.empty())
Chris Lattner5ff7f562009-11-07 08:05:03 +0000471 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000472
Chris Lattner5ff7f562009-11-07 08:05:03 +0000473 ConstantInt *InterestingVal;
474 if (I->getOpcode() == Instruction::Or)
475 InterestingVal = ConstantInt::getTrue(I->getContext());
476 else
477 InterestingVal = ConstantInt::getFalse(I->getContext());
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000478
Chris Lattner3c603022010-08-18 03:14:36 +0000479 SmallPtrSet<BasicBlock*, 4> LHSKnownBBs;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000480
Chris Lattnerd924f632010-02-11 04:40:44 +0000481 // Scan for the sentinel. If we find an undef, force it to the
482 // interesting value: x|undef -> true and x&undef -> false.
Benjamin Kramer543762d2016-01-09 18:43:01 +0000483 for (const auto &LHSVal : LHSVals)
484 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
485 Result.emplace_back(InterestingVal, LHSVal.second);
486 LHSKnownBBs.insert(LHSVal.second);
Chris Lattnerd924f632010-02-11 04:40:44 +0000487 }
Benjamin Kramer543762d2016-01-09 18:43:01 +0000488 for (const auto &RHSVal : RHSVals)
489 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
Chris Lattnerbbc25ff2010-07-12 00:47:34 +0000490 // If we already inferred a value for this block on the LHS, don't
491 // re-add it.
Benjamin Kramer543762d2016-01-09 18:43:01 +0000492 if (!LHSKnownBBs.count(RHSVal.second))
493 Result.emplace_back(InterestingVal, RHSVal.second);
Chris Lattnerd924f632010-02-11 04:40:44 +0000494 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000495
Chris Lattner5ff7f562009-11-07 08:05:03 +0000496 return !Result.empty();
497 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000498
Chris Lattner9518fbb2009-11-10 22:39:16 +0000499 // Handle the NOT form of XOR.
500 if (I->getOpcode() == Instruction::Xor &&
501 isa<ConstantInt>(I->getOperand(1)) &&
502 cast<ConstantInt>(I->getOperand(1))->isOne()) {
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000503 ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result,
504 WantInteger, CxtI);
Owen Anderson6fdcb1722010-08-31 19:24:27 +0000505 if (Result.empty())
Chris Lattner9518fbb2009-11-10 22:39:16 +0000506 return false;
507
508 // Invert the known values.
Benjamin Kramer543762d2016-01-09 18:43:01 +0000509 for (auto &R : Result)
510 R.first = ConstantExpr::getNot(R.first);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000511
Chris Lattner9518fbb2009-11-10 22:39:16 +0000512 return true;
513 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000514
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000515 // Try to simplify some other binary operator values.
516 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000517 assert(Preference != WantBlockAddress
518 && "A binary operator creating a block address?");
Owen Anderson3c84ecb2010-08-31 20:26:04 +0000519 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
Frits van Bommel76244862010-12-05 19:06:41 +0000520 PredValueInfoTy LHSVals;
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000521 ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000522 WantInteger, CxtI);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000523
Owen Anderson3997a072010-08-31 07:36:34 +0000524 // Try to use constant folding to simplify the binary operator.
Benjamin Kramer543762d2016-01-09 18:43:01 +0000525 for (const auto &LHSVal : LHSVals) {
526 Constant *V = LHSVal.first;
Owen Anderson3c84ecb2010-08-31 20:26:04 +0000527 Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000528
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000529 if (Constant *KC = getKnownConstant(Folded, WantInteger))
Benjamin Kramer543762d2016-01-09 18:43:01 +0000530 Result.push_back(std::make_pair(KC, LHSVal.second));
Owen Anderson3997a072010-08-31 07:36:34 +0000531 }
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000532 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000533
Owen Anderson3997a072010-08-31 07:36:34 +0000534 return !Result.empty();
Chris Lattner5ff7f562009-11-07 08:05:03 +0000535 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000536
Chris Lattner5ff7f562009-11-07 08:05:03 +0000537 // Handle compare with phi operand, where the PHI is defined in this block.
538 if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000539 assert(Preference == WantInteger && "Compares only produce integers");
Chris Lattner5ff7f562009-11-07 08:05:03 +0000540 PHINode *PN = dyn_cast<PHINode>(Cmp->getOperand(0));
541 if (PN && PN->getParent() == BB) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000542 const DataLayout &DL = PN->getModule()->getDataLayout();
Chris Lattner5ff7f562009-11-07 08:05:03 +0000543 // We can do this simplification if any comparisons fold to true or false.
544 // See if any do.
545 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
546 BasicBlock *PredBB = PN->getIncomingBlock(i);
547 Value *LHS = PN->getIncomingValue(i);
548 Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000549
Rafael Espindola37dc9e12014-02-21 00:06:31 +0000550 Value *Res = SimplifyCmpInst(Cmp->getPredicate(), LHS, RHS, DL);
Craig Topperf40110f2014-04-25 05:29:35 +0000551 if (!Res) {
Owen Andersond361aac2010-09-14 20:57:41 +0000552 if (!isa<Constant>(RHS))
Chris Lattner5f6b8b22009-11-12 05:24:05 +0000553 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000554
555 LazyValueInfo::Tristate
Chris Lattner5f6b8b22009-11-12 05:24:05 +0000556 ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS,
Hal Finkel7e184492014-09-07 20:29:59 +0000557 cast<Constant>(RHS), PredBB, BB,
558 CxtI ? CxtI : Cmp);
Chris Lattner5f6b8b22009-11-12 05:24:05 +0000559 if (ResT == LazyValueInfo::Unknown)
560 continue;
561 Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT);
562 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000563
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000564 if (Constant *KC = getKnownConstant(Res, WantInteger))
565 Result.push_back(std::make_pair(KC, PredBB));
Chris Lattner5ff7f562009-11-07 08:05:03 +0000566 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000567
Chris Lattner5ff7f562009-11-07 08:05:03 +0000568 return !Result.empty();
569 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000570
Chris Lattner67146692009-11-11 22:31:38 +0000571 // If comparing a live-in value against a constant, see if we know the
572 // live-in value on any predecessors.
Owen Andersond361aac2010-09-14 20:57:41 +0000573 if (isa<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) {
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000574 if (!isa<Instruction>(Cmp->getOperand(0)) ||
Owen Andersonc910acb2010-08-30 23:22:36 +0000575 cast<Instruction>(Cmp->getOperand(0))->getParent() != BB) {
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000576 Constant *RHSCst = cast<Constant>(Cmp->getOperand(1));
Gabor Greifa5fa8852010-07-12 14:10:24 +0000577
Benjamin Kramer543762d2016-01-09 18:43:01 +0000578 for (BasicBlock *P : predecessors(BB)) {
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000579 // If the value is known by LazyValueInfo to be a constant in a
580 // predecessor, use that information to try to thread this block.
581 LazyValueInfo::Tristate Res =
582 LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0),
Hal Finkel7e184492014-09-07 20:29:59 +0000583 RHSCst, P, BB, CxtI ? CxtI : Cmp);
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000584 if (Res == LazyValueInfo::Unknown)
585 continue;
Chris Lattnerc893c4ed2009-11-12 04:37:50 +0000586
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000587 Constant *ResC = ConstantInt::get(Cmp->getType(), Res);
Frits van Bommel76244862010-12-05 19:06:41 +0000588 Result.push_back(std::make_pair(ResC, P));
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000589 }
590
591 return !Result.empty();
Chris Lattner67146692009-11-11 22:31:38 +0000592 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000593
Owen Anderson3997a072010-08-31 07:36:34 +0000594 // Try to find a constant value for the LHS of a comparison,
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000595 // and evaluate it statically if we can.
Owen Andersonc910acb2010-08-30 23:22:36 +0000596 if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) {
Frits van Bommel76244862010-12-05 19:06:41 +0000597 PredValueInfoTy LHSVals;
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000598 ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000599 WantInteger, CxtI);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000600
Benjamin Kramer543762d2016-01-09 18:43:01 +0000601 for (const auto &LHSVal : LHSVals) {
602 Constant *V = LHSVal.first;
Owen Anderson3c84ecb2010-08-31 20:26:04 +0000603 Constant *Folded = ConstantExpr::getCompare(Cmp->getPredicate(),
604 V, CmpConst);
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000605 if (Constant *KC = getKnownConstant(Folded, WantInteger))
Benjamin Kramer543762d2016-01-09 18:43:01 +0000606 Result.push_back(std::make_pair(KC, LHSVal.second));
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000607 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000608
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000609 return !Result.empty();
610 }
Chris Lattner67146692009-11-11 22:31:38 +0000611 }
Chris Lattner5ff7f562009-11-07 08:05:03 +0000612 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000613
Frits van Bommel3d180342010-12-15 09:51:20 +0000614 if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
615 // Handle select instructions where at least one operand is a known constant
616 // and we can figure out the condition value for any predecessor block.
617 Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference);
618 Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference);
619 PredValueInfoTy Conds;
620 if ((TrueVal || FalseVal) &&
621 ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +0000622 WantInteger, CxtI)) {
Benjamin Kramer543762d2016-01-09 18:43:01 +0000623 for (auto &C : Conds) {
624 Constant *Cond = C.first;
Frits van Bommel3d180342010-12-15 09:51:20 +0000625
626 // Figure out what value to use for the condition.
627 bool KnownCond;
628 if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) {
629 // A known boolean.
630 KnownCond = CI->isOne();
631 } else {
632 assert(isa<UndefValue>(Cond) && "Unexpected condition value");
633 // Either operand will do, so be sure to pick the one that's a known
634 // constant.
635 // FIXME: Do this more cleverly if both values are known constants?
Craig Topperf40110f2014-04-25 05:29:35 +0000636 KnownCond = (TrueVal != nullptr);
Frits van Bommel3d180342010-12-15 09:51:20 +0000637 }
638
639 // See if the select has a known constant value for this predecessor.
640 if (Constant *Val = KnownCond ? TrueVal : FalseVal)
Benjamin Kramer543762d2016-01-09 18:43:01 +0000641 Result.push_back(std::make_pair(Val, C.second));
Frits van Bommel3d180342010-12-15 09:51:20 +0000642 }
643
644 return !Result.empty();
645 }
646 }
647
Owen Andersond361aac2010-09-14 20:57:41 +0000648 // If all else fails, see if LVI can figure out a constant value for us.
Hal Finkel7e184492014-09-07 20:29:59 +0000649 Constant *CI = LVI->getConstant(V, BB, CxtI);
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000650 if (Constant *KC = getKnownConstant(CI, Preference)) {
Benjamin Kramer543762d2016-01-09 18:43:01 +0000651 for (BasicBlock *Pred : predecessors(BB))
652 Result.push_back(std::make_pair(KC, Pred));
Owen Andersonbd2ecc72010-08-26 17:40:24 +0000653 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000654
Owen Andersond361aac2010-09-14 20:57:41 +0000655 return !Result.empty();
Chris Lattner5ff7f562009-11-07 08:05:03 +0000656}
657
658
Chris Lattner3df4c152008-04-22 07:05:46 +0000659
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000660/// GetBestDestForBranchOnUndef - If we determine that the specified block ends
661/// in an undefined jump, decide which block is best to revector to.
662///
663/// Since we can pick an arbitrary destination, we pick the successor with the
664/// fewest predecessors. This should reduce the in-degree of the others.
665///
666static unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) {
667 TerminatorInst *BBTerm = BB->getTerminator();
668 unsigned MinSucc = 0;
669 BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
670 // Compute the successor with the minimum number of predecessors.
671 unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
672 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
673 TestBB = BBTerm->getSuccessor(i);
674 unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
Jakub Staszak423651e2011-06-27 21:51:12 +0000675 if (NumPreds < MinNumPreds) {
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000676 MinSucc = i;
Jakub Staszak423651e2011-06-27 21:51:12 +0000677 MinNumPreds = NumPreds;
678 }
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000679 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000680
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000681 return MinSucc;
682}
683
Chris Lattner1a924e72011-02-18 04:43:06 +0000684static bool hasAddressTakenAndUsed(BasicBlock *BB) {
685 if (!BB->hasAddressTaken()) return false;
Owen Anderson92651ec2011-04-14 21:35:50 +0000686
Chris Lattner1a924e72011-02-18 04:43:06 +0000687 // If the block has its address taken, it may be a tree of dead constants
688 // hanging off of it. These shouldn't keep the block alive.
689 BlockAddress *BA = BlockAddress::get(BB);
690 BA->removeDeadConstantUsers();
691 return !BA->use_empty();
692}
693
Chris Lattner240051a2008-11-27 07:20:04 +0000694/// ProcessBlock - If there are any predecessors whose control can be threaded
Chris Lattner21157222008-04-20 21:13:06 +0000695/// through to a successor, transform them now.
Sean Silva46590d52016-06-14 00:51:09 +0000696bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
Chris Lattnerde5ab4862010-01-23 18:56:07 +0000697 // If the block is trivially dead, just return and let the caller nuke it.
698 // This simplifies other transformations.
Ramkumar Ramachandra40c3e032015-01-13 03:46:47 +0000699 if (pred_empty(BB) &&
Chris Lattnerde5ab4862010-01-23 18:56:07 +0000700 BB != &BB->getParent()->getEntryBlock())
701 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000702
Chris Lattner98d89d12008-11-27 05:07:53 +0000703 // If this block has a single predecessor, and if that pred has a single
704 // successor, merge the blocks. This encourages recursive jump threading
705 // because now the condition in this block can be threaded through
706 // predecessors of our predecessor block.
Chris Lattner5ff7f562009-11-07 08:05:03 +0000707 if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
David Majnemer654e1302015-07-31 17:58:14 +0000708 const TerminatorInst *TI = SinglePred->getTerminator();
709 if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
Chris Lattner1a924e72011-02-18 04:43:06 +0000710 SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
Chris Lattnerd579cb12009-05-04 02:28:08 +0000711 // If SinglePred was a loop header, BB becomes one.
712 if (LoopHeaders.erase(SinglePred))
713 LoopHeaders.insert(BB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000714
Igor Laevsky87f0d0e2016-06-16 16:25:53 +0000715 LVI->eraseBlock(SinglePred);
Chris Lattner98d89d12008-11-27 05:07:53 +0000716 MergeBasicBlockIntoOnlyPred(BB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000717
Chris Lattner98d89d12008-11-27 05:07:53 +0000718 return true;
719 }
Chris Lattner5ff7f562009-11-07 08:05:03 +0000720 }
721
Haicheng Wua6a32792016-01-08 19:39:39 +0000722 if (TryToUnfoldSelectInCurrBB(BB))
723 return true;
724
Sanjoy Das8b859c22017-02-17 04:21:14 +0000725 // Look if we can propagate guards to predecessors.
726 if (HasGuards && ProcessGuards(BB))
727 return true;
728
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000729 // What kind of constant we're looking for.
730 ConstantPreference Preference = WantInteger;
731
732 // Look to see if the terminator is a conditional branch, switch or indirect
733 // branch, if not we can't thread it.
Chris Lattner21157222008-04-20 21:13:06 +0000734 Value *Condition;
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000735 Instruction *Terminator = BB->getTerminator();
736 if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
Chris Lattnerff1c6e32008-04-20 22:39:42 +0000737 // Can't thread an unconditional jump.
738 if (BI->isUnconditional()) return false;
Chris Lattner21157222008-04-20 21:13:06 +0000739 Condition = BI->getCondition();
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000740 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
Chris Lattner21157222008-04-20 21:13:06 +0000741 Condition = SI->getCondition();
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000742 } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
Richard Osborne0ab2b0d2012-07-20 10:36:17 +0000743 // Can't thread indirect branch with no successors.
744 if (IB->getNumSuccessors() == 0) return false;
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000745 Condition = IB->getAddress()->stripPointerCasts();
746 Preference = WantBlockAddress;
747 } else {
Chris Lattner21157222008-04-20 21:13:06 +0000748 return false; // Must be an invoke.
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000749 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000750
Owen Anderson92651ec2011-04-14 21:35:50 +0000751 // Run constant folding to see if we can reduce the condition to a simple
752 // constant.
753 if (Instruction *I = dyn_cast<Instruction>(Condition)) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000754 Value *SimpleVal =
755 ConstantFoldInstruction(I, BB->getModule()->getDataLayout(), TLI);
Owen Anderson92651ec2011-04-14 21:35:50 +0000756 if (SimpleVal) {
757 I->replaceAllUsesWith(SimpleVal);
David Majnemer522a9112016-07-22 04:54:44 +0000758 if (isInstructionTriviallyDead(I, TLI))
759 I->eraseFromParent();
Owen Anderson92651ec2011-04-14 21:35:50 +0000760 Condition = SimpleVal;
761 }
762 }
763
Chris Lattner595c7272008-12-03 07:48:08 +0000764 // If the terminator is branching on an undef, we can pick any of the
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000765 // successors to branch to. Let GetBestDestForJumpOnUndef decide.
Chris Lattner595c7272008-12-03 07:48:08 +0000766 if (isa<UndefValue>(Condition)) {
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000767 unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000768
Chris Lattner595c7272008-12-03 07:48:08 +0000769 // Fold the branch/switch.
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000770 TerminatorInst *BBTerm = BB->getTerminator();
Chris Lattner595c7272008-12-03 07:48:08 +0000771 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000772 if (i == BestSucc) continue;
Owen Anderson99c985c2010-09-29 20:34:41 +0000773 BBTerm->getSuccessor(i)->removePredecessor(BB, true);
Chris Lattner595c7272008-12-03 07:48:08 +0000774 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000775
David Greene1efdb452010-01-05 01:27:19 +0000776 DEBUG(dbgs() << " In block '" << BB->getName()
Chris Lattner97b14052009-10-11 07:24:57 +0000777 << "' folding undef terminator: " << *BBTerm << '\n');
Chris Lattnerf99a74e2009-10-11 04:18:15 +0000778 BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
Chris Lattner595c7272008-12-03 07:48:08 +0000779 BBTerm->eraseFromParent();
780 return true;
781 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000782
Frits van Bommel76244862010-12-05 19:06:41 +0000783 // If the terminator of this block is branching on a constant, simplify the
784 // terminator to an unconditional branch. This can occur due to threading in
785 // other blocks.
Frits van Bommeld9df6ea2010-12-06 23:36:56 +0000786 if (getKnownConstant(Condition, Preference)) {
Frits van Bommel76244862010-12-05 19:06:41 +0000787 DEBUG(dbgs() << " In block '" << BB->getName()
788 << "' folding terminator: " << *BB->getTerminator() << '\n');
789 ++NumFolds;
Frits van Bommelad964552011-05-22 16:24:18 +0000790 ConstantFoldTerminator(BB, true);
Frits van Bommel76244862010-12-05 19:06:41 +0000791 return true;
792 }
793
Chris Lattner595c7272008-12-03 07:48:08 +0000794 Instruction *CondInst = dyn_cast<Instruction>(Condition);
795
Chris Lattner595c7272008-12-03 07:48:08 +0000796 // All the rest of our checks depend on the condition being an instruction.
Craig Topperf40110f2014-04-25 05:29:35 +0000797 if (!CondInst) {
Chris Lattnerba456162009-11-12 01:41:34 +0000798 // FIXME: Unify this with code below.
Hal Finkel7e184492014-09-07 20:29:59 +0000799 if (ProcessThreadableEdges(Condition, BB, Preference, Terminator))
Chris Lattnerba456162009-11-12 01:41:34 +0000800 return true;
Chris Lattner595c7272008-12-03 07:48:08 +0000801 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000802 }
803
Nick Lewycky77585a22009-06-19 04:56:29 +0000804 if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
Philip Reames66ab0f02015-06-16 00:49:59 +0000805 // If we're branching on a conditional, LVI might be able to determine
Eric Christopher572e03a2015-06-19 01:53:21 +0000806 // it's value at the branch instruction. We only handle comparisons
Philip Reames66ab0f02015-06-16 00:49:59 +0000807 // against a constant at this time.
Larisse Voufo532bf712015-09-18 19:14:35 +0000808 // TODO: This should be extended to handle switches as well.
Owen Anderson6ebbd922010-08-27 17:12:29 +0000809 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
810 Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
Xin Tongac2b5762017-03-07 18:59:09 +0000811 if (CondBr && CondConst) {
812 // We should have returned as soon as we turn a conditional branch to
813 // unconditional. Because its no longer interesting as far as jump
814 // threading is concerned.
815 assert(CondBr->isConditional() && "Threading on unconditional terminator");
816
Hal Finkel7e184492014-09-07 20:29:59 +0000817 LazyValueInfo::Tristate Ret =
818 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
Philip Reames66ab0f02015-06-16 00:49:59 +0000819 CondConst, CondBr);
Hal Finkel7e184492014-09-07 20:29:59 +0000820 if (Ret != LazyValueInfo::Unknown) {
821 unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
822 unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
823 CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);
824 BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
825 CondBr->eraseFromParent();
Philip Reames66ab0f02015-06-16 00:49:59 +0000826 if (CondCmp->use_empty())
827 CondCmp->eraseFromParent();
828 else if (CondCmp->getParent() == BB) {
829 // If the fact we just learned is true for all uses of the
830 // condition, replace it with a constant value
831 auto *CI = Ret == LazyValueInfo::True ?
832 ConstantInt::getTrue(CondCmp->getType()) :
833 ConstantInt::getFalse(CondCmp->getType());
834 CondCmp->replaceAllUsesWith(CI);
835 CondCmp->eraseFromParent();
836 }
Hal Finkel7e184492014-09-07 20:29:59 +0000837 return true;
838 }
Benjamin Kramer6a4976d2013-08-07 10:29:38 +0000839
Xin Tongac2b5762017-03-07 18:59:09 +0000840 // We did not manage to simplify this branch, try to see whether
841 // CondCmp depends on a known phi-select pattern.
842 if (TryToUnfoldSelect(CondCmp, BB))
843 return true;
844 }
Nick Lewycky77585a22009-06-19 04:56:29 +0000845 }
Chris Lattner98d89d12008-11-27 05:07:53 +0000846
847 // Check for some cases that are worth simplifying. Right now we want to look
848 // for loads that are used by a switch or by the condition for the branch. If
849 // we see one, check to see if it's partially redundant. If so, insert a PHI
850 // which can then be used to thread the values.
851 //
Chris Lattner595c7272008-12-03 07:48:08 +0000852 Value *SimplifyValue = CondInst;
Chris Lattner98d89d12008-11-27 05:07:53 +0000853 if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
854 if (isa<Constant>(CondCmp->getOperand(1)))
855 SimplifyValue = CondCmp->getOperand(0);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000856
Chris Lattner9d9812a2009-11-15 19:58:31 +0000857 // TODO: There are other places where load PRE would be profitable, such as
858 // more complex comparisons.
Chris Lattner98d89d12008-11-27 05:07:53 +0000859 if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue))
860 if (SimplifyPartiallyRedundantLoad(LI))
861 return true;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000862
Chris Lattner5ff7f562009-11-07 08:05:03 +0000863 // Handle a variety of cases where we are branching on something derived from
864 // a PHI node in the current block. If we can prove that any predecessors
865 // compute a predictable value based on a PHI node, thread those predecessors.
866 //
Hal Finkel7e184492014-09-07 20:29:59 +0000867 if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator))
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000868 return true;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000869
Chris Lattner6a19ed02010-01-11 23:41:09 +0000870 // If this is an otherwise-unfoldable branch on a phi node in the current
871 // block, see if we can simplify.
872 if (PHINode *PN = dyn_cast<PHINode>(CondInst))
873 if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
874 return ProcessBranchOnPHI(PN);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000875
Chris Lattnereb73bdb2010-01-12 02:07:17 +0000876 // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify.
877 if (CondInst->getOpcode() == Instruction::Xor &&
878 CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
879 return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst));
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000880
Sanjoy Das13e63a22015-10-28 21:27:08 +0000881 // Search for a stronger dominating condition that can be used to simplify a
882 // conditional branch leaving BB.
883 if (ProcessImpliedCondition(BB))
884 return true;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000885
Sanjoy Das13e63a22015-10-28 21:27:08 +0000886 return false;
887}
888
Sean Silva46590d52016-06-14 00:51:09 +0000889bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
Sanjoy Das13e63a22015-10-28 21:27:08 +0000890 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
891 if (!BI || !BI->isConditional())
892 return false;
893
894 Value *Cond = BI->getCondition();
895 BasicBlock *CurrentBB = BB;
896 BasicBlock *CurrentPred = BB->getSinglePredecessor();
897 unsigned Iter = 0;
898
Sanjoy Das55ea67c2015-11-06 19:01:08 +0000899 auto &DL = BB->getModule()->getDataLayout();
900
Sanjoy Das13e63a22015-10-28 21:27:08 +0000901 while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
902 auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
Chad Rosiere2cbd132016-04-25 17:23:36 +0000903 if (!PBI || !PBI->isConditional())
904 return false;
905 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
Sanjoy Das13e63a22015-10-28 21:27:08 +0000906 return false;
907
Chad Rosiere2cbd132016-04-25 17:23:36 +0000908 bool FalseDest = PBI->getSuccessor(1) == CurrentBB;
Chad Rosier41dd31f2016-04-20 19:15:26 +0000909 Optional<bool> Implication =
Chad Rosiere2cbd132016-04-25 17:23:36 +0000910 isImpliedCondition(PBI->getCondition(), Cond, DL, FalseDest);
Chad Rosier41dd31f2016-04-20 19:15:26 +0000911 if (Implication) {
912 BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB);
913 BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI);
Sanjoy Das13e63a22015-10-28 21:27:08 +0000914 BI->eraseFromParent();
915 return true;
916 }
917 CurrentBB = CurrentPred;
918 CurrentPred = CurrentBB->getSinglePredecessor();
919 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000920
Chris Lattnere369c352008-04-22 06:36:15 +0000921 return false;
922}
923
Chris Lattner98d89d12008-11-27 05:07:53 +0000924/// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
925/// load instruction, eliminate it by replacing it with a PHI node. This is an
926/// important optimization that encourages jump threading, and needs to be run
927/// interlaced with other jump threading tasks.
Sean Silva46590d52016-06-14 00:51:09 +0000928bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
Sanjoy Das13623ad2016-07-14 19:21:15 +0000929 // Don't hack volatile and ordered loads.
930 if (!LI->isUnordered()) return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000931
Chris Lattner98d89d12008-11-27 05:07:53 +0000932 // If the load is defined in a block with exactly one predecessor, it can't be
933 // partially redundant.
934 BasicBlock *LoadBB = LI->getParent();
935 if (LoadBB->getSinglePredecessor())
936 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000937
David Majnemereb518bd2015-08-04 08:21:40 +0000938 // If the load is defined in an EH pad, it can't be partially redundant,
939 // because the edges between the invoke and the EH pad cannot have other
Bill Wendling90dd90a2013-10-21 04:09:17 +0000940 // instructions between them.
David Majnemereb518bd2015-08-04 08:21:40 +0000941 if (LoadBB->isEHPad())
Bill Wendling90dd90a2013-10-21 04:09:17 +0000942 return false;
943
Chris Lattner98d89d12008-11-27 05:07:53 +0000944 Value *LoadedPtr = LI->getOperand(0);
945
946 // If the loaded operand is defined in the LoadBB, it can't be available.
Chris Lattner9d9812a2009-11-15 19:58:31 +0000947 // TODO: Could do simple PHI translation, that would be fun :)
Chris Lattner98d89d12008-11-27 05:07:53 +0000948 if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
949 if (PtrOp->getParent() == LoadBB)
950 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000951
Chris Lattner98d89d12008-11-27 05:07:53 +0000952 // Scan a few instructions up from the load, to see if it is obviously live at
953 // the entry to its block.
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +0000954 BasicBlock::iterator BBIt(LI);
Eli Friedman02419a92016-08-08 04:10:22 +0000955 bool IsLoadCSE;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000956 if (Value *AvailableVal =
Eli Friedman02419a92016-08-08 04:10:22 +0000957 FindAvailableLoadedValue(LI, LoadBB, BBIt, DefMaxInstsToScan, nullptr, &IsLoadCSE)) {
David L Kreitzerda700ce2015-09-16 13:27:30 +0000958 // If the value of the load is locally available within the block, just use
Chris Lattner98d89d12008-11-27 05:07:53 +0000959 // it. This frequently occurs for reg2mem'd allocas.
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000960
Eli Friedman02419a92016-08-08 04:10:22 +0000961 if (IsLoadCSE) {
962 LoadInst *NLI = cast<LoadInst>(AvailableVal);
963 combineMetadataForCSE(NLI, LI);
964 };
965
Chris Lattner482eb702009-01-09 06:08:12 +0000966 // If the returned value is the load itself, replace with an undef. This can
967 // only happen in dead loops.
Owen Andersonb292b8c2009-07-30 23:03:37 +0000968 if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType());
Chandler Carrutheeec35a2014-10-20 00:24:14 +0000969 if (AvailableVal->getType() != LI->getType())
Chandler Carruth1a3c2c42014-11-25 08:20:27 +0000970 AvailableVal =
971 CastInst::CreateBitOrPointerCast(AvailableVal, LI->getType(), "", LI);
Chris Lattner98d89d12008-11-27 05:07:53 +0000972 LI->replaceAllUsesWith(AvailableVal);
973 LI->eraseFromParent();
974 return true;
975 }
976
977 // Otherwise, if we scanned the whole block and got to the top of the block,
978 // we know the block is locally transparent to the load. If not, something
979 // might clobber its value.
980 if (BBIt != LoadBB->begin())
981 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000982
Hal Finkelcc39b672014-07-24 12:16:19 +0000983 // If all of the loads and stores that feed the value have the same AA tags,
984 // then we can propagate them onto any newly inserted loads.
985 AAMDNodes AATags;
986 LI->getAAMetadata(AATags);
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000987
Chris Lattner98d89d12008-11-27 05:07:53 +0000988 SmallPtrSet<BasicBlock*, 8> PredsScanned;
989 typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy;
990 AvailablePredsTy AvailablePreds;
Craig Topperf40110f2014-04-25 05:29:35 +0000991 BasicBlock *OneUnavailablePred = nullptr;
Eli Friedman02419a92016-08-08 04:10:22 +0000992 SmallVector<LoadInst*, 8> CSELoads;
Frits van Bommel5e75ef42010-12-05 19:02:47 +0000993
Chris Lattner98d89d12008-11-27 05:07:53 +0000994 // If we got here, the loaded value is transparent through to the start of the
995 // block. Check to see if it is available in any of the predecessor blocks.
Benjamin Kramer543762d2016-01-09 18:43:01 +0000996 for (BasicBlock *PredBB : predecessors(LoadBB)) {
Chris Lattner98d89d12008-11-27 05:07:53 +0000997 // If we already scanned this predecessor, skip it.
David Blaikie70573dc2014-11-19 07:49:26 +0000998 if (!PredsScanned.insert(PredBB).second)
Chris Lattner98d89d12008-11-27 05:07:53 +0000999 continue;
1000
1001 // Scan the predecessor to see if the value is available in the pred.
1002 BBIt = PredBB->end();
Jun Bum Lim180bc5a2017-02-02 15:12:34 +00001003 unsigned NumScanedInst = 0;
1004 Value *PredAvailable =
1005 FindAvailableLoadedValue(LI, PredBB, BBIt, DefMaxInstsToScan, nullptr,
1006 &IsLoadCSE, &NumScanedInst);
1007
1008 // If PredBB has a single predecessor, continue scanning through the single
Xin Tongfb0dc622017-03-02 08:39:11 +00001009 // predecessor.
Jun Bum Lim180bc5a2017-02-02 15:12:34 +00001010 BasicBlock *SinglePredBB = PredBB;
1011 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
1012 NumScanedInst < DefMaxInstsToScan) {
1013 SinglePredBB = SinglePredBB->getSinglePredecessor();
1014 if (SinglePredBB) {
1015 BBIt = SinglePredBB->end();
1016 PredAvailable = FindAvailableLoadedValue(
1017 LI, SinglePredBB, BBIt, (DefMaxInstsToScan - NumScanedInst),
1018 nullptr, &IsLoadCSE, &NumScanedInst);
1019 }
1020 }
1021
Chris Lattner98d89d12008-11-27 05:07:53 +00001022 if (!PredAvailable) {
1023 OneUnavailablePred = PredBB;
1024 continue;
1025 }
Nadav Rotem465834c2012-07-24 10:51:42 +00001026
Eli Friedman02419a92016-08-08 04:10:22 +00001027 if (IsLoadCSE)
1028 CSELoads.push_back(cast<LoadInst>(PredAvailable));
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001029
Chris Lattner98d89d12008-11-27 05:07:53 +00001030 // If so, this load is partially redundant. Remember this info so that we
1031 // can create a PHI node.
1032 AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
1033 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001034
Chris Lattner98d89d12008-11-27 05:07:53 +00001035 // If the loaded value isn't available in any predecessor, it isn't partially
1036 // redundant.
1037 if (AvailablePreds.empty()) return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001038
Chris Lattner98d89d12008-11-27 05:07:53 +00001039 // Okay, the loaded value is available in at least one (and maybe all!)
1040 // predecessors. If the value is unavailable in more than one unique
1041 // predecessor, we want to insert a merge block for those common predecessors.
1042 // This ensures that we only have to insert one reload, thus not increasing
1043 // code size.
Craig Topperf40110f2014-04-25 05:29:35 +00001044 BasicBlock *UnavailablePred = nullptr;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001045
Chris Lattner98d89d12008-11-27 05:07:53 +00001046 // If there is exactly one predecessor where the value is unavailable, the
1047 // already computed 'OneUnavailablePred' block is it. If it ends in an
1048 // unconditional branch, we know that it isn't a critical edge.
1049 if (PredsScanned.size() == AvailablePreds.size()+1 &&
1050 OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
1051 UnavailablePred = OneUnavailablePred;
1052 } else if (PredsScanned.size() != AvailablePreds.size()) {
1053 // Otherwise, we had multiple unavailable predecessors or we had a critical
1054 // edge from the one.
1055 SmallVector<BasicBlock*, 8> PredsToSplit;
1056 SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
1057
Benjamin Kramer543762d2016-01-09 18:43:01 +00001058 for (const auto &AvailablePred : AvailablePreds)
1059 AvailablePredSet.insert(AvailablePred.first);
Chris Lattner98d89d12008-11-27 05:07:53 +00001060
1061 // Add all the unavailable predecessors to the PredsToSplit list.
Benjamin Kramer543762d2016-01-09 18:43:01 +00001062 for (BasicBlock *P : predecessors(LoadBB)) {
Chris Lattner329ea062010-06-14 19:45:43 +00001063 // If the predecessor is an indirect goto, we can't split the edge.
Gabor Greifa5fa8852010-07-12 14:10:24 +00001064 if (isa<IndirectBrInst>(P->getTerminator()))
Chris Lattner329ea062010-06-14 19:45:43 +00001065 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001066
Gabor Greifa5fa8852010-07-12 14:10:24 +00001067 if (!AvailablePredSet.count(P))
1068 PredsToSplit.push_back(P);
Chris Lattner329ea062010-06-14 19:45:43 +00001069 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001070
Chris Lattner98d89d12008-11-27 05:07:53 +00001071 // Split them out to their own block.
Manman Ren72d44b12015-10-15 14:59:40 +00001072 UnavailablePred = SplitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split");
Chris Lattner98d89d12008-11-27 05:07:53 +00001073 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001074
Chris Lattner98d89d12008-11-27 05:07:53 +00001075 // If the value isn't available in all predecessors, then there will be
1076 // exactly one where it isn't available. Insert a load on that edge and add
1077 // it to the AvailablePreds list.
1078 if (UnavailablePred) {
1079 assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
1080 "Can't handle critical edge here!");
Sanjoy Das13623ad2016-07-14 19:21:15 +00001081 LoadInst *NewVal =
1082 new LoadInst(LoadedPtr, LI->getName() + ".pr", false,
1083 LI->getAlignment(), LI->getOrdering(), LI->getSynchScope(),
1084 UnavailablePred->getTerminator());
Devang Patel306f8db2011-05-04 22:48:19 +00001085 NewVal->setDebugLoc(LI->getDebugLoc());
Hal Finkelcc39b672014-07-24 12:16:19 +00001086 if (AATags)
1087 NewVal->setAAMetadata(AATags);
Nadav Rotem465834c2012-07-24 10:51:42 +00001088
Chris Lattner98d89d12008-11-27 05:07:53 +00001089 AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
1090 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001091
Chris Lattner98d89d12008-11-27 05:07:53 +00001092 // Now we know that each predecessor of this block has a value in
1093 // AvailablePreds, sort them for efficient access as we're walking the preds.
Chris Lattner2b07d3c2008-12-01 06:52:57 +00001094 array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001095
Chris Lattner98d89d12008-11-27 05:07:53 +00001096 // Create a PHI node at the start of the block for the PRE'd load value.
Jay Foade0938d82011-03-30 11:19:20 +00001097 pred_iterator PB = pred_begin(LoadBB), PE = pred_end(LoadBB);
Jay Foad52131342011-03-30 11:28:46 +00001098 PHINode *PN = PHINode::Create(LI->getType(), std::distance(PB, PE), "",
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +00001099 &LoadBB->front());
Chris Lattner98d89d12008-11-27 05:07:53 +00001100 PN->takeName(LI);
Devang Patel306f8db2011-05-04 22:48:19 +00001101 PN->setDebugLoc(LI->getDebugLoc());
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001102
Chris Lattner98d89d12008-11-27 05:07:53 +00001103 // Insert new entries into the PHI for each predecessor. A single block may
1104 // have multiple entries here.
Jay Foade0938d82011-03-30 11:19:20 +00001105 for (pred_iterator PI = PB; PI != PE; ++PI) {
Gabor Greifa5fa8852010-07-12 14:10:24 +00001106 BasicBlock *P = *PI;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001107 AvailablePredsTy::iterator I =
Chris Lattner98d89d12008-11-27 05:07:53 +00001108 std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(),
Craig Topperf40110f2014-04-25 05:29:35 +00001109 std::make_pair(P, (Value*)nullptr));
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001110
Gabor Greifa5fa8852010-07-12 14:10:24 +00001111 assert(I != AvailablePreds.end() && I->first == P &&
Chris Lattner98d89d12008-11-27 05:07:53 +00001112 "Didn't find entry for predecessor!");
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001113
Chandler Carrutheeec35a2014-10-20 00:24:14 +00001114 // If we have an available predecessor but it requires casting, insert the
Chandler Carruth6665d622014-10-20 05:34:36 +00001115 // cast in the predecessor and use the cast. Note that we have to update the
1116 // AvailablePreds vector as we go so that all of the PHI entries for this
1117 // predecessor use the same bitcast.
1118 Value *&PredV = I->second;
Chandler Carrutheeec35a2014-10-20 00:24:14 +00001119 if (PredV->getType() != LI->getType())
Chandler Carruth1a3c2c42014-11-25 08:20:27 +00001120 PredV = CastInst::CreateBitOrPointerCast(PredV, LI->getType(), "",
1121 P->getTerminator());
Chandler Carrutheeec35a2014-10-20 00:24:14 +00001122
1123 PN->addIncoming(PredV, I->first);
Chris Lattner98d89d12008-11-27 05:07:53 +00001124 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001125
Eli Friedman02419a92016-08-08 04:10:22 +00001126 for (LoadInst *PredLI : CSELoads) {
1127 combineMetadataForCSE(PredLI, LI);
1128 }
1129
Chris Lattner98d89d12008-11-27 05:07:53 +00001130 LI->replaceAllUsesWith(PN);
1131 LI->eraseFromParent();
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001132
Chris Lattner98d89d12008-11-27 05:07:53 +00001133 return true;
1134}
1135
Chris Lattner5ff7f562009-11-07 08:05:03 +00001136/// FindMostPopularDest - The specified list contains multiple possible
1137/// threadable destinations. Pick the one that occurs the most frequently in
1138/// the list.
1139static BasicBlock *
1140FindMostPopularDest(BasicBlock *BB,
1141 const SmallVectorImpl<std::pair<BasicBlock*,
1142 BasicBlock*> > &PredToDestList) {
1143 assert(!PredToDestList.empty());
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001144
Chris Lattner5ff7f562009-11-07 08:05:03 +00001145 // Determine popularity. If there are multiple possible destinations, we
1146 // explicitly choose to ignore 'undef' destinations. We prefer to thread
1147 // blocks with known and real destinations to threading undef. We'll handle
1148 // them later if interesting.
1149 DenseMap<BasicBlock*, unsigned> DestPopularity;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001150 for (const auto &PredToDest : PredToDestList)
1151 if (PredToDest.second)
1152 DestPopularity[PredToDest.second]++;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001153
Chris Lattner5ff7f562009-11-07 08:05:03 +00001154 // Find the most popular dest.
1155 DenseMap<BasicBlock*, unsigned>::iterator DPI = DestPopularity.begin();
1156 BasicBlock *MostPopularDest = DPI->first;
1157 unsigned Popularity = DPI->second;
1158 SmallVector<BasicBlock*, 4> SamePopularity;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001159
Chris Lattner5ff7f562009-11-07 08:05:03 +00001160 for (++DPI; DPI != DestPopularity.end(); ++DPI) {
1161 // If the popularity of this entry isn't higher than the popularity we've
1162 // seen so far, ignore it.
1163 if (DPI->second < Popularity)
1164 ; // ignore.
1165 else if (DPI->second == Popularity) {
1166 // If it is the same as what we've seen so far, keep track of it.
1167 SamePopularity.push_back(DPI->first);
1168 } else {
1169 // If it is more popular, remember it.
1170 SamePopularity.clear();
1171 MostPopularDest = DPI->first;
1172 Popularity = DPI->second;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001173 }
Chris Lattner5ff7f562009-11-07 08:05:03 +00001174 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001175
Frits van Bommel9bbe8492010-12-16 12:16:00 +00001176 // Okay, now we know the most popular destination. If there is more than one
Chris Lattner5ff7f562009-11-07 08:05:03 +00001177 // destination, we need to determine one. This is arbitrary, but we need
1178 // to make a deterministic decision. Pick the first one that appears in the
1179 // successor list.
1180 if (!SamePopularity.empty()) {
1181 SamePopularity.push_back(MostPopularDest);
1182 TerminatorInst *TI = BB->getTerminator();
1183 for (unsigned i = 0; ; ++i) {
1184 assert(i != TI->getNumSuccessors() && "Didn't find any successor!");
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001185
David Majnemer0d955d02016-08-11 22:21:41 +00001186 if (!is_contained(SamePopularity, TI->getSuccessor(i)))
Chris Lattner5ff7f562009-11-07 08:05:03 +00001187 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001188
Chris Lattner5ff7f562009-11-07 08:05:03 +00001189 MostPopularDest = TI->getSuccessor(i);
1190 break;
1191 }
1192 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001193
Chris Lattner5ff7f562009-11-07 08:05:03 +00001194 // Okay, we have finally picked the most popular destination.
1195 return MostPopularDest;
1196}
1197
Sean Silva46590d52016-06-14 00:51:09 +00001198bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
1199 ConstantPreference Preference,
1200 Instruction *CxtI) {
Chris Lattner5ff7f562009-11-07 08:05:03 +00001201 // If threading this would thread across a loop header, don't even try to
1202 // thread the edge.
1203 if (LoopHeaders.count(BB))
1204 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001205
Frits van Bommel76244862010-12-05 19:06:41 +00001206 PredValueInfoTy PredValues;
Haicheng Wu64d9d7c2016-03-15 23:38:47 +00001207 if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI))
1208 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001209
Chris Lattner5ff7f562009-11-07 08:05:03 +00001210 assert(!PredValues.empty() &&
1211 "ComputeValueKnownInPredecessors returned true with no values");
1212
David Greene1efdb452010-01-05 01:27:19 +00001213 DEBUG(dbgs() << "IN BB: " << *BB;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001214 for (const auto &PredValue : PredValues) {
Frits van Bommel76244862010-12-05 19:06:41 +00001215 dbgs() << " BB '" << BB->getName() << "': FOUND condition = "
Benjamin Kramer543762d2016-01-09 18:43:01 +00001216 << *PredValue.first
1217 << " for pred '" << PredValue.second->getName() << "'.\n";
Chris Lattner5ff7f562009-11-07 08:05:03 +00001218 });
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001219
Chris Lattner5ff7f562009-11-07 08:05:03 +00001220 // Decide what we want to thread through. Convert our list of known values to
1221 // a list of known destinations for each pred. This also discards duplicate
1222 // predecessors and keeps track of the undefined inputs (which are represented
Chris Lattnerea465e22009-11-09 00:41:49 +00001223 // as a null dest in the PredToDestList).
Chris Lattner5ff7f562009-11-07 08:05:03 +00001224 SmallPtrSet<BasicBlock*, 16> SeenPreds;
1225 SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001226
Craig Topperf40110f2014-04-25 05:29:35 +00001227 BasicBlock *OnlyDest = nullptr;
Chris Lattner5ff7f562009-11-07 08:05:03 +00001228 BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001229
Benjamin Kramer543762d2016-01-09 18:43:01 +00001230 for (const auto &PredValue : PredValues) {
1231 BasicBlock *Pred = PredValue.second;
David Blaikie70573dc2014-11-19 07:49:26 +00001232 if (!SeenPreds.insert(Pred).second)
Chris Lattner5ff7f562009-11-07 08:05:03 +00001233 continue; // Duplicate predecessor entry.
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001234
Chris Lattner5ff7f562009-11-07 08:05:03 +00001235 // If the predecessor ends with an indirect goto, we can't change its
1236 // destination.
1237 if (isa<IndirectBrInst>(Pred->getTerminator()))
1238 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001239
Benjamin Kramer543762d2016-01-09 18:43:01 +00001240 Constant *Val = PredValue.first;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001241
Chris Lattner5ff7f562009-11-07 08:05:03 +00001242 BasicBlock *DestBB;
Frits van Bommel76244862010-12-05 19:06:41 +00001243 if (isa<UndefValue>(Val))
Craig Topperf40110f2014-04-25 05:29:35 +00001244 DestBB = nullptr;
Chris Lattner5ff7f562009-11-07 08:05:03 +00001245 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
Frits van Bommel76244862010-12-05 19:06:41 +00001246 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
Stepan Dyatkovskiy513aaa52012-02-01 07:49:51 +00001247 else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
Stepan Dyatkovskiy5b648af2012-03-08 07:06:20 +00001248 DestBB = SI->findCaseValue(cast<ConstantInt>(Val)).getCaseSuccessor();
Stepan Dyatkovskiy513aaa52012-02-01 07:49:51 +00001249 } else {
Frits van Bommeld9df6ea2010-12-06 23:36:56 +00001250 assert(isa<IndirectBrInst>(BB->getTerminator())
1251 && "Unexpected terminator");
1252 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
Chris Lattner5ff7f562009-11-07 08:05:03 +00001253 }
1254
1255 // If we have exactly one destination, remember it for efficiency below.
Frits van Bommel9bbe8492010-12-16 12:16:00 +00001256 if (PredToDestList.empty())
Chris Lattner5ff7f562009-11-07 08:05:03 +00001257 OnlyDest = DestBB;
1258 else if (OnlyDest != DestBB)
1259 OnlyDest = MultipleDestSentinel;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001260
Chris Lattner5ff7f562009-11-07 08:05:03 +00001261 PredToDestList.push_back(std::make_pair(Pred, DestBB));
1262 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001263
Chris Lattner5ff7f562009-11-07 08:05:03 +00001264 // If all edges were unthreadable, we fail.
1265 if (PredToDestList.empty())
Haicheng Wu64d9d7c2016-03-15 23:38:47 +00001266 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001267
Chris Lattner5ff7f562009-11-07 08:05:03 +00001268 // Determine which is the most common successor. If we have many inputs and
1269 // this block is a switch, we want to start by threading the batch that goes
1270 // to the most popular destination first. If we only know about one
1271 // threadable destination (the common case) we can avoid this.
1272 BasicBlock *MostPopularDest = OnlyDest;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001273
Chris Lattner5ff7f562009-11-07 08:05:03 +00001274 if (MostPopularDest == MultipleDestSentinel)
1275 MostPopularDest = FindMostPopularDest(BB, PredToDestList);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001276
Chris Lattner5ff7f562009-11-07 08:05:03 +00001277 // Now that we know what the most popular destination is, factor all
1278 // predecessors that will jump to it into a single predecessor.
1279 SmallVector<BasicBlock*, 16> PredsToFactor;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001280 for (const auto &PredToDest : PredToDestList)
1281 if (PredToDest.second == MostPopularDest) {
1282 BasicBlock *Pred = PredToDest.first;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001283
Chris Lattner5ff7f562009-11-07 08:05:03 +00001284 // This predecessor may be a switch or something else that has multiple
1285 // edges to the block. Factor each of these edges by listing them
1286 // according to # occurrences in PredsToFactor.
Benjamin Kramer543762d2016-01-09 18:43:01 +00001287 for (BasicBlock *Succ : successors(Pred))
1288 if (Succ == BB)
Chris Lattner5ff7f562009-11-07 08:05:03 +00001289 PredsToFactor.push_back(Pred);
1290 }
1291
1292 // If the threadable edges are branching on an undefined value, we get to pick
1293 // the destination that these predecessors should get to.
Craig Topperf40110f2014-04-25 05:29:35 +00001294 if (!MostPopularDest)
Chris Lattner5ff7f562009-11-07 08:05:03 +00001295 MostPopularDest = BB->getTerminator()->
1296 getSuccessor(GetBestDestForJumpOnUndef(BB));
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001297
Chris Lattner5ff7f562009-11-07 08:05:03 +00001298 // Ok, try to thread it!
Haicheng Wu64d9d7c2016-03-15 23:38:47 +00001299 return ThreadEdge(BB, PredsToFactor, MostPopularDest);
Chris Lattner5ff7f562009-11-07 08:05:03 +00001300}
Chris Lattner98d89d12008-11-27 05:07:53 +00001301
Chris Lattner6a19ed02010-01-11 23:41:09 +00001302/// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on
1303/// a PHI node in the current block. See if there are any simplifications we
1304/// can do based on inputs to the phi node.
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001305///
Sean Silva46590d52016-06-14 00:51:09 +00001306bool JumpThreadingPass::ProcessBranchOnPHI(PHINode *PN) {
Chris Lattner6ce85e82009-10-11 04:40:21 +00001307 BasicBlock *BB = PN->getParent();
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001308
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001309 // TODO: We could make use of this to do it once for blocks with common PHI
1310 // values.
1311 SmallVector<BasicBlock*, 1> PredBBs;
1312 PredBBs.resize(1);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001313
Chris Lattner5ff7f562009-11-07 08:05:03 +00001314 // If any of the predecessor blocks end in an unconditional branch, we can
Chris Lattner6a19ed02010-01-11 23:41:09 +00001315 // *duplicate* the conditional branch into that block in order to further
1316 // encourage jump threading and to eliminate cases where we have branch on a
1317 // phi of an icmp (branch on icmp is much better).
Chris Lattner97b14052009-10-11 07:24:57 +00001318 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1319 BasicBlock *PredBB = PN->getIncomingBlock(i);
1320 if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator()))
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001321 if (PredBr->isUnconditional()) {
1322 PredBBs[0] = PredBB;
1323 // Try to duplicate BB into PredBB.
1324 if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs))
1325 return true;
1326 }
Chris Lattner97b14052009-10-11 07:24:57 +00001327 }
1328
Chris Lattner6ce85e82009-10-11 04:40:21 +00001329 return false;
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001330}
1331
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001332/// ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on
1333/// a xor instruction in the current block. See if there are any
1334/// simplifications we can do based on inputs to the xor.
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001335///
Sean Silva46590d52016-06-14 00:51:09 +00001336bool JumpThreadingPass::ProcessBranchOnXOR(BinaryOperator *BO) {
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001337 BasicBlock *BB = BO->getParent();
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001338
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001339 // If either the LHS or RHS of the xor is a constant, don't do this
1340 // optimization.
1341 if (isa<ConstantInt>(BO->getOperand(0)) ||
1342 isa<ConstantInt>(BO->getOperand(1)))
1343 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001344
Chris Lattnerba2d0b82010-01-23 19:16:25 +00001345 // If the first instruction in BB isn't a phi, we won't be able to infer
1346 // anything special about any particular predecessor.
1347 if (!isa<PHINode>(BB->front()))
1348 return false;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001349
Hans Wennborgb4d26782016-10-03 18:18:04 +00001350 // If this BB is a landing pad, we won't be able to split the edge into it.
1351 if (BB->isEHPad())
1352 return false;
1353
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001354 // If we have a xor as the branch input to this block, and we know that the
1355 // LHS or RHS of the xor in any predecessor is true/false, then we can clone
1356 // the condition into the predecessor and fix that value to true, saving some
1357 // logical ops on that path and encouraging other paths to simplify.
1358 //
1359 // This copies something like this:
1360 //
1361 // BB:
1362 // %X = phi i1 [1], [%X']
1363 // %Y = icmp eq i32 %A, %B
1364 // %Z = xor i1 %X, %Y
1365 // br i1 %Z, ...
1366 //
1367 // Into:
1368 // BB':
1369 // %Y = icmp ne i32 %A, %B
David L Kreitzerda700ce2015-09-16 13:27:30 +00001370 // br i1 %Y, ...
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001371
Frits van Bommel76244862010-12-05 19:06:41 +00001372 PredValueInfoTy XorOpValues;
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001373 bool isLHS = true;
Frits van Bommeld9df6ea2010-12-06 23:36:56 +00001374 if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +00001375 WantInteger, BO)) {
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001376 assert(XorOpValues.empty());
Frits van Bommeld9df6ea2010-12-06 23:36:56 +00001377 if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues,
Haicheng Wu64d9d7c2016-03-15 23:38:47 +00001378 WantInteger, BO))
1379 return false;
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001380 isLHS = false;
1381 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001382
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001383 assert(!XorOpValues.empty() &&
1384 "ComputeValueKnownInPredecessors returned true with no values");
1385
1386 // Scan the information to see which is most popular: true or false. The
1387 // predecessors can be of the set true, false, or undef.
1388 unsigned NumTrue = 0, NumFalse = 0;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001389 for (const auto &XorOpValue : XorOpValues) {
1390 if (isa<UndefValue>(XorOpValue.first))
Frits van Bommel76244862010-12-05 19:06:41 +00001391 // Ignore undefs for the count.
1392 continue;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001393 if (cast<ConstantInt>(XorOpValue.first)->isZero())
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001394 ++NumFalse;
1395 else
1396 ++NumTrue;
1397 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001398
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001399 // Determine which value to split on, true, false, or undef if neither.
Craig Topperf40110f2014-04-25 05:29:35 +00001400 ConstantInt *SplitVal = nullptr;
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001401 if (NumTrue > NumFalse)
1402 SplitVal = ConstantInt::getTrue(BB->getContext());
1403 else if (NumTrue != 0 || NumFalse != 0)
1404 SplitVal = ConstantInt::getFalse(BB->getContext());
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001405
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001406 // Collect all of the blocks that this can be folded into so that we can
1407 // factor this once and clone it once.
1408 SmallVector<BasicBlock*, 8> BlocksToFoldInto;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001409 for (const auto &XorOpValue : XorOpValues) {
1410 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
Frits van Bommel76244862010-12-05 19:06:41 +00001411 continue;
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001412
Benjamin Kramer543762d2016-01-09 18:43:01 +00001413 BlocksToFoldInto.push_back(XorOpValue.second);
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001414 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001415
Chris Lattnerba2d0b82010-01-23 19:16:25 +00001416 // If we inferred a value for all of the predecessors, then duplication won't
1417 // help us. However, we can just replace the LHS or RHS with the constant.
1418 if (BlocksToFoldInto.size() ==
1419 cast<PHINode>(BB->front()).getNumIncomingValues()) {
Craig Topperf40110f2014-04-25 05:29:35 +00001420 if (!SplitVal) {
Chris Lattnerba2d0b82010-01-23 19:16:25 +00001421 // If all preds provide undef, just nuke the xor, because it is undef too.
1422 BO->replaceAllUsesWith(UndefValue::get(BO->getType()));
1423 BO->eraseFromParent();
1424 } else if (SplitVal->isZero()) {
1425 // If all preds provide 0, replace the xor with the other input.
1426 BO->replaceAllUsesWith(BO->getOperand(isLHS));
1427 BO->eraseFromParent();
1428 } else {
1429 // If all preds provide 1, set the computed value to 1.
1430 BO->setOperand(!isLHS, SplitVal);
1431 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001432
Chris Lattnerba2d0b82010-01-23 19:16:25 +00001433 return true;
1434 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001435
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001436 // Try to duplicate BB into PredBB.
Haicheng Wu64d9d7c2016-03-15 23:38:47 +00001437 return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001438}
1439
1440
Chris Lattner97b14052009-10-11 07:24:57 +00001441/// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
1442/// predecessor to the PHIBB block. If it has PHI nodes, add entries for
1443/// NewPred using the entries from OldPred (suitably mapped).
1444static void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB,
1445 BasicBlock *OldPred,
1446 BasicBlock *NewPred,
1447 DenseMap<Instruction*, Value*> &ValueMap) {
1448 for (BasicBlock::iterator PNI = PHIBB->begin();
1449 PHINode *PN = dyn_cast<PHINode>(PNI); ++PNI) {
1450 // Ok, we have a PHI node. Figure out what the incoming value was for the
1451 // DestBlock.
1452 Value *IV = PN->getIncomingValueForBlock(OldPred);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001453
Chris Lattner97b14052009-10-11 07:24:57 +00001454 // Remap the value if necessary.
1455 if (Instruction *Inst = dyn_cast<Instruction>(IV)) {
1456 DenseMap<Instruction*, Value*>::iterator I = ValueMap.find(Inst);
1457 if (I != ValueMap.end())
1458 IV = I->second;
1459 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001460
Chris Lattner97b14052009-10-11 07:24:57 +00001461 PN->addIncoming(IV, NewPred);
1462 }
1463}
Chris Lattner3df4c152008-04-22 07:05:46 +00001464
Chris Lattner5ff7f562009-11-07 08:05:03 +00001465/// ThreadEdge - We have decided that it is safe and profitable to factor the
1466/// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB
1467/// across BB. Transform the IR to reflect this change.
Sean Silva46590d52016-06-14 00:51:09 +00001468bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
1469 const SmallVectorImpl<BasicBlock *> &PredBBs,
1470 BasicBlock *SuccBB) {
Chris Lattnerd579cb12009-05-04 02:28:08 +00001471 // If threading to the same block as we come from, we would infinite loop.
1472 if (SuccBB == BB) {
David Greene1efdb452010-01-05 01:27:19 +00001473 DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
Daniel Dunbar9813b0b2009-07-26 07:49:05 +00001474 << "' - would thread to self!\n");
Chris Lattnerd579cb12009-05-04 02:28:08 +00001475 return false;
1476 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001477
Chris Lattnerd579cb12009-05-04 02:28:08 +00001478 // If threading this would thread across a loop header, don't thread the edge.
1479 // See the comments above FindLoopHeaders for justifications and caveats.
1480 if (LoopHeaders.count(BB)) {
David Greene1efdb452010-01-05 01:27:19 +00001481 DEBUG(dbgs() << " Not threading across loop header BB '" << BB->getName()
Daniel Dunbar9813b0b2009-07-26 07:49:05 +00001482 << "' to dest BB '" << SuccBB->getName()
1483 << "' - it might create an irreducible loop!\n");
Chris Lattnerd579cb12009-05-04 02:28:08 +00001484 return false;
1485 }
1486
Sanjoy Das8b859c22017-02-17 04:21:14 +00001487 unsigned JumpThreadCost =
1488 getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
Michael Liaod1209162014-09-24 04:59:06 +00001489 if (JumpThreadCost > BBDupThreshold) {
David Greene1efdb452010-01-05 01:27:19 +00001490 DEBUG(dbgs() << " Not threading BB '" << BB->getName()
Chris Lattner97b14052009-10-11 07:24:57 +00001491 << "' - Cost is too high: " << JumpThreadCost << "\n");
1492 return false;
1493 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001494
David L Kreitzerda700ce2015-09-16 13:27:30 +00001495 // And finally, do it! Start by factoring the predecessors if needed.
Chris Lattner5ff7f562009-11-07 08:05:03 +00001496 BasicBlock *PredBB;
1497 if (PredBBs.size() == 1)
1498 PredBB = PredBBs[0];
1499 else {
David Greene1efdb452010-01-05 01:27:19 +00001500 DEBUG(dbgs() << " Factoring out " << PredBBs.size()
Chris Lattner5ff7f562009-11-07 08:05:03 +00001501 << " common predecessors.\n");
Manman Ren72d44b12015-10-15 14:59:40 +00001502 PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
Chris Lattner5ff7f562009-11-07 08:05:03 +00001503 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001504
Chris Lattnerd579cb12009-05-04 02:28:08 +00001505 // And finally, do it!
David Greene1efdb452010-01-05 01:27:19 +00001506 DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() << "' to '"
Daniel Dunbar6115b392009-07-26 09:48:23 +00001507 << SuccBB->getName() << "' with cost: " << JumpThreadCost
Daniel Dunbar9813b0b2009-07-26 07:49:05 +00001508 << ", across block:\n "
1509 << *BB << "\n");
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001510
Owen Andersond361aac2010-09-14 20:57:41 +00001511 LVI->threadEdge(PredBB, BB, SuccBB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001512
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001513 // We are going to have to map operands from the original BB block to the new
1514 // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to
1515 // account for entry from PredBB.
1516 DenseMap<Instruction*, Value*> ValueMapping;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001517
1518 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(),
1519 BB->getName()+".thread",
Owen Anderson55f1c092009-08-13 21:58:54 +00001520 BB->getParent(), BB);
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001521 NewBB->moveAfter(PredBB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001522
Manman Ren72d44b12015-10-15 14:59:40 +00001523 // Set the block frequency of NewBB.
1524 if (HasProfileData) {
1525 auto NewBBFreq =
1526 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
1527 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
1528 }
1529
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001530 BasicBlock::iterator BI = BB->begin();
1531 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
1532 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001533
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001534 // Clone the non-phi instructions of BB into NewBB, keeping track of the
1535 // mapping and using it to remap operands in the cloned instructions.
1536 for (; !isa<TerminatorInst>(BI); ++BI) {
Nick Lewycky42fb7452009-09-27 07:38:41 +00001537 Instruction *New = BI->clone();
Daniel Dunbar6115b392009-07-26 09:48:23 +00001538 New->setName(BI->getName());
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001539 NewBB->getInstList().push_back(New);
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +00001540 ValueMapping[&*BI] = New;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001541
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001542 // Remap operands to patch up intra-block references.
1543 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
Dan Gohman43f33dd2009-07-02 00:17:47 +00001544 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
1545 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
1546 if (I != ValueMapping.end())
1547 New->setOperand(i, I->second);
1548 }
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001549 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001550
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001551 // We didn't copy the terminator from BB over to NewBB, because there is now
1552 // an unconditional jump to SuccBB. Insert the unconditional jump.
Manman Ren72d44b12015-10-15 14:59:40 +00001553 BranchInst *NewBI = BranchInst::Create(SuccBB, NewBB);
Devang Patel306f8db2011-05-04 22:48:19 +00001554 NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc());
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001555
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001556 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
1557 // PHI nodes for NewBB now.
Chris Lattner97b14052009-10-11 07:24:57 +00001558 AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001559
Chris Lattner84095072009-10-10 09:05:58 +00001560 // If there were values defined in BB that are used outside the block, then we
1561 // now have to update all uses of the value to use either the original value,
1562 // the cloned value, or some PHI derived value. This can require arbitrary
1563 // PHI insertion, of which we are prepared to do, clean these up now.
1564 SSAUpdater SSAUpdate;
1565 SmallVector<Use*, 16> UsesToRename;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001566 for (Instruction &I : *BB) {
Chris Lattner84095072009-10-10 09:05:58 +00001567 // Scan all uses of this instruction to see if it is used outside of its
1568 // block, and if so, record them in UsesToRename.
Benjamin Kramer543762d2016-01-09 18:43:01 +00001569 for (Use &U : I.uses()) {
Chandler Carruthcdf47882014-03-09 03:16:01 +00001570 Instruction *User = cast<Instruction>(U.getUser());
Chris Lattner84095072009-10-10 09:05:58 +00001571 if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
Chandler Carruthcdf47882014-03-09 03:16:01 +00001572 if (UserPN->getIncomingBlock(U) == BB)
Chris Lattner84095072009-10-10 09:05:58 +00001573 continue;
1574 } else if (User->getParent() == BB)
1575 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001576
Chandler Carruthcdf47882014-03-09 03:16:01 +00001577 UsesToRename.push_back(&U);
Chris Lattner84095072009-10-10 09:05:58 +00001578 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001579
Chris Lattner84095072009-10-10 09:05:58 +00001580 // If there are no uses outside the block, we're done with this instruction.
1581 if (UsesToRename.empty())
1582 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001583
Benjamin Kramer543762d2016-01-09 18:43:01 +00001584 DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
Chris Lattner84095072009-10-10 09:05:58 +00001585
1586 // We found a use of I outside of BB. Rename all uses of I that are outside
1587 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
1588 // with the two values we know.
Benjamin Kramer543762d2016-01-09 18:43:01 +00001589 SSAUpdate.Initialize(I.getType(), I.getName());
1590 SSAUpdate.AddAvailableValue(BB, &I);
1591 SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001592
Chris Lattner84095072009-10-10 09:05:58 +00001593 while (!UsesToRename.empty())
1594 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
David Greene1efdb452010-01-05 01:27:19 +00001595 DEBUG(dbgs() << "\n");
Chris Lattner84095072009-10-10 09:05:58 +00001596 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001597
1598
Chris Lattner88a1f022008-12-01 04:48:07 +00001599 // Ok, NewBB is good to go. Update the terminator of PredBB to jump to
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001600 // NewBB instead of BB. This eliminates predecessors from BB, which requires
1601 // us to simplify any PHI nodes in BB.
1602 TerminatorInst *PredTerm = PredBB->getTerminator();
1603 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
1604 if (PredTerm->getSuccessor(i) == BB) {
Owen Anderson99c985c2010-09-29 20:34:41 +00001605 BB->removePredecessor(PredBB, true);
Chris Lattnerff1c6e32008-04-20 22:39:42 +00001606 PredTerm->setSuccessor(i, NewBB);
1607 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001608
Chris Lattner88a1f022008-12-01 04:48:07 +00001609 // At this point, the IR is fully up to date and consistent. Do a quick scan
1610 // over the new instructions and zap any that are constants or dead. This
1611 // frequently happens because of phi translation.
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001612 SimplifyInstructionsInBlock(NewBB, TLI);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001613
Manman Ren72d44b12015-10-15 14:59:40 +00001614 // Update the edge weight from BB to SuccBB, which should be less than before.
1615 UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
1616
Chris Lattnerd579cb12009-05-04 02:28:08 +00001617 // Threaded an edge!
1618 ++NumThreads;
1619 return true;
Chris Lattner21157222008-04-20 21:13:06 +00001620}
Chris Lattner97b14052009-10-11 07:24:57 +00001621
Manman Ren72d44b12015-10-15 14:59:40 +00001622/// Create a new basic block that will be the predecessor of BB and successor of
Simon Pilgrim7d18a702016-11-20 13:19:49 +00001623/// all blocks in Preds. When profile data is available, update the frequency of
Manman Ren72d44b12015-10-15 14:59:40 +00001624/// this new block.
Sean Silva46590d52016-06-14 00:51:09 +00001625BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB,
1626 ArrayRef<BasicBlock *> Preds,
1627 const char *Suffix) {
Manman Ren72d44b12015-10-15 14:59:40 +00001628 // Collect the frequencies of all predecessors of BB, which will be used to
1629 // update the edge weight on BB->SuccBB.
1630 BlockFrequency PredBBFreq(0);
1631 if (HasProfileData)
1632 for (auto Pred : Preds)
1633 PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB);
1634
1635 BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix);
1636
1637 // Set the block frequency of the newly created PredBB, which is the sum of
1638 // frequencies of Preds.
1639 if (HasProfileData)
1640 BFI->setBlockFreq(PredBB, PredBBFreq.getFrequency());
1641 return PredBB;
1642}
1643
Adam Nemetc5208222016-09-06 16:08:33 +00001644bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
1645 const TerminatorInst *TI = BB->getTerminator();
1646 assert(TI->getNumSuccessors() > 1 && "not a split");
1647
1648 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
1649 if (!WeightsNode)
1650 return false;
1651
1652 MDString *MDName = cast<MDString>(WeightsNode->getOperand(0));
1653 if (MDName->getString() != "branch_weights")
1654 return false;
1655
1656 // Ensure there are weights for all of the successors. Note that the first
1657 // operand to the metadata node is a name, not a weight.
1658 return WeightsNode->getNumOperands() == TI->getNumSuccessors() + 1;
1659}
1660
Manman Ren72d44b12015-10-15 14:59:40 +00001661/// Update the block frequency of BB and branch weight and the metadata on the
1662/// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 -
1663/// Freq(PredBB->BB) / Freq(BB->SuccBB).
Sean Silva46590d52016-06-14 00:51:09 +00001664void JumpThreadingPass::UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
1665 BasicBlock *BB,
1666 BasicBlock *NewBB,
1667 BasicBlock *SuccBB) {
Manman Ren72d44b12015-10-15 14:59:40 +00001668 if (!HasProfileData)
1669 return;
1670
1671 assert(BFI && BPI && "BFI & BPI should have been created here");
1672
1673 // As the edge from PredBB to BB is deleted, we have to update the block
1674 // frequency of BB.
1675 auto BBOrigFreq = BFI->getBlockFreq(BB);
1676 auto NewBBFreq = BFI->getBlockFreq(NewBB);
1677 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);
1678 auto BBNewFreq = BBOrigFreq - NewBBFreq;
1679 BFI->setBlockFreq(BB, BBNewFreq.getFrequency());
1680
1681 // Collect updated outgoing edges' frequencies from BB and use them to update
Cong Houe93b8e12015-12-22 18:56:14 +00001682 // edge probabilities.
Manman Ren72d44b12015-10-15 14:59:40 +00001683 SmallVector<uint64_t, 4> BBSuccFreq;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001684 for (BasicBlock *Succ : successors(BB)) {
1685 auto SuccFreq = (Succ == SuccBB)
Manman Ren72d44b12015-10-15 14:59:40 +00001686 ? BB2SuccBBFreq - NewBBFreq
Benjamin Kramer543762d2016-01-09 18:43:01 +00001687 : BBOrigFreq * BPI->getEdgeProbability(BB, Succ);
Manman Ren72d44b12015-10-15 14:59:40 +00001688 BBSuccFreq.push_back(SuccFreq.getFrequency());
1689 }
1690
Cong Houe93b8e12015-12-22 18:56:14 +00001691 uint64_t MaxBBSuccFreq =
1692 *std::max_element(BBSuccFreq.begin(), BBSuccFreq.end());
Manman Ren72d44b12015-10-15 14:59:40 +00001693
Cong Hou6a2c71a2015-12-22 23:45:55 +00001694 SmallVector<BranchProbability, 4> BBSuccProbs;
1695 if (MaxBBSuccFreq == 0)
1696 BBSuccProbs.assign(BBSuccFreq.size(),
1697 {1, static_cast<unsigned>(BBSuccFreq.size())});
1698 else {
1699 for (uint64_t Freq : BBSuccFreq)
1700 BBSuccProbs.push_back(
1701 BranchProbability::getBranchProbability(Freq, MaxBBSuccFreq));
1702 // Normalize edge probabilities so that they sum up to one.
1703 BranchProbability::normalizeProbabilities(BBSuccProbs.begin(),
1704 BBSuccProbs.end());
1705 }
Manman Ren72d44b12015-10-15 14:59:40 +00001706
Cong Houe93b8e12015-12-22 18:56:14 +00001707 // Update edge probabilities in BPI.
1708 for (int I = 0, E = BBSuccProbs.size(); I < E; I++)
1709 BPI->setEdgeProbability(BB, I, BBSuccProbs[I]);
Manman Ren72d44b12015-10-15 14:59:40 +00001710
Adam Nemetc5208222016-09-06 16:08:33 +00001711 // Update the profile metadata as well.
1712 //
1713 // Don't do this if the profile of the transformed blocks was statically
1714 // estimated. (This could occur despite the function having an entry
1715 // frequency in completely cold parts of the CFG.)
1716 //
1717 // In this case we don't want to suggest to subsequent passes that the
1718 // calculated weights are fully consistent. Consider this graph:
1719 //
1720 // check_1
1721 // 50% / |
1722 // eq_1 | 50%
1723 // \ |
1724 // check_2
1725 // 50% / |
1726 // eq_2 | 50%
1727 // \ |
1728 // check_3
1729 // 50% / |
1730 // eq_3 | 50%
1731 // \ |
1732 //
1733 // Assuming the blocks check_* all compare the same value against 1, 2 and 3,
1734 // the overall probabilities are inconsistent; the total probability that the
1735 // value is either 1, 2 or 3 is 150%.
1736 //
1737 // As a consequence if we thread eq_1 -> check_2 to check_3, check_2->check_3
1738 // becomes 0%. This is even worse if the edge whose probability becomes 0% is
1739 // the loop exit edge. Then based solely on static estimation we would assume
1740 // the loop was extremely hot.
1741 //
1742 // FIXME this locally as well so that BPI and BFI are consistent as well. We
1743 // shouldn't make edges extremely likely or unlikely based solely on static
1744 // estimation.
1745 if (BBSuccProbs.size() >= 2 && doesBlockHaveProfileData(BB)) {
Cong Houe93b8e12015-12-22 18:56:14 +00001746 SmallVector<uint32_t, 4> Weights;
1747 for (auto Prob : BBSuccProbs)
1748 Weights.push_back(Prob.getNumerator());
1749
Manman Ren72d44b12015-10-15 14:59:40 +00001750 auto TI = BB->getTerminator();
1751 TI->setMetadata(
1752 LLVMContext::MD_prof,
1753 MDBuilder(TI->getParent()->getContext()).createBranchWeights(Weights));
1754 }
1755}
1756
Chris Lattner97b14052009-10-11 07:24:57 +00001757/// DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch
1758/// to BB which contains an i1 PHI node and a conditional branch on that PHI.
1759/// If we can duplicate the contents of BB up into PredBB do so now, this
1760/// improves the odds that the branch will be on an analyzable instruction like
1761/// a compare.
Sean Silva46590d52016-06-14 00:51:09 +00001762bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
1763 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) {
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001764 assert(!PredBBs.empty() && "Can't handle an empty set");
1765
Chris Lattner97b14052009-10-11 07:24:57 +00001766 // If BB is a loop header, then duplicating this block outside the loop would
1767 // cause us to transform this into an irreducible loop, don't do this.
1768 // See the comments above FindLoopHeaders for justifications and caveats.
1769 if (LoopHeaders.count(BB)) {
David Greene1efdb452010-01-05 01:27:19 +00001770 DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName()
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001771 << "' into predecessor block '" << PredBBs[0]->getName()
Chris Lattner97b14052009-10-11 07:24:57 +00001772 << "' - it might create an irreducible loop!\n");
1773 return false;
1774 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001775
Sanjoy Das8b859c22017-02-17 04:21:14 +00001776 unsigned DuplicationCost =
1777 getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
Michael Liaod1209162014-09-24 04:59:06 +00001778 if (DuplicationCost > BBDupThreshold) {
David Greene1efdb452010-01-05 01:27:19 +00001779 DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
Chris Lattner97b14052009-10-11 07:24:57 +00001780 << "' - Cost is too high: " << DuplicationCost << "\n");
1781 return false;
1782 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001783
David L Kreitzerda700ce2015-09-16 13:27:30 +00001784 // And finally, do it! Start by factoring the predecessors if needed.
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001785 BasicBlock *PredBB;
1786 if (PredBBs.size() == 1)
1787 PredBB = PredBBs[0];
1788 else {
1789 DEBUG(dbgs() << " Factoring out " << PredBBs.size()
1790 << " common predecessors.\n");
Manman Ren72d44b12015-10-15 14:59:40 +00001791 PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001792 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001793
Chris Lattner97b14052009-10-11 07:24:57 +00001794 // Okay, we decided to do this! Clone all the instructions in BB onto the end
1795 // of PredBB.
David Greene1efdb452010-01-05 01:27:19 +00001796 DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '"
Chris Lattner97b14052009-10-11 07:24:57 +00001797 << PredBB->getName() << "' to eliminate branch on phi. Cost: "
1798 << DuplicationCost << " block is:" << *BB << "\n");
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001799
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001800 // Unless PredBB ends with an unconditional branch, split the edge so that we
1801 // can just clone the bits from BB into the end of the new PredBB.
Chris Lattner29b15c52010-01-23 19:21:31 +00001802 BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001803
Craig Topperf40110f2014-04-25 05:29:35 +00001804 if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
Chandler Carruthd4500562015-01-19 12:36:53 +00001805 PredBB = SplitEdge(PredBB, BB);
Chris Lattnereb73bdb2010-01-12 02:07:17 +00001806 OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
1807 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001808
Chris Lattner97b14052009-10-11 07:24:57 +00001809 // We are going to have to map operands from the original BB block into the
1810 // PredBB block. Evaluate PHI nodes in BB.
1811 DenseMap<Instruction*, Value*> ValueMapping;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001812
Chris Lattner97b14052009-10-11 07:24:57 +00001813 BasicBlock::iterator BI = BB->begin();
1814 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
1815 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
Chris Lattner97b14052009-10-11 07:24:57 +00001816 // Clone the non-phi instructions of BB into PredBB, keeping track of the
1817 // mapping and using it to remap operands in the cloned instructions.
1818 for (; BI != BB->end(); ++BI) {
1819 Instruction *New = BI->clone();
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001820
Chris Lattner97b14052009-10-11 07:24:57 +00001821 // Remap operands to patch up intra-block references.
1822 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
1823 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
1824 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
1825 if (I != ValueMapping.end())
1826 New->setOperand(i, I->second);
1827 }
Chris Lattner573da8a2010-01-12 20:41:47 +00001828
1829 // If this instruction can be simplified after the operands are updated,
1830 // just use the simplified value instead. This frequently happens due to
1831 // phi translation.
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001832 if (Value *IV =
1833 SimplifyInstruction(New, BB->getModule()->getDataLayout())) {
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +00001834 ValueMapping[&*BI] = IV;
David Majnemerb8da3a22016-06-25 00:04:10 +00001835 if (!New->mayHaveSideEffects()) {
1836 delete New;
1837 New = nullptr;
1838 }
Chris Lattner573da8a2010-01-12 20:41:47 +00001839 } else {
David Majnemerb8da3a22016-06-25 00:04:10 +00001840 ValueMapping[&*BI] = New;
1841 }
1842 if (New) {
Chris Lattner573da8a2010-01-12 20:41:47 +00001843 // Otherwise, insert the new instruction into the block.
1844 New->setName(BI->getName());
Duncan P. N. Exon Smith3a9c9e32015-10-13 18:26:00 +00001845 PredBB->getInstList().insert(OldPredBranch->getIterator(), New);
Chris Lattner573da8a2010-01-12 20:41:47 +00001846 }
Chris Lattner97b14052009-10-11 07:24:57 +00001847 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001848
Chris Lattner97b14052009-10-11 07:24:57 +00001849 // Check to see if the targets of the branch had PHI nodes. If so, we need to
1850 // add entries to the PHI nodes for branch from PredBB now.
1851 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
1852 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
1853 ValueMapping);
1854 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB,
1855 ValueMapping);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001856
Chris Lattner97b14052009-10-11 07:24:57 +00001857 // If there were values defined in BB that are used outside the block, then we
1858 // now have to update all uses of the value to use either the original value,
1859 // the cloned value, or some PHI derived value. This can require arbitrary
1860 // PHI insertion, of which we are prepared to do, clean these up now.
1861 SSAUpdater SSAUpdate;
1862 SmallVector<Use*, 16> UsesToRename;
Benjamin Kramer543762d2016-01-09 18:43:01 +00001863 for (Instruction &I : *BB) {
Chris Lattner97b14052009-10-11 07:24:57 +00001864 // Scan all uses of this instruction to see if it is used outside of its
1865 // block, and if so, record them in UsesToRename.
Benjamin Kramer543762d2016-01-09 18:43:01 +00001866 for (Use &U : I.uses()) {
Chandler Carruthcdf47882014-03-09 03:16:01 +00001867 Instruction *User = cast<Instruction>(U.getUser());
Chris Lattner97b14052009-10-11 07:24:57 +00001868 if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
Chandler Carruthcdf47882014-03-09 03:16:01 +00001869 if (UserPN->getIncomingBlock(U) == BB)
Chris Lattner97b14052009-10-11 07:24:57 +00001870 continue;
1871 } else if (User->getParent() == BB)
1872 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001873
Chandler Carruthcdf47882014-03-09 03:16:01 +00001874 UsesToRename.push_back(&U);
Chris Lattner97b14052009-10-11 07:24:57 +00001875 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001876
Chris Lattner97b14052009-10-11 07:24:57 +00001877 // If there are no uses outside the block, we're done with this instruction.
1878 if (UsesToRename.empty())
1879 continue;
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001880
Benjamin Kramer543762d2016-01-09 18:43:01 +00001881 DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001882
Chris Lattner97b14052009-10-11 07:24:57 +00001883 // We found a use of I outside of BB. Rename all uses of I that are outside
1884 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
1885 // with the two values we know.
Benjamin Kramer543762d2016-01-09 18:43:01 +00001886 SSAUpdate.Initialize(I.getType(), I.getName());
1887 SSAUpdate.AddAvailableValue(BB, &I);
1888 SSAUpdate.AddAvailableValue(PredBB, ValueMapping[&I]);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001889
Chris Lattner97b14052009-10-11 07:24:57 +00001890 while (!UsesToRename.empty())
1891 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
David Greene1efdb452010-01-05 01:27:19 +00001892 DEBUG(dbgs() << "\n");
Chris Lattner97b14052009-10-11 07:24:57 +00001893 }
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001894
Chris Lattner97b14052009-10-11 07:24:57 +00001895 // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
1896 // that we nuked.
Owen Anderson99c985c2010-09-29 20:34:41 +00001897 BB->removePredecessor(PredBB, true);
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001898
Chris Lattner97b14052009-10-11 07:24:57 +00001899 // Remove the unconditional branch at the end of the PredBB block.
1900 OldPredBranch->eraseFromParent();
Frits van Bommel5e75ef42010-12-05 19:02:47 +00001901
Chris Lattner97b14052009-10-11 07:24:57 +00001902 ++NumDupes;
1903 return true;
1904}
Benjamin Kramer6a4976d2013-08-07 10:29:38 +00001905
1906/// TryToUnfoldSelect - Look for blocks of the form
1907/// bb1:
1908/// %a = select
Xin Tong3ca169f2017-02-26 19:08:44 +00001909/// br bb2
Benjamin Kramer6a4976d2013-08-07 10:29:38 +00001910///
1911/// bb2:
Xin Tong3ca169f2017-02-26 19:08:44 +00001912/// %p = phi [%a, %bb1] ...
Benjamin Kramer6a4976d2013-08-07 10:29:38 +00001913/// %c = icmp %p
1914/// br i1 %c
1915///
1916/// And expand the select into a branch structure if one of its arms allows %c
1917/// to be folded. This later enables threading from bb1 over bb2.
Sean Silva46590d52016-06-14 00:51:09 +00001918bool JumpThreadingPass::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) {
Benjamin Kramer6a4976d2013-08-07 10:29:38 +00001919 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
1920 PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0));
1921 Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1));
1922
1923 if (!CondBr || !CondBr->isConditional() || !CondLHS ||
1924 CondLHS->getParent() != BB)
1925 return false;
1926
1927 for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
1928 BasicBlock *Pred = CondLHS->getIncomingBlock(I);
1929 SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I));
1930
1931 // Look if one of the incoming values is a select in the corresponding
1932 // predecessor.
1933 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
1934 continue;
1935
1936 BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
1937 if (!PredTerm || !PredTerm->isUnconditional())
1938 continue;
1939
1940 // Now check if one of the select values would allow us to constant fold the
1941 // terminator in BB. We don't do the transform if both sides fold, those
1942 // cases will be threaded in any case.
1943 LazyValueInfo::Tristate LHSFolds =
1944 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),
Hal Finkel7e184492014-09-07 20:29:59 +00001945 CondRHS, Pred, BB, CondCmp);
Benjamin Kramer6a4976d2013-08-07 10:29:38 +00001946 LazyValueInfo::Tristate RHSFolds =
1947 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),
Hal Finkel7e184492014-09-07 20:29:59 +00001948 CondRHS, Pred, BB, CondCmp);
Benjamin Kramer6a4976d2013-08-07 10:29:38 +00001949 if ((LHSFolds != LazyValueInfo::Unknown ||
1950 RHSFolds != LazyValueInfo::Unknown) &&
1951 LHSFolds != RHSFolds) {
1952 // Expand the select.
1953 //
1954 // Pred --
1955 // | v
1956 // | NewBB
1957 // | |
1958 // |-----
1959 // v
1960 // BB
1961 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
1962 BB->getParent(), BB);
1963 // Move the unconditional branch to NewBB.
1964 PredTerm->removeFromParent();
1965 NewBB->getInstList().insert(NewBB->end(), PredTerm);
1966 // Create a conditional branch and update PHI nodes.
1967 BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
1968 CondLHS->setIncomingValue(I, SI->getFalseValue());
1969 CondLHS->addIncoming(SI->getTrueValue(), NewBB);
1970 // The select is now dead.
1971 SI->eraseFromParent();
1972
1973 // Update any other PHI nodes in BB.
1974 for (BasicBlock::iterator BI = BB->begin();
1975 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
1976 if (Phi != CondLHS)
1977 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
1978 return true;
1979 }
1980 }
1981 return false;
1982}
Haicheng Wua6a32792016-01-08 19:39:39 +00001983
Pablo Barrio4f80c932016-11-15 15:42:23 +00001984/// TryToUnfoldSelectInCurrBB - Look for PHI/Select in the same BB of the form
Haicheng Wua6a32792016-01-08 19:39:39 +00001985/// bb:
1986/// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ...
1987/// %s = select p, trueval, falseval
1988///
Pablo Barrio4f80c932016-11-15 15:42:23 +00001989/// And expand the select into a branch structure. This later enables
Haicheng Wua6a32792016-01-08 19:39:39 +00001990/// jump-threading over bb in this pass.
1991///
Pablo Barrio4f80c932016-11-15 15:42:23 +00001992/// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
1993/// select if the associated PHI has at least one constant. If the unfolded
1994/// select is not jump-threaded, it will be folded again in the later
1995/// optimizations.
Sean Silva46590d52016-06-14 00:51:09 +00001996bool JumpThreadingPass::TryToUnfoldSelectInCurrBB(BasicBlock *BB) {
Haicheng Wua6a32792016-01-08 19:39:39 +00001997 // If threading this would thread across a loop header, don't thread the edge.
1998 // See the comments above FindLoopHeaders for justifications and caveats.
1999 if (LoopHeaders.count(BB))
2000 return false;
2001
Pablo Barrio4f80c932016-11-15 15:42:23 +00002002 // Look for a Phi/Select pair in the same basic block. The Phi feeds the
2003 // condition of the Select and at least one of the incoming values is a
2004 // constant.
2005 for (BasicBlock::iterator BI = BB->begin();
2006 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2007 unsigned NumPHIValues = PN->getNumIncomingValues();
2008 if (NumPHIValues == 0 || !PN->hasOneUse())
Nico Weberb38d3412016-10-24 14:52:04 +00002009 continue;
Pablo Barrio4f80c932016-11-15 15:42:23 +00002010
2011 SelectInst *SI = dyn_cast<SelectInst>(PN->user_back());
2012 if (!SI || SI->getParent() != BB)
2013 continue;
2014
2015 Value *Cond = SI->getCondition();
2016 if (!Cond || Cond != PN || !Cond->getType()->isIntegerTy(1))
2017 continue;
2018
2019 bool HasConst = false;
2020 for (unsigned i = 0; i != NumPHIValues; ++i) {
2021 if (PN->getIncomingBlock(i) == BB)
2022 return false;
2023 if (isa<ConstantInt>(PN->getIncomingValue(i)))
2024 HasConst = true;
Haicheng Wua6a32792016-01-08 19:39:39 +00002025 }
2026
Pablo Barrio4f80c932016-11-15 15:42:23 +00002027 if (HasConst) {
2028 // Expand the select.
2029 TerminatorInst *Term =
2030 SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
2031 PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
2032 NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
2033 NewPN->addIncoming(SI->getFalseValue(), BB);
2034 SI->replaceAllUsesWith(NewPN);
2035 SI->eraseFromParent();
2036 return true;
Haicheng Wua6a32792016-01-08 19:39:39 +00002037 }
2038 }
Pablo Barrio4f80c932016-11-15 15:42:23 +00002039
2040 return false;
Haicheng Wua6a32792016-01-08 19:39:39 +00002041}
Sanjoy Das8b859c22017-02-17 04:21:14 +00002042
2043/// Try to propagate a guard from the current BB into one of its predecessors
2044/// in case if another branch of execution implies that the condition of this
2045/// guard is always true. Currently we only process the simplest case that
2046/// looks like:
2047///
2048/// Start:
2049/// %cond = ...
2050/// br i1 %cond, label %T1, label %F1
2051/// T1:
2052/// br label %Merge
2053/// F1:
2054/// br label %Merge
2055/// Merge:
2056/// %condGuard = ...
2057/// call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
2058///
2059/// And cond either implies condGuard or !condGuard. In this case all the
2060/// instructions before the guard can be duplicated in both branches, and the
2061/// guard is then threaded to one of them.
2062bool JumpThreadingPass::ProcessGuards(BasicBlock *BB) {
2063 using namespace PatternMatch;
2064 // We only want to deal with two predecessors.
2065 BasicBlock *Pred1, *Pred2;
2066 auto PI = pred_begin(BB), PE = pred_end(BB);
2067 if (PI == PE)
2068 return false;
2069 Pred1 = *PI++;
2070 if (PI == PE)
2071 return false;
2072 Pred2 = *PI++;
2073 if (PI != PE)
2074 return false;
2075 if (Pred1 == Pred2)
2076 return false;
2077
2078 // Try to thread one of the guards of the block.
2079 // TODO: Look up deeper than to immediate predecessor?
2080 auto *Parent = Pred1->getSinglePredecessor();
2081 if (!Parent || Parent != Pred2->getSinglePredecessor())
2082 return false;
2083
2084 if (auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
2085 for (auto &I : *BB)
2086 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
2087 if (ThreadGuard(BB, cast<IntrinsicInst>(&I), BI))
2088 return true;
2089
2090 return false;
2091}
2092
2093/// Try to propagate the guard from BB which is the lower block of a diamond
2094/// to one of its branches, in case if diamond's condition implies guard's
2095/// condition.
2096bool JumpThreadingPass::ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard,
2097 BranchInst *BI) {
2098 assert(BI->getNumSuccessors() == 2 && "Wrong number of successors?");
2099 assert(BI->isConditional() && "Unconditional branch has 2 successors?");
2100 Value *GuardCond = Guard->getArgOperand(0);
2101 Value *BranchCond = BI->getCondition();
2102 BasicBlock *TrueDest = BI->getSuccessor(0);
2103 BasicBlock *FalseDest = BI->getSuccessor(1);
2104
2105 auto &DL = BB->getModule()->getDataLayout();
2106 bool TrueDestIsSafe = false;
2107 bool FalseDestIsSafe = false;
2108
2109 // True dest is safe if BranchCond => GuardCond.
2110 auto Impl = isImpliedCondition(BranchCond, GuardCond, DL);
2111 if (Impl && *Impl)
2112 TrueDestIsSafe = true;
2113 else {
2114 // False dest is safe if !BranchCond => GuardCond.
2115 Impl =
2116 isImpliedCondition(BranchCond, GuardCond, DL, /* InvertAPred */ true);
2117 if (Impl && *Impl)
2118 FalseDestIsSafe = true;
2119 }
2120
2121 if (!TrueDestIsSafe && !FalseDestIsSafe)
2122 return false;
2123
2124 BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
2125 BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
2126
2127 ValueToValueMapTy UnguardedMapping, GuardedMapping;
2128 Instruction *AfterGuard = Guard->getNextNode();
2129 unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
2130 if (Cost > BBDupThreshold)
2131 return false;
2132 // Duplicate all instructions before the guard and the guard itself to the
2133 // branch where implication is not proved.
2134 GuardedBlock = DuplicateInstructionsInSplitBetween(
2135 BB, GuardedBlock, AfterGuard, GuardedMapping);
2136 assert(GuardedBlock && "Could not create the guarded block?");
2137 // Duplicate all instructions before the guard in the unguarded branch.
2138 // Since we have successfully duplicated the guarded block and this block
2139 // has fewer instructions, we expect it to succeed.
2140 UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock,
2141 Guard, UnguardedMapping);
2142 assert(UnguardedBlock && "Could not create the unguarded block?");
2143 DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
2144 << GuardedBlock->getName() << "\n");
2145
2146 // Some instructions before the guard may still have uses. For them, we need
2147 // to create Phi nodes merging their copies in both guarded and unguarded
2148 // branches. Those instructions that have no uses can be just removed.
2149 SmallVector<Instruction *, 4> ToRemove;
2150 for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
2151 if (!isa<PHINode>(&*BI))
2152 ToRemove.push_back(&*BI);
2153
2154 Instruction *InsertionPoint = &*BB->getFirstInsertionPt();
2155 assert(InsertionPoint && "Empty block?");
2156 // Substitute with Phis & remove.
2157 for (auto *Inst : reverse(ToRemove)) {
2158 if (!Inst->use_empty()) {
2159 PHINode *NewPN = PHINode::Create(Inst->getType(), 2);
2160 NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
2161 NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
2162 NewPN->insertBefore(InsertionPoint);
2163 Inst->replaceAllUsesWith(NewPN);
2164 }
2165 Inst->eraseFromParent();
2166 }
2167 return true;
2168}