Bug Summary

File:lib/CodeGen/CodeGenPrepare.cpp
Warning:line 5542, column 3
Undefined or garbage value returned to caller

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CodeGenPrepare.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/CodeGen -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp -faddrsig
1//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass munges the code in the input function to better prepare it for
11// SelectionDAG-based code generation. This works around limitations in it's
12// basic-block-at-a-time approach. It should eventually be removed.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/PointerIntPair.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/BlockFrequencyInfo.h"
25#include "llvm/Analysis/BranchProbabilityInfo.h"
26#include "llvm/Analysis/ConstantFolding.h"
27#include "llvm/Analysis/InstructionSimplify.h"
28#include "llvm/Analysis/LoopInfo.h"
29#include "llvm/Analysis/MemoryBuiltins.h"
30#include "llvm/Analysis/ProfileSummaryInfo.h"
31#include "llvm/Analysis/TargetLibraryInfo.h"
32#include "llvm/Analysis/TargetTransformInfo.h"
33#include "llvm/Transforms/Utils/Local.h"
34#include "llvm/Analysis/ValueTracking.h"
35#include "llvm/CodeGen/Analysis.h"
36#include "llvm/CodeGen/ISDOpcodes.h"
37#include "llvm/CodeGen/SelectionDAGNodes.h"
38#include "llvm/CodeGen/TargetLowering.h"
39#include "llvm/CodeGen/TargetPassConfig.h"
40#include "llvm/CodeGen/TargetSubtargetInfo.h"
41#include "llvm/CodeGen/ValueTypes.h"
42#include "llvm/Config/llvm-config.h"
43#include "llvm/IR/Argument.h"
44#include "llvm/IR/Attributes.h"
45#include "llvm/IR/BasicBlock.h"
46#include "llvm/IR/CallSite.h"
47#include "llvm/IR/Constant.h"
48#include "llvm/IR/Constants.h"
49#include "llvm/IR/DataLayout.h"
50#include "llvm/IR/DerivedTypes.h"
51#include "llvm/IR/Dominators.h"
52#include "llvm/IR/Function.h"
53#include "llvm/IR/GetElementPtrTypeIterator.h"
54#include "llvm/IR/GlobalValue.h"
55#include "llvm/IR/GlobalVariable.h"
56#include "llvm/IR/IRBuilder.h"
57#include "llvm/IR/InlineAsm.h"
58#include "llvm/IR/InstrTypes.h"
59#include "llvm/IR/Instruction.h"
60#include "llvm/IR/Instructions.h"
61#include "llvm/IR/IntrinsicInst.h"
62#include "llvm/IR/Intrinsics.h"
63#include "llvm/IR/LLVMContext.h"
64#include "llvm/IR/MDBuilder.h"
65#include "llvm/IR/Module.h"
66#include "llvm/IR/Operator.h"
67#include "llvm/IR/PatternMatch.h"
68#include "llvm/IR/Statepoint.h"
69#include "llvm/IR/Type.h"
70#include "llvm/IR/Use.h"
71#include "llvm/IR/User.h"
72#include "llvm/IR/Value.h"
73#include "llvm/IR/ValueHandle.h"
74#include "llvm/IR/ValueMap.h"
75#include "llvm/Pass.h"
76#include "llvm/Support/BlockFrequency.h"
77#include "llvm/Support/BranchProbability.h"
78#include "llvm/Support/Casting.h"
79#include "llvm/Support/CommandLine.h"
80#include "llvm/Support/Compiler.h"
81#include "llvm/Support/Debug.h"
82#include "llvm/Support/ErrorHandling.h"
83#include "llvm/Support/MachineValueType.h"
84#include "llvm/Support/MathExtras.h"
85#include "llvm/Support/raw_ostream.h"
86#include "llvm/Target/TargetMachine.h"
87#include "llvm/Target/TargetOptions.h"
88#include "llvm/Transforms/Utils/BasicBlockUtils.h"
89#include "llvm/Transforms/Utils/BypassSlowDivision.h"
90#include "llvm/Transforms/Utils/SimplifyLibCalls.h"
91#include <algorithm>
92#include <cassert>
93#include <cstdint>
94#include <iterator>
95#include <limits>
96#include <memory>
97#include <utility>
98#include <vector>
99
100using namespace llvm;
101using namespace llvm::PatternMatch;
102
103#define DEBUG_TYPE"codegenprepare" "codegenprepare"
104
105STATISTIC(NumBlocksElim, "Number of blocks eliminated")static llvm::Statistic NumBlocksElim = {"codegenprepare", "NumBlocksElim"
, "Number of blocks eliminated", {0}, {false}}
;
106STATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated")static llvm::Statistic NumPHIsElim = {"codegenprepare", "NumPHIsElim"
, "Number of trivial PHIs eliminated", {0}, {false}}
;
107STATISTIC(NumGEPsElim, "Number of GEPs converted to casts")static llvm::Statistic NumGEPsElim = {"codegenprepare", "NumGEPsElim"
, "Number of GEPs converted to casts", {0}, {false}}
;
108STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "static llvm::Statistic NumCmpUses = {"codegenprepare", "NumCmpUses"
, "Number of uses of Cmp expressions replaced with uses of " "sunken Cmps"
, {0}, {false}}
109 "sunken Cmps")static llvm::Statistic NumCmpUses = {"codegenprepare", "NumCmpUses"
, "Number of uses of Cmp expressions replaced with uses of " "sunken Cmps"
, {0}, {false}}
;
110STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "static llvm::Statistic NumCastUses = {"codegenprepare", "NumCastUses"
, "Number of uses of Cast expressions replaced with uses " "of sunken Casts"
, {0}, {false}}
111 "of sunken Casts")static llvm::Statistic NumCastUses = {"codegenprepare", "NumCastUses"
, "Number of uses of Cast expressions replaced with uses " "of sunken Casts"
, {0}, {false}}
;
112STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "static llvm::Statistic NumMemoryInsts = {"codegenprepare", "NumMemoryInsts"
, "Number of memory instructions whose address " "computations were sunk"
, {0}, {false}}
113 "computations were sunk")static llvm::Statistic NumMemoryInsts = {"codegenprepare", "NumMemoryInsts"
, "Number of memory instructions whose address " "computations were sunk"
, {0}, {false}}
;
114STATISTIC(NumMemoryInstsPhiCreated,static llvm::Statistic NumMemoryInstsPhiCreated = {"codegenprepare"
, "NumMemoryInstsPhiCreated", "Number of phis created when address "
"computations were sunk to memory instructions", {0}, {false
}}
115 "Number of phis created when address "static llvm::Statistic NumMemoryInstsPhiCreated = {"codegenprepare"
, "NumMemoryInstsPhiCreated", "Number of phis created when address "
"computations were sunk to memory instructions", {0}, {false
}}
116 "computations were sunk to memory instructions")static llvm::Statistic NumMemoryInstsPhiCreated = {"codegenprepare"
, "NumMemoryInstsPhiCreated", "Number of phis created when address "
"computations were sunk to memory instructions", {0}, {false
}}
;
117STATISTIC(NumMemoryInstsSelectCreated,static llvm::Statistic NumMemoryInstsSelectCreated = {"codegenprepare"
, "NumMemoryInstsSelectCreated", "Number of select created when address "
"computations were sunk to memory instructions", {0}, {false
}}
118 "Number of select created when address "static llvm::Statistic NumMemoryInstsSelectCreated = {"codegenprepare"
, "NumMemoryInstsSelectCreated", "Number of select created when address "
"computations were sunk to memory instructions", {0}, {false
}}
119 "computations were sunk to memory instructions")static llvm::Statistic NumMemoryInstsSelectCreated = {"codegenprepare"
, "NumMemoryInstsSelectCreated", "Number of select created when address "
"computations were sunk to memory instructions", {0}, {false
}}
;
120STATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads")static llvm::Statistic NumExtsMoved = {"codegenprepare", "NumExtsMoved"
, "Number of [s|z]ext instructions combined with loads", {0},
{false}}
;
121STATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized")static llvm::Statistic NumExtUses = {"codegenprepare", "NumExtUses"
, "Number of uses of [s|z]ext instructions optimized", {0}, {
false}}
;
122STATISTIC(NumAndsAdded,static llvm::Statistic NumAndsAdded = {"codegenprepare", "NumAndsAdded"
, "Number of and mask instructions added to form ext loads", {
0}, {false}}
123 "Number of and mask instructions added to form ext loads")static llvm::Statistic NumAndsAdded = {"codegenprepare", "NumAndsAdded"
, "Number of and mask instructions added to form ext loads", {
0}, {false}}
;
124STATISTIC(NumAndUses, "Number of uses of and mask instructions optimized")static llvm::Statistic NumAndUses = {"codegenprepare", "NumAndUses"
, "Number of uses of and mask instructions optimized", {0}, {
false}}
;
125STATISTIC(NumRetsDup, "Number of return instructions duplicated")static llvm::Statistic NumRetsDup = {"codegenprepare", "NumRetsDup"
, "Number of return instructions duplicated", {0}, {false}}
;
126STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved")static llvm::Statistic NumDbgValueMoved = {"codegenprepare", "NumDbgValueMoved"
, "Number of debug value instructions moved", {0}, {false}}
;
127STATISTIC(NumSelectsExpanded, "Number of selects turned into branches")static llvm::Statistic NumSelectsExpanded = {"codegenprepare"
, "NumSelectsExpanded", "Number of selects turned into branches"
, {0}, {false}}
;
128STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed")static llvm::Statistic NumStoreExtractExposed = {"codegenprepare"
, "NumStoreExtractExposed", "Number of store(extractelement) exposed"
, {0}, {false}}
;
129
130static cl::opt<bool> DisableBranchOpts(
131 "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
132 cl::desc("Disable branch optimizations in CodeGenPrepare"));
133
134static cl::opt<bool>
135 DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false),
136 cl::desc("Disable GC optimizations in CodeGenPrepare"));
137
138static cl::opt<bool> DisableSelectToBranch(
139 "disable-cgp-select2branch", cl::Hidden, cl::init(false),
140 cl::desc("Disable select to branch conversion."));
141
142static cl::opt<bool> AddrSinkUsingGEPs(
143 "addr-sink-using-gep", cl::Hidden, cl::init(true),
144 cl::desc("Address sinking in CGP using GEPs."));
145
146static cl::opt<bool> EnableAndCmpSinking(
147 "enable-andcmp-sinking", cl::Hidden, cl::init(true),
148 cl::desc("Enable sinkinig and/cmp into branches."));
149
150static cl::opt<bool> DisableStoreExtract(
151 "disable-cgp-store-extract", cl::Hidden, cl::init(false),
152 cl::desc("Disable store(extract) optimizations in CodeGenPrepare"));
153
154static cl::opt<bool> StressStoreExtract(
155 "stress-cgp-store-extract", cl::Hidden, cl::init(false),
156 cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"));
157
158static cl::opt<bool> DisableExtLdPromotion(
159 "disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
160 cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
161 "CodeGenPrepare"));
162
163static cl::opt<bool> StressExtLdPromotion(
164 "stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
165 cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
166 "optimization in CodeGenPrepare"));
167
168static cl::opt<bool> DisablePreheaderProtect(
169 "disable-preheader-prot", cl::Hidden, cl::init(false),
170 cl::desc("Disable protection against removing loop preheaders"));
171
172static cl::opt<bool> ProfileGuidedSectionPrefix(
173 "profile-guided-section-prefix", cl::Hidden, cl::init(true), cl::ZeroOrMore,
174 cl::desc("Use profile info to add section prefix for hot/cold functions"));
175
176static cl::opt<unsigned> FreqRatioToSkipMerge(
177 "cgp-freq-ratio-to-skip-merge", cl::Hidden, cl::init(2),
178 cl::desc("Skip merging empty blocks if (frequency of empty block) / "
179 "(frequency of destination block) is greater than this ratio"));
180
181static cl::opt<bool> ForceSplitStore(
182 "force-split-store", cl::Hidden, cl::init(false),
183 cl::desc("Force store splitting no matter what the target query says."));
184
185static cl::opt<bool>
186EnableTypePromotionMerge("cgp-type-promotion-merge", cl::Hidden,
187 cl::desc("Enable merging of redundant sexts when one is dominating"
188 " the other."), cl::init(true));
189
190static cl::opt<bool> DisableComplexAddrModes(
191 "disable-complex-addr-modes", cl::Hidden, cl::init(false),
192 cl::desc("Disables combining addressing modes with different parts "
193 "in optimizeMemoryInst."));
194
195static cl::opt<bool>
196AddrSinkNewPhis("addr-sink-new-phis", cl::Hidden, cl::init(false),
197 cl::desc("Allow creation of Phis in Address sinking."));
198
199static cl::opt<bool>
200AddrSinkNewSelects("addr-sink-new-select", cl::Hidden, cl::init(true),
201 cl::desc("Allow creation of selects in Address sinking."));
202
203static cl::opt<bool> AddrSinkCombineBaseReg(
204 "addr-sink-combine-base-reg", cl::Hidden, cl::init(true),
205 cl::desc("Allow combining of BaseReg field in Address sinking."));
206
207static cl::opt<bool> AddrSinkCombineBaseGV(
208 "addr-sink-combine-base-gv", cl::Hidden, cl::init(true),
209 cl::desc("Allow combining of BaseGV field in Address sinking."));
210
211static cl::opt<bool> AddrSinkCombineBaseOffs(
212 "addr-sink-combine-base-offs", cl::Hidden, cl::init(true),
213 cl::desc("Allow combining of BaseOffs field in Address sinking."));
214
215static cl::opt<bool> AddrSinkCombineScaledReg(
216 "addr-sink-combine-scaled-reg", cl::Hidden, cl::init(true),
217 cl::desc("Allow combining of ScaledReg field in Address sinking."));
218
219static cl::opt<bool>
220 EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden,
221 cl::init(true),
222 cl::desc("Enable splitting large offset of GEP."));
223
224namespace {
225
226using SetOfInstrs = SmallPtrSet<Instruction *, 16>;
227using TypeIsSExt = PointerIntPair<Type *, 1, bool>;
228using InstrToOrigTy = DenseMap<Instruction *, TypeIsSExt>;
229using SExts = SmallVector<Instruction *, 16>;
230using ValueToSExts = DenseMap<Value *, SExts>;
231
232class TypePromotionTransaction;
233
234 class CodeGenPrepare : public FunctionPass {
235 const TargetMachine *TM = nullptr;
236 const TargetSubtargetInfo *SubtargetInfo;
237 const TargetLowering *TLI = nullptr;
238 const TargetRegisterInfo *TRI;
239 const TargetTransformInfo *TTI = nullptr;
240 const TargetLibraryInfo *TLInfo;
241 const LoopInfo *LI;
242 std::unique_ptr<BlockFrequencyInfo> BFI;
243 std::unique_ptr<BranchProbabilityInfo> BPI;
244
245 /// As we scan instructions optimizing them, this is the next instruction
246 /// to optimize. Transforms that can invalidate this should update it.
247 BasicBlock::iterator CurInstIterator;
248
249 /// Keeps track of non-local addresses that have been sunk into a block.
250 /// This allows us to avoid inserting duplicate code for blocks with
251 /// multiple load/stores of the same address. The usage of WeakTrackingVH
252 /// enables SunkAddrs to be treated as a cache whose entries can be
253 /// invalidated if a sunken address computation has been erased.
254 ValueMap<Value*, WeakTrackingVH> SunkAddrs;
255
256 /// Keeps track of all instructions inserted for the current function.
257 SetOfInstrs InsertedInsts;
258
259 /// Keeps track of the type of the related instruction before their
260 /// promotion for the current function.
261 InstrToOrigTy PromotedInsts;
262
263 /// Keep track of instructions removed during promotion.
264 SetOfInstrs RemovedInsts;
265
266 /// Keep track of sext chains based on their initial value.
267 DenseMap<Value *, Instruction *> SeenChainsForSExt;
268
269 /// Keep track of GEPs accessing the same data structures such as structs or
270 /// arrays that are candidates to be split later because of their large
271 /// size.
272 DenseMap<
273 AssertingVH<Value>,
274 SmallVector<std::pair<AssertingVH<GetElementPtrInst>, int64_t>, 32>>
275 LargeOffsetGEPMap;
276
277 /// Keep track of new GEP base after splitting the GEPs having large offset.
278 SmallSet<AssertingVH<Value>, 2> NewGEPBases;
279
280 /// Map serial numbers to Large offset GEPs.
281 DenseMap<AssertingVH<GetElementPtrInst>, int> LargeOffsetGEPID;
282
283 /// Keep track of SExt promoted.
284 ValueToSExts ValToSExtendedUses;
285
286 /// True if CFG is modified in any way.
287 bool ModifiedDT;
288
289 /// True if optimizing for size.
290 bool OptSize;
291
292 /// DataLayout for the Function being processed.
293 const DataLayout *DL = nullptr;
294
295 public:
296 static char ID; // Pass identification, replacement for typeid
297
298 CodeGenPrepare() : FunctionPass(ID) {
299 initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
300 }
301
302 bool runOnFunction(Function &F) override;
303
304 StringRef getPassName() const override { return "CodeGen Prepare"; }
305
306 void getAnalysisUsage(AnalysisUsage &AU) const override {
307 // FIXME: When we can selectively preserve passes, preserve the domtree.
308 AU.addRequired<ProfileSummaryInfoWrapperPass>();
309 AU.addRequired<TargetLibraryInfoWrapperPass>();
310 AU.addRequired<TargetTransformInfoWrapperPass>();
311 AU.addRequired<LoopInfoWrapperPass>();
312 }
313
314 private:
315 bool eliminateFallThrough(Function &F);
316 bool eliminateMostlyEmptyBlocks(Function &F);
317 BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
318 bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
319 void eliminateMostlyEmptyBlock(BasicBlock *BB);
320 bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
321 bool isPreheader);
322 bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT);
323 bool optimizeInst(Instruction *I, bool &ModifiedDT);
324 bool optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
325 Type *AccessTy, unsigned AddrSpace);
326 bool optimizeInlineAsmInst(CallInst *CS);
327 bool optimizeCallInst(CallInst *CI, bool &ModifiedDT);
328 bool optimizeExt(Instruction *&I);
329 bool optimizeExtUses(Instruction *I);
330 bool optimizeLoadExt(LoadInst *Load);
331 bool optimizeSelectInst(SelectInst *SI);
332 bool optimizeShuffleVectorInst(ShuffleVectorInst *SVI);
333 bool optimizeSwitchInst(SwitchInst *SI);
334 bool optimizeExtractElementInst(Instruction *Inst);
335 bool dupRetToEnableTailCallOpts(BasicBlock *BB);
336 bool placeDbgValues(Function &F);
337 bool canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
338 LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
339 bool tryToPromoteExts(TypePromotionTransaction &TPT,
340 const SmallVectorImpl<Instruction *> &Exts,
341 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
342 unsigned CreatedInstsCost = 0);
343 bool mergeSExts(Function &F);
344 bool splitLargeGEPOffsets();
345 bool performAddressTypePromotion(
346 Instruction *&Inst,
347 bool AllowPromotionWithoutCommonHeader,
348 bool HasPromoted, TypePromotionTransaction &TPT,
349 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
350 bool splitBranchCondition(Function &F);
351 bool simplifyOffsetableRelocate(Instruction &I);
352 };
353
354} // end anonymous namespace
355
356char CodeGenPrepare::ID = 0;
357
358INITIALIZE_PASS_BEGIN(CodeGenPrepare, DEBUG_TYPE,static void *initializeCodeGenPreparePassOnce(PassRegistry &
Registry) {
359 "Optimize for code generation", false, false)static void *initializeCodeGenPreparePassOnce(PassRegistry &
Registry) {
360INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)initializeProfileSummaryInfoWrapperPassPass(Registry);
361INITIALIZE_PASS_END(CodeGenPrepare, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Optimize for code generation", "codegenprepare"
, &CodeGenPrepare::ID, PassInfo::NormalCtor_t(callDefaultCtor
<CodeGenPrepare>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeCodeGenPreparePassFlag
; void llvm::initializeCodeGenPreparePass(PassRegistry &Registry
) { llvm::call_once(InitializeCodeGenPreparePassFlag, initializeCodeGenPreparePassOnce
, std::ref(Registry)); }
362 "Optimize for code generation", false, false)PassInfo *PI = new PassInfo( "Optimize for code generation", "codegenprepare"
, &CodeGenPrepare::ID, PassInfo::NormalCtor_t(callDefaultCtor
<CodeGenPrepare>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeCodeGenPreparePassFlag
; void llvm::initializeCodeGenPreparePass(PassRegistry &Registry
) { llvm::call_once(InitializeCodeGenPreparePassFlag, initializeCodeGenPreparePassOnce
, std::ref(Registry)); }
363
364FunctionPass *llvm::createCodeGenPreparePass() { return new CodeGenPrepare(); }
365
366bool CodeGenPrepare::runOnFunction(Function &F) {
367 if (skipFunction(F))
1
Assuming the condition is false
2
Taking false branch
368 return false;
369
370 DL = &F.getParent()->getDataLayout();
371
372 bool EverMadeChange = false;
373 // Clear per function information.
374 InsertedInsts.clear();
375 PromotedInsts.clear();
376
377 ModifiedDT = false;
378 if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
3
Assuming 'TPC' is null
4
Taking false branch
379 TM = &TPC->getTM<TargetMachine>();
380 SubtargetInfo = TM->getSubtargetImpl(F);
381 TLI = SubtargetInfo->getTargetLowering();
382 TRI = SubtargetInfo->getRegisterInfo();
383 }
384 TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
385 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
386 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
387 BPI.reset(new BranchProbabilityInfo(F, *LI));
388 BFI.reset(new BlockFrequencyInfo(F, *BPI, *LI));
389 OptSize = F.optForSize();
390
391 ProfileSummaryInfo *PSI =
392 getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
393 if (ProfileGuidedSectionPrefix) {
5
Assuming the condition is false
6
Taking false branch
394 if (PSI->isFunctionHotInCallGraph(&F, *BFI))
395 F.setSectionPrefix(".hot");
396 else if (PSI->isFunctionColdInCallGraph(&F, *BFI))
397 F.setSectionPrefix(".unlikely");
398 }
399
400 /// This optimization identifies DIV instructions that can be
401 /// profitably bypassed and carried out with a shorter, faster divide.
402 if (!OptSize && !PSI->hasHugeWorkingSetSize() && TLI &&
7
Assuming the condition is false
403 TLI->isSlowDivBypassed()) {
404 const DenseMap<unsigned int, unsigned int> &BypassWidths =
405 TLI->getBypassSlowDivWidths();
406 BasicBlock* BB = &*F.begin();
407 while (BB != nullptr) {
408 // bypassSlowDivision may create new BBs, but we don't want to reapply the
409 // optimization to those blocks.
410 BasicBlock* Next = BB->getNextNode();
411 EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
412 BB = Next;
413 }
414 }
415
416 // Eliminate blocks that contain only PHI nodes and an
417 // unconditional branch.
418 EverMadeChange |= eliminateMostlyEmptyBlocks(F);
419
420 // llvm.dbg.value is far away from the value then iSel may not be able
421 // handle it properly. iSel will drop llvm.dbg.value if it can not
422 // find a node corresponding to the value.
423 EverMadeChange |= placeDbgValues(F);
424
425 if (!DisableBranchOpts)
8
Assuming the condition is false
9
Taking false branch
426 EverMadeChange |= splitBranchCondition(F);
427
428 // Split some critical edges where one of the sources is an indirect branch,
429 // to help generate sane code for PHIs involving such edges.
430 EverMadeChange |= SplitIndirectBrCriticalEdges(F);
431
432 bool MadeChange = true;
433 while (MadeChange) {
10
Loop condition is true. Entering loop body
434 MadeChange = false;
435 SeenChainsForSExt.clear();
436 ValToSExtendedUses.clear();
437 RemovedInsts.clear();
438 LargeOffsetGEPMap.clear();
439 LargeOffsetGEPID.clear();
440 for (Function::iterator I = F.begin(); I != F.end(); ) {
11
Loop condition is true. Entering loop body
441 BasicBlock *BB = &*I++;
442 bool ModifiedDTOnIteration = false;
443 MadeChange |= optimizeBlock(*BB, ModifiedDTOnIteration);
12
Calling 'CodeGenPrepare::optimizeBlock'
444
445 // Restart BB iteration if the dominator tree of the Function was changed
446 if (ModifiedDTOnIteration)
447 break;
448 }
449 if (EnableTypePromotionMerge && !ValToSExtendedUses.empty())
450 MadeChange |= mergeSExts(F);
451 if (!LargeOffsetGEPMap.empty())
452 MadeChange |= splitLargeGEPOffsets();
453
454 // Really free removed instructions during promotion.
455 for (Instruction *I : RemovedInsts)
456 I->deleteValue();
457
458 EverMadeChange |= MadeChange;
459 }
460
461 SunkAddrs.clear();
462
463 if (!DisableBranchOpts) {
464 MadeChange = false;
465 // Use a set vector to get deterministic iteration order. The order the
466 // blocks are removed may affect whether or not PHI nodes in successors
467 // are removed.
468 SmallSetVector<BasicBlock*, 8> WorkList;
469 for (BasicBlock &BB : F) {
470 SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB));
471 MadeChange |= ConstantFoldTerminator(&BB, true);
472 if (!MadeChange) continue;
473
474 for (SmallVectorImpl<BasicBlock*>::iterator
475 II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
476 if (pred_begin(*II) == pred_end(*II))
477 WorkList.insert(*II);
478 }
479
480 // Delete the dead blocks and any of their dead successors.
481 MadeChange |= !WorkList.empty();
482 while (!WorkList.empty()) {
483 BasicBlock *BB = WorkList.pop_back_val();
484 SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
485
486 DeleteDeadBlock(BB);
487
488 for (SmallVectorImpl<BasicBlock*>::iterator
489 II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
490 if (pred_begin(*II) == pred_end(*II))
491 WorkList.insert(*II);
492 }
493
494 // Merge pairs of basic blocks with unconditional branches, connected by
495 // a single edge.
496 if (EverMadeChange || MadeChange)
497 MadeChange |= eliminateFallThrough(F);
498
499 EverMadeChange |= MadeChange;
500 }
501
502 if (!DisableGCOpts) {
503 SmallVector<Instruction *, 2> Statepoints;
504 for (BasicBlock &BB : F)
505 for (Instruction &I : BB)
506 if (isStatepoint(I))
507 Statepoints.push_back(&I);
508 for (auto &I : Statepoints)
509 EverMadeChange |= simplifyOffsetableRelocate(*I);
510 }
511
512 return EverMadeChange;
513}
514
515/// Merge basic blocks which are connected by a single edge, where one of the
516/// basic blocks has a single successor pointing to the other basic block,
517/// which has a single predecessor.
518bool CodeGenPrepare::eliminateFallThrough(Function &F) {
519 bool Changed = false;
520 // Scan all of the blocks in the function, except for the entry block.
521 // Use a temporary array to avoid iterator being invalidated when
522 // deleting blocks.
523 SmallVector<WeakTrackingVH, 16> Blocks;
524 for (auto &Block : llvm::make_range(std::next(F.begin()), F.end()))
525 Blocks.push_back(&Block);
526
527 for (auto &Block : Blocks) {
528 auto *BB = cast_or_null<BasicBlock>(Block);
529 if (!BB)
530 continue;
531 // If the destination block has a single pred, then this is a trivial
532 // edge, just collapse it.
533 BasicBlock *SinglePred = BB->getSinglePredecessor();
534
535 // Don't merge if BB's address is taken.
536 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
537
538 BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
539 if (Term && !Term->isConditional()) {
540 Changed = true;
541 LLVM_DEBUG(dbgs() << "To merge:\n" << *BB << "\n\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "To merge:\n" << *
BB << "\n\n\n"; } } while (false)
;
542
543 // Merge BB into SinglePred and delete it.
544 MergeBlockIntoPredecessor(BB);
545 }
546 }
547 return Changed;
548}
549
550/// Find a destination block from BB if BB is mergeable empty block.
551BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
552 // If this block doesn't end with an uncond branch, ignore it.
553 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
554 if (!BI || !BI->isUnconditional())
555 return nullptr;
556
557 // If the instruction before the branch (skipping debug info) isn't a phi
558 // node, then other stuff is happening here.
559 BasicBlock::iterator BBI = BI->getIterator();
560 if (BBI != BB->begin()) {
561 --BBI;
562 while (isa<DbgInfoIntrinsic>(BBI)) {
563 if (BBI == BB->begin())
564 break;
565 --BBI;
566 }
567 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
568 return nullptr;
569 }
570
571 // Do not break infinite loops.
572 BasicBlock *DestBB = BI->getSuccessor(0);
573 if (DestBB == BB)
574 return nullptr;
575
576 if (!canMergeBlocks(BB, DestBB))
577 DestBB = nullptr;
578
579 return DestBB;
580}
581
582/// Eliminate blocks that contain only PHI nodes, debug info directives, and an
583/// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split
584/// edges in ways that are non-optimal for isel. Start by eliminating these
585/// blocks so we can split them the way we want them.
586bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
587 SmallPtrSet<BasicBlock *, 16> Preheaders;
588 SmallVector<Loop *, 16> LoopList(LI->begin(), LI->end());
589 while (!LoopList.empty()) {
590 Loop *L = LoopList.pop_back_val();
591 LoopList.insert(LoopList.end(), L->begin(), L->end());
592 if (BasicBlock *Preheader = L->getLoopPreheader())
593 Preheaders.insert(Preheader);
594 }
595
596 bool MadeChange = false;
597 // Copy blocks into a temporary array to avoid iterator invalidation issues
598 // as we remove them.
599 // Note that this intentionally skips the entry block.
600 SmallVector<WeakTrackingVH, 16> Blocks;
601 for (auto &Block : llvm::make_range(std::next(F.begin()), F.end()))
602 Blocks.push_back(&Block);
603
604 for (auto &Block : Blocks) {
605 BasicBlock *BB = cast_or_null<BasicBlock>(Block);
606 if (!BB)
607 continue;
608 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
609 if (!DestBB ||
610 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.count(BB)))
611 continue;
612
613 eliminateMostlyEmptyBlock(BB);
614 MadeChange = true;
615 }
616 return MadeChange;
617}
618
619bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
620 BasicBlock *DestBB,
621 bool isPreheader) {
622 // Do not delete loop preheaders if doing so would create a critical edge.
623 // Loop preheaders can be good locations to spill registers. If the
624 // preheader is deleted and we create a critical edge, registers may be
625 // spilled in the loop body instead.
626 if (!DisablePreheaderProtect && isPreheader &&
627 !(BB->getSinglePredecessor() &&
628 BB->getSinglePredecessor()->getSingleSuccessor()))
629 return false;
630
631 // Try to skip merging if the unique predecessor of BB is terminated by a
632 // switch or indirect branch instruction, and BB is used as an incoming block
633 // of PHIs in DestBB. In such case, merging BB and DestBB would cause ISel to
634 // add COPY instructions in the predecessor of BB instead of BB (if it is not
635 // merged). Note that the critical edge created by merging such blocks wont be
636 // split in MachineSink because the jump table is not analyzable. By keeping
637 // such empty block (BB), ISel will place COPY instructions in BB, not in the
638 // predecessor of BB.
639 BasicBlock *Pred = BB->getUniquePredecessor();
640 if (!Pred ||
641 !(isa<SwitchInst>(Pred->getTerminator()) ||
642 isa<IndirectBrInst>(Pred->getTerminator())))
643 return true;
644
645 if (BB->getTerminator() != BB->getFirstNonPHI())
646 return true;
647
648 // We use a simple cost heuristic which determine skipping merging is
649 // profitable if the cost of skipping merging is less than the cost of
650 // merging : Cost(skipping merging) < Cost(merging BB), where the
651 // Cost(skipping merging) is Freq(BB) * (Cost(Copy) + Cost(Branch)), and
652 // the Cost(merging BB) is Freq(Pred) * Cost(Copy).
653 // Assuming Cost(Copy) == Cost(Branch), we could simplify it to :
654 // Freq(Pred) / Freq(BB) > 2.
655 // Note that if there are multiple empty blocks sharing the same incoming
656 // value for the PHIs in the DestBB, we consider them together. In such
657 // case, Cost(merging BB) will be the sum of their frequencies.
658
659 if (!isa<PHINode>(DestBB->begin()))
660 return true;
661
662 SmallPtrSet<BasicBlock *, 16> SameIncomingValueBBs;
663
664 // Find all other incoming blocks from which incoming values of all PHIs in
665 // DestBB are the same as the ones from BB.
666 for (pred_iterator PI = pred_begin(DestBB), E = pred_end(DestBB); PI != E;
667 ++PI) {
668 BasicBlock *DestBBPred = *PI;
669 if (DestBBPred == BB)
670 continue;
671
672 if (llvm::all_of(DestBB->phis(), [&](const PHINode &DestPN) {
673 return DestPN.getIncomingValueForBlock(BB) ==
674 DestPN.getIncomingValueForBlock(DestBBPred);
675 }))
676 SameIncomingValueBBs.insert(DestBBPred);
677 }
678
679 // See if all BB's incoming values are same as the value from Pred. In this
680 // case, no reason to skip merging because COPYs are expected to be place in
681 // Pred already.
682 if (SameIncomingValueBBs.count(Pred))
683 return true;
684
685 BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
686 BlockFrequency BBFreq = BFI->getBlockFreq(BB);
687
688 for (auto SameValueBB : SameIncomingValueBBs)
689 if (SameValueBB->getUniquePredecessor() == Pred &&
690 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
691 BBFreq += BFI->getBlockFreq(SameValueBB);
692
693 return PredFreq.getFrequency() <=
694 BBFreq.getFrequency() * FreqRatioToSkipMerge;
695}
696
697/// Return true if we can merge BB into DestBB if there is a single
698/// unconditional branch between them, and BB contains no other non-phi
699/// instructions.
700bool CodeGenPrepare::canMergeBlocks(const BasicBlock *BB,
701 const BasicBlock *DestBB) const {
702 // We only want to eliminate blocks whose phi nodes are used by phi nodes in
703 // the successor. If there are more complex condition (e.g. preheaders),
704 // don't mess around with them.
705 for (const PHINode &PN : BB->phis()) {
706 for (const User *U : PN.users()) {
707 const Instruction *UI = cast<Instruction>(U);
708 if (UI->getParent() != DestBB || !isa<PHINode>(UI))
709 return false;
710 // If User is inside DestBB block and it is a PHINode then check
711 // incoming value. If incoming value is not from BB then this is
712 // a complex condition (e.g. preheaders) we want to avoid here.
713 if (UI->getParent() == DestBB) {
714 if (const PHINode *UPN = dyn_cast<PHINode>(UI))
715 for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
716 Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
717 if (Insn && Insn->getParent() == BB &&
718 Insn->getParent() != UPN->getIncomingBlock(I))
719 return false;
720 }
721 }
722 }
723 }
724
725 // If BB and DestBB contain any common predecessors, then the phi nodes in BB
726 // and DestBB may have conflicting incoming values for the block. If so, we
727 // can't merge the block.
728 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
729 if (!DestBBPN) return true; // no conflict.
730
731 // Collect the preds of BB.
732 SmallPtrSet<const BasicBlock*, 16> BBPreds;
733 if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
734 // It is faster to get preds from a PHI than with pred_iterator.
735 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
736 BBPreds.insert(BBPN->getIncomingBlock(i));
737 } else {
738 BBPreds.insert(pred_begin(BB), pred_end(BB));
739 }
740
741 // Walk the preds of DestBB.
742 for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
743 BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
744 if (BBPreds.count(Pred)) { // Common predecessor?
745 for (const PHINode &PN : DestBB->phis()) {
746 const Value *V1 = PN.getIncomingValueForBlock(Pred);
747 const Value *V2 = PN.getIncomingValueForBlock(BB);
748
749 // If V2 is a phi node in BB, look up what the mapped value will be.
750 if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
751 if (V2PN->getParent() == BB)
752 V2 = V2PN->getIncomingValueForBlock(Pred);
753
754 // If there is a conflict, bail out.
755 if (V1 != V2) return false;
756 }
757 }
758 }
759
760 return true;
761}
762
763/// Eliminate a basic block that has only phi's and an unconditional branch in
764/// it.
765void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
766 BranchInst *BI = cast<BranchInst>(BB->getTerminator());
767 BasicBlock *DestBB = BI->getSuccessor(0);
768
769 LLVM_DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n"
<< *BB << *DestBB; } } while (false)
770 << *BB << *DestBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n"
<< *BB << *DestBB; } } while (false)
;
771
772 // If the destination block has a single pred, then this is a trivial edge,
773 // just collapse it.
774 if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
775 if (SinglePred != DestBB) {
776 assert(SinglePred == BB &&(static_cast <bool> (SinglePred == BB && "Single predecessor not the same as predecessor"
) ? void (0) : __assert_fail ("SinglePred == BB && \"Single predecessor not the same as predecessor\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 777, __extension__ __PRETTY_FUNCTION__))
777 "Single predecessor not the same as predecessor")(static_cast <bool> (SinglePred == BB && "Single predecessor not the same as predecessor"
) ? void (0) : __assert_fail ("SinglePred == BB && \"Single predecessor not the same as predecessor\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 777, __extension__ __PRETTY_FUNCTION__))
;
778 // Merge DestBB into SinglePred/BB and delete it.
779 MergeBlockIntoPredecessor(DestBB);
780 // Note: BB(=SinglePred) will not be deleted on this path.
781 // DestBB(=its single successor) is the one that was deleted.
782 LLVM_DEBUG(dbgs() << "AFTER:\n" << *SinglePred << "\n\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "AFTER:\n" << *SinglePred
<< "\n\n\n"; } } while (false)
;
783 return;
784 }
785 }
786
787 // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB
788 // to handle the new incoming edges it is about to have.
789 for (PHINode &PN : DestBB->phis()) {
790 // Remove the incoming value for BB, and remember it.
791 Value *InVal = PN.removeIncomingValue(BB, false);
792
793 // Two options: either the InVal is a phi node defined in BB or it is some
794 // value that dominates BB.
795 PHINode *InValPhi = dyn_cast<PHINode>(InVal);
796 if (InValPhi && InValPhi->getParent() == BB) {
797 // Add all of the input values of the input PHI as inputs of this phi.
798 for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
799 PN.addIncoming(InValPhi->getIncomingValue(i),
800 InValPhi->getIncomingBlock(i));
801 } else {
802 // Otherwise, add one instance of the dominating value for each edge that
803 // we will be adding.
804 if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
805 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
806 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
807 } else {
808 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
809 PN.addIncoming(InVal, *PI);
810 }
811 }
812 }
813
814 // The PHIs are now updated, change everything that refers to BB to use
815 // DestBB and remove BB.
816 BB->replaceAllUsesWith(DestBB);
817 BB->eraseFromParent();
818 ++NumBlocksElim;
819
820 LLVM_DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "AFTER:\n" << *DestBB
<< "\n\n\n"; } } while (false)
;
821}
822
823// Computes a map of base pointer relocation instructions to corresponding
824// derived pointer relocation instructions given a vector of all relocate calls
825static void computeBaseDerivedRelocateMap(
826 const SmallVectorImpl<GCRelocateInst *> &AllRelocateCalls,
827 DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>>
828 &RelocateInstMap) {
829 // Collect information in two maps: one primarily for locating the base object
830 // while filling the second map; the second map is the final structure holding
831 // a mapping between Base and corresponding Derived relocate calls
832 DenseMap<std::pair<unsigned, unsigned>, GCRelocateInst *> RelocateIdxMap;
833 for (auto *ThisRelocate : AllRelocateCalls) {
834 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
835 ThisRelocate->getDerivedPtrIndex());
836 RelocateIdxMap.insert(std::make_pair(K, ThisRelocate));
837 }
838 for (auto &Item : RelocateIdxMap) {
839 std::pair<unsigned, unsigned> Key = Item.first;
840 if (Key.first == Key.second)
841 // Base relocation: nothing to insert
842 continue;
843
844 GCRelocateInst *I = Item.second;
845 auto BaseKey = std::make_pair(Key.first, Key.first);
846
847 // We're iterating over RelocateIdxMap so we cannot modify it.
848 auto MaybeBase = RelocateIdxMap.find(BaseKey);
849 if (MaybeBase == RelocateIdxMap.end())
850 // TODO: We might want to insert a new base object relocate and gep off
851 // that, if there are enough derived object relocates.
852 continue;
853
854 RelocateInstMap[MaybeBase->second].push_back(I);
855 }
856}
857
858// Accepts a GEP and extracts the operands into a vector provided they're all
859// small integer constants
860static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
861 SmallVectorImpl<Value *> &OffsetV) {
862 for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
863 // Only accept small constant integer operands
864 auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
865 if (!Op || Op->getZExtValue() > 20)
866 return false;
867 }
868
869 for (unsigned i = 1; i < GEP->getNumOperands(); i++)
870 OffsetV.push_back(GEP->getOperand(i));
871 return true;
872}
873
874// Takes a RelocatedBase (base pointer relocation instruction) and Targets to
875// replace, computes a replacement, and affects it.
876static bool
877simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase,
878 const SmallVectorImpl<GCRelocateInst *> &Targets) {
879 bool MadeChange = false;
880 // We must ensure the relocation of derived pointer is defined after
881 // relocation of base pointer. If we find a relocation corresponding to base
882 // defined earlier than relocation of base then we move relocation of base
883 // right before found relocation. We consider only relocation in the same
884 // basic block as relocation of base. Relocations from other basic block will
885 // be skipped by optimization and we do not care about them.
886 for (auto R = RelocatedBase->getParent()->getFirstInsertionPt();
887 &*R != RelocatedBase; ++R)
888 if (auto RI = dyn_cast<GCRelocateInst>(R))
889 if (RI->getStatepoint() == RelocatedBase->getStatepoint())
890 if (RI->getBasePtrIndex() == RelocatedBase->getBasePtrIndex()) {
891 RelocatedBase->moveBefore(RI);
892 break;
893 }
894
895 for (GCRelocateInst *ToReplace : Targets) {
896 assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() &&(static_cast <bool> (ToReplace->getBasePtrIndex() ==
RelocatedBase->getBasePtrIndex() && "Not relocating a derived object of the original base object"
) ? void (0) : __assert_fail ("ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() && \"Not relocating a derived object of the original base object\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 897, __extension__ __PRETTY_FUNCTION__))
897 "Not relocating a derived object of the original base object")(static_cast <bool> (ToReplace->getBasePtrIndex() ==
RelocatedBase->getBasePtrIndex() && "Not relocating a derived object of the original base object"
) ? void (0) : __assert_fail ("ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() && \"Not relocating a derived object of the original base object\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 897, __extension__ __PRETTY_FUNCTION__))
;
898 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
899 // A duplicate relocate call. TODO: coalesce duplicates.
900 continue;
901 }
902
903 if (RelocatedBase->getParent() != ToReplace->getParent()) {
904 // Base and derived relocates are in different basic blocks.
905 // In this case transform is only valid when base dominates derived
906 // relocate. However it would be too expensive to check dominance
907 // for each such relocate, so we skip the whole transformation.
908 continue;
909 }
910
911 Value *Base = ToReplace->getBasePtr();
912 auto Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
913 if (!Derived || Derived->getPointerOperand() != Base)
914 continue;
915
916 SmallVector<Value *, 2> OffsetV;
917 if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
918 continue;
919
920 // Create a Builder and replace the target callsite with a gep
921 assert(RelocatedBase->getNextNode() &&(static_cast <bool> (RelocatedBase->getNextNode() &&
"Should always have one since it's not a terminator") ? void
(0) : __assert_fail ("RelocatedBase->getNextNode() && \"Should always have one since it's not a terminator\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 922, __extension__ __PRETTY_FUNCTION__))
922 "Should always have one since it's not a terminator")(static_cast <bool> (RelocatedBase->getNextNode() &&
"Should always have one since it's not a terminator") ? void
(0) : __assert_fail ("RelocatedBase->getNextNode() && \"Should always have one since it's not a terminator\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 922, __extension__ __PRETTY_FUNCTION__))
;
923
924 // Insert after RelocatedBase
925 IRBuilder<> Builder(RelocatedBase->getNextNode());
926 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
927
928 // If gc_relocate does not match the actual type, cast it to the right type.
929 // In theory, there must be a bitcast after gc_relocate if the type does not
930 // match, and we should reuse it to get the derived pointer. But it could be
931 // cases like this:
932 // bb1:
933 // ...
934 // %g1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
935 // br label %merge
936 //
937 // bb2:
938 // ...
939 // %g2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
940 // br label %merge
941 //
942 // merge:
943 // %p1 = phi i8 addrspace(1)* [ %g1, %bb1 ], [ %g2, %bb2 ]
944 // %cast = bitcast i8 addrspace(1)* %p1 in to i32 addrspace(1)*
945 //
946 // In this case, we can not find the bitcast any more. So we insert a new bitcast
947 // no matter there is already one or not. In this way, we can handle all cases, and
948 // the extra bitcast should be optimized away in later passes.
949 Value *ActualRelocatedBase = RelocatedBase;
950 if (RelocatedBase->getType() != Base->getType()) {
951 ActualRelocatedBase =
952 Builder.CreateBitCast(RelocatedBase, Base->getType());
953 }
954 Value *Replacement = Builder.CreateGEP(
955 Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV));
956 Replacement->takeName(ToReplace);
957 // If the newly generated derived pointer's type does not match the original derived
958 // pointer's type, cast the new derived pointer to match it. Same reasoning as above.
959 Value *ActualReplacement = Replacement;
960 if (Replacement->getType() != ToReplace->getType()) {
961 ActualReplacement =
962 Builder.CreateBitCast(Replacement, ToReplace->getType());
963 }
964 ToReplace->replaceAllUsesWith(ActualReplacement);
965 ToReplace->eraseFromParent();
966
967 MadeChange = true;
968 }
969 return MadeChange;
970}
971
972// Turns this:
973//
974// %base = ...
975// %ptr = gep %base + 15
976// %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
977// %base' = relocate(%tok, i32 4, i32 4)
978// %ptr' = relocate(%tok, i32 4, i32 5)
979// %val = load %ptr'
980//
981// into this:
982//
983// %base = ...
984// %ptr = gep %base + 15
985// %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
986// %base' = gc.relocate(%tok, i32 4, i32 4)
987// %ptr' = gep %base' + 15
988// %val = load %ptr'
989bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
990 bool MadeChange = false;
991 SmallVector<GCRelocateInst *, 2> AllRelocateCalls;
992
993 for (auto *U : I.users())
994 if (GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U))
995 // Collect all the relocate calls associated with a statepoint
996 AllRelocateCalls.push_back(Relocate);
997
998 // We need atleast one base pointer relocation + one derived pointer
999 // relocation to mangle
1000 if (AllRelocateCalls.size() < 2)
1001 return false;
1002
1003 // RelocateInstMap is a mapping from the base relocate instruction to the
1004 // corresponding derived relocate instructions
1005 DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>> RelocateInstMap;
1006 computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
1007 if (RelocateInstMap.empty())
1008 return false;
1009
1010 for (auto &Item : RelocateInstMap)
1011 // Item.first is the RelocatedBase to offset against
1012 // Item.second is the vector of Targets to replace
1013 MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
1014 return MadeChange;
1015}
1016
1017/// SinkCast - Sink the specified cast instruction into its user blocks
1018static bool SinkCast(CastInst *CI) {
1019 BasicBlock *DefBB = CI->getParent();
1020
1021 /// InsertedCasts - Only insert a cast in each block once.
1022 DenseMap<BasicBlock*, CastInst*> InsertedCasts;
1023
1024 bool MadeChange = false;
1025 for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1026 UI != E; ) {
1027 Use &TheUse = UI.getUse();
1028 Instruction *User = cast<Instruction>(*UI);
1029
1030 // Figure out which BB this cast is used in. For PHI's this is the
1031 // appropriate predecessor block.
1032 BasicBlock *UserBB = User->getParent();
1033 if (PHINode *PN = dyn_cast<PHINode>(User)) {
1034 UserBB = PN->getIncomingBlock(TheUse);
1035 }
1036
1037 // Preincrement use iterator so we don't invalidate it.
1038 ++UI;
1039
1040 // The first insertion point of a block containing an EH pad is after the
1041 // pad. If the pad is the user, we cannot sink the cast past the pad.
1042 if (User->isEHPad())
1043 continue;
1044
1045 // If the block selected to receive the cast is an EH pad that does not
1046 // allow non-PHI instructions before the terminator, we can't sink the
1047 // cast.
1048 if (UserBB->getTerminator()->isEHPad())
1049 continue;
1050
1051 // If this user is in the same block as the cast, don't change the cast.
1052 if (UserBB == DefBB) continue;
1053
1054 // If we have already inserted a cast into this block, use it.
1055 CastInst *&InsertedCast = InsertedCasts[UserBB];
1056
1057 if (!InsertedCast) {
1058 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1059 assert(InsertPt != UserBB->end())(static_cast <bool> (InsertPt != UserBB->end()) ? void
(0) : __assert_fail ("InsertPt != UserBB->end()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1059, __extension__ __PRETTY_FUNCTION__))
;
1060 InsertedCast = CastInst::Create(CI->getOpcode(), CI->getOperand(0),
1061 CI->getType(), "", &*InsertPt);
1062 InsertedCast->setDebugLoc(CI->getDebugLoc());
1063 }
1064
1065 // Replace a use of the cast with a use of the new cast.
1066 TheUse = InsertedCast;
1067 MadeChange = true;
1068 ++NumCastUses;
1069 }
1070
1071 // If we removed all uses, nuke the cast.
1072 if (CI->use_empty()) {
1073 salvageDebugInfo(*CI);
1074 CI->eraseFromParent();
1075 MadeChange = true;
1076 }
1077
1078 return MadeChange;
1079}
1080
1081/// If the specified cast instruction is a noop copy (e.g. it's casting from
1082/// one pointer type to another, i32->i8 on PPC), sink it into user blocks to
1083/// reduce the number of virtual registers that must be created and coalesced.
1084///
1085/// Return true if any changes are made.
1086static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
1087 const DataLayout &DL) {
1088 // Sink only "cheap" (or nop) address-space casts. This is a weaker condition
1089 // than sinking only nop casts, but is helpful on some platforms.
1090 if (auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1091 if (!TLI.isCheapAddrSpaceCast(ASC->getSrcAddressSpace(),
1092 ASC->getDestAddressSpace()))
1093 return false;
1094 }
1095
1096 // If this is a noop copy,
1097 EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType());
1098 EVT DstVT = TLI.getValueType(DL, CI->getType());
1099
1100 // This is an fp<->int conversion?
1101 if (SrcVT.isInteger() != DstVT.isInteger())
1102 return false;
1103
1104 // If this is an extension, it will be a zero or sign extension, which
1105 // isn't a noop.
1106 if (SrcVT.bitsLT(DstVT)) return false;
1107
1108 // If these values will be promoted, find out what they will be promoted
1109 // to. This helps us consider truncates on PPC as noop copies when they
1110 // are.
1111 if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
1112 TargetLowering::TypePromoteInteger)
1113 SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
1114 if (TLI.getTypeAction(CI->getContext(), DstVT) ==
1115 TargetLowering::TypePromoteInteger)
1116 DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
1117
1118 // If, after promotion, these are the same types, this is a noop copy.
1119 if (SrcVT != DstVT)
1120 return false;
1121
1122 return SinkCast(CI);
1123}
1124
1125/// Try to combine CI into a call to the llvm.uadd.with.overflow intrinsic if
1126/// possible.
1127///
1128/// Return true if any changes were made.
1129static bool CombineUAddWithOverflow(CmpInst *CI) {
1130 Value *A, *B;
1131 Instruction *AddI;
1132 if (!match(CI,
1133 m_UAddWithOverflow(m_Value(A), m_Value(B), m_Instruction(AddI))))
1134 return false;
1135
1136 Type *Ty = AddI->getType();
1137 if (!isa<IntegerType>(Ty))
1138 return false;
1139
1140 // We don't want to move around uses of condition values this late, so we we
1141 // check if it is legal to create the call to the intrinsic in the basic
1142 // block containing the icmp:
1143
1144 if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse())
1145 return false;
1146
1147#ifndef NDEBUG
1148 // Someday m_UAddWithOverflow may get smarter, but this is a safe assumption
1149 // for now:
1150 if (AddI->hasOneUse())
1151 assert(*AddI->user_begin() == CI && "expected!")(static_cast <bool> (*AddI->user_begin() == CI &&
"expected!") ? void (0) : __assert_fail ("*AddI->user_begin() == CI && \"expected!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1151, __extension__ __PRETTY_FUNCTION__))
;
1152#endif
1153
1154 Module *M = CI->getModule();
1155 Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty);
1156
1157 auto *InsertPt = AddI->hasOneUse() ? CI : AddI;
1158
1159 auto *UAddWithOverflow =
1160 CallInst::Create(F, {A, B}, "uadd.overflow", InsertPt);
1161 auto *UAdd = ExtractValueInst::Create(UAddWithOverflow, 0, "uadd", InsertPt);
1162 auto *Overflow =
1163 ExtractValueInst::Create(UAddWithOverflow, 1, "overflow", InsertPt);
1164
1165 CI->replaceAllUsesWith(Overflow);
1166 AddI->replaceAllUsesWith(UAdd);
1167 CI->eraseFromParent();
1168 AddI->eraseFromParent();
1169 return true;
1170}
1171
1172/// Sink the given CmpInst into user blocks to reduce the number of virtual
1173/// registers that must be created and coalesced. This is a clear win except on
1174/// targets with multiple condition code registers (PowerPC), where it might
1175/// lose; some adjustment may be wanted there.
1176///
1177/// Return true if any changes are made.
1178static bool SinkCmpExpression(CmpInst *CI, const TargetLowering *TLI) {
1179 BasicBlock *DefBB = CI->getParent();
1180
1181 // Avoid sinking soft-FP comparisons, since this can move them into a loop.
1182 if (TLI && TLI->useSoftFloat() && isa<FCmpInst>(CI))
1183 return false;
1184
1185 // Only insert a cmp in each block once.
1186 DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
1187
1188 bool MadeChange = false;
1189 for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1190 UI != E; ) {
1191 Use &TheUse = UI.getUse();
1192 Instruction *User = cast<Instruction>(*UI);
1193
1194 // Preincrement use iterator so we don't invalidate it.
1195 ++UI;
1196
1197 // Don't bother for PHI nodes.
1198 if (isa<PHINode>(User))
1199 continue;
1200
1201 // Figure out which BB this cmp is used in.
1202 BasicBlock *UserBB = User->getParent();
1203
1204 // If this user is in the same block as the cmp, don't change the cmp.
1205 if (UserBB == DefBB) continue;
1206
1207 // If we have already inserted a cmp into this block, use it.
1208 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1209
1210 if (!InsertedCmp) {
1211 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1212 assert(InsertPt != UserBB->end())(static_cast <bool> (InsertPt != UserBB->end()) ? void
(0) : __assert_fail ("InsertPt != UserBB->end()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1212, __extension__ __PRETTY_FUNCTION__))
;
1213 InsertedCmp =
1214 CmpInst::Create(CI->getOpcode(), CI->getPredicate(),
1215 CI->getOperand(0), CI->getOperand(1), "", &*InsertPt);
1216 // Propagate the debug info.
1217 InsertedCmp->setDebugLoc(CI->getDebugLoc());
1218 }
1219
1220 // Replace a use of the cmp with a use of the new cmp.
1221 TheUse = InsertedCmp;
1222 MadeChange = true;
1223 ++NumCmpUses;
1224 }
1225
1226 // If we removed all uses, nuke the cmp.
1227 if (CI->use_empty()) {
1228 CI->eraseFromParent();
1229 MadeChange = true;
1230 }
1231
1232 return MadeChange;
1233}
1234
1235static bool OptimizeCmpExpression(CmpInst *CI, const TargetLowering *TLI) {
1236 if (SinkCmpExpression(CI, TLI))
1237 return true;
1238
1239 if (CombineUAddWithOverflow(CI))
1240 return true;
1241
1242 return false;
1243}
1244
1245/// Duplicate and sink the given 'and' instruction into user blocks where it is
1246/// used in a compare to allow isel to generate better code for targets where
1247/// this operation can be combined.
1248///
1249/// Return true if any changes are made.
1250static bool sinkAndCmp0Expression(Instruction *AndI,
1251 const TargetLowering &TLI,
1252 SetOfInstrs &InsertedInsts) {
1253 // Double-check that we're not trying to optimize an instruction that was
1254 // already optimized by some other part of this pass.
1255 assert(!InsertedInsts.count(AndI) &&(static_cast <bool> (!InsertedInsts.count(AndI) &&
"Attempting to optimize already optimized and instruction") ?
void (0) : __assert_fail ("!InsertedInsts.count(AndI) && \"Attempting to optimize already optimized and instruction\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1256, __extension__ __PRETTY_FUNCTION__))
1256 "Attempting to optimize already optimized and instruction")(static_cast <bool> (!InsertedInsts.count(AndI) &&
"Attempting to optimize already optimized and instruction") ?
void (0) : __assert_fail ("!InsertedInsts.count(AndI) && \"Attempting to optimize already optimized and instruction\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1256, __extension__ __PRETTY_FUNCTION__))
;
1257 (void) InsertedInsts;
1258
1259 // Nothing to do for single use in same basic block.
1260 if (AndI->hasOneUse() &&
1261 AndI->getParent() == cast<Instruction>(*AndI->user_begin())->getParent())
1262 return false;
1263
1264 // Try to avoid cases where sinking/duplicating is likely to increase register
1265 // pressure.
1266 if (!isa<ConstantInt>(AndI->getOperand(0)) &&
1267 !isa<ConstantInt>(AndI->getOperand(1)) &&
1268 AndI->getOperand(0)->hasOneUse() && AndI->getOperand(1)->hasOneUse())
1269 return false;
1270
1271 for (auto *U : AndI->users()) {
1272 Instruction *User = cast<Instruction>(U);
1273
1274 // Only sink for and mask feeding icmp with 0.
1275 if (!isa<ICmpInst>(User))
1276 return false;
1277
1278 auto *CmpC = dyn_cast<ConstantInt>(User->getOperand(1));
1279 if (!CmpC || !CmpC->isZero())
1280 return false;
1281 }
1282
1283 if (!TLI.isMaskAndCmp0FoldingBeneficial(*AndI))
1284 return false;
1285
1286 LLVM_DEBUG(dbgs() << "found 'and' feeding only icmp 0;\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "found 'and' feeding only icmp 0;\n"
; } } while (false)
;
1287 LLVM_DEBUG(AndI->getParent()->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { AndI->getParent()->dump(); } } while
(false)
;
1288
1289 // Push the 'and' into the same block as the icmp 0. There should only be
1290 // one (icmp (and, 0)) in each block, since CSE/GVN should have removed any
1291 // others, so we don't need to keep track of which BBs we insert into.
1292 for (Value::user_iterator UI = AndI->user_begin(), E = AndI->user_end();
1293 UI != E; ) {
1294 Use &TheUse = UI.getUse();
1295 Instruction *User = cast<Instruction>(*UI);
1296
1297 // Preincrement use iterator so we don't invalidate it.
1298 ++UI;
1299
1300 LLVM_DEBUG(dbgs() << "sinking 'and' use: " << *User << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "sinking 'and' use: " <<
*User << "\n"; } } while (false)
;
1301
1302 // Keep the 'and' in the same place if the use is already in the same block.
1303 Instruction *InsertPt =
1304 User->getParent() == AndI->getParent() ? AndI : User;
1305 Instruction *InsertedAnd =
1306 BinaryOperator::Create(Instruction::And, AndI->getOperand(0),
1307 AndI->getOperand(1), "", InsertPt);
1308 // Propagate the debug info.
1309 InsertedAnd->setDebugLoc(AndI->getDebugLoc());
1310
1311 // Replace a use of the 'and' with a use of the new 'and'.
1312 TheUse = InsertedAnd;
1313 ++NumAndUses;
1314 LLVM_DEBUG(User->getParent()->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { User->getParent()->dump(); } } while
(false)
;
1315 }
1316
1317 // We removed all uses, nuke the and.
1318 AndI->eraseFromParent();
1319 return true;
1320}
1321
1322/// Check if the candidates could be combined with a shift instruction, which
1323/// includes:
1324/// 1. Truncate instruction
1325/// 2. And instruction and the imm is a mask of the low bits:
1326/// imm & (imm+1) == 0
1327static bool isExtractBitsCandidateUse(Instruction *User) {
1328 if (!isa<TruncInst>(User)) {
1329 if (User->getOpcode() != Instruction::And ||
1330 !isa<ConstantInt>(User->getOperand(1)))
1331 return false;
1332
1333 const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
1334
1335 if ((Cimm & (Cimm + 1)).getBoolValue())
1336 return false;
1337 }
1338 return true;
1339}
1340
1341/// Sink both shift and truncate instruction to the use of truncate's BB.
1342static bool
1343SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
1344 DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
1345 const TargetLowering &TLI, const DataLayout &DL) {
1346 BasicBlock *UserBB = User->getParent();
1347 DenseMap<BasicBlock *, CastInst *> InsertedTruncs;
1348 TruncInst *TruncI = dyn_cast<TruncInst>(User);
1349 bool MadeChange = false;
1350
1351 for (Value::user_iterator TruncUI = TruncI->user_begin(),
1352 TruncE = TruncI->user_end();
1353 TruncUI != TruncE;) {
1354
1355 Use &TruncTheUse = TruncUI.getUse();
1356 Instruction *TruncUser = cast<Instruction>(*TruncUI);
1357 // Preincrement use iterator so we don't invalidate it.
1358
1359 ++TruncUI;
1360
1361 int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
1362 if (!ISDOpcode)
1363 continue;
1364
1365 // If the use is actually a legal node, there will not be an
1366 // implicit truncate.
1367 // FIXME: always querying the result type is just an
1368 // approximation; some nodes' legality is determined by the
1369 // operand or other means. There's no good way to find out though.
1370 if (TLI.isOperationLegalOrCustom(
1371 ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true)))
1372 continue;
1373
1374 // Don't bother for PHI nodes.
1375 if (isa<PHINode>(TruncUser))
1376 continue;
1377
1378 BasicBlock *TruncUserBB = TruncUser->getParent();
1379
1380 if (UserBB == TruncUserBB)
1381 continue;
1382
1383 BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
1384 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
1385
1386 if (!InsertedShift && !InsertedTrunc) {
1387 BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
1388 assert(InsertPt != TruncUserBB->end())(static_cast <bool> (InsertPt != TruncUserBB->end())
? void (0) : __assert_fail ("InsertPt != TruncUserBB->end()"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1388, __extension__ __PRETTY_FUNCTION__))
;
1389 // Sink the shift
1390 if (ShiftI->getOpcode() == Instruction::AShr)
1391 InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
1392 "", &*InsertPt);
1393 else
1394 InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
1395 "", &*InsertPt);
1396
1397 // Sink the trunc
1398 BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
1399 TruncInsertPt++;
1400 assert(TruncInsertPt != TruncUserBB->end())(static_cast <bool> (TruncInsertPt != TruncUserBB->end
()) ? void (0) : __assert_fail ("TruncInsertPt != TruncUserBB->end()"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1400, __extension__ __PRETTY_FUNCTION__))
;
1401
1402 InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
1403 TruncI->getType(), "", &*TruncInsertPt);
1404
1405 MadeChange = true;
1406
1407 TruncTheUse = InsertedTrunc;
1408 }
1409 }
1410 return MadeChange;
1411}
1412
1413/// Sink the shift *right* instruction into user blocks if the uses could
1414/// potentially be combined with this shift instruction and generate BitExtract
1415/// instruction. It will only be applied if the architecture supports BitExtract
1416/// instruction. Here is an example:
1417/// BB1:
1418/// %x.extract.shift = lshr i64 %arg1, 32
1419/// BB2:
1420/// %x.extract.trunc = trunc i64 %x.extract.shift to i16
1421/// ==>
1422///
1423/// BB2:
1424/// %x.extract.shift.1 = lshr i64 %arg1, 32
1425/// %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
1426///
1427/// CodeGen will recognize the pattern in BB2 and generate BitExtract
1428/// instruction.
1429/// Return true if any changes are made.
1430static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
1431 const TargetLowering &TLI,
1432 const DataLayout &DL) {
1433 BasicBlock *DefBB = ShiftI->getParent();
1434
1435 /// Only insert instructions in each block once.
1436 DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
1437
1438 bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(DL, ShiftI->getType()));
1439
1440 bool MadeChange = false;
1441 for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
1442 UI != E;) {
1443 Use &TheUse = UI.getUse();
1444 Instruction *User = cast<Instruction>(*UI);
1445 // Preincrement use iterator so we don't invalidate it.
1446 ++UI;
1447
1448 // Don't bother for PHI nodes.
1449 if (isa<PHINode>(User))
1450 continue;
1451
1452 if (!isExtractBitsCandidateUse(User))
1453 continue;
1454
1455 BasicBlock *UserBB = User->getParent();
1456
1457 if (UserBB == DefBB) {
1458 // If the shift and truncate instruction are in the same BB. The use of
1459 // the truncate(TruncUse) may still introduce another truncate if not
1460 // legal. In this case, we would like to sink both shift and truncate
1461 // instruction to the BB of TruncUse.
1462 // for example:
1463 // BB1:
1464 // i64 shift.result = lshr i64 opnd, imm
1465 // trunc.result = trunc shift.result to i16
1466 //
1467 // BB2:
1468 // ----> We will have an implicit truncate here if the architecture does
1469 // not have i16 compare.
1470 // cmp i16 trunc.result, opnd2
1471 //
1472 if (isa<TruncInst>(User) && shiftIsLegal
1473 // If the type of the truncate is legal, no truncate will be
1474 // introduced in other basic blocks.
1475 &&
1476 (!TLI.isTypeLegal(TLI.getValueType(DL, User->getType()))))
1477 MadeChange =
1478 SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI, DL);
1479
1480 continue;
1481 }
1482 // If we have already inserted a shift into this block, use it.
1483 BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
1484
1485 if (!InsertedShift) {
1486 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1487 assert(InsertPt != UserBB->end())(static_cast <bool> (InsertPt != UserBB->end()) ? void
(0) : __assert_fail ("InsertPt != UserBB->end()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1487, __extension__ __PRETTY_FUNCTION__))
;
1488
1489 if (ShiftI->getOpcode() == Instruction::AShr)
1490 InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
1491 "", &*InsertPt);
1492 else
1493 InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
1494 "", &*InsertPt);
1495
1496 MadeChange = true;
1497 }
1498
1499 // Replace a use of the shift with a use of the new shift.
1500 TheUse = InsertedShift;
1501 }
1502
1503 // If we removed all uses, nuke the shift.
1504 if (ShiftI->use_empty())
1505 ShiftI->eraseFromParent();
1506
1507 return MadeChange;
1508}
1509
1510/// If counting leading or trailing zeros is an expensive operation and a zero
1511/// input is defined, add a check for zero to avoid calling the intrinsic.
1512///
1513/// We want to transform:
1514/// %z = call i64 @llvm.cttz.i64(i64 %A, i1 false)
1515///
1516/// into:
1517/// entry:
1518/// %cmpz = icmp eq i64 %A, 0
1519/// br i1 %cmpz, label %cond.end, label %cond.false
1520/// cond.false:
1521/// %z = call i64 @llvm.cttz.i64(i64 %A, i1 true)
1522/// br label %cond.end
1523/// cond.end:
1524/// %ctz = phi i64 [ 64, %entry ], [ %z, %cond.false ]
1525///
1526/// If the transform is performed, return true and set ModifiedDT to true.
1527static bool despeculateCountZeros(IntrinsicInst *CountZeros,
1528 const TargetLowering *TLI,
1529 const DataLayout *DL,
1530 bool &ModifiedDT) {
1531 if (!TLI || !DL)
1532 return false;
1533
1534 // If a zero input is undefined, it doesn't make sense to despeculate that.
1535 if (match(CountZeros->getOperand(1), m_One()))
1536 return false;
1537
1538 // If it's cheap to speculate, there's nothing to do.
1539 auto IntrinsicID = CountZeros->getIntrinsicID();
1540 if ((IntrinsicID == Intrinsic::cttz && TLI->isCheapToSpeculateCttz()) ||
1541 (IntrinsicID == Intrinsic::ctlz && TLI->isCheapToSpeculateCtlz()))
1542 return false;
1543
1544 // Only handle legal scalar cases. Anything else requires too much work.
1545 Type *Ty = CountZeros->getType();
1546 unsigned SizeInBits = Ty->getPrimitiveSizeInBits();
1547 if (Ty->isVectorTy() || SizeInBits > DL->getLargestLegalIntTypeSizeInBits())
1548 return false;
1549
1550 // The intrinsic will be sunk behind a compare against zero and branch.
1551 BasicBlock *StartBlock = CountZeros->getParent();
1552 BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false");
1553
1554 // Create another block after the count zero intrinsic. A PHI will be added
1555 // in this block to select the result of the intrinsic or the bit-width
1556 // constant if the input to the intrinsic is zero.
1557 BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(CountZeros));
1558 BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end");
1559
1560 // Set up a builder to create a compare, conditional branch, and PHI.
1561 IRBuilder<> Builder(CountZeros->getContext());
1562 Builder.SetInsertPoint(StartBlock->getTerminator());
1563 Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc());
1564
1565 // Replace the unconditional branch that was created by the first split with
1566 // a compare against zero and a conditional branch.
1567 Value *Zero = Constant::getNullValue(Ty);
1568 Value *Cmp = Builder.CreateICmpEQ(CountZeros->getOperand(0), Zero, "cmpz");
1569 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
1570 StartBlock->getTerminator()->eraseFromParent();
1571
1572 // Create a PHI in the end block to select either the output of the intrinsic
1573 // or the bit width of the operand.
1574 Builder.SetInsertPoint(&EndBlock->front());
1575 PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz");
1576 CountZeros->replaceAllUsesWith(PN);
1577 Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits));
1578 PN->addIncoming(BitWidth, StartBlock);
1579 PN->addIncoming(CountZeros, CallBlock);
1580
1581 // We are explicitly handling the zero case, so we can set the intrinsic's
1582 // undefined zero argument to 'true'. This will also prevent reprocessing the
1583 // intrinsic; we only despeculate when a zero input is defined.
1584 CountZeros->setArgOperand(1, Builder.getTrue());
1585 ModifiedDT = true;
1586 return true;
1587}
1588
1589bool CodeGenPrepare::optimizeCallInst(CallInst *CI, bool &ModifiedDT) {
1590 BasicBlock *BB = CI->getParent();
1591
1592 // Lower inline assembly if we can.
1593 // If we found an inline asm expession, and if the target knows how to
1594 // lower it to normal LLVM code, do so now.
1595 if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
1596 if (TLI->ExpandInlineAsm(CI)) {
1597 // Avoid invalidating the iterator.
1598 CurInstIterator = BB->begin();
1599 // Avoid processing instructions out of order, which could cause
1600 // reuse before a value is defined.
1601 SunkAddrs.clear();
1602 return true;
1603 }
1604 // Sink address computing for memory operands into the block.
1605 if (optimizeInlineAsmInst(CI))
1606 return true;
1607 }
1608
1609 // Align the pointer arguments to this call if the target thinks it's a good
1610 // idea
1611 unsigned MinSize, PrefAlign;
1612 if (TLI && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
1613 for (auto &Arg : CI->arg_operands()) {
1614 // We want to align both objects whose address is used directly and
1615 // objects whose address is used in casts and GEPs, though it only makes
1616 // sense for GEPs if the offset is a multiple of the desired alignment and
1617 // if size - offset meets the size threshold.
1618 if (!Arg->getType()->isPointerTy())
1619 continue;
1620 APInt Offset(DL->getIndexSizeInBits(
1621 cast<PointerType>(Arg->getType())->getAddressSpace()),
1622 0);
1623 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
1624 uint64_t Offset2 = Offset.getLimitedValue();
1625 if ((Offset2 & (PrefAlign-1)) != 0)
1626 continue;
1627 AllocaInst *AI;
1628 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlignment() < PrefAlign &&
1629 DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
1630 AI->setAlignment(PrefAlign);
1631 // Global variables can only be aligned if they are defined in this
1632 // object (i.e. they are uniquely initialized in this object), and
1633 // over-aligning global variables that have an explicit section is
1634 // forbidden.
1635 GlobalVariable *GV;
1636 if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->canIncreaseAlignment() &&
1637 GV->getPointerAlignment(*DL) < PrefAlign &&
1638 DL->getTypeAllocSize(GV->getValueType()) >=
1639 MinSize + Offset2)
1640 GV->setAlignment(PrefAlign);
1641 }
1642 // If this is a memcpy (or similar) then we may be able to improve the
1643 // alignment
1644 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(CI)) {
1645 unsigned DestAlign = getKnownAlignment(MI->getDest(), *DL);
1646 if (DestAlign > MI->getDestAlignment())
1647 MI->setDestAlignment(DestAlign);
1648 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
1649 unsigned SrcAlign = getKnownAlignment(MTI->getSource(), *DL);
1650 if (SrcAlign > MTI->getSourceAlignment())
1651 MTI->setSourceAlignment(SrcAlign);
1652 }
1653 }
1654 }
1655
1656 // If we have a cold call site, try to sink addressing computation into the
1657 // cold block. This interacts with our handling for loads and stores to
1658 // ensure that we can fold all uses of a potential addressing computation
1659 // into their uses. TODO: generalize this to work over profiling data
1660 if (!OptSize && CI->hasFnAttr(Attribute::Cold))
1661 for (auto &Arg : CI->arg_operands()) {
1662 if (!Arg->getType()->isPointerTy())
1663 continue;
1664 unsigned AS = Arg->getType()->getPointerAddressSpace();
1665 return optimizeMemoryInst(CI, Arg, Arg->getType(), AS);
1666 }
1667
1668 IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
1669 if (II) {
1670 switch (II->getIntrinsicID()) {
1671 default: break;
1672 case Intrinsic::objectsize: {
1673 // Lower all uses of llvm.objectsize.*
1674 ConstantInt *RetVal =
1675 lowerObjectSizeCall(II, *DL, TLInfo, /*MustSucceed=*/true);
1676 // Substituting this can cause recursive simplifications, which can
1677 // invalidate our iterator. Use a WeakTrackingVH to hold onto it in case
1678 // this
1679 // happens.
1680 Value *CurValue = &*CurInstIterator;
1681 WeakTrackingVH IterHandle(CurValue);
1682
1683 replaceAndRecursivelySimplify(CI, RetVal, TLInfo, nullptr);
1684
1685 // If the iterator instruction was recursively deleted, start over at the
1686 // start of the block.
1687 if (IterHandle != CurValue) {
1688 CurInstIterator = BB->begin();
1689 SunkAddrs.clear();
1690 }
1691 return true;
1692 }
1693 case Intrinsic::aarch64_stlxr:
1694 case Intrinsic::aarch64_stxr: {
1695 ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
1696 if (!ExtVal || !ExtVal->hasOneUse() ||
1697 ExtVal->getParent() == CI->getParent())
1698 return false;
1699 // Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
1700 ExtVal->moveBefore(CI);
1701 // Mark this instruction as "inserted by CGP", so that other
1702 // optimizations don't touch it.
1703 InsertedInsts.insert(ExtVal);
1704 return true;
1705 }
1706 case Intrinsic::launder_invariant_group:
1707 case Intrinsic::strip_invariant_group:
1708 II->replaceAllUsesWith(II->getArgOperand(0));
1709 II->eraseFromParent();
1710 return true;
1711
1712 case Intrinsic::cttz:
1713 case Intrinsic::ctlz:
1714 // If counting zeros is expensive, try to avoid it.
1715 return despeculateCountZeros(II, TLI, DL, ModifiedDT);
1716 }
1717
1718 if (TLI) {
1719 SmallVector<Value*, 2> PtrOps;
1720 Type *AccessTy;
1721 if (TLI->getAddrModeArguments(II, PtrOps, AccessTy))
1722 while (!PtrOps.empty()) {
1723 Value *PtrVal = PtrOps.pop_back_val();
1724 unsigned AS = PtrVal->getType()->getPointerAddressSpace();
1725 if (optimizeMemoryInst(II, PtrVal, AccessTy, AS))
1726 return true;
1727 }
1728 }
1729 }
1730
1731 // From here on out we're working with named functions.
1732 if (!CI->getCalledFunction()) return false;
1733
1734 // Lower all default uses of _chk calls. This is very similar
1735 // to what InstCombineCalls does, but here we are only lowering calls
1736 // to fortified library functions (e.g. __memcpy_chk) that have the default
1737 // "don't know" as the objectsize. Anything else should be left alone.
1738 FortifiedLibCallSimplifier Simplifier(TLInfo, true);
1739 if (Value *V = Simplifier.optimizeCall(CI)) {
1740 CI->replaceAllUsesWith(V);
1741 CI->eraseFromParent();
1742 return true;
1743 }
1744
1745 return false;
1746}
1747
1748/// Look for opportunities to duplicate return instructions to the predecessor
1749/// to enable tail call optimizations. The case it is currently looking for is:
1750/// @code
1751/// bb0:
1752/// %tmp0 = tail call i32 @f0()
1753/// br label %return
1754/// bb1:
1755/// %tmp1 = tail call i32 @f1()
1756/// br label %return
1757/// bb2:
1758/// %tmp2 = tail call i32 @f2()
1759/// br label %return
1760/// return:
1761/// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
1762/// ret i32 %retval
1763/// @endcode
1764///
1765/// =>
1766///
1767/// @code
1768/// bb0:
1769/// %tmp0 = tail call i32 @f0()
1770/// ret i32 %tmp0
1771/// bb1:
1772/// %tmp1 = tail call i32 @f1()
1773/// ret i32 %tmp1
1774/// bb2:
1775/// %tmp2 = tail call i32 @f2()
1776/// ret i32 %tmp2
1777/// @endcode
1778bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) {
1779 if (!TLI)
1780 return false;
1781
1782 ReturnInst *RetI = dyn_cast<ReturnInst>(BB->getTerminator());
1783 if (!RetI)
1784 return false;
1785
1786 PHINode *PN = nullptr;
1787 BitCastInst *BCI = nullptr;
1788 Value *V = RetI->getReturnValue();
1789 if (V) {
1790 BCI = dyn_cast<BitCastInst>(V);
1791 if (BCI)
1792 V = BCI->getOperand(0);
1793
1794 PN = dyn_cast<PHINode>(V);
1795 if (!PN)
1796 return false;
1797 }
1798
1799 if (PN && PN->getParent() != BB)
1800 return false;
1801
1802 // Make sure there are no instructions between the PHI and return, or that the
1803 // return is the first instruction in the block.
1804 if (PN) {
1805 BasicBlock::iterator BI = BB->begin();
1806 do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
1807 if (&*BI == BCI)
1808 // Also skip over the bitcast.
1809 ++BI;
1810 if (&*BI != RetI)
1811 return false;
1812 } else {
1813 BasicBlock::iterator BI = BB->begin();
1814 while (isa<DbgInfoIntrinsic>(BI)) ++BI;
1815 if (&*BI != RetI)
1816 return false;
1817 }
1818
1819 /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
1820 /// call.
1821 const Function *F = BB->getParent();
1822 SmallVector<CallInst*, 4> TailCalls;
1823 if (PN) {
1824 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
1825 CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
1826 // Make sure the phi value is indeed produced by the tail call.
1827 if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
1828 TLI->mayBeEmittedAsTailCall(CI) &&
1829 attributesPermitTailCall(F, CI, RetI, *TLI))
1830 TailCalls.push_back(CI);
1831 }
1832 } else {
1833 SmallPtrSet<BasicBlock*, 4> VisitedBBs;
1834 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1835 if (!VisitedBBs.insert(*PI).second)
1836 continue;
1837
1838 BasicBlock::InstListType &InstList = (*PI)->getInstList();
1839 BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
1840 BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
1841 do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
1842 if (RI == RE)
1843 continue;
1844
1845 CallInst *CI = dyn_cast<CallInst>(&*RI);
1846 if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI) &&
1847 attributesPermitTailCall(F, CI, RetI, *TLI))
1848 TailCalls.push_back(CI);
1849 }
1850 }
1851
1852 bool Changed = false;
1853 for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
1854 CallInst *CI = TailCalls[i];
1855 CallSite CS(CI);
1856
1857 // Conservatively require the attributes of the call to match those of the
1858 // return. Ignore noalias because it doesn't affect the call sequence.
1859 AttributeList CalleeAttrs = CS.getAttributes();
1860 if (AttrBuilder(CalleeAttrs, AttributeList::ReturnIndex)
1861 .removeAttribute(Attribute::NoAlias) !=
1862 AttrBuilder(CalleeAttrs, AttributeList::ReturnIndex)
1863 .removeAttribute(Attribute::NoAlias))
1864 continue;
1865
1866 // Make sure the call instruction is followed by an unconditional branch to
1867 // the return block.
1868 BasicBlock *CallBB = CI->getParent();
1869 BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
1870 if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
1871 continue;
1872
1873 // Duplicate the return into CallBB.
1874 (void)FoldReturnIntoUncondBranch(RetI, BB, CallBB);
1875 ModifiedDT = Changed = true;
1876 ++NumRetsDup;
1877 }
1878
1879 // If we eliminated all predecessors of the block, delete the block now.
1880 if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
1881 BB->eraseFromParent();
1882
1883 return Changed;
1884}
1885
1886//===----------------------------------------------------------------------===//
1887// Memory Optimization
1888//===----------------------------------------------------------------------===//
1889
1890namespace {
1891
1892/// This is an extended version of TargetLowering::AddrMode
1893/// which holds actual Value*'s for register values.
1894struct ExtAddrMode : public TargetLowering::AddrMode {
1895 Value *BaseReg = nullptr;
1896 Value *ScaledReg = nullptr;
1897 Value *OriginalValue = nullptr;
1898
1899 enum FieldName {
1900 NoField = 0x00,
1901 BaseRegField = 0x01,
1902 BaseGVField = 0x02,
1903 BaseOffsField = 0x04,
1904 ScaledRegField = 0x08,
1905 ScaleField = 0x10,
1906 MultipleFields = 0xff
1907 };
1908
1909 ExtAddrMode() = default;
1910
1911 void print(raw_ostream &OS) const;
1912 void dump() const;
1913
1914 FieldName compare(const ExtAddrMode &other) {
1915 // First check that the types are the same on each field, as differing types
1916 // is something we can't cope with later on.
1917 if (BaseReg && other.BaseReg &&
1918 BaseReg->getType() != other.BaseReg->getType())
1919 return MultipleFields;
1920 if (BaseGV && other.BaseGV &&
1921 BaseGV->getType() != other.BaseGV->getType())
1922 return MultipleFields;
1923 if (ScaledReg && other.ScaledReg &&
1924 ScaledReg->getType() != other.ScaledReg->getType())
1925 return MultipleFields;
1926
1927 // Check each field to see if it differs.
1928 unsigned Result = NoField;
1929 if (BaseReg != other.BaseReg)
1930 Result |= BaseRegField;
1931 if (BaseGV != other.BaseGV)
1932 Result |= BaseGVField;
1933 if (BaseOffs != other.BaseOffs)
1934 Result |= BaseOffsField;
1935 if (ScaledReg != other.ScaledReg)
1936 Result |= ScaledRegField;
1937 // Don't count 0 as being a different scale, because that actually means
1938 // unscaled (which will already be counted by having no ScaledReg).
1939 if (Scale && other.Scale && Scale != other.Scale)
1940 Result |= ScaleField;
1941
1942 if (countPopulation(Result) > 1)
1943 return MultipleFields;
1944 else
1945 return static_cast<FieldName>(Result);
1946 }
1947
1948 // An AddrMode is trivial if it involves no calculation i.e. it is just a base
1949 // with no offset.
1950 bool isTrivial() {
1951 // An AddrMode is (BaseGV + BaseReg + BaseOffs + ScaleReg * Scale) so it is
1952 // trivial if at most one of these terms is nonzero, except that BaseGV and
1953 // BaseReg both being zero actually means a null pointer value, which we
1954 // consider to be 'non-zero' here.
1955 return !BaseOffs && !Scale && !(BaseGV && BaseReg);
1956 }
1957
1958 Value *GetFieldAsValue(FieldName Field, Type *IntPtrTy) {
1959 switch (Field) {
1960 default:
1961 return nullptr;
1962 case BaseRegField:
1963 return BaseReg;
1964 case BaseGVField:
1965 return BaseGV;
1966 case ScaledRegField:
1967 return ScaledReg;
1968 case BaseOffsField:
1969 return ConstantInt::get(IntPtrTy, BaseOffs);
1970 }
1971 }
1972
1973 void SetCombinedField(FieldName Field, Value *V,
1974 const SmallVectorImpl<ExtAddrMode> &AddrModes) {
1975 switch (Field) {
1976 default:
1977 llvm_unreachable("Unhandled fields are expected to be rejected earlier")::llvm::llvm_unreachable_internal("Unhandled fields are expected to be rejected earlier"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1977)
;
1978 break;
1979 case ExtAddrMode::BaseRegField:
1980 BaseReg = V;
1981 break;
1982 case ExtAddrMode::BaseGVField:
1983 // A combined BaseGV is an Instruction, not a GlobalValue, so it goes
1984 // in the BaseReg field.
1985 assert(BaseReg == nullptr)(static_cast <bool> (BaseReg == nullptr) ? void (0) : __assert_fail
("BaseReg == nullptr", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 1985, __extension__ __PRETTY_FUNCTION__))
;
1986 BaseReg = V;
1987 BaseGV = nullptr;
1988 break;
1989 case ExtAddrMode::ScaledRegField:
1990 ScaledReg = V;
1991 // If we have a mix of scaled and unscaled addrmodes then we want scale
1992 // to be the scale and not zero.
1993 if (!Scale)
1994 for (const ExtAddrMode &AM : AddrModes)
1995 if (AM.Scale) {
1996 Scale = AM.Scale;
1997 break;
1998 }
1999 break;
2000 case ExtAddrMode::BaseOffsField:
2001 // The offset is no longer a constant, so it goes in ScaledReg with a
2002 // scale of 1.
2003 assert(ScaledReg == nullptr)(static_cast <bool> (ScaledReg == nullptr) ? void (0) :
__assert_fail ("ScaledReg == nullptr", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 2003, __extension__ __PRETTY_FUNCTION__))
;
2004 ScaledReg = V;
2005 Scale = 1;
2006 BaseOffs = 0;
2007 break;
2008 }
2009 }
2010};
2011
2012} // end anonymous namespace
2013
2014#ifndef NDEBUG
2015static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
2016 AM.print(OS);
2017 return OS;
2018}
2019#endif
2020
2021#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2022void ExtAddrMode::print(raw_ostream &OS) const {
2023 bool NeedPlus = false;
2024 OS << "[";
2025 if (BaseGV) {
2026 OS << (NeedPlus ? " + " : "")
2027 << "GV:";
2028 BaseGV->printAsOperand(OS, /*PrintType=*/false);
2029 NeedPlus = true;
2030 }
2031
2032 if (BaseOffs) {
2033 OS << (NeedPlus ? " + " : "")
2034 << BaseOffs;
2035 NeedPlus = true;
2036 }
2037
2038 if (BaseReg) {
2039 OS << (NeedPlus ? " + " : "")
2040 << "Base:";
2041 BaseReg->printAsOperand(OS, /*PrintType=*/false);
2042 NeedPlus = true;
2043 }
2044 if (Scale) {
2045 OS << (NeedPlus ? " + " : "")
2046 << Scale << "*";
2047 ScaledReg->printAsOperand(OS, /*PrintType=*/false);
2048 }
2049
2050 OS << ']';
2051}
2052
2053LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ExtAddrMode::dump() const {
2054 print(dbgs());
2055 dbgs() << '\n';
2056}
2057#endif
2058
2059namespace {
2060
2061/// This class provides transaction based operation on the IR.
2062/// Every change made through this class is recorded in the internal state and
2063/// can be undone (rollback) until commit is called.
2064class TypePromotionTransaction {
2065 /// This represents the common interface of the individual transaction.
2066 /// Each class implements the logic for doing one specific modification on
2067 /// the IR via the TypePromotionTransaction.
2068 class TypePromotionAction {
2069 protected:
2070 /// The Instruction modified.
2071 Instruction *Inst;
2072
2073 public:
2074 /// Constructor of the action.
2075 /// The constructor performs the related action on the IR.
2076 TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
2077
2078 virtual ~TypePromotionAction() = default;
2079
2080 /// Undo the modification done by this action.
2081 /// When this method is called, the IR must be in the same state as it was
2082 /// before this action was applied.
2083 /// \pre Undoing the action works if and only if the IR is in the exact same
2084 /// state as it was directly after this action was applied.
2085 virtual void undo() = 0;
2086
2087 /// Advocate every change made by this action.
2088 /// When the results on the IR of the action are to be kept, it is important
2089 /// to call this function, otherwise hidden information may be kept forever.
2090 virtual void commit() {
2091 // Nothing to be done, this action is not doing anything.
2092 }
2093 };
2094
2095 /// Utility to remember the position of an instruction.
2096 class InsertionHandler {
2097 /// Position of an instruction.
2098 /// Either an instruction:
2099 /// - Is the first in a basic block: BB is used.
2100 /// - Has a previous instruction: PrevInst is used.
2101 union {
2102 Instruction *PrevInst;
2103 BasicBlock *BB;
2104 } Point;
2105
2106 /// Remember whether or not the instruction had a previous instruction.
2107 bool HasPrevInstruction;
2108
2109 public:
2110 /// Record the position of \p Inst.
2111 InsertionHandler(Instruction *Inst) {
2112 BasicBlock::iterator It = Inst->getIterator();
2113 HasPrevInstruction = (It != (Inst->getParent()->begin()));
2114 if (HasPrevInstruction)
2115 Point.PrevInst = &*--It;
2116 else
2117 Point.BB = Inst->getParent();
2118 }
2119
2120 /// Insert \p Inst at the recorded position.
2121 void insert(Instruction *Inst) {
2122 if (HasPrevInstruction) {
2123 if (Inst->getParent())
2124 Inst->removeFromParent();
2125 Inst->insertAfter(Point.PrevInst);
2126 } else {
2127 Instruction *Position = &*Point.BB->getFirstInsertionPt();
2128 if (Inst->getParent())
2129 Inst->moveBefore(Position);
2130 else
2131 Inst->insertBefore(Position);
2132 }
2133 }
2134 };
2135
2136 /// Move an instruction before another.
2137 class InstructionMoveBefore : public TypePromotionAction {
2138 /// Original position of the instruction.
2139 InsertionHandler Position;
2140
2141 public:
2142 /// Move \p Inst before \p Before.
2143 InstructionMoveBefore(Instruction *Inst, Instruction *Before)
2144 : TypePromotionAction(Inst), Position(Inst) {
2145 LLVM_DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Beforedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: move: " << *
Inst << "\nbefore: " << *Before << "\n"; } }
while (false)
2146 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: move: " << *
Inst << "\nbefore: " << *Before << "\n"; } }
while (false)
;
2147 Inst->moveBefore(Before);
2148 }
2149
2150 /// Move the instruction back to its original position.
2151 void undo() override {
2152 LLVM_DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: moveBefore: " <<
*Inst << "\n"; } } while (false)
;
2153 Position.insert(Inst);
2154 }
2155 };
2156
2157 /// Set the operand of an instruction with a new value.
2158 class OperandSetter : public TypePromotionAction {
2159 /// Original operand of the instruction.
2160 Value *Origin;
2161
2162 /// Index of the modified instruction.
2163 unsigned Idx;
2164
2165 public:
2166 /// Set \p Idx operand of \p Inst with \p NewVal.
2167 OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal)
2168 : TypePromotionAction(Inst), Idx(Idx) {
2169 LLVM_DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: setOperand: " <<
Idx << "\n" << "for:" << *Inst << "\n"
<< "with:" << *NewVal << "\n"; } } while (
false)
2170 << "for:" << *Inst << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: setOperand: " <<
Idx << "\n" << "for:" << *Inst << "\n"
<< "with:" << *NewVal << "\n"; } } while (
false)
2171 << "with:" << *NewVal << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: setOperand: " <<
Idx << "\n" << "for:" << *Inst << "\n"
<< "with:" << *NewVal << "\n"; } } while (
false)
;
2172 Origin = Inst->getOperand(Idx);
2173 Inst->setOperand(Idx, NewVal);
2174 }
2175
2176 /// Restore the original value of the instruction.
2177 void undo() override {
2178 LLVM_DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: setOperand:" <<
Idx << "\n" << "for: " << *Inst << "\n"
<< "with: " << *Origin << "\n"; } } while (
false)
2179 << "for: " << *Inst << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: setOperand:" <<
Idx << "\n" << "for: " << *Inst << "\n"
<< "with: " << *Origin << "\n"; } } while (
false)
2180 << "with: " << *Origin << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: setOperand:" <<
Idx << "\n" << "for: " << *Inst << "\n"
<< "with: " << *Origin << "\n"; } } while (
false)
;
2181 Inst->setOperand(Idx, Origin);
2182 }
2183 };
2184
2185 /// Hide the operands of an instruction.
2186 /// Do as if this instruction was not using any of its operands.
2187 class OperandsHider : public TypePromotionAction {
2188 /// The list of original operands.
2189 SmallVector<Value *, 4> OriginalValues;
2190
2191 public:
2192 /// Remove \p Inst from the uses of the operands of \p Inst.
2193 OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
2194 LLVM_DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: OperandsHider: " <<
*Inst << "\n"; } } while (false)
;
2195 unsigned NumOpnds = Inst->getNumOperands();
2196 OriginalValues.reserve(NumOpnds);
2197 for (unsigned It = 0; It < NumOpnds; ++It) {
2198 // Save the current operand.
2199 Value *Val = Inst->getOperand(It);
2200 OriginalValues.push_back(Val);
2201 // Set a dummy one.
2202 // We could use OperandSetter here, but that would imply an overhead
2203 // that we are not willing to pay.
2204 Inst->setOperand(It, UndefValue::get(Val->getType()));
2205 }
2206 }
2207
2208 /// Restore the original list of uses.
2209 void undo() override {
2210 LLVM_DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: OperandsHider: "
<< *Inst << "\n"; } } while (false)
;
2211 for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It)
2212 Inst->setOperand(It, OriginalValues[It]);
2213 }
2214 };
2215
2216 /// Build a truncate instruction.
2217 class TruncBuilder : public TypePromotionAction {
2218 Value *Val;
2219
2220 public:
2221 /// Build a truncate instruction of \p Opnd producing a \p Ty
2222 /// result.
2223 /// trunc Opnd to Ty.
2224 TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
2225 IRBuilder<> Builder(Opnd);
2226 Val = Builder.CreateTrunc(Opnd, Ty, "promoted");
2227 LLVM_DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: TruncBuilder: " <<
*Val << "\n"; } } while (false)
;
2228 }
2229
2230 /// Get the built value.
2231 Value *getBuiltValue() { return Val; }
2232
2233 /// Remove the built instruction.
2234 void undo() override {
2235 LLVM_DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: TruncBuilder: " <<
*Val << "\n"; } } while (false)
;
2236 if (Instruction *IVal = dyn_cast<Instruction>(Val))
2237 IVal->eraseFromParent();
2238 }
2239 };
2240
2241 /// Build a sign extension instruction.
2242 class SExtBuilder : public TypePromotionAction {
2243 Value *Val;
2244
2245 public:
2246 /// Build a sign extension instruction of \p Opnd producing a \p Ty
2247 /// result.
2248 /// sext Opnd to Ty.
2249 SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
2250 : TypePromotionAction(InsertPt) {
2251 IRBuilder<> Builder(InsertPt);
2252 Val = Builder.CreateSExt(Opnd, Ty, "promoted");
2253 LLVM_DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: SExtBuilder: " <<
*Val << "\n"; } } while (false)
;
2254 }
2255
2256 /// Get the built value.
2257 Value *getBuiltValue() { return Val; }
2258
2259 /// Remove the built instruction.
2260 void undo() override {
2261 LLVM_DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: SExtBuilder: " <<
*Val << "\n"; } } while (false)
;
2262 if (Instruction *IVal = dyn_cast<Instruction>(Val))
2263 IVal->eraseFromParent();
2264 }
2265 };
2266
2267 /// Build a zero extension instruction.
2268 class ZExtBuilder : public TypePromotionAction {
2269 Value *Val;
2270
2271 public:
2272 /// Build a zero extension instruction of \p Opnd producing a \p Ty
2273 /// result.
2274 /// zext Opnd to Ty.
2275 ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
2276 : TypePromotionAction(InsertPt) {
2277 IRBuilder<> Builder(InsertPt);
2278 Val = Builder.CreateZExt(Opnd, Ty, "promoted");
2279 LLVM_DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: ZExtBuilder: " <<
*Val << "\n"; } } while (false)
;
2280 }
2281
2282 /// Get the built value.
2283 Value *getBuiltValue() { return Val; }
2284
2285 /// Remove the built instruction.
2286 void undo() override {
2287 LLVM_DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: ZExtBuilder: " <<
*Val << "\n"; } } while (false)
;
2288 if (Instruction *IVal = dyn_cast<Instruction>(Val))
2289 IVal->eraseFromParent();
2290 }
2291 };
2292
2293 /// Mutate an instruction to another type.
2294 class TypeMutator : public TypePromotionAction {
2295 /// Record the original type.
2296 Type *OrigTy;
2297
2298 public:
2299 /// Mutate the type of \p Inst into \p NewTy.
2300 TypeMutator(Instruction *Inst, Type *NewTy)
2301 : TypePromotionAction(Inst), OrigTy(Inst->getType()) {
2302 LLVM_DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTydo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: MutateType: " <<
*Inst << " with " << *NewTy << "\n"; } } while
(false)
2303 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: MutateType: " <<
*Inst << " with " << *NewTy << "\n"; } } while
(false)
;
2304 Inst->mutateType(NewTy);
2305 }
2306
2307 /// Mutate the instruction back to its original type.
2308 void undo() override {
2309 LLVM_DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTydo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: MutateType: " <<
*Inst << " with " << *OrigTy << "\n"; } } while
(false)
2310 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: MutateType: " <<
*Inst << " with " << *OrigTy << "\n"; } } while
(false)
;
2311 Inst->mutateType(OrigTy);
2312 }
2313 };
2314
2315 /// Replace the uses of an instruction by another instruction.
2316 class UsesReplacer : public TypePromotionAction {
2317 /// Helper structure to keep track of the replaced uses.
2318 struct InstructionAndIdx {
2319 /// The instruction using the instruction.
2320 Instruction *Inst;
2321
2322 /// The index where this instruction is used for Inst.
2323 unsigned Idx;
2324
2325 InstructionAndIdx(Instruction *Inst, unsigned Idx)
2326 : Inst(Inst), Idx(Idx) {}
2327 };
2328
2329 /// Keep track of the original uses (pair Instruction, Index).
2330 SmallVector<InstructionAndIdx, 4> OriginalUses;
2331
2332 using use_iterator = SmallVectorImpl<InstructionAndIdx>::iterator;
2333
2334 public:
2335 /// Replace all the use of \p Inst by \p New.
2336 UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) {
2337 LLVM_DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *Newdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: UsersReplacer: " <<
*Inst << " with " << *New << "\n"; } } while
(false)
2338 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: UsersReplacer: " <<
*Inst << " with " << *New << "\n"; } } while
(false)
;
2339 // Record the original uses.
2340 for (Use &U : Inst->uses()) {
2341 Instruction *UserI = cast<Instruction>(U.getUser());
2342 OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo()));
2343 }
2344 // Now, we can replace the uses.
2345 Inst->replaceAllUsesWith(New);
2346 }
2347
2348 /// Reassign the original uses of Inst to Inst.
2349 void undo() override {
2350 LLVM_DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: UsersReplacer: "
<< *Inst << "\n"; } } while (false)
;
2351 for (use_iterator UseIt = OriginalUses.begin(),
2352 EndIt = OriginalUses.end();
2353 UseIt != EndIt; ++UseIt) {
2354 UseIt->Inst->setOperand(UseIt->Idx, Inst);
2355 }
2356 }
2357 };
2358
2359 /// Remove an instruction from the IR.
2360 class InstructionRemover : public TypePromotionAction {
2361 /// Original position of the instruction.
2362 InsertionHandler Inserter;
2363
2364 /// Helper structure to hide all the link to the instruction. In other
2365 /// words, this helps to do as if the instruction was removed.
2366 OperandsHider Hider;
2367
2368 /// Keep track of the uses replaced, if any.
2369 UsesReplacer *Replacer = nullptr;
2370
2371 /// Keep track of instructions removed.
2372 SetOfInstrs &RemovedInsts;
2373
2374 public:
2375 /// Remove all reference of \p Inst and optionally replace all its
2376 /// uses with New.
2377 /// \p RemovedInsts Keep track of the instructions removed by this Action.
2378 /// \pre If !Inst->use_empty(), then New != nullptr
2379 InstructionRemover(Instruction *Inst, SetOfInstrs &RemovedInsts,
2380 Value *New = nullptr)
2381 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
2382 RemovedInsts(RemovedInsts) {
2383 if (New)
2384 Replacer = new UsesReplacer(Inst, New);
2385 LLVM_DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Do: InstructionRemover: "
<< *Inst << "\n"; } } while (false)
;
2386 RemovedInsts.insert(Inst);
2387 /// The instructions removed here will be freed after completing
2388 /// optimizeBlock() for all blocks as we need to keep track of the
2389 /// removed instructions during promotion.
2390 Inst->removeFromParent();
2391 }
2392
2393 ~InstructionRemover() override { delete Replacer; }
2394
2395 /// Resurrect the instruction and reassign it to the proper uses if
2396 /// new value was provided when build this action.
2397 void undo() override {
2398 LLVM_DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Undo: InstructionRemover: "
<< *Inst << "\n"; } } while (false)
;
2399 Inserter.insert(Inst);
2400 if (Replacer)
2401 Replacer->undo();
2402 Hider.undo();
2403 RemovedInsts.erase(Inst);
2404 }
2405 };
2406
2407public:
2408 /// Restoration point.
2409 /// The restoration point is a pointer to an action instead of an iterator
2410 /// because the iterator may be invalidated but not the pointer.
2411 using ConstRestorationPt = const TypePromotionAction *;
2412
2413 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
2414 : RemovedInsts(RemovedInsts) {}
2415
2416 /// Advocate every changes made in that transaction.
2417 void commit();
2418
2419 /// Undo all the changes made after the given point.
2420 void rollback(ConstRestorationPt Point);
2421
2422 /// Get the current restoration point.
2423 ConstRestorationPt getRestorationPoint() const;
2424
2425 /// \name API for IR modification with state keeping to support rollback.
2426 /// @{
2427 /// Same as Instruction::setOperand.
2428 void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal);
2429
2430 /// Same as Instruction::eraseFromParent.
2431 void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr);
2432
2433 /// Same as Value::replaceAllUsesWith.
2434 void replaceAllUsesWith(Instruction *Inst, Value *New);
2435
2436 /// Same as Value::mutateType.
2437 void mutateType(Instruction *Inst, Type *NewTy);
2438
2439 /// Same as IRBuilder::createTrunc.
2440 Value *createTrunc(Instruction *Opnd, Type *Ty);
2441
2442 /// Same as IRBuilder::createSExt.
2443 Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
2444
2445 /// Same as IRBuilder::createZExt.
2446 Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty);
2447
2448 /// Same as Instruction::moveBefore.
2449 void moveBefore(Instruction *Inst, Instruction *Before);
2450 /// @}
2451
2452private:
2453 /// The ordered list of actions made so far.
2454 SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
2455
2456 using CommitPt = SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator;
2457
2458 SetOfInstrs &RemovedInsts;
2459};
2460
2461} // end anonymous namespace
2462
2463void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
2464 Value *NewVal) {
2465 Actions.push_back(llvm::make_unique<TypePromotionTransaction::OperandSetter>(
2466 Inst, Idx, NewVal));
2467}
2468
2469void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
2470 Value *NewVal) {
2471 Actions.push_back(
2472 llvm::make_unique<TypePromotionTransaction::InstructionRemover>(
2473 Inst, RemovedInsts, NewVal));
2474}
2475
2476void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
2477 Value *New) {
2478 Actions.push_back(
2479 llvm::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
2480}
2481
2482void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
2483 Actions.push_back(
2484 llvm::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
2485}
2486
2487Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
2488 Type *Ty) {
2489 std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty));
2490 Value *Val = Ptr->getBuiltValue();
2491 Actions.push_back(std::move(Ptr));
2492 return Val;
2493}
2494
2495Value *TypePromotionTransaction::createSExt(Instruction *Inst,
2496 Value *Opnd, Type *Ty) {
2497 std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty));
2498 Value *Val = Ptr->getBuiltValue();
2499 Actions.push_back(std::move(Ptr));
2500 return Val;
2501}
2502
2503Value *TypePromotionTransaction::createZExt(Instruction *Inst,
2504 Value *Opnd, Type *Ty) {
2505 std::unique_ptr<ZExtBuilder> Ptr(new ZExtBuilder(Inst, Opnd, Ty));
2506 Value *Val = Ptr->getBuiltValue();
2507 Actions.push_back(std::move(Ptr));
2508 return Val;
2509}
2510
2511void TypePromotionTransaction::moveBefore(Instruction *Inst,
2512 Instruction *Before) {
2513 Actions.push_back(
2514 llvm::make_unique<TypePromotionTransaction::InstructionMoveBefore>(
2515 Inst, Before));
2516}
2517
2518TypePromotionTransaction::ConstRestorationPt
2519TypePromotionTransaction::getRestorationPoint() const {
2520 return !Actions.empty() ? Actions.back().get() : nullptr;
2521}
2522
2523void TypePromotionTransaction::commit() {
2524 for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
2525 ++It)
2526 (*It)->commit();
2527 Actions.clear();
2528}
2529
2530void TypePromotionTransaction::rollback(
2531 TypePromotionTransaction::ConstRestorationPt Point) {
2532 while (!Actions.empty() && Point != Actions.back().get()) {
2533 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
2534 Curr->undo();
2535 }
2536}
2537
2538namespace {
2539
2540/// A helper class for matching addressing modes.
2541///
2542/// This encapsulates the logic for matching the target-legal addressing modes.
2543class AddressingModeMatcher {
2544 SmallVectorImpl<Instruction*> &AddrModeInsts;
2545 const TargetLowering &TLI;
2546 const TargetRegisterInfo &TRI;
2547 const DataLayout &DL;
2548
2549 /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
2550 /// the memory instruction that we're computing this address for.
2551 Type *AccessTy;
2552 unsigned AddrSpace;
2553 Instruction *MemoryInst;
2554
2555 /// This is the addressing mode that we're building up. This is
2556 /// part of the return value of this addressing mode matching stuff.
2557 ExtAddrMode &AddrMode;
2558
2559 /// The instructions inserted by other CodeGenPrepare optimizations.
2560 const SetOfInstrs &InsertedInsts;
2561
2562 /// A map from the instructions to their type before promotion.
2563 InstrToOrigTy &PromotedInsts;
2564
2565 /// The ongoing transaction where every action should be registered.
2566 TypePromotionTransaction &TPT;
2567
2568 // A GEP which has too large offset to be folded into the addressing mode.
2569 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
2570
2571 /// This is set to true when we should not do profitability checks.
2572 /// When true, IsProfitableToFoldIntoAddressingMode always returns true.
2573 bool IgnoreProfitability;
2574
2575 AddressingModeMatcher(
2576 SmallVectorImpl<Instruction *> &AMI, const TargetLowering &TLI,
2577 const TargetRegisterInfo &TRI, Type *AT, unsigned AS, Instruction *MI,
2578 ExtAddrMode &AM, const SetOfInstrs &InsertedInsts,
2579 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
2580 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP)
2581 : AddrModeInsts(AMI), TLI(TLI), TRI(TRI),
2582 DL(MI->getModule()->getDataLayout()), AccessTy(AT), AddrSpace(AS),
2583 MemoryInst(MI), AddrMode(AM), InsertedInsts(InsertedInsts),
2584 PromotedInsts(PromotedInsts), TPT(TPT), LargeOffsetGEP(LargeOffsetGEP) {
2585 IgnoreProfitability = false;
2586 }
2587
2588public:
2589 /// Find the maximal addressing mode that a load/store of V can fold,
2590 /// give an access type of AccessTy. This returns a list of involved
2591 /// instructions in AddrModeInsts.
2592 /// \p InsertedInsts The instructions inserted by other CodeGenPrepare
2593 /// optimizations.
2594 /// \p PromotedInsts maps the instructions to their type before promotion.
2595 /// \p The ongoing transaction where every action should be registered.
2596 static ExtAddrMode
2597 Match(Value *V, Type *AccessTy, unsigned AS, Instruction *MemoryInst,
2598 SmallVectorImpl<Instruction *> &AddrModeInsts,
2599 const TargetLowering &TLI, const TargetRegisterInfo &TRI,
2600 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
2601 TypePromotionTransaction &TPT,
2602 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP) {
2603 ExtAddrMode Result;
2604
2605 bool Success = AddressingModeMatcher(AddrModeInsts, TLI, TRI, AccessTy, AS,
2606 MemoryInst, Result, InsertedInsts,
2607 PromotedInsts, TPT, LargeOffsetGEP)
2608 .matchAddr(V, 0);
2609 (void)Success; assert(Success && "Couldn't select *anything*?")(static_cast <bool> (Success && "Couldn't select *anything*?"
) ? void (0) : __assert_fail ("Success && \"Couldn't select *anything*?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 2609, __extension__ __PRETTY_FUNCTION__))
;
2610 return Result;
2611 }
2612
2613private:
2614 bool matchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
2615 bool matchAddr(Value *Addr, unsigned Depth);
2616 bool matchOperationAddr(User *AddrInst, unsigned Opcode, unsigned Depth,
2617 bool *MovedAway = nullptr);
2618 bool isProfitableToFoldIntoAddressingMode(Instruction *I,
2619 ExtAddrMode &AMBefore,
2620 ExtAddrMode &AMAfter);
2621 bool valueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
2622 bool isPromotionProfitable(unsigned NewCost, unsigned OldCost,
2623 Value *PromotedOperand) const;
2624};
2625
2626/// Keep track of simplification of Phi nodes.
2627/// Accept the set of all phi nodes and erase phi node from this set
2628/// if it is simplified.
2629class SimplificationTracker {
2630 DenseMap<Value *, Value *> Storage;
2631 const SimplifyQuery &SQ;
2632 // Tracks newly created Phi nodes. We use a SetVector to get deterministic
2633 // order when iterating over the set in MatchPhiSet.
2634 SmallSetVector<PHINode *, 32> AllPhiNodes;
2635 // Tracks newly created Select nodes.
2636 SmallPtrSet<SelectInst *, 32> AllSelectNodes;
2637
2638public:
2639 SimplificationTracker(const SimplifyQuery &sq)
2640 : SQ(sq) {}
2641
2642 Value *Get(Value *V) {
2643 do {
2644 auto SV = Storage.find(V);
2645 if (SV == Storage.end())
2646 return V;
2647 V = SV->second;
2648 } while (true);
2649 }
2650
2651 Value *Simplify(Value *Val) {
2652 SmallVector<Value *, 32> WorkList;
2653 SmallPtrSet<Value *, 32> Visited;
2654 WorkList.push_back(Val);
2655 while (!WorkList.empty()) {
2656 auto P = WorkList.pop_back_val();
2657 if (!Visited.insert(P).second)
2658 continue;
2659 if (auto *PI = dyn_cast<Instruction>(P))
2660 if (Value *V = SimplifyInstruction(cast<Instruction>(PI), SQ)) {
2661 for (auto *U : PI->users())
2662 WorkList.push_back(cast<Value>(U));
2663 Put(PI, V);
2664 PI->replaceAllUsesWith(V);
2665 if (auto *PHI = dyn_cast<PHINode>(PI))
2666 AllPhiNodes.remove(PHI);
2667 if (auto *Select = dyn_cast<SelectInst>(PI))
2668 AllSelectNodes.erase(Select);
2669 PI->eraseFromParent();
2670 }
2671 }
2672 return Get(Val);
2673 }
2674
2675 void Put(Value *From, Value *To) {
2676 Storage.insert({ From, To });
2677 }
2678
2679 void ReplacePhi(PHINode *From, PHINode *To) {
2680 Value* OldReplacement = Get(From);
2681 while (OldReplacement != From) {
2682 From = To;
2683 To = dyn_cast<PHINode>(OldReplacement);
2684 OldReplacement = Get(From);
2685 }
2686 assert(Get(To) == To && "Replacement PHI node is already replaced.")(static_cast <bool> (Get(To) == To && "Replacement PHI node is already replaced."
) ? void (0) : __assert_fail ("Get(To) == To && \"Replacement PHI node is already replaced.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 2686, __extension__ __PRETTY_FUNCTION__))
;
2687 Put(From, To);
2688 From->replaceAllUsesWith(To);
2689 AllPhiNodes.remove(From);
2690 From->eraseFromParent();
2691 }
2692
2693 SmallSetVector<PHINode *, 32>& newPhiNodes() { return AllPhiNodes; }
2694
2695 void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); }
2696
2697 void insertNewSelect(SelectInst *SI) { AllSelectNodes.insert(SI); }
2698
2699 unsigned countNewPhiNodes() const { return AllPhiNodes.size(); }
2700
2701 unsigned countNewSelectNodes() const { return AllSelectNodes.size(); }
2702
2703 void destroyNewNodes(Type *CommonType) {
2704 // For safe erasing, replace the uses with dummy value first.
2705 auto Dummy = UndefValue::get(CommonType);
2706 for (auto I : AllPhiNodes) {
2707 I->replaceAllUsesWith(Dummy);
2708 I->eraseFromParent();
2709 }
2710 AllPhiNodes.clear();
2711 for (auto I : AllSelectNodes) {
2712 I->replaceAllUsesWith(Dummy);
2713 I->eraseFromParent();
2714 }
2715 AllSelectNodes.clear();
2716 }
2717};
2718
2719/// A helper class for combining addressing modes.
2720class AddressingModeCombiner {
2721 typedef std::pair<Value *, BasicBlock *> ValueInBB;
2722 typedef DenseMap<ValueInBB, Value *> FoldAddrToValueMapping;
2723 typedef std::pair<PHINode *, PHINode *> PHIPair;
2724
2725private:
2726 /// The addressing modes we've collected.
2727 SmallVector<ExtAddrMode, 16> AddrModes;
2728
2729 /// The field in which the AddrModes differ, when we have more than one.
2730 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
2731
2732 /// Are the AddrModes that we have all just equal to their original values?
2733 bool AllAddrModesTrivial = true;
2734
2735 /// Common Type for all different fields in addressing modes.
2736 Type *CommonType;
2737
2738 /// SimplifyQuery for simplifyInstruction utility.
2739 const SimplifyQuery &SQ;
2740
2741 /// Original Address.
2742 ValueInBB Original;
2743
2744public:
2745 AddressingModeCombiner(const SimplifyQuery &_SQ, ValueInBB OriginalValue)
2746 : CommonType(nullptr), SQ(_SQ), Original(OriginalValue) {}
2747
2748 /// Get the combined AddrMode
2749 const ExtAddrMode &getAddrMode() const {
2750 return AddrModes[0];
2751 }
2752
2753 /// Add a new AddrMode if it's compatible with the AddrModes we already
2754 /// have.
2755 /// \return True iff we succeeded in doing so.
2756 bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
2757 // Take note of if we have any non-trivial AddrModes, as we need to detect
2758 // when all AddrModes are trivial as then we would introduce a phi or select
2759 // which just duplicates what's already there.
2760 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
2761
2762 // If this is the first addrmode then everything is fine.
2763 if (AddrModes.empty()) {
2764 AddrModes.emplace_back(NewAddrMode);
2765 return true;
2766 }
2767
2768 // Figure out how different this is from the other address modes, which we
2769 // can do just by comparing against the first one given that we only care
2770 // about the cumulative difference.
2771 ExtAddrMode::FieldName ThisDifferentField =
2772 AddrModes[0].compare(NewAddrMode);
2773 if (DifferentField == ExtAddrMode::NoField)
2774 DifferentField = ThisDifferentField;
2775 else if (DifferentField != ThisDifferentField)
2776 DifferentField = ExtAddrMode::MultipleFields;
2777
2778 // If NewAddrMode differs in more than one dimension we cannot handle it.
2779 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
2780
2781 // If Scale Field is different then we reject.
2782 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
2783
2784 // We also must reject the case when base offset is different and
2785 // scale reg is not null, we cannot handle this case due to merge of
2786 // different offsets will be used as ScaleReg.
2787 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
2788 !NewAddrMode.ScaledReg);
2789
2790 // We also must reject the case when GV is different and BaseReg installed
2791 // due to we want to use base reg as a merge of GV values.
2792 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
2793 !NewAddrMode.HasBaseReg);
2794
2795 // Even if NewAddMode is the same we still need to collect it due to
2796 // original value is different. And later we will need all original values
2797 // as anchors during finding the common Phi node.
2798 if (CanHandle)
2799 AddrModes.emplace_back(NewAddrMode);
2800 else
2801 AddrModes.clear();
2802
2803 return CanHandle;
2804 }
2805
2806 /// Combine the addressing modes we've collected into a single
2807 /// addressing mode.
2808 /// \return True iff we successfully combined them or we only had one so
2809 /// didn't need to combine them anyway.
2810 bool combineAddrModes() {
2811 // If we have no AddrModes then they can't be combined.
2812 if (AddrModes.size() == 0)
2813 return false;
2814
2815 // A single AddrMode can trivially be combined.
2816 if (AddrModes.size() == 1 || DifferentField == ExtAddrMode::NoField)
2817 return true;
2818
2819 // If the AddrModes we collected are all just equal to the value they are
2820 // derived from then combining them wouldn't do anything useful.
2821 if (AllAddrModesTrivial)
2822 return false;
2823
2824 if (!addrModeCombiningAllowed())
2825 return false;
2826
2827 // Build a map between <original value, basic block where we saw it> to
2828 // value of base register.
2829 // Bail out if there is no common type.
2830 FoldAddrToValueMapping Map;
2831 if (!initializeMap(Map))
2832 return false;
2833
2834 Value *CommonValue = findCommon(Map);
2835 if (CommonValue)
2836 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
2837 return CommonValue != nullptr;
2838 }
2839
2840private:
2841 /// Initialize Map with anchor values. For address seen in some BB
2842 /// we set the value of different field saw in this address.
2843 /// If address is not an instruction than basic block is set to null.
2844 /// At the same time we find a common type for different field we will
2845 /// use to create new Phi/Select nodes. Keep it in CommonType field.
2846 /// Return false if there is no common type found.
2847 bool initializeMap(FoldAddrToValueMapping &Map) {
2848 // Keep track of keys where the value is null. We will need to replace it
2849 // with constant null when we know the common type.
2850 SmallVector<ValueInBB, 2> NullValue;
2851 Type *IntPtrTy = SQ.DL.getIntPtrType(AddrModes[0].OriginalValue->getType());
2852 for (auto &AM : AddrModes) {
2853 BasicBlock *BB = nullptr;
2854 if (Instruction *I = dyn_cast<Instruction>(AM.OriginalValue))
2855 BB = I->getParent();
2856
2857 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
2858 if (DV) {
2859 auto *Type = DV->getType();
2860 if (CommonType && CommonType != Type)
2861 return false;
2862 CommonType = Type;
2863 Map[{ AM.OriginalValue, BB }] = DV;
2864 } else {
2865 NullValue.push_back({ AM.OriginalValue, BB });
2866 }
2867 }
2868 assert(CommonType && "At least one non-null value must be!")(static_cast <bool> (CommonType && "At least one non-null value must be!"
) ? void (0) : __assert_fail ("CommonType && \"At least one non-null value must be!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 2868, __extension__ __PRETTY_FUNCTION__))
;
2869 for (auto VIBB : NullValue)
2870 Map[VIBB] = Constant::getNullValue(CommonType);
2871 return true;
2872 }
2873
2874 /// We have mapping between value A and basic block where value A
2875 /// seen to other value B where B was a field in addressing mode represented
2876 /// by A. Also we have an original value C representing an address in some
2877 /// basic block. Traversing from C through phi and selects we ended up with
2878 /// A's in a map. This utility function tries to find a value V which is a
2879 /// field in addressing mode C and traversing through phi nodes and selects
2880 /// we will end up in corresponded values B in a map.
2881 /// The utility will create a new Phi/Selects if needed.
2882 // The simple example looks as follows:
2883 // BB1:
2884 // p1 = b1 + 40
2885 // br cond BB2, BB3
2886 // BB2:
2887 // p2 = b2 + 40
2888 // br BB3
2889 // BB3:
2890 // p = phi [p1, BB1], [p2, BB2]
2891 // v = load p
2892 // Map is
2893 // <p1, BB1> -> b1
2894 // <p2, BB2> -> b2
2895 // Request is
2896 // <p, BB3> -> ?
2897 // The function tries to find or build phi [b1, BB1], [b2, BB2] in BB3
2898 Value *findCommon(FoldAddrToValueMapping &Map) {
2899 // Tracks the simplification of newly created phi nodes. The reason we use
2900 // this mapping is because we will add new created Phi nodes in AddrToBase.
2901 // Simplification of Phi nodes is recursive, so some Phi node may
2902 // be simplified after we added it to AddrToBase.
2903 // Using this mapping we can find the current value in AddrToBase.
2904 SimplificationTracker ST(SQ);
2905
2906 // First step, DFS to create PHI nodes for all intermediate blocks.
2907 // Also fill traverse order for the second step.
2908 SmallVector<ValueInBB, 32> TraverseOrder;
2909 InsertPlaceholders(Map, TraverseOrder, ST);
2910
2911 // Second Step, fill new nodes by merged values and simplify if possible.
2912 FillPlaceholders(Map, TraverseOrder, ST);
2913
2914 if (!AddrSinkNewSelects && ST.countNewSelectNodes() > 0) {
2915 ST.destroyNewNodes(CommonType);
2916 return nullptr;
2917 }
2918
2919 // Now we'd like to match New Phi nodes to existed ones.
2920 unsigned PhiNotMatchedCount = 0;
2921 if (!MatchPhiSet(ST, AddrSinkNewPhis, PhiNotMatchedCount)) {
2922 ST.destroyNewNodes(CommonType);
2923 return nullptr;
2924 }
2925
2926 auto *Result = ST.Get(Map.find(Original)->second);
2927 if (Result) {
2928 NumMemoryInstsPhiCreated += ST.countNewPhiNodes() + PhiNotMatchedCount;
2929 NumMemoryInstsSelectCreated += ST.countNewSelectNodes();
2930 }
2931 return Result;
2932 }
2933
2934 /// Try to match PHI node to Candidate.
2935 /// Matcher tracks the matched Phi nodes.
2936 bool MatchPhiNode(PHINode *PHI, PHINode *Candidate,
2937 SmallSetVector<PHIPair, 8> &Matcher,
2938 SmallSetVector<PHINode *, 32> &PhiNodesToMatch) {
2939 SmallVector<PHIPair, 8> WorkList;
2940 Matcher.insert({ PHI, Candidate });
2941 WorkList.push_back({ PHI, Candidate });
2942 SmallSet<PHIPair, 8> Visited;
2943 while (!WorkList.empty()) {
2944 auto Item = WorkList.pop_back_val();
2945 if (!Visited.insert(Item).second)
2946 continue;
2947 // We iterate over all incoming values to Phi to compare them.
2948 // If values are different and both of them Phi and the first one is a
2949 // Phi we added (subject to match) and both of them is in the same basic
2950 // block then we can match our pair if values match. So we state that
2951 // these values match and add it to work list to verify that.
2952 for (auto B : Item.first->blocks()) {
2953 Value *FirstValue = Item.first->getIncomingValueForBlock(B);
2954 Value *SecondValue = Item.second->getIncomingValueForBlock(B);
2955 if (FirstValue == SecondValue)
2956 continue;
2957
2958 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
2959 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
2960
2961 // One of them is not Phi or
2962 // The first one is not Phi node from the set we'd like to match or
2963 // Phi nodes from different basic blocks then
2964 // we will not be able to match.
2965 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
2966 FirstPhi->getParent() != SecondPhi->getParent())
2967 return false;
2968
2969 // If we already matched them then continue.
2970 if (Matcher.count({ FirstPhi, SecondPhi }))
2971 continue;
2972 // So the values are different and does not match. So we need them to
2973 // match.
2974 Matcher.insert({ FirstPhi, SecondPhi });
2975 // But me must check it.
2976 WorkList.push_back({ FirstPhi, SecondPhi });
2977 }
2978 }
2979 return true;
2980 }
2981
2982 /// For the given set of PHI nodes (in the SimplificationTracker) try
2983 /// to find their equivalents.
2984 /// Returns false if this matching fails and creation of new Phi is disabled.
2985 bool MatchPhiSet(SimplificationTracker &ST, bool AllowNewPhiNodes,
2986 unsigned &PhiNotMatchedCount) {
2987 // Use a SetVector for Matched to make sure we do replacements (ReplacePhi)
2988 // in a deterministic order below.
2989 SmallSetVector<PHIPair, 8> Matched;
2990 SmallPtrSet<PHINode *, 8> WillNotMatch;
2991 SmallSetVector<PHINode *, 32> &PhiNodesToMatch = ST.newPhiNodes();
2992 while (PhiNodesToMatch.size()) {
2993 PHINode *PHI = *PhiNodesToMatch.begin();
2994
2995 // Add us, if no Phi nodes in the basic block we do not match.
2996 WillNotMatch.clear();
2997 WillNotMatch.insert(PHI);
2998
2999 // Traverse all Phis until we found equivalent or fail to do that.
3000 bool IsMatched = false;
3001 for (auto &P : PHI->getParent()->phis()) {
3002 if (&P == PHI)
3003 continue;
3004 if ((IsMatched = MatchPhiNode(PHI, &P, Matched, PhiNodesToMatch)))
3005 break;
3006 // If it does not match, collect all Phi nodes from matcher.
3007 // if we end up with no match, them all these Phi nodes will not match
3008 // later.
3009 for (auto M : Matched)
3010 WillNotMatch.insert(M.first);
3011 Matched.clear();
3012 }
3013 if (IsMatched) {
3014 // Replace all matched values and erase them.
3015 for (auto MV : Matched)
3016 ST.ReplacePhi(MV.first, MV.second);
3017 Matched.clear();
3018 continue;
3019 }
3020 // If we are not allowed to create new nodes then bail out.
3021 if (!AllowNewPhiNodes)
3022 return false;
3023 // Just remove all seen values in matcher. They will not match anything.
3024 PhiNotMatchedCount += WillNotMatch.size();
3025 for (auto *P : WillNotMatch)
3026 PhiNodesToMatch.remove(P);
3027 }
3028 return true;
3029 }
3030 /// Fill the placeholder with values from predecessors and simplify it.
3031 void FillPlaceholders(FoldAddrToValueMapping &Map,
3032 SmallVectorImpl<ValueInBB> &TraverseOrder,
3033 SimplificationTracker &ST) {
3034 while (!TraverseOrder.empty()) {
3035 auto Current = TraverseOrder.pop_back_val();
3036 assert(Map.find(Current) != Map.end() && "No node to fill!!!")(static_cast <bool> (Map.find(Current) != Map.end() &&
"No node to fill!!!") ? void (0) : __assert_fail ("Map.find(Current) != Map.end() && \"No node to fill!!!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3036, __extension__ __PRETTY_FUNCTION__))
;
3037 Value *CurrentValue = Current.first;
3038 BasicBlock *CurrentBlock = Current.second;
3039 Value *V = Map[Current];
3040
3041 if (SelectInst *Select = dyn_cast<SelectInst>(V)) {
3042 // CurrentValue also must be Select.
3043 auto *CurrentSelect = cast<SelectInst>(CurrentValue);
3044 auto *TrueValue = CurrentSelect->getTrueValue();
3045 ValueInBB TrueItem = { TrueValue, isa<Instruction>(TrueValue)
3046 ? CurrentBlock
3047 : nullptr };
3048 assert(Map.find(TrueItem) != Map.end() && "No True Value!")(static_cast <bool> (Map.find(TrueItem) != Map.end() &&
"No True Value!") ? void (0) : __assert_fail ("Map.find(TrueItem) != Map.end() && \"No True Value!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3048, __extension__ __PRETTY_FUNCTION__))
;
3049 Select->setTrueValue(ST.Get(Map[TrueItem]));
3050 auto *FalseValue = CurrentSelect->getFalseValue();
3051 ValueInBB FalseItem = { FalseValue, isa<Instruction>(FalseValue)
3052 ? CurrentBlock
3053 : nullptr };
3054 assert(Map.find(FalseItem) != Map.end() && "No False Value!")(static_cast <bool> (Map.find(FalseItem) != Map.end() &&
"No False Value!") ? void (0) : __assert_fail ("Map.find(FalseItem) != Map.end() && \"No False Value!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3054, __extension__ __PRETTY_FUNCTION__))
;
3055 Select->setFalseValue(ST.Get(Map[FalseItem]));
3056 } else {
3057 // Must be a Phi node then.
3058 PHINode *PHI = cast<PHINode>(V);
3059 // Fill the Phi node with values from predecessors.
3060 bool IsDefinedInThisBB =
3061 cast<Instruction>(CurrentValue)->getParent() == CurrentBlock;
3062 auto *CurrentPhi = dyn_cast<PHINode>(CurrentValue);
3063 for (auto B : predecessors(CurrentBlock)) {
3064 Value *PV = IsDefinedInThisBB
3065 ? CurrentPhi->getIncomingValueForBlock(B)
3066 : CurrentValue;
3067 ValueInBB item = { PV, isa<Instruction>(PV) ? B : nullptr };
3068 assert(Map.find(item) != Map.end() && "No predecessor Value!")(static_cast <bool> (Map.find(item) != Map.end() &&
"No predecessor Value!") ? void (0) : __assert_fail ("Map.find(item) != Map.end() && \"No predecessor Value!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3068, __extension__ __PRETTY_FUNCTION__))
;
3069 PHI->addIncoming(ST.Get(Map[item]), B);
3070 }
3071 }
3072 // Simplify if possible.
3073 Map[Current] = ST.Simplify(V);
3074 }
3075 }
3076
3077 /// Starting from value recursively iterates over predecessors up to known
3078 /// ending values represented in a map. For each traversed block inserts
3079 /// a placeholder Phi or Select.
3080 /// Reports all new created Phi/Select nodes by adding them to set.
3081 /// Also reports and order in what basic blocks have been traversed.
3082 void InsertPlaceholders(FoldAddrToValueMapping &Map,
3083 SmallVectorImpl<ValueInBB> &TraverseOrder,
3084 SimplificationTracker &ST) {
3085 SmallVector<ValueInBB, 32> Worklist;
3086 assert((isa<PHINode>(Original.first) || isa<SelectInst>(Original.first)) &&(static_cast <bool> ((isa<PHINode>(Original.first
) || isa<SelectInst>(Original.first)) && "Address must be a Phi or Select node"
) ? void (0) : __assert_fail ("(isa<PHINode>(Original.first) || isa<SelectInst>(Original.first)) && \"Address must be a Phi or Select node\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3087, __extension__ __PRETTY_FUNCTION__))
3087 "Address must be a Phi or Select node")(static_cast <bool> ((isa<PHINode>(Original.first
) || isa<SelectInst>(Original.first)) && "Address must be a Phi or Select node"
) ? void (0) : __assert_fail ("(isa<PHINode>(Original.first) || isa<SelectInst>(Original.first)) && \"Address must be a Phi or Select node\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3087, __extension__ __PRETTY_FUNCTION__))
;
3088 auto *Dummy = UndefValue::get(CommonType);
3089 Worklist.push_back(Original);
3090 while (!Worklist.empty()) {
3091 auto Current = Worklist.pop_back_val();
3092 // If value is not an instruction it is something global, constant,
3093 // parameter and we can say that this value is observable in any block.
3094 // Set block to null to denote it.
3095 // Also please take into account that it is how we build anchors.
3096 if (!isa<Instruction>(Current.first))
3097 Current.second = nullptr;
3098 // if it is already visited or it is an ending value then skip it.
3099 if (Map.find(Current) != Map.end())
3100 continue;
3101 TraverseOrder.push_back(Current);
3102
3103 Value *CurrentValue = Current.first;
3104 BasicBlock *CurrentBlock = Current.second;
3105 // CurrentValue must be a Phi node or select. All others must be covered
3106 // by anchors.
3107 Instruction *CurrentI = cast<Instruction>(CurrentValue);
3108 bool IsDefinedInThisBB = CurrentI->getParent() == CurrentBlock;
3109
3110 unsigned PredCount = pred_size(CurrentBlock);
3111 // if Current Value is not defined in this basic block we are interested
3112 // in values in predecessors.
3113 if (!IsDefinedInThisBB) {
3114 assert(PredCount && "Unreachable block?!")(static_cast <bool> (PredCount && "Unreachable block?!"
) ? void (0) : __assert_fail ("PredCount && \"Unreachable block?!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3114, __extension__ __PRETTY_FUNCTION__))
;
3115 PHINode *PHI = PHINode::Create(CommonType, PredCount, "sunk_phi",
3116 &CurrentBlock->front());
3117 Map[Current] = PHI;
3118 ST.insertNewPhi(PHI);
3119 // Add all predecessors in work list.
3120 for (auto B : predecessors(CurrentBlock))
3121 Worklist.push_back({ CurrentValue, B });
3122 continue;
3123 }
3124 // Value is defined in this basic block.
3125 if (SelectInst *OrigSelect = dyn_cast<SelectInst>(CurrentI)) {
3126 // Is it OK to get metadata from OrigSelect?!
3127 // Create a Select placeholder with dummy value.
3128 SelectInst *Select =
3129 SelectInst::Create(OrigSelect->getCondition(), Dummy, Dummy,
3130 OrigSelect->getName(), OrigSelect, OrigSelect);
3131 Map[Current] = Select;
3132 ST.insertNewSelect(Select);
3133 // We are interested in True and False value in this basic block.
3134 Worklist.push_back({ OrigSelect->getTrueValue(), CurrentBlock });
3135 Worklist.push_back({ OrigSelect->getFalseValue(), CurrentBlock });
3136 } else {
3137 // It must be a Phi node then.
3138 auto *CurrentPhi = cast<PHINode>(CurrentI);
3139 // Create new Phi node for merge of bases.
3140 assert(PredCount && "Unreachable block?!")(static_cast <bool> (PredCount && "Unreachable block?!"
) ? void (0) : __assert_fail ("PredCount && \"Unreachable block?!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3140, __extension__ __PRETTY_FUNCTION__))
;
3141 PHINode *PHI = PHINode::Create(CommonType, PredCount, "sunk_phi",
3142 &CurrentBlock->front());
3143 Map[Current] = PHI;
3144 ST.insertNewPhi(PHI);
3145
3146 // Add all predecessors in work list.
3147 for (auto B : predecessors(CurrentBlock))
3148 Worklist.push_back({ CurrentPhi->getIncomingValueForBlock(B), B });
3149 }
3150 }
3151 }
3152
3153 bool addrModeCombiningAllowed() {
3154 if (DisableComplexAddrModes)
3155 return false;
3156 switch (DifferentField) {
3157 default:
3158 return false;
3159 case ExtAddrMode::BaseRegField:
3160 return AddrSinkCombineBaseReg;
3161 case ExtAddrMode::BaseGVField:
3162 return AddrSinkCombineBaseGV;
3163 case ExtAddrMode::BaseOffsField:
3164 return AddrSinkCombineBaseOffs;
3165 case ExtAddrMode::ScaledRegField:
3166 return AddrSinkCombineScaledReg;
3167 }
3168 }
3169};
3170} // end anonymous namespace
3171
3172/// Try adding ScaleReg*Scale to the current addressing mode.
3173/// Return true and update AddrMode if this addr mode is legal for the target,
3174/// false if not.
3175bool AddressingModeMatcher::matchScaledValue(Value *ScaleReg, int64_t Scale,
3176 unsigned Depth) {
3177 // If Scale is 1, then this is the same as adding ScaleReg to the addressing
3178 // mode. Just process that directly.
3179 if (Scale == 1)
3180 return matchAddr(ScaleReg, Depth);
3181
3182 // If the scale is 0, it takes nothing to add this.
3183 if (Scale == 0)
3184 return true;
3185
3186 // If we already have a scale of this value, we can add to it, otherwise, we
3187 // need an available scale field.
3188 if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
3189 return false;
3190
3191 ExtAddrMode TestAddrMode = AddrMode;
3192
3193 // Add scale to turn X*4+X*3 -> X*7. This could also do things like
3194 // [A+B + A*7] -> [B+A*8].
3195 TestAddrMode.Scale += Scale;
3196 TestAddrMode.ScaledReg = ScaleReg;
3197
3198 // If the new address isn't legal, bail out.
3199 if (!TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace))
3200 return false;
3201
3202 // It was legal, so commit it.
3203 AddrMode = TestAddrMode;
3204
3205 // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now
3206 // to see if ScaleReg is actually X+C. If so, we can turn this into adding
3207 // X*Scale + C*Scale to addr mode.
3208 ConstantInt *CI = nullptr; Value *AddLHS = nullptr;
3209 if (isa<Instruction>(ScaleReg) && // not a constant expr.
3210 match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
3211 TestAddrMode.ScaledReg = AddLHS;
3212 TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
3213
3214 // If this addressing mode is legal, commit it and remember that we folded
3215 // this instruction.
3216 if (TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) {
3217 AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
3218 AddrMode = TestAddrMode;
3219 return true;
3220 }
3221 }
3222
3223 // Otherwise, not (x+c)*scale, just return what we have.
3224 return true;
3225}
3226
3227/// This is a little filter, which returns true if an addressing computation
3228/// involving I might be folded into a load/store accessing it.
3229/// This doesn't need to be perfect, but needs to accept at least
3230/// the set of instructions that MatchOperationAddr can.
3231static bool MightBeFoldableInst(Instruction *I) {
3232 switch (I->getOpcode()) {
3233 case Instruction::BitCast:
3234 case Instruction::AddrSpaceCast:
3235 // Don't touch identity bitcasts.
3236 if (I->getType() == I->getOperand(0)->getType())
3237 return false;
3238 return I->getType()->isIntOrPtrTy();
3239 case Instruction::PtrToInt:
3240 // PtrToInt is always a noop, as we know that the int type is pointer sized.
3241 return true;
3242 case Instruction::IntToPtr:
3243 // We know the input is intptr_t, so this is foldable.
3244 return true;
3245 case Instruction::Add:
3246 return true;
3247 case Instruction::Mul:
3248 case Instruction::Shl:
3249 // Can only handle X*C and X << C.
3250 return isa<ConstantInt>(I->getOperand(1));
3251 case Instruction::GetElementPtr:
3252 return true;
3253 default:
3254 return false;
3255 }
3256}
3257
3258/// Check whether or not \p Val is a legal instruction for \p TLI.
3259/// \note \p Val is assumed to be the product of some type promotion.
3260/// Therefore if \p Val has an undefined state in \p TLI, this is assumed
3261/// to be legal, as the non-promoted value would have had the same state.
3262static bool isPromotedInstructionLegal(const TargetLowering &TLI,
3263 const DataLayout &DL, Value *Val) {
3264 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
3265 if (!PromotedInst)
3266 return false;
3267 int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
3268 // If the ISDOpcode is undefined, it was undefined before the promotion.
3269 if (!ISDOpcode)
3270 return true;
3271 // Otherwise, check if the promoted instruction is legal or not.
3272 return TLI.isOperationLegalOrCustom(
3273 ISDOpcode, TLI.getValueType(DL, PromotedInst->getType()));
3274}
3275
3276namespace {
3277
3278/// Hepler class to perform type promotion.
3279class TypePromotionHelper {
3280 /// Utility function to check whether or not a sign or zero extension
3281 /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by
3282 /// either using the operands of \p Inst or promoting \p Inst.
3283 /// The type of the extension is defined by \p IsSExt.
3284 /// In other words, check if:
3285 /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType.
3286 /// #1 Promotion applies:
3287 /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...).
3288 /// #2 Operand reuses:
3289 /// ext opnd1 to ConsideredExtType.
3290 /// \p PromotedInsts maps the instructions to their type before promotion.
3291 static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType,
3292 const InstrToOrigTy &PromotedInsts, bool IsSExt);
3293
3294 /// Utility function to determine if \p OpIdx should be promoted when
3295 /// promoting \p Inst.
3296 static bool shouldExtOperand(const Instruction *Inst, int OpIdx) {
3297 return !(isa<SelectInst>(Inst) && OpIdx == 0);
3298 }
3299
3300 /// Utility function to promote the operand of \p Ext when this
3301 /// operand is a promotable trunc or sext or zext.
3302 /// \p PromotedInsts maps the instructions to their type before promotion.
3303 /// \p CreatedInstsCost[out] contains the cost of all instructions
3304 /// created to promote the operand of Ext.
3305 /// Newly added extensions are inserted in \p Exts.
3306 /// Newly added truncates are inserted in \p Truncs.
3307 /// Should never be called directly.
3308 /// \return The promoted value which is used instead of Ext.
3309 static Value *promoteOperandForTruncAndAnyExt(
3310 Instruction *Ext, TypePromotionTransaction &TPT,
3311 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3312 SmallVectorImpl<Instruction *> *Exts,
3313 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI);
3314
3315 /// Utility function to promote the operand of \p Ext when this
3316 /// operand is promotable and is not a supported trunc or sext.
3317 /// \p PromotedInsts maps the instructions to their type before promotion.
3318 /// \p CreatedInstsCost[out] contains the cost of all the instructions
3319 /// created to promote the operand of Ext.
3320 /// Newly added extensions are inserted in \p Exts.
3321 /// Newly added truncates are inserted in \p Truncs.
3322 /// Should never be called directly.
3323 /// \return The promoted value which is used instead of Ext.
3324 static Value *promoteOperandForOther(Instruction *Ext,
3325 TypePromotionTransaction &TPT,
3326 InstrToOrigTy &PromotedInsts,
3327 unsigned &CreatedInstsCost,
3328 SmallVectorImpl<Instruction *> *Exts,
3329 SmallVectorImpl<Instruction *> *Truncs,
3330 const TargetLowering &TLI, bool IsSExt);
3331
3332 /// \see promoteOperandForOther.
3333 static Value *signExtendOperandForOther(
3334 Instruction *Ext, TypePromotionTransaction &TPT,
3335 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3336 SmallVectorImpl<Instruction *> *Exts,
3337 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
3338 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
3339 Exts, Truncs, TLI, true);
3340 }
3341
3342 /// \see promoteOperandForOther.
3343 static Value *zeroExtendOperandForOther(
3344 Instruction *Ext, TypePromotionTransaction &TPT,
3345 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3346 SmallVectorImpl<Instruction *> *Exts,
3347 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
3348 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
3349 Exts, Truncs, TLI, false);
3350 }
3351
3352public:
3353 /// Type for the utility function that promotes the operand of Ext.
3354 using Action = Value *(*)(Instruction *Ext, TypePromotionTransaction &TPT,
3355 InstrToOrigTy &PromotedInsts,
3356 unsigned &CreatedInstsCost,
3357 SmallVectorImpl<Instruction *> *Exts,
3358 SmallVectorImpl<Instruction *> *Truncs,
3359 const TargetLowering &TLI);
3360
3361 /// Given a sign/zero extend instruction \p Ext, return the appropriate
3362 /// action to promote the operand of \p Ext instead of using Ext.
3363 /// \return NULL if no promotable action is possible with the current
3364 /// sign extension.
3365 /// \p InsertedInsts keeps track of all the instructions inserted by the
3366 /// other CodeGenPrepare optimizations. This information is important
3367 /// because we do not want to promote these instructions as CodeGenPrepare
3368 /// will reinsert them later. Thus creating an infinite loop: create/remove.
3369 /// \p PromotedInsts maps the instructions to their type before promotion.
3370 static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedInsts,
3371 const TargetLowering &TLI,
3372 const InstrToOrigTy &PromotedInsts);
3373};
3374
3375} // end anonymous namespace
3376
3377bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
3378 Type *ConsideredExtType,
3379 const InstrToOrigTy &PromotedInsts,
3380 bool IsSExt) {
3381 // The promotion helper does not know how to deal with vector types yet.
3382 // To be able to fix that, we would need to fix the places where we
3383 // statically extend, e.g., constants and such.
3384 if (Inst->getType()->isVectorTy())
3385 return false;
3386
3387 // We can always get through zext.
3388 if (isa<ZExtInst>(Inst))
3389 return true;
3390
3391 // sext(sext) is ok too.
3392 if (IsSExt && isa<SExtInst>(Inst))
3393 return true;
3394
3395 // We can get through binary operator, if it is legal. In other words, the
3396 // binary operator must have a nuw or nsw flag.
3397 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
3398 if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
3399 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
3400 (IsSExt && BinOp->hasNoSignedWrap())))
3401 return true;
3402
3403 // ext(and(opnd, cst)) --> and(ext(opnd), ext(cst))
3404 if ((Inst->getOpcode() == Instruction::And ||
3405 Inst->getOpcode() == Instruction::Or))
3406 return true;
3407
3408 // ext(xor(opnd, cst)) --> xor(ext(opnd), ext(cst))
3409 if (Inst->getOpcode() == Instruction::Xor) {
3410 const ConstantInt *Cst = dyn_cast<ConstantInt>(Inst->getOperand(1));
3411 // Make sure it is not a NOT.
3412 if (Cst && !Cst->getValue().isAllOnesValue())
3413 return true;
3414 }
3415
3416 // zext(shrl(opnd, cst)) --> shrl(zext(opnd), zext(cst))
3417 // It may change a poisoned value into a regular value, like
3418 // zext i32 (shrl i8 %val, 12) --> shrl i32 (zext i8 %val), 12
3419 // poisoned value regular value
3420 // It should be OK since undef covers valid value.
3421 if (Inst->getOpcode() == Instruction::LShr && !IsSExt)
3422 return true;
3423
3424 // and(ext(shl(opnd, cst)), cst) --> and(shl(ext(opnd), ext(cst)), cst)
3425 // It may change a poisoned value into a regular value, like
3426 // zext i32 (shl i8 %val, 12) --> shl i32 (zext i8 %val), 12
3427 // poisoned value regular value
3428 // It should be OK since undef covers valid value.
3429 if (Inst->getOpcode() == Instruction::Shl && Inst->hasOneUse()) {
3430 const Instruction *ExtInst =
3431 dyn_cast<const Instruction>(*Inst->user_begin());
3432 if (ExtInst->hasOneUse()) {
3433 const Instruction *AndInst =
3434 dyn_cast<const Instruction>(*ExtInst->user_begin());
3435 if (AndInst && AndInst->getOpcode() == Instruction::And) {
3436 const ConstantInt *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
3437 if (Cst &&
3438 Cst->getValue().isIntN(Inst->getType()->getIntegerBitWidth()))
3439 return true;
3440 }
3441 }
3442 }
3443
3444 // Check if we can do the following simplification.
3445 // ext(trunc(opnd)) --> ext(opnd)
3446 if (!isa<TruncInst>(Inst))
3447 return false;
3448
3449 Value *OpndVal = Inst->getOperand(0);
3450 // Check if we can use this operand in the extension.
3451 // If the type is larger than the result type of the extension, we cannot.
3452 if (!OpndVal->getType()->isIntegerTy() ||
3453 OpndVal->getType()->getIntegerBitWidth() >
3454 ConsideredExtType->getIntegerBitWidth())
3455 return false;
3456
3457 // If the operand of the truncate is not an instruction, we will not have
3458 // any information on the dropped bits.
3459 // (Actually we could for constant but it is not worth the extra logic).
3460 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
3461 if (!Opnd)
3462 return false;
3463
3464 // Check if the source of the type is narrow enough.
3465 // I.e., check that trunc just drops extended bits of the same kind of
3466 // the extension.
3467 // #1 get the type of the operand and check the kind of the extended bits.
3468 const Type *OpndType;
3469 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
3470 if (It != PromotedInsts.end() && It->second.getInt() == IsSExt)
3471 OpndType = It->second.getPointer();
3472 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
3473 OpndType = Opnd->getOperand(0)->getType();
3474 else
3475 return false;
3476
3477 // #2 check that the truncate just drops extended bits.
3478 return Inst->getType()->getIntegerBitWidth() >=
3479 OpndType->getIntegerBitWidth();
3480}
3481
3482TypePromotionHelper::Action TypePromotionHelper::getAction(
3483 Instruction *Ext, const SetOfInstrs &InsertedInsts,
3484 const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
3485 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&(static_cast <bool> ((isa<SExtInst>(Ext) || isa<
ZExtInst>(Ext)) && "Unexpected instruction type") ?
void (0) : __assert_fail ("(isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) && \"Unexpected instruction type\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3486, __extension__ __PRETTY_FUNCTION__))
3486 "Unexpected instruction type")(static_cast <bool> ((isa<SExtInst>(Ext) || isa<
ZExtInst>(Ext)) && "Unexpected instruction type") ?
void (0) : __assert_fail ("(isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) && \"Unexpected instruction type\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3486, __extension__ __PRETTY_FUNCTION__))
;
3487 Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0));
3488 Type *ExtTy = Ext->getType();
3489 bool IsSExt = isa<SExtInst>(Ext);
3490 // If the operand of the extension is not an instruction, we cannot
3491 // get through.
3492 // If it, check we can get through.
3493 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
3494 return nullptr;
3495
3496 // Do not promote if the operand has been added by codegenprepare.
3497 // Otherwise, it means we are undoing an optimization that is likely to be
3498 // redone, thus causing potential infinite loop.
3499 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
3500 return nullptr;
3501
3502 // SExt or Trunc instructions.
3503 // Return the related handler.
3504 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
3505 isa<ZExtInst>(ExtOpnd))
3506 return promoteOperandForTruncAndAnyExt;
3507
3508 // Regular instruction.
3509 // Abort early if we will have to insert non-free instructions.
3510 if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
3511 return nullptr;
3512 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
3513}
3514
3515Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
3516 Instruction *SExt, TypePromotionTransaction &TPT,
3517 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3518 SmallVectorImpl<Instruction *> *Exts,
3519 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
3520 // By construction, the operand of SExt is an instruction. Otherwise we cannot
3521 // get through it and this method should not be called.
3522 Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
3523 Value *ExtVal = SExt;
3524 bool HasMergedNonFreeExt = false;
3525 if (isa<ZExtInst>(SExtOpnd)) {
3526 // Replace s|zext(zext(opnd))
3527 // => zext(opnd).
3528 HasMergedNonFreeExt = !TLI.isExtFree(SExtOpnd);
3529 Value *ZExt =
3530 TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType());
3531 TPT.replaceAllUsesWith(SExt, ZExt);
3532 TPT.eraseInstruction(SExt);
3533 ExtVal = ZExt;
3534 } else {
3535 // Replace z|sext(trunc(opnd)) or sext(sext(opnd))
3536 // => z|sext(opnd).
3537 TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
3538 }
3539 CreatedInstsCost = 0;
3540
3541 // Remove dead code.
3542 if (SExtOpnd->use_empty())
3543 TPT.eraseInstruction(SExtOpnd);
3544
3545 // Check if the extension is still needed.
3546 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
3547 if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) {
3548 if (ExtInst) {
3549 if (Exts)
3550 Exts->push_back(ExtInst);
3551 CreatedInstsCost = !TLI.isExtFree(ExtInst) && !HasMergedNonFreeExt;
3552 }
3553 return ExtVal;
3554 }
3555
3556 // At this point we have: ext ty opnd to ty.
3557 // Reassign the uses of ExtInst to the opnd and remove ExtInst.
3558 Value *NextVal = ExtInst->getOperand(0);
3559 TPT.eraseInstruction(ExtInst, NextVal);
3560 return NextVal;
3561}
3562
3563Value *TypePromotionHelper::promoteOperandForOther(
3564 Instruction *Ext, TypePromotionTransaction &TPT,
3565 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3566 SmallVectorImpl<Instruction *> *Exts,
3567 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI,
3568 bool IsSExt) {
3569 // By construction, the operand of Ext is an instruction. Otherwise we cannot
3570 // get through it and this method should not be called.
3571 Instruction *ExtOpnd = cast<Instruction>(Ext->getOperand(0));
3572 CreatedInstsCost = 0;
3573 if (!ExtOpnd->hasOneUse()) {
3574 // ExtOpnd will be promoted.
3575 // All its uses, but Ext, will need to use a truncated value of the
3576 // promoted version.
3577 // Create the truncate now.
3578 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType());
3579 if (Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
3580 // Insert it just after the definition.
3581 ITrunc->moveAfter(ExtOpnd);
3582 if (Truncs)
3583 Truncs->push_back(ITrunc);
3584 }
3585
3586 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
3587 // Restore the operand of Ext (which has been replaced by the previous call
3588 // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext.
3589 TPT.setOperand(Ext, 0, ExtOpnd);
3590 }
3591
3592 // Get through the Instruction:
3593 // 1. Update its type.
3594 // 2. Replace the uses of Ext by Inst.
3595 // 3. Extend each operand that needs to be extended.
3596
3597 // Remember the original type of the instruction before promotion.
3598 // This is useful to know that the high bits are sign extended bits.
3599 PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>(
3600 ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt)));
3601 // Step #1.
3602 TPT.mutateType(ExtOpnd, Ext->getType());
3603 // Step #2.
3604 TPT.replaceAllUsesWith(Ext, ExtOpnd);
3605 // Step #3.
3606 Instruction *ExtForOpnd = Ext;
3607
3608 LLVM_DEBUG(dbgs() << "Propagate Ext to operands\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Propagate Ext to operands\n"
; } } while (false)
;
3609 for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
3610 ++OpIdx) {
3611 LLVM_DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Operand:\n" << *
(ExtOpnd->getOperand(OpIdx)) << '\n'; } } while (false
)
;
3612 if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() ||
3613 !shouldExtOperand(ExtOpnd, OpIdx)) {
3614 LLVM_DEBUG(dbgs() << "No need to propagate\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "No need to propagate\n"
; } } while (false)
;
3615 continue;
3616 }
3617 // Check if we can statically extend the operand.
3618 Value *Opnd = ExtOpnd->getOperand(OpIdx);
3619 if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
3620 LLVM_DEBUG(dbgs() << "Statically extend\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Statically extend\n"; }
} while (false)
;
3621 unsigned BitWidth = Ext->getType()->getIntegerBitWidth();
3622 APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth)
3623 : Cst->getValue().zext(BitWidth);
3624 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal));
3625 continue;
3626 }
3627 // UndefValue are typed, so we have to statically sign extend them.
3628 if (isa<UndefValue>(Opnd)) {
3629 LLVM_DEBUG(dbgs() << "Statically extend\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Statically extend\n"; }
} while (false)
;
3630 TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType()));
3631 continue;
3632 }
3633
3634 // Otherwise we have to explicitly sign extend the operand.
3635 // Check if Ext was reused to extend an operand.
3636 if (!ExtForOpnd) {
3637 // If yes, create a new one.
3638 LLVM_DEBUG(dbgs() << "More operands to ext\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "More operands to ext\n"
; } } while (false)
;
3639 Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType())
3640 : TPT.createZExt(Ext, Opnd, Ext->getType());
3641 if (!isa<Instruction>(ValForExtOpnd)) {
3642 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
3643 continue;
3644 }
3645 ExtForOpnd = cast<Instruction>(ValForExtOpnd);
3646 }
3647 if (Exts)
3648 Exts->push_back(ExtForOpnd);
3649 TPT.setOperand(ExtForOpnd, 0, Opnd);
3650
3651 // Move the sign extension before the insertion point.
3652 TPT.moveBefore(ExtForOpnd, ExtOpnd);
3653 TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd);
3654 CreatedInstsCost += !TLI.isExtFree(ExtForOpnd);
3655 // If more sext are required, new instructions will have to be created.
3656 ExtForOpnd = nullptr;
3657 }
3658 if (ExtForOpnd == Ext) {
3659 LLVM_DEBUG(dbgs() << "Extension is useless now\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Extension is useless now\n"
; } } while (false)
;
3660 TPT.eraseInstruction(Ext);
3661 }
3662 return ExtOpnd;
3663}
3664
3665/// Check whether or not promoting an instruction to a wider type is profitable.
3666/// \p NewCost gives the cost of extension instructions created by the
3667/// promotion.
3668/// \p OldCost gives the cost of extension instructions before the promotion
3669/// plus the number of instructions that have been
3670/// matched in the addressing mode the promotion.
3671/// \p PromotedOperand is the value that has been promoted.
3672/// \return True if the promotion is profitable, false otherwise.
3673bool AddressingModeMatcher::isPromotionProfitable(
3674 unsigned NewCost, unsigned OldCost, Value *PromotedOperand) const {
3675 LLVM_DEBUG(dbgs() << "OldCost: " << OldCost << "\tNewCost: " << NewCostdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "OldCost: " << OldCost
<< "\tNewCost: " << NewCost << '\n'; } } while
(false)
3676 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "OldCost: " << OldCost
<< "\tNewCost: " << NewCost << '\n'; } } while
(false)
;
3677 // The cost of the new extensions is greater than the cost of the
3678 // old extension plus what we folded.
3679 // This is not profitable.
3680 if (NewCost > OldCost)
3681 return false;
3682 if (NewCost < OldCost)
3683 return true;
3684 // The promotion is neutral but it may help folding the sign extension in
3685 // loads for instance.
3686 // Check that we did not create an illegal instruction.
3687 return isPromotedInstructionLegal(TLI, DL, PromotedOperand);
3688}
3689
3690/// Given an instruction or constant expr, see if we can fold the operation
3691/// into the addressing mode. If so, update the addressing mode and return
3692/// true, otherwise return false without modifying AddrMode.
3693/// If \p MovedAway is not NULL, it contains the information of whether or
3694/// not AddrInst has to be folded into the addressing mode on success.
3695/// If \p MovedAway == true, \p AddrInst will not be part of the addressing
3696/// because it has been moved away.
3697/// Thus AddrInst must not be added in the matched instructions.
3698/// This state can happen when AddrInst is a sext, since it may be moved away.
3699/// Therefore, AddrInst may not be valid when MovedAway is true and it must
3700/// not be referenced anymore.
3701bool AddressingModeMatcher::matchOperationAddr(User *AddrInst, unsigned Opcode,
3702 unsigned Depth,
3703 bool *MovedAway) {
3704 // Avoid exponential behavior on extremely deep expression trees.
3705 if (Depth >= 5) return false;
3706
3707 // By default, all matched instructions stay in place.
3708 if (MovedAway)
3709 *MovedAway = false;
3710
3711 switch (Opcode) {
3712 case Instruction::PtrToInt:
3713 // PtrToInt is always a noop, as we know that the int type is pointer sized.
3714 return matchAddr(AddrInst->getOperand(0), Depth);
3715 case Instruction::IntToPtr: {
3716 auto AS = AddrInst->getType()->getPointerAddressSpace();
3717 auto PtrTy = MVT::getIntegerVT(DL.getPointerSizeInBits(AS));
3718 // This inttoptr is a no-op if the integer type is pointer sized.
3719 if (TLI.getValueType(DL, AddrInst->getOperand(0)->getType()) == PtrTy)
3720 return matchAddr(AddrInst->getOperand(0), Depth);
3721 return false;
3722 }
3723 case Instruction::BitCast:
3724 // BitCast is always a noop, and we can handle it as long as it is
3725 // int->int or pointer->pointer (we don't want int<->fp or something).
3726 if (AddrInst->getOperand(0)->getType()->isIntOrPtrTy() &&
3727 // Don't touch identity bitcasts. These were probably put here by LSR,
3728 // and we don't want to mess around with them. Assume it knows what it
3729 // is doing.
3730 AddrInst->getOperand(0)->getType() != AddrInst->getType())
3731 return matchAddr(AddrInst->getOperand(0), Depth);
3732 return false;
3733 case Instruction::AddrSpaceCast: {
3734 unsigned SrcAS
3735 = AddrInst->getOperand(0)->getType()->getPointerAddressSpace();
3736 unsigned DestAS = AddrInst->getType()->getPointerAddressSpace();
3737 if (TLI.isNoopAddrSpaceCast(SrcAS, DestAS))
3738 return matchAddr(AddrInst->getOperand(0), Depth);
3739 return false;
3740 }
3741 case Instruction::Add: {
3742 // Check to see if we can merge in the RHS then the LHS. If so, we win.
3743 ExtAddrMode BackupAddrMode = AddrMode;
3744 unsigned OldSize = AddrModeInsts.size();
3745 // Start a transaction at this point.
3746 // The LHS may match but not the RHS.
3747 // Therefore, we need a higher level restoration point to undo partially
3748 // matched operation.
3749 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
3750 TPT.getRestorationPoint();
3751
3752 if (matchAddr(AddrInst->getOperand(1), Depth+1) &&
3753 matchAddr(AddrInst->getOperand(0), Depth+1))
3754 return true;
3755
3756 // Restore the old addr mode info.
3757 AddrMode = BackupAddrMode;
3758 AddrModeInsts.resize(OldSize);
3759 TPT.rollback(LastKnownGood);
3760
3761 // Otherwise this was over-aggressive. Try merging in the LHS then the RHS.
3762 if (matchAddr(AddrInst->getOperand(0), Depth+1) &&
3763 matchAddr(AddrInst->getOperand(1), Depth+1))
3764 return true;
3765
3766 // Otherwise we definitely can't merge the ADD in.
3767 AddrMode = BackupAddrMode;
3768 AddrModeInsts.resize(OldSize);
3769 TPT.rollback(LastKnownGood);
3770 break;
3771 }
3772 //case Instruction::Or:
3773 // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
3774 //break;
3775 case Instruction::Mul:
3776 case Instruction::Shl: {
3777 // Can only handle X*C and X << C.
3778 ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
3779 if (!RHS || RHS->getBitWidth() > 64)
3780 return false;
3781 int64_t Scale = RHS->getSExtValue();
3782 if (Opcode == Instruction::Shl)
3783 Scale = 1LL << Scale;
3784
3785 return matchScaledValue(AddrInst->getOperand(0), Scale, Depth);
3786 }
3787 case Instruction::GetElementPtr: {
3788 // Scan the GEP. We check it if it contains constant offsets and at most
3789 // one variable offset.
3790 int VariableOperand = -1;
3791 unsigned VariableScale = 0;
3792
3793 int64_t ConstantOffset = 0;
3794 gep_type_iterator GTI = gep_type_begin(AddrInst);
3795 for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
3796 if (StructType *STy = GTI.getStructTypeOrNull()) {
3797 const StructLayout *SL = DL.getStructLayout(STy);
3798 unsigned Idx =
3799 cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
3800 ConstantOffset += SL->getElementOffset(Idx);
3801 } else {
3802 uint64_t TypeSize = DL.getTypeAllocSize(GTI.getIndexedType());
3803 if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
3804 ConstantOffset += CI->getSExtValue() * TypeSize;
3805 } else if (TypeSize) { // Scales of zero don't do anything.
3806 // We only allow one variable index at the moment.
3807 if (VariableOperand != -1)
3808 return false;
3809
3810 // Remember the variable index.
3811 VariableOperand = i;
3812 VariableScale = TypeSize;
3813 }
3814 }
3815 }
3816
3817 // A common case is for the GEP to only do a constant offset. In this case,
3818 // just add it to the disp field and check validity.
3819 if (VariableOperand == -1) {
3820 AddrMode.BaseOffs += ConstantOffset;
3821 if (ConstantOffset == 0 ||
3822 TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) {
3823 // Check to see if we can fold the base pointer in too.
3824 if (matchAddr(AddrInst->getOperand(0), Depth+1))
3825 return true;
3826 } else if (EnableGEPOffsetSplit && isa<GetElementPtrInst>(AddrInst) &&
3827 TLI.shouldConsiderGEPOffsetSplit() && Depth == 0 &&
3828 ConstantOffset > 0) {
3829 // Record GEPs with non-zero offsets as candidates for splitting in the
3830 // event that the offset cannot fit into the r+i addressing mode.
3831 // Simple and common case that only one GEP is used in calculating the
3832 // address for the memory access.
3833 Value *Base = AddrInst->getOperand(0);
3834 auto *BaseI = dyn_cast<Instruction>(Base);
3835 auto *GEP = cast<GetElementPtrInst>(AddrInst);
3836 if (isa<Argument>(Base) || isa<GlobalValue>(Base) ||
3837 (BaseI && !isa<CastInst>(BaseI) &&
3838 !isa<GetElementPtrInst>(BaseI))) {
3839 // If the base is an instruction, make sure the GEP is not in the same
3840 // basic block as the base. If the base is an argument or global
3841 // value, make sure the GEP is not in the entry block. Otherwise,
3842 // instruction selection can undo the split. Also make sure the
3843 // parent block allows inserting non-PHI instructions before the
3844 // terminator.
3845 BasicBlock *Parent =
3846 BaseI ? BaseI->getParent() : &GEP->getFunction()->getEntryBlock();
3847 if (GEP->getParent() != Parent && !Parent->getTerminator()->isEHPad())
3848 LargeOffsetGEP = std::make_pair(GEP, ConstantOffset);
3849 }
3850 }
3851 AddrMode.BaseOffs -= ConstantOffset;
3852 return false;
3853 }
3854
3855 // Save the valid addressing mode in case we can't match.
3856 ExtAddrMode BackupAddrMode = AddrMode;
3857 unsigned OldSize = AddrModeInsts.size();
3858
3859 // See if the scale and offset amount is valid for this target.
3860 AddrMode.BaseOffs += ConstantOffset;
3861
3862 // Match the base operand of the GEP.
3863 if (!matchAddr(AddrInst->getOperand(0), Depth+1)) {
3864 // If it couldn't be matched, just stuff the value in a register.
3865 if (AddrMode.HasBaseReg) {
3866 AddrMode = BackupAddrMode;
3867 AddrModeInsts.resize(OldSize);
3868 return false;
3869 }
3870 AddrMode.HasBaseReg = true;
3871 AddrMode.BaseReg = AddrInst->getOperand(0);
3872 }
3873
3874 // Match the remaining variable portion of the GEP.
3875 if (!matchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
3876 Depth)) {
3877 // If it couldn't be matched, try stuffing the base into a register
3878 // instead of matching it, and retrying the match of the scale.
3879 AddrMode = BackupAddrMode;
3880 AddrModeInsts.resize(OldSize);
3881 if (AddrMode.HasBaseReg)
3882 return false;
3883 AddrMode.HasBaseReg = true;
3884 AddrMode.BaseReg = AddrInst->getOperand(0);
3885 AddrMode.BaseOffs += ConstantOffset;
3886 if (!matchScaledValue(AddrInst->getOperand(VariableOperand),
3887 VariableScale, Depth)) {
3888 // If even that didn't work, bail.
3889 AddrMode = BackupAddrMode;
3890 AddrModeInsts.resize(OldSize);
3891 return false;
3892 }
3893 }
3894
3895 return true;
3896 }
3897 case Instruction::SExt:
3898 case Instruction::ZExt: {
3899 Instruction *Ext = dyn_cast<Instruction>(AddrInst);
3900 if (!Ext)
3901 return false;
3902
3903 // Try to move this ext out of the way of the addressing mode.
3904 // Ask for a method for doing so.
3905 TypePromotionHelper::Action TPH =
3906 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
3907 if (!TPH)
3908 return false;
3909
3910 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
3911 TPT.getRestorationPoint();
3912 unsigned CreatedInstsCost = 0;
3913 unsigned ExtCost = !TLI.isExtFree(Ext);
3914 Value *PromotedOperand =
3915 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost, nullptr, nullptr, TLI);
3916 // SExt has been moved away.
3917 // Thus either it will be rematched later in the recursive calls or it is
3918 // gone. Anyway, we must not fold it into the addressing mode at this point.
3919 // E.g.,
3920 // op = add opnd, 1
3921 // idx = ext op
3922 // addr = gep base, idx
3923 // is now:
3924 // promotedOpnd = ext opnd <- no match here
3925 // op = promoted_add promotedOpnd, 1 <- match (later in recursive calls)
3926 // addr = gep base, op <- match
3927 if (MovedAway)
3928 *MovedAway = true;
3929
3930 assert(PromotedOperand &&(static_cast <bool> (PromotedOperand && "TypePromotionHelper should have filtered out those cases"
) ? void (0) : __assert_fail ("PromotedOperand && \"TypePromotionHelper should have filtered out those cases\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3931, __extension__ __PRETTY_FUNCTION__))
3931 "TypePromotionHelper should have filtered out those cases")(static_cast <bool> (PromotedOperand && "TypePromotionHelper should have filtered out those cases"
) ? void (0) : __assert_fail ("PromotedOperand && \"TypePromotionHelper should have filtered out those cases\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 3931, __extension__ __PRETTY_FUNCTION__))
;
3932
3933 ExtAddrMode BackupAddrMode = AddrMode;
3934 unsigned OldSize = AddrModeInsts.size();
3935
3936 if (!matchAddr(PromotedOperand, Depth) ||
3937 // The total of the new cost is equal to the cost of the created
3938 // instructions.
3939 // The total of the old cost is equal to the cost of the extension plus
3940 // what we have saved in the addressing mode.
3941 !isPromotionProfitable(CreatedInstsCost,
3942 ExtCost + (AddrModeInsts.size() - OldSize),
3943 PromotedOperand)) {
3944 AddrMode = BackupAddrMode;
3945 AddrModeInsts.resize(OldSize);
3946 LLVM_DEBUG(dbgs() << "Sign extension does not pay off: rollback\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "Sign extension does not pay off: rollback\n"
; } } while (false)
;
3947 TPT.rollback(LastKnownGood);
3948 return false;
3949 }
3950 return true;
3951 }
3952 }
3953 return false;
3954}
3955
3956/// If we can, try to add the value of 'Addr' into the current addressing mode.
3957/// If Addr can't be added to AddrMode this returns false and leaves AddrMode
3958/// unmodified. This assumes that Addr is either a pointer type or intptr_t
3959/// for the target.
3960///
3961bool AddressingModeMatcher::matchAddr(Value *Addr, unsigned Depth) {
3962 // Start a transaction at this point that we will rollback if the matching
3963 // fails.
3964 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
3965 TPT.getRestorationPoint();
3966 if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
3967 // Fold in immediates if legal for the target.
3968 AddrMode.BaseOffs += CI->getSExtValue();
3969 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace))
3970 return true;
3971 AddrMode.BaseOffs -= CI->getSExtValue();
3972 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
3973 // If this is a global variable, try to fold it into the addressing mode.
3974 if (!AddrMode.BaseGV) {
3975 AddrMode.BaseGV = GV;
3976 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace))
3977 return true;
3978 AddrMode.BaseGV = nullptr;
3979 }
3980 } else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
3981 ExtAddrMode BackupAddrMode = AddrMode;
3982 unsigned OldSize = AddrModeInsts.size();
3983
3984 // Check to see if it is possible to fold this operation.
3985 bool MovedAway = false;
3986 if (matchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) {
3987 // This instruction may have been moved away. If so, there is nothing
3988 // to check here.
3989 if (MovedAway)
3990 return true;
3991 // Okay, it's possible to fold this. Check to see if it is actually
3992 // *profitable* to do so. We use a simple cost model to avoid increasing
3993 // register pressure too much.
3994 if (I->hasOneUse() ||
3995 isProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
3996 AddrModeInsts.push_back(I);
3997 return true;
3998 }
3999
4000 // It isn't profitable to do this, roll back.
4001 //cerr << "NOT FOLDING: " << *I;
4002 AddrMode = BackupAddrMode;
4003 AddrModeInsts.resize(OldSize);
4004 TPT.rollback(LastKnownGood);
4005 }
4006 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
4007 if (matchOperationAddr(CE, CE->getOpcode(), Depth))
4008 return true;
4009 TPT.rollback(LastKnownGood);
4010 } else if (isa<ConstantPointerNull>(Addr)) {
4011 // Null pointer gets folded without affecting the addressing mode.
4012 return true;
4013 }
4014
4015 // Worse case, the target should support [reg] addressing modes. :)
4016 if (!AddrMode.HasBaseReg) {
4017 AddrMode.HasBaseReg = true;
4018 AddrMode.BaseReg = Addr;
4019 // Still check for legality in case the target supports [imm] but not [i+r].
4020 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace))
4021 return true;
4022 AddrMode.HasBaseReg = false;
4023 AddrMode.BaseReg = nullptr;
4024 }
4025
4026 // If the base register is already taken, see if we can do [r+r].
4027 if (AddrMode.Scale == 0) {
4028 AddrMode.Scale = 1;
4029 AddrMode.ScaledReg = Addr;
4030 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace))
4031 return true;
4032 AddrMode.Scale = 0;
4033 AddrMode.ScaledReg = nullptr;
4034 }
4035 // Couldn't match.
4036 TPT.rollback(LastKnownGood);
4037 return false;
4038}
4039
4040/// Check to see if all uses of OpVal by the specified inline asm call are due
4041/// to memory operands. If so, return true, otherwise return false.
4042static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
4043 const TargetLowering &TLI,
4044 const TargetRegisterInfo &TRI) {
4045 const Function *F = CI->getFunction();
4046 TargetLowering::AsmOperandInfoVector TargetConstraints =
4047 TLI.ParseConstraints(F->getParent()->getDataLayout(), &TRI,
4048 ImmutableCallSite(CI));
4049
4050 for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
4051 TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
4052
4053 // Compute the constraint code and ConstraintType to use.
4054 TLI.ComputeConstraintToUse(OpInfo, SDValue());
4055
4056 // If this asm operand is our Value*, and if it isn't an indirect memory
4057 // operand, we can't fold it!
4058 if (OpInfo.CallOperandVal == OpVal &&
4059 (OpInfo.ConstraintType != TargetLowering::C_Memory ||
4060 !OpInfo.isIndirect))
4061 return false;
4062 }
4063
4064 return true;
4065}
4066
4067// Max number of memory uses to look at before aborting the search to conserve
4068// compile time.
4069static constexpr int MaxMemoryUsesToScan = 20;
4070
4071/// Recursively walk all the uses of I until we find a memory use.
4072/// If we find an obviously non-foldable instruction, return true.
4073/// Add the ultimately found memory instructions to MemoryUses.
4074static bool FindAllMemoryUses(
4075 Instruction *I,
4076 SmallVectorImpl<std::pair<Instruction *, unsigned>> &MemoryUses,
4077 SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetLowering &TLI,
4078 const TargetRegisterInfo &TRI, int SeenInsts = 0) {
4079 // If we already considered this instruction, we're done.
4080 if (!ConsideredInsts.insert(I).second)
4081 return false;
4082
4083 // If this is an obviously unfoldable instruction, bail out.
4084 if (!MightBeFoldableInst(I))
4085 return true;
4086
4087 const bool OptSize = I->getFunction()->optForSize();
4088
4089 // Loop over all the uses, recursively processing them.
4090 for (Use &U : I->uses()) {
4091 // Conservatively return true if we're seeing a large number or a deep chain
4092 // of users. This avoids excessive compilation times in pathological cases.
4093 if (SeenInsts++ >= MaxMemoryUsesToScan)
4094 return true;
4095
4096 Instruction *UserI = cast<Instruction>(U.getUser());
4097 if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
4098 MemoryUses.push_back(std::make_pair(LI, U.getOperandNo()));
4099 continue;
4100 }
4101
4102 if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
4103 unsigned opNo = U.getOperandNo();
4104 if (opNo != StoreInst::getPointerOperandIndex())
4105 return true; // Storing addr, not into addr.
4106 MemoryUses.push_back(std::make_pair(SI, opNo));
4107 continue;
4108 }
4109
4110 if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(UserI)) {
4111 unsigned opNo = U.getOperandNo();
4112 if (opNo != AtomicRMWInst::getPointerOperandIndex())
4113 return true; // Storing addr, not into addr.
4114 MemoryUses.push_back(std::make_pair(RMW, opNo));
4115 continue;
4116 }
4117
4118 if (AtomicCmpXchgInst *CmpX = dyn_cast<AtomicCmpXchgInst>(UserI)) {
4119 unsigned opNo = U.getOperandNo();
4120 if (opNo != AtomicCmpXchgInst::getPointerOperandIndex())
4121 return true; // Storing addr, not into addr.
4122 MemoryUses.push_back(std::make_pair(CmpX, opNo));
4123 continue;
4124 }
4125
4126 if (CallInst *CI = dyn_cast<CallInst>(UserI)) {
4127 // If this is a cold call, we can sink the addressing calculation into
4128 // the cold path. See optimizeCallInst
4129 if (!OptSize && CI->hasFnAttr(Attribute::Cold))
4130 continue;
4131
4132 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
4133 if (!IA) return true;
4134
4135 // If this is a memory operand, we're cool, otherwise bail out.
4136 if (!IsOperandAMemoryOperand(CI, IA, I, TLI, TRI))
4137 return true;
4138 continue;
4139 }
4140
4141 if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TLI, TRI,
4142 SeenInsts))
4143 return true;
4144 }
4145
4146 return false;
4147}
4148
4149/// Return true if Val is already known to be live at the use site that we're
4150/// folding it into. If so, there is no cost to include it in the addressing
4151/// mode. KnownLive1 and KnownLive2 are two values that we know are live at the
4152/// instruction already.
4153bool AddressingModeMatcher::valueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
4154 Value *KnownLive2) {
4155 // If Val is either of the known-live values, we know it is live!
4156 if (Val == nullptr || Val == KnownLive1 || Val == KnownLive2)
4157 return true;
4158
4159 // All values other than instructions and arguments (e.g. constants) are live.
4160 if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
4161
4162 // If Val is a constant sized alloca in the entry block, it is live, this is
4163 // true because it is just a reference to the stack/frame pointer, which is
4164 // live for the whole function.
4165 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
4166 if (AI->isStaticAlloca())
4167 return true;
4168
4169 // Check to see if this value is already used in the memory instruction's
4170 // block. If so, it's already live into the block at the very least, so we
4171 // can reasonably fold it.
4172 return Val->isUsedInBasicBlock(MemoryInst->getParent());
4173}
4174
4175/// It is possible for the addressing mode of the machine to fold the specified
4176/// instruction into a load or store that ultimately uses it.
4177/// However, the specified instruction has multiple uses.
4178/// Given this, it may actually increase register pressure to fold it
4179/// into the load. For example, consider this code:
4180///
4181/// X = ...
4182/// Y = X+1
4183/// use(Y) -> nonload/store
4184/// Z = Y+1
4185/// load Z
4186///
4187/// In this case, Y has multiple uses, and can be folded into the load of Z
4188/// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to
4189/// be live at the use(Y) line. If we don't fold Y into load Z, we use one
4190/// fewer register. Since Y can't be folded into "use(Y)" we don't increase the
4191/// number of computations either.
4192///
4193/// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If
4194/// X was live across 'load Z' for other reasons, we actually *would* want to
4195/// fold the addressing mode in the Z case. This would make Y die earlier.
4196bool AddressingModeMatcher::
4197isProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
4198 ExtAddrMode &AMAfter) {
4199 if (IgnoreProfitability) return true;
4200
4201 // AMBefore is the addressing mode before this instruction was folded into it,
4202 // and AMAfter is the addressing mode after the instruction was folded. Get
4203 // the set of registers referenced by AMAfter and subtract out those
4204 // referenced by AMBefore: this is the set of values which folding in this
4205 // address extends the lifetime of.
4206 //
4207 // Note that there are only two potential values being referenced here,
4208 // BaseReg and ScaleReg (global addresses are always available, as are any
4209 // folded immediates).
4210 Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
4211
4212 // If the BaseReg or ScaledReg was referenced by the previous addrmode, their
4213 // lifetime wasn't extended by adding this instruction.
4214 if (valueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
4215 BaseReg = nullptr;
4216 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
4217 ScaledReg = nullptr;
4218
4219 // If folding this instruction (and it's subexprs) didn't extend any live
4220 // ranges, we're ok with it.
4221 if (!BaseReg && !ScaledReg)
4222 return true;
4223
4224 // If all uses of this instruction can have the address mode sunk into them,
4225 // we can remove the addressing mode and effectively trade one live register
4226 // for another (at worst.) In this context, folding an addressing mode into
4227 // the use is just a particularly nice way of sinking it.
4228 SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
4229 SmallPtrSet<Instruction*, 16> ConsideredInsts;
4230 if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI, TRI))
4231 return false; // Has a non-memory, non-foldable use!
4232
4233 // Now that we know that all uses of this instruction are part of a chain of
4234 // computation involving only operations that could theoretically be folded
4235 // into a memory use, loop over each of these memory operation uses and see
4236 // if they could *actually* fold the instruction. The assumption is that
4237 // addressing modes are cheap and that duplicating the computation involved
4238 // many times is worthwhile, even on a fastpath. For sinking candidates
4239 // (i.e. cold call sites), this serves as a way to prevent excessive code
4240 // growth since most architectures have some reasonable small and fast way to
4241 // compute an effective address. (i.e LEA on x86)
4242 SmallVector<Instruction*, 32> MatchedAddrModeInsts;
4243 for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
4244 Instruction *User = MemoryUses[i].first;
4245 unsigned OpNo = MemoryUses[i].second;
4246
4247 // Get the access type of this use. If the use isn't a pointer, we don't
4248 // know what it accesses.
4249 Value *Address = User->getOperand(OpNo);
4250 PointerType *AddrTy = dyn_cast<PointerType>(Address->getType());
4251 if (!AddrTy)
4252 return false;
4253 Type *AddressAccessTy = AddrTy->getElementType();
4254 unsigned AS = AddrTy->getAddressSpace();
4255
4256 // Do a match against the root of this address, ignoring profitability. This
4257 // will tell us if the addressing mode for the memory operation will
4258 // *actually* cover the shared instruction.
4259 ExtAddrMode Result;
4260 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(nullptr,
4261 0);
4262 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4263 TPT.getRestorationPoint();
4264 AddressingModeMatcher Matcher(
4265 MatchedAddrModeInsts, TLI, TRI, AddressAccessTy, AS, MemoryInst, Result,
4266 InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP);
4267 Matcher.IgnoreProfitability = true;
4268 bool Success = Matcher.matchAddr(Address, 0);
4269 (void)Success; assert(Success && "Couldn't select *anything*?")(static_cast <bool> (Success && "Couldn't select *anything*?"
) ? void (0) : __assert_fail ("Success && \"Couldn't select *anything*?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4269, __extension__ __PRETTY_FUNCTION__))
;
4270
4271 // The match was to check the profitability, the changes made are not
4272 // part of the original matcher. Therefore, they should be dropped
4273 // otherwise the original matcher will not present the right state.
4274 TPT.rollback(LastKnownGood);
4275
4276 // If the match didn't cover I, then it won't be shared by it.
4277 if (!is_contained(MatchedAddrModeInsts, I))
4278 return false;
4279
4280 MatchedAddrModeInsts.clear();
4281 }
4282
4283 return true;
4284}
4285
4286/// Return true if the specified values are defined in a
4287/// different basic block than BB.
4288static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
4289 if (Instruction *I = dyn_cast<Instruction>(V))
4290 return I->getParent() != BB;
4291 return false;
4292}
4293
4294/// Sink addressing mode computation immediate before MemoryInst if doing so
4295/// can be done without increasing register pressure. The need for the
4296/// register pressure constraint means this can end up being an all or nothing
4297/// decision for all uses of the same addressing computation.
4298///
4299/// Load and Store Instructions often have addressing modes that can do
4300/// significant amounts of computation. As such, instruction selection will try
4301/// to get the load or store to do as much computation as possible for the
4302/// program. The problem is that isel can only see within a single block. As
4303/// such, we sink as much legal addressing mode work into the block as possible.
4304///
4305/// This method is used to optimize both load/store and inline asms with memory
4306/// operands. It's also used to sink addressing computations feeding into cold
4307/// call sites into their (cold) basic block.
4308///
4309/// The motivation for handling sinking into cold blocks is that doing so can
4310/// both enable other address mode sinking (by satisfying the register pressure
4311/// constraint above), and reduce register pressure globally (by removing the
4312/// addressing mode computation from the fast path entirely.).
4313bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
4314 Type *AccessTy, unsigned AddrSpace) {
4315 Value *Repl = Addr;
4316
4317 // Try to collapse single-value PHI nodes. This is necessary to undo
4318 // unprofitable PRE transformations.
4319 SmallVector<Value*, 8> worklist;
4320 SmallPtrSet<Value*, 16> Visited;
4321 worklist.push_back(Addr);
4322
4323 // Use a worklist to iteratively look through PHI and select nodes, and
4324 // ensure that the addressing mode obtained from the non-PHI/select roots of
4325 // the graph are compatible.
4326 bool PhiOrSelectSeen = false;
4327 SmallVector<Instruction*, 16> AddrModeInsts;
4328 const SimplifyQuery SQ(*DL, TLInfo);
4329 AddressingModeCombiner AddrModes(SQ, { Addr, MemoryInst->getParent() });
4330 TypePromotionTransaction TPT(RemovedInsts);
4331 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4332 TPT.getRestorationPoint();
4333 while (!worklist.empty()) {
4334 Value *V = worklist.back();
4335 worklist.pop_back();
4336
4337 // We allow traversing cyclic Phi nodes.
4338 // In case of success after this loop we ensure that traversing through
4339 // Phi nodes ends up with all cases to compute address of the form
4340 // BaseGV + Base + Scale * Index + Offset
4341 // where Scale and Offset are constans and BaseGV, Base and Index
4342 // are exactly the same Values in all cases.
4343 // It means that BaseGV, Scale and Offset dominate our memory instruction
4344 // and have the same value as they had in address computation represented
4345 // as Phi. So we can safely sink address computation to memory instruction.
4346 if (!Visited.insert(V).second)
4347 continue;
4348
4349 // For a PHI node, push all of its incoming values.
4350 if (PHINode *P = dyn_cast<PHINode>(V)) {
4351 for (Value *IncValue : P->incoming_values())
4352 worklist.push_back(IncValue);
4353 PhiOrSelectSeen = true;
4354 continue;
4355 }
4356 // Similar for select.
4357 if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
4358 worklist.push_back(SI->getFalseValue());
4359 worklist.push_back(SI->getTrueValue());
4360 PhiOrSelectSeen = true;
4361 continue;
4362 }
4363
4364 // For non-PHIs, determine the addressing mode being computed. Note that
4365 // the result may differ depending on what other uses our candidate
4366 // addressing instructions might have.
4367 AddrModeInsts.clear();
4368 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(nullptr,
4369 0);
4370 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
4371 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *TRI,
4372 InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP);
4373
4374 GetElementPtrInst *GEP = LargeOffsetGEP.first;
4375 if (GEP && GEP->getParent() != MemoryInst->getParent() &&
4376 !NewGEPBases.count(GEP)) {
4377 // If splitting the underlying data structure can reduce the offset of a
4378 // GEP, collect the GEP. Skip the GEPs that are the new bases of
4379 // previously split data structures.
4380 LargeOffsetGEPMap[GEP->getPointerOperand()].push_back(LargeOffsetGEP);
4381 if (LargeOffsetGEPID.find(GEP) == LargeOffsetGEPID.end())
4382 LargeOffsetGEPID[GEP] = LargeOffsetGEPID.size();
4383 }
4384
4385 NewAddrMode.OriginalValue = V;
4386 if (!AddrModes.addNewAddrMode(NewAddrMode))
4387 break;
4388 }
4389
4390 // Try to combine the AddrModes we've collected. If we couldn't collect any,
4391 // or we have multiple but either couldn't combine them or combining them
4392 // wouldn't do anything useful, bail out now.
4393 if (!AddrModes.combineAddrModes()) {
4394 TPT.rollback(LastKnownGood);
4395 return false;
4396 }
4397 TPT.commit();
4398
4399 // Get the combined AddrMode (or the only AddrMode, if we only had one).
4400 ExtAddrMode AddrMode = AddrModes.getAddrMode();
4401
4402 // If all the instructions matched are already in this BB, don't do anything.
4403 // If we saw a Phi node then it is not local definitely, and if we saw a select
4404 // then we want to push the address calculation past it even if it's already
4405 // in this BB.
4406 if (!PhiOrSelectSeen && none_of(AddrModeInsts, [&](Value *V) {
4407 return IsNonLocalValue(V, MemoryInst->getParent());
4408 })) {
4409 LLVM_DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrModedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: Found local addrmode: "
<< AddrMode << "\n"; } } while (false)
4410 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: Found local addrmode: "
<< AddrMode << "\n"; } } while (false)
;
4411 return false;
4412 }
4413
4414 // Insert this computation right after this user. Since our caller is
4415 // scanning from the top of the BB to the bottom, reuse of the expr are
4416 // guaranteed to happen later.
4417 IRBuilder<> Builder(MemoryInst);
4418
4419 // Now that we determined the addressing expression we want to use and know
4420 // that we have to sink it into this block. Check to see if we have already
4421 // done this for some other load/store instr in this block. If so, reuse
4422 // the computation. Before attempting reuse, check if the address is valid
4423 // as it may have been erased.
4424
4425 WeakTrackingVH SunkAddrVH = SunkAddrs[Addr];
4426
4427 Value * SunkAddr = SunkAddrVH.pointsToAliveValue() ? SunkAddrVH : nullptr;
4428 if (SunkAddr) {
4429 LLVM_DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrModedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: Reusing nonlocal addrmode: "
<< AddrMode << " for " << *MemoryInst <<
"\n"; } } while (false)
4430 << " for " << *MemoryInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: Reusing nonlocal addrmode: "
<< AddrMode << " for " << *MemoryInst <<
"\n"; } } while (false)
;
4431 if (SunkAddr->getType() != Addr->getType())
4432 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->getType());
4433 } else if (AddrSinkUsingGEPs ||
4434 (!AddrSinkUsingGEPs.getNumOccurrences() && TM && TTI->useAA())) {
4435 // By default, we use the GEP-based method when AA is used later. This
4436 // prevents new inttoptr/ptrtoint pairs from degrading AA capabilities.
4437 LLVM_DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrModedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: SINKING nonlocal addrmode: "
<< AddrMode << " for " << *MemoryInst <<
"\n"; } } while (false)
4438 << " for " << *MemoryInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: SINKING nonlocal addrmode: "
<< AddrMode << " for " << *MemoryInst <<
"\n"; } } while (false)
;
4439 Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
4440 Value *ResultPtr = nullptr, *ResultIndex = nullptr;
4441
4442 // First, find the pointer.
4443 if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) {
4444 ResultPtr = AddrMode.BaseReg;
4445 AddrMode.BaseReg = nullptr;
4446 }
4447
4448 if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) {
4449 // We can't add more than one pointer together, nor can we scale a
4450 // pointer (both of which seem meaningless).
4451 if (ResultPtr || AddrMode.Scale != 1)
4452 return false;
4453
4454 ResultPtr = AddrMode.ScaledReg;
4455 AddrMode.Scale = 0;
4456 }
4457
4458 // It is only safe to sign extend the BaseReg if we know that the math
4459 // required to create it did not overflow before we extend it. Since
4460 // the original IR value was tossed in favor of a constant back when
4461 // the AddrMode was created we need to bail out gracefully if widths
4462 // do not match instead of extending it.
4463 //
4464 // (See below for code to add the scale.)
4465 if (AddrMode.Scale) {
4466 Type *ScaledRegTy = AddrMode.ScaledReg->getType();
4467 if (cast<IntegerType>(IntPtrTy)->getBitWidth() >
4468 cast<IntegerType>(ScaledRegTy)->getBitWidth())
4469 return false;
4470 }
4471
4472 if (AddrMode.BaseGV) {
4473 if (ResultPtr)
4474 return false;
4475
4476 ResultPtr = AddrMode.BaseGV;
4477 }
4478
4479 // If the real base value actually came from an inttoptr, then the matcher
4480 // will look through it and provide only the integer value. In that case,
4481 // use it here.
4482 if (!DL->isNonIntegralPointerType(Addr->getType())) {
4483 if (!ResultPtr && AddrMode.BaseReg) {
4484 ResultPtr = Builder.CreateIntToPtr(AddrMode.BaseReg, Addr->getType(),
4485 "sunkaddr");
4486 AddrMode.BaseReg = nullptr;
4487 } else if (!ResultPtr && AddrMode.Scale == 1) {
4488 ResultPtr = Builder.CreateIntToPtr(AddrMode.ScaledReg, Addr->getType(),
4489 "sunkaddr");
4490 AddrMode.Scale = 0;
4491 }
4492 }
4493
4494 if (!ResultPtr &&
4495 !AddrMode.BaseReg && !AddrMode.Scale && !AddrMode.BaseOffs) {
4496 SunkAddr = Constant::getNullValue(Addr->getType());
4497 } else if (!ResultPtr) {
4498 return false;
4499 } else {
4500 Type *I8PtrTy =
4501 Builder.getInt8PtrTy(Addr->getType()->getPointerAddressSpace());
4502 Type *I8Ty = Builder.getInt8Ty();
4503
4504 // Start with the base register. Do this first so that subsequent address
4505 // matching finds it last, which will prevent it from trying to match it
4506 // as the scaled value in case it happens to be a mul. That would be
4507 // problematic if we've sunk a different mul for the scale, because then
4508 // we'd end up sinking both muls.
4509 if (AddrMode.BaseReg) {
4510 Value *V = AddrMode.BaseReg;
4511 if (V->getType() != IntPtrTy)
4512 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
4513
4514 ResultIndex = V;
4515 }
4516
4517 // Add the scale value.
4518 if (AddrMode.Scale) {
4519 Value *V = AddrMode.ScaledReg;
4520 if (V->getType() == IntPtrTy) {
4521 // done.
4522 } else {
4523 assert(cast<IntegerType>(IntPtrTy)->getBitWidth() <(static_cast <bool> (cast<IntegerType>(IntPtrTy)->
getBitWidth() < cast<IntegerType>(V->getType())->
getBitWidth() && "We can't transform if ScaledReg is too narrow"
) ? void (0) : __assert_fail ("cast<IntegerType>(IntPtrTy)->getBitWidth() < cast<IntegerType>(V->getType())->getBitWidth() && \"We can't transform if ScaledReg is too narrow\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4525, __extension__ __PRETTY_FUNCTION__))
4524 cast<IntegerType>(V->getType())->getBitWidth() &&(static_cast <bool> (cast<IntegerType>(IntPtrTy)->
getBitWidth() < cast<IntegerType>(V->getType())->
getBitWidth() && "We can't transform if ScaledReg is too narrow"
) ? void (0) : __assert_fail ("cast<IntegerType>(IntPtrTy)->getBitWidth() < cast<IntegerType>(V->getType())->getBitWidth() && \"We can't transform if ScaledReg is too narrow\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4525, __extension__ __PRETTY_FUNCTION__))
4525 "We can't transform if ScaledReg is too narrow")(static_cast <bool> (cast<IntegerType>(IntPtrTy)->
getBitWidth() < cast<IntegerType>(V->getType())->
getBitWidth() && "We can't transform if ScaledReg is too narrow"
) ? void (0) : __assert_fail ("cast<IntegerType>(IntPtrTy)->getBitWidth() < cast<IntegerType>(V->getType())->getBitWidth() && \"We can't transform if ScaledReg is too narrow\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4525, __extension__ __PRETTY_FUNCTION__))
;
4526 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
4527 }
4528
4529 if (AddrMode.Scale != 1)
4530 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
4531 "sunkaddr");
4532 if (ResultIndex)
4533 ResultIndex = Builder.CreateAdd(ResultIndex, V, "sunkaddr");
4534 else
4535 ResultIndex = V;
4536 }
4537
4538 // Add in the Base Offset if present.
4539 if (AddrMode.BaseOffs) {
4540 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
4541 if (ResultIndex) {
4542 // We need to add this separately from the scale above to help with
4543 // SDAG consecutive load/store merging.
4544 if (ResultPtr->getType() != I8PtrTy)
4545 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
4546 ResultPtr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr");
4547 }
4548
4549 ResultIndex = V;
4550 }
4551
4552 if (!ResultIndex) {
4553 SunkAddr = ResultPtr;
4554 } else {
4555 if (ResultPtr->getType() != I8PtrTy)
4556 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
4557 SunkAddr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr");
4558 }
4559
4560 if (SunkAddr->getType() != Addr->getType())
4561 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->getType());
4562 }
4563 } else {
4564 // We'd require a ptrtoint/inttoptr down the line, which we can't do for
4565 // non-integral pointers, so in that case bail out now.
4566 Type *BaseTy = AddrMode.BaseReg ? AddrMode.BaseReg->getType() : nullptr;
4567 Type *ScaleTy = AddrMode.Scale ? AddrMode.ScaledReg->getType() : nullptr;
4568 PointerType *BasePtrTy = dyn_cast_or_null<PointerType>(BaseTy);
4569 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
4570 if (DL->isNonIntegralPointerType(Addr->getType()) ||
4571 (BasePtrTy && DL->isNonIntegralPointerType(BasePtrTy)) ||
4572 (ScalePtrTy && DL->isNonIntegralPointerType(ScalePtrTy)) ||
4573 (AddrMode.BaseGV &&
4574 DL->isNonIntegralPointerType(AddrMode.BaseGV->getType())))
4575 return false;
4576
4577 LLVM_DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrModedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: SINKING nonlocal addrmode: "
<< AddrMode << " for " << *MemoryInst <<
"\n"; } } while (false)
4578 << " for " << *MemoryInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("codegenprepare")) { dbgs() << "CGP: SINKING nonlocal addrmode: "
<< AddrMode << " for " << *MemoryInst <<
"\n"; } } while (false)
;
4579 Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
4580 Value *Result = nullptr;
4581
4582 // Start with the base register. Do this first so that subsequent address
4583 // matching finds it last, which will prevent it from trying to match it
4584 // as the scaled value in case it happens to be a mul. That would be
4585 // problematic if we've sunk a different mul for the scale, because then
4586 // we'd end up sinking both muls.
4587 if (AddrMode.BaseReg) {
4588 Value *V = AddrMode.BaseReg;
4589 if (V->getType()->isPointerTy())
4590 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
4591 if (V->getType() != IntPtrTy)
4592 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
4593 Result = V;
4594 }
4595
4596 // Add the scale value.
4597 if (AddrMode.Scale) {
4598 Value *V = AddrMode.ScaledReg;
4599 if (V->getType() == IntPtrTy) {
4600 // done.
4601 } else if (V->getType()->isPointerTy()) {
4602 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
4603 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
4604 cast<IntegerType>(V->getType())->getBitWidth()) {
4605 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
4606 } else {
4607 // It is only safe to sign extend the BaseReg if we know that the math
4608 // required to create it did not overflow before we extend it. Since
4609 // the original IR value was tossed in favor of a constant back when
4610 // the AddrMode was created we need to bail out gracefully if widths
4611 // do not match instead of extending it.
4612 Instruction *I = dyn_cast_or_null<Instruction>(Result);
4613 if (I && (Result != AddrMode.BaseReg))
4614 I->eraseFromParent();
4615 return false;
4616 }
4617 if (AddrMode.Scale != 1)
4618 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
4619 "sunkaddr");
4620 if (Result)
4621 Result = Builder.CreateAdd(Result, V, "sunkaddr");
4622 else
4623 Result = V;
4624 }
4625
4626 // Add in the BaseGV if present.
4627 if (AddrMode.BaseGV) {
4628 Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr");
4629 if (Result)
4630 Result = Builder.CreateAdd(Result, V, "sunkaddr");
4631 else
4632 Result = V;
4633 }
4634
4635 // Add in the Base Offset if present.
4636 if (AddrMode.BaseOffs) {
4637 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
4638 if (Result)
4639 Result = Builder.CreateAdd(Result, V, "sunkaddr");
4640 else
4641 Result = V;
4642 }
4643
4644 if (!Result)
4645 SunkAddr = Constant::getNullValue(Addr->getType());
4646 else
4647 SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
4648 }
4649
4650 MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
4651 // Store the newly computed address into the cache. In the case we reused a
4652 // value, this should be idempotent.
4653 SunkAddrs[Addr] = WeakTrackingVH(SunkAddr);
4654
4655 // If we have no uses, recursively delete the value and all dead instructions
4656 // using it.
4657 if (Repl->use_empty()) {
4658 // This can cause recursive deletion, which can invalidate our iterator.
4659 // Use a WeakTrackingVH to hold onto it in case this happens.
4660 Value *CurValue = &*CurInstIterator;
4661 WeakTrackingVH IterHandle(CurValue);
4662 BasicBlock *BB = CurInstIterator->getParent();
4663
4664 RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo);
4665
4666 if (IterHandle != CurValue) {
4667 // If the iterator instruction was recursively deleted, start over at the
4668 // start of the block.
4669 CurInstIterator = BB->begin();
4670 SunkAddrs.clear();
4671 }
4672 }
4673 ++NumMemoryInsts;
4674 return true;
4675}
4676
4677/// If there are any memory operands, use OptimizeMemoryInst to sink their
4678/// address computing into the block when possible / profitable.
4679bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) {
4680 bool MadeChange = false;
4681
4682 const TargetRegisterInfo *TRI =
4683 TM->getSubtargetImpl(*CS->getFunction())->getRegisterInfo();
4684 TargetLowering::AsmOperandInfoVector TargetConstraints =
4685 TLI->ParseConstraints(*DL, TRI, CS);
4686 unsigned ArgNo = 0;
4687 for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
4688 TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
4689
4690 // Compute the constraint code and ConstraintType to use.
4691 TLI->ComputeConstraintToUse(OpInfo, SDValue());
4692
4693 if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
4694 OpInfo.isIndirect) {
4695 Value *OpVal = CS->getArgOperand(ArgNo++);
4696 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->getType(), ~0u);
4697 } else if (OpInfo.Type == InlineAsm::isInput)
4698 ArgNo++;
4699 }
4700
4701 return MadeChange;
4702}
4703
4704/// Check if all the uses of \p Val are equivalent (or free) zero or
4705/// sign extensions.
4706static bool hasSameExtUse(Value *Val, const TargetLowering &TLI) {
4707 assert(!Val->use_empty() && "Input must have at least one use")(static_cast <bool> (!Val->use_empty() && "Input must have at least one use"
) ? void (0) : __assert_fail ("!Val->use_empty() && \"Input must have at least one use\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4707, __extension__ __PRETTY_FUNCTION__))
;
4708 const Instruction *FirstUser = cast<Instruction>(*Val->user_begin());
4709 bool IsSExt = isa<SExtInst>(FirstUser);
4710 Type *ExtTy = FirstUser->getType();
4711 for (const User *U : Val->users()) {
4712 const Instruction *UI = cast<Instruction>(U);
4713 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
4714 return false;
4715 Type *CurTy = UI->getType();
4716 // Same input and output types: Same instruction after CSE.
4717 if (CurTy == ExtTy)
4718 continue;
4719
4720 // If IsSExt is true, we are in this situation:
4721 // a = Val
4722 // b = sext ty1 a to ty2
4723 // c = sext ty1 a to ty3
4724 // Assuming ty2 is shorter than ty3, this could be turned into:
4725 // a = Val
4726 // b = sext ty1 a to ty2
4727 // c = sext ty2 b to ty3
4728 // However, the last sext is not free.
4729 if (IsSExt)
4730 return false;
4731
4732 // This is a ZExt, maybe this is free to extend from one type to another.
4733 // In that case, we would not account for a different use.
4734 Type *NarrowTy;
4735 Type *LargeTy;
4736 if (ExtTy->getScalarType()->getIntegerBitWidth() >
4737 CurTy->getScalarType()->getIntegerBitWidth()) {
4738 NarrowTy = CurTy;
4739 LargeTy = ExtTy;
4740 } else {
4741 NarrowTy = ExtTy;
4742 LargeTy = CurTy;
4743 }
4744
4745 if (!TLI.isZExtFree(NarrowTy, LargeTy))
4746 return false;
4747 }
4748 // All uses are the same or can be derived from one another for free.
4749 return true;
4750}
4751
4752/// Try to speculatively promote extensions in \p Exts and continue
4753/// promoting through newly promoted operands recursively as far as doing so is
4754/// profitable. Save extensions profitably moved up, in \p ProfitablyMovedExts.
4755/// When some promotion happened, \p TPT contains the proper state to revert
4756/// them.
4757///
4758/// \return true if some promotion happened, false otherwise.
4759bool CodeGenPrepare::tryToPromoteExts(
4760 TypePromotionTransaction &TPT, const SmallVectorImpl<Instruction *> &Exts,
4761 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
4762 unsigned CreatedInstsCost) {
4763 bool Promoted = false;
4764
4765 // Iterate over all the extensions to try to promote them.
4766 for (auto I : Exts) {
4767 // Early check if we directly have ext(load).
4768 if (isa<LoadInst>(I->getOperand(0))) {
4769 ProfitablyMovedExts.push_back(I);
4770 continue;
4771 }
4772
4773 // Check whether or not we want to do any promotion. The reason we have
4774 // this check inside the for loop is to catch the case where an extension
4775 // is directly fed by a load because in such case the extension can be moved
4776 // up without any promotion on its operands.
4777 if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion)
4778 return false;
4779
4780 // Get the action to perform the promotion.
4781 TypePromotionHelper::Action TPH =
4782 TypePromotionHelper::getAction(I, InsertedInsts, *TLI, PromotedInsts);
4783 // Check if we can promote.
4784 if (!TPH) {
4785 // Save the current extension as we cannot move up through its operand.
4786 ProfitablyMovedExts.push_back(I);
4787 continue;
4788 }
4789
4790 // Save the current state.
4791 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4792 TPT.getRestorationPoint();
4793 SmallVector<Instruction *, 4> NewExts;
4794 unsigned NewCreatedInstsCost = 0;
4795 unsigned ExtCost = !TLI->isExtFree(I);
4796 // Promote.
4797 Value *PromotedVal = TPH(I, TPT, PromotedInsts, NewCreatedInstsCost,
4798 &NewExts, nullptr, *TLI);
4799 assert(PromotedVal &&(static_cast <bool> (PromotedVal && "TypePromotionHelper should have filtered out those cases"
) ? void (0) : __assert_fail ("PromotedVal && \"TypePromotionHelper should have filtered out those cases\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4800, __extension__ __PRETTY_FUNCTION__))
4800 "TypePromotionHelper should have filtered out those cases")(static_cast <bool> (PromotedVal && "TypePromotionHelper should have filtered out those cases"
) ? void (0) : __assert_fail ("PromotedVal && \"TypePromotionHelper should have filtered out those cases\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 4800, __extension__ __PRETTY_FUNCTION__))
;
4801
4802 // We would be able to merge only one extension in a load.
4803 // Therefore, if we have more than 1 new extension we heuristically
4804 // cut this search path, because it means we degrade the code quality.
4805 // With exactly 2, the transformation is neutral, because we will merge
4806 // one extension but leave one. However, we optimistically keep going,
4807 // because the new extension may be removed too.
4808 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
4809 // FIXME: It would be possible to propagate a negative value instead of
4810 // conservatively ceiling it to 0.
4811 TotalCreatedInstsCost =
4812 std::max((long long)0, (TotalCreatedInstsCost - ExtCost));
4813 if (!StressExtLdPromotion &&
4814 (TotalCreatedInstsCost > 1 ||
4815 !isPromotedInstructionLegal(*TLI, *DL, PromotedVal))) {
4816 // This promotion is not profitable, rollback to the previous state, and
4817 // save the current extension in ProfitablyMovedExts as the latest
4818 // speculative promotion turned out to be unprofitable.
4819 TPT.rollback(LastKnownGood);
4820 ProfitablyMovedExts.push_back(I);
4821 continue;
4822 }
4823 // Continue promoting NewExts as far as doing so is profitable.
4824 SmallVector<Instruction *, 2> NewlyMovedExts;
4825 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
4826 bool NewPromoted = false;
4827 for (auto ExtInst : NewlyMovedExts) {
4828 Instruction *MovedExt = cast<Instruction>(ExtInst);
4829 Value *ExtOperand = MovedExt->getOperand(0);
4830 // If we have reached to a load, we need this extra profitability check
4831 // as it could potentially be merged into an ext(load).
4832 if (isa<LoadInst>(ExtOperand) &&
4833 !(StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
4834 (ExtOperand->hasOneUse() || hasSameExtUse(ExtOperand, *TLI))))
4835 continue;
4836
4837 ProfitablyMovedExts.push_back(MovedExt);
4838 NewPromoted = true;
4839 }
4840
4841 // If none of speculative promotions for NewExts is profitable, rollback
4842 // and save the current extension (I) as the last profitable extension.
4843 if (!NewPromoted) {
4844 TPT.rollback(LastKnownGood);
4845 ProfitablyMovedExts.push_back(I);
4846 continue;
4847 }
4848 // The promotion is profitable.
4849 Promoted = true;
4850 }
4851 return Promoted;
4852}
4853
4854/// Merging redundant sexts when one is dominating the other.
4855bool CodeGenPrepare::mergeSExts(Function &F) {
4856 DominatorTree DT(F);
4857 bool Changed = false;
4858 for (auto &Entry : ValToSExtendedUses) {
4859 SExts &Insts = Entry.second;
4860 SExts CurPts;
4861 for (Instruction *Inst : Insts) {
4862 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
4863 Inst->getOperand(0) != Entry.first)
4864 continue;
4865 bool inserted = false;
4866 for (auto &Pt : CurPts) {
4867 if (DT.dominates(Inst, Pt)) {
4868 Pt->replaceAllUsesWith(Inst);
4869 RemovedInsts.insert(Pt);
4870 Pt->removeFromParent();
4871 Pt = Inst;
4872 inserted = true;
4873 Changed = true;
4874 break;
4875 }
4876 if (!DT.dominates(Pt, Inst))
4877 // Give up if we need to merge in a common dominator as the
4878 // experiments show it is not profitable.
4879 continue;
4880 Inst->replaceAllUsesWith(Pt);
4881 RemovedInsts.insert(Inst);
4882 Inst->removeFromParent();
4883 inserted = true;
4884 Changed = true;
4885 break;
4886 }
4887 if (!inserted)
4888 CurPts.push_back(Inst);
4889 }
4890 }
4891 return Changed;
4892}
4893
4894// Spliting large data structures so that the GEPs accessing them can have
4895// smaller offsets so that they can be sunk to the same blocks as their users.
4896// For example, a large struct starting from %base is splitted into two parts
4897// where the second part starts from %new_base.
4898//
4899// Before:
4900// BB0:
4901// %base =
4902//
4903// BB1:
4904// %gep0 = gep %base, off0
4905// %gep1 = gep %base, off1
4906// %gep2 = gep %base, off2
4907//
4908// BB2:
4909// %load1 = load %gep0
4910// %load2 = load %gep1
4911// %load3 = load %gep2
4912//
4913// After:
4914// BB0:
4915// %base =
4916// %new_base = gep %base, off0
4917//
4918// BB1:
4919// %new_gep0 = %new_base
4920// %new_gep1 = gep %new_base, off1 - off0
4921// %new_gep2 = gep %new_base, off2 - off0
4922//
4923// BB2:
4924// %load1 = load i32, i32* %new_gep0
4925// %load2 = load i32, i32* %new_gep1
4926// %load3 = load i32, i32* %new_gep2
4927//
4928// %new_gep1 and %new_gep2 can be sunk to BB2 now after the splitting because
4929// their offsets are smaller enough to fit into the addressing mode.
4930bool CodeGenPrepare::splitLargeGEPOffsets() {
4931 bool Changed = false;
4932 for (auto &Entry : LargeOffsetGEPMap) {
4933 Value *OldBase = Entry.first;
4934 SmallVectorImpl<std::pair<AssertingVH<GetElementPtrInst>, int64_t>>
4935 &LargeOffsetGEPs = Entry.second;
4936 auto compareGEPOffset =
4937 [&](const std::pair<GetElementPtrInst *, int64_t> &LHS,
4938 const std::pair<GetElementPtrInst *, int64_t> &RHS) {
4939 if (LHS.first == RHS.first)
4940 return false;
4941 if (LHS.second != RHS.second)
4942 return LHS.second < RHS.second;
4943 return LargeOffsetGEPID[LHS.first] < LargeOffsetGEPID[RHS.first];
4944 };
4945 // Sorting all the GEPs of the same data structures based on the offsets.
4946 llvm::sort(LargeOffsetGEPs.begin(), LargeOffsetGEPs.end(),
4947 compareGEPOffset);
4948 LargeOffsetGEPs.erase(
4949 std::unique(LargeOffsetGEPs.begin(), LargeOffsetGEPs.end()),
4950 LargeOffsetGEPs.end());
4951 // Skip if all the GEPs have the same offsets.
4952 if (LargeOffsetGEPs.front().second == LargeOffsetGEPs.back().second)
4953 continue;
4954 GetElementPtrInst *BaseGEP = LargeOffsetGEPs.begin()->first;
4955 int64_t BaseOffset = LargeOffsetGEPs.begin()->second;
4956 Value *NewBaseGEP = nullptr;
4957
4958 auto LargeOffsetGEP = LargeOffsetGEPs.begin();
4959 while (LargeOffsetGEP != LargeOffsetGEPs.end()) {
4960 GetElementPtrInst *GEP = LargeOffsetGEP->first;
4961 int64_t Offset = LargeOffsetGEP->second;
4962 if (Offset != BaseOffset) {
4963 TargetLowering::AddrMode AddrMode;
4964 AddrMode.BaseOffs = Offset - BaseOffset;
4965 // The result type of the GEP might not be the type of the memory
4966 // access.
4967 if (!TLI->isLegalAddressingMode(*DL, AddrMode,
4968 GEP->getResultElementType(),
4969 GEP->getAddressSpace())) {
4970 // We need to create a new base if the offset to the current base is
4971 // too large to fit into the addressing mode. So, a very large struct
4972 // may be splitted into several parts.
4973 BaseGEP = GEP;
4974 BaseOffset = Offset;
4975 NewBaseGEP = nullptr;
4976 }
4977 }
4978
4979 // Generate a new GEP to replace the current one.
4980 IRBuilder<> Builder(GEP);
4981 Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
4982 Type *I8PtrTy =
4983 Builder.getInt8PtrTy(GEP->getType()->getPointerAddressSpace());
4984 Type *I8Ty = Builder.getInt8Ty();
4985
4986 if (!NewBaseGEP) {
4987 // Create a new base if we don't have one yet. Find the insertion
4988 // pointer for the new base first.
4989 BasicBlock::iterator NewBaseInsertPt;
4990 BasicBlock *NewBaseInsertBB;
4991 if (auto *BaseI = dyn_cast<Instruction>(OldBase)) {
4992 // If the base of the struct is an instruction, the new base will be
4993 // inserted close to it.
4994 NewBaseInsertBB = BaseI->getParent();
4995 if (isa<PHINode>(BaseI))
4996 NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
4997 else if (InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
4998 NewBaseInsertBB =
4999 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest());
5000 NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
5001 } else
5002 NewBaseInsertPt = std::next(BaseI->getIterator());
5003 } else {
5004 // If the current base is an argument or global value, the new base
5005 // will be inserted to the entry block.
5006 NewBaseInsertBB = &BaseGEP->getFunction()->getEntryBlock();
5007 NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
5008 }
5009 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
5010 // Create a new base.
5011 Value *BaseIndex = ConstantInt::get(IntPtrTy, BaseOffset);
5012 NewBaseGEP = OldBase;
5013 if (NewBaseGEP->getType() != I8PtrTy)
5014 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
5015 NewBaseGEP =
5016 NewBaseBuilder.CreateGEP(I8Ty, NewBaseGEP, BaseIndex, "splitgep");
5017 NewGEPBases.insert(NewBaseGEP);
5018 }
5019
5020 Value *NewGEP = NewBaseGEP;
5021 if (Offset == BaseOffset) {
5022 if (GEP->getType() != I8PtrTy)
5023 NewGEP = Builder.CreatePointerCast(NewGEP, GEP->getType());
5024 } else {
5025 // Calculate the new offset for the new GEP.
5026 Value *Index = ConstantInt::get(IntPtrTy, Offset - BaseOffset);
5027 NewGEP = Builder.CreateGEP(I8Ty, NewBaseGEP, Index);
5028
5029 if (GEP->getType() != I8PtrTy)
5030 NewGEP = Builder.CreatePointerCast(NewGEP, GEP->getType());
5031 }
5032 GEP->replaceAllUsesWith(NewGEP);
5033 LargeOffsetGEPID.erase(GEP);
5034 LargeOffsetGEP = LargeOffsetGEPs.erase(LargeOffsetGEP);
5035 GEP->eraseFromParent();
5036 Changed = true;
5037 }
5038 }
5039 return Changed;
5040}
5041
5042/// Return true, if an ext(load) can be formed from an extension in
5043/// \p MovedExts.
5044bool CodeGenPrepare::canFormExtLd(
5045 const SmallVectorImpl<Instruction *> &MovedExts, LoadInst *&LI,
5046 Instruction *&Inst, bool HasPromoted) {
5047 for (auto *MovedExtInst : MovedExts) {
5048 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
5049 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
5050 Inst = MovedExtInst;
5051 break;
5052 }
5053 }
5054 if (!LI)
5055 return false;
5056
5057 // If they're already in the same block, there's nothing to do.
5058 // Make the cheap checks first if we did not promote.
5059 // If we promoted, we need to check if it is indeed profitable.
5060 if (!HasPromoted && LI->getParent() == Inst->getParent())
5061 return false;
5062
5063 return TLI->isExtLoad(LI, Inst, *DL);
5064}
5065
5066/// Move a zext or sext fed by a load into the same basic block as the load,
5067/// unless conditions are unfavorable. This allows SelectionDAG to fold the
5068/// extend into the load.
5069///
5070/// E.g.,
5071/// \code
5072/// %ld = load i32* %addr
5073/// %add = add nuw i32 %ld, 4
5074/// %zext = zext i32 %add to i64
5075// \endcode
5076/// =>
5077/// \code
5078/// %ld = load i32* %addr
5079/// %zext = zext i32 %ld to i64
5080/// %add = add nuw i64 %zext, 4
5081/// \encode
5082/// Note that the promotion in %add to i64 is done in tryToPromoteExts(), which
5083/// allow us to match zext(load i32*) to i64.
5084///
5085/// Also, try to promote the computations used to obtain a sign extended
5086/// value used into memory accesses.
5087/// E.g.,
5088/// \code
5089/// a = add nsw i32 b, 3
5090/// d = sext i32 a to i64
5091/// e = getelementptr ..., i64 d
5092/// \endcode
5093/// =>
5094/// \code
5095/// f = sext i32 b to i64
5096/// a = add nsw i64 f, 3
5097/// e = getelementptr ..., i64 a
5098/// \endcode
5099///
5100/// \p Inst[in/out] the extension may be modified during the process if some
5101/// promotions apply.
5102bool CodeGenPrepare::optimizeExt(Instruction *&Inst) {
5103 // ExtLoad formation and address type promotion infrastructure requires TLI to
5104 // be effective.
5105 if (!TLI)
5106 return false;
5107
5108 bool AllowPromotionWithoutCommonHeader = false;
5109 /// See if it is an interesting sext operations for the address type
5110 /// promotion before trying to promote it, e.g., the ones with the right
5111 /// type and used in memory accesses.
5112 bool ATPConsiderable = TTI->shouldConsiderAddressTypePromotion(
5113 *Inst, AllowPromotionWithoutCommonHeader);
5114 TypePromotionTransaction TPT(RemovedInsts);
5115 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5116 TPT.getRestorationPoint();
5117 SmallVector<Instruction *, 1> Exts;
5118 SmallVector<Instruction *, 2> SpeculativelyMovedExts;
5119 Exts.push_back(Inst);
5120
5121 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
5122
5123 // Look for a load being extended.
5124 LoadInst *LI = nullptr;
5125 Instruction *ExtFedByLoad;
5126
5127 // Try to promote a chain of computation if it allows to form an extended
5128 // load.
5129 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
5130 assert(LI && ExtFedByLoad && "Expect a valid load and extension")(static_cast <bool> (LI && ExtFedByLoad &&
"Expect a valid load and extension") ? void (0) : __assert_fail
("LI && ExtFedByLoad && \"Expect a valid load and extension\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5130, __extension__ __PRETTY_FUNCTION__))
;
5131 TPT.commit();
5132 // Move the extend into the same block as the load
5133 ExtFedByLoad->moveAfter(LI);
5134 // CGP does not check if the zext would be speculatively executed when moved
5135 // to the same basic block as the load. Preserving its original location
5136 // would pessimize the debugging experience, as well as negatively impact
5137 // the quality of sample pgo. We don't want to use "line 0" as that has a
5138 // size cost in the line-table section and logically the zext can be seen as
5139 // part of the load. Therefore we conservatively reuse the same debug
5140 // location for the load and the zext.
5141 ExtFedByLoad->setDebugLoc(LI->getDebugLoc());
5142 ++NumExtsMoved;
5143 Inst = ExtFedByLoad;
5144 return true;
5145 }
5146
5147 // Continue promoting SExts if known as considerable depending on targets.
5148 if (ATPConsiderable &&
5149 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
5150 HasPromoted, TPT, SpeculativelyMovedExts))
5151 return true;
5152
5153 TPT.rollback(LastKnownGood);
5154 return false;
5155}
5156
5157// Perform address type promotion if doing so is profitable.
5158// If AllowPromotionWithoutCommonHeader == false, we should find other sext
5159// instructions that sign extended the same initial value. However, if
5160// AllowPromotionWithoutCommonHeader == true, we expect promoting the
5161// extension is just profitable.
5162bool CodeGenPrepare::performAddressTypePromotion(
5163 Instruction *&Inst, bool AllowPromotionWithoutCommonHeader,
5164 bool HasPromoted, TypePromotionTransaction &TPT,
5165 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts) {
5166 bool Promoted = false;
5167 SmallPtrSet<Instruction *, 1> UnhandledExts;
5168 bool AllSeenFirst = true;
5169 for (auto I : SpeculativelyMovedExts) {
5170 Value *HeadOfChain = I->getOperand(0);
5171 DenseMap<Value *, Instruction *>::iterator AlreadySeen =
5172 SeenChainsForSExt.find(HeadOfChain);
5173 // If there is an unhandled SExt which has the same header, try to promote
5174 // it as well.
5175 if (AlreadySeen != SeenChainsForSExt.end()) {
5176 if (AlreadySeen->second != nullptr)
5177 UnhandledExts.insert(AlreadySeen->second);
5178 AllSeenFirst = false;
5179 }
5180 }
5181
5182 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
5183 SpeculativelyMovedExts.size() == 1)) {
5184 TPT.commit();
5185 if (HasPromoted)
5186 Promoted = true;
5187 for (auto I : SpeculativelyMovedExts) {
5188 Value *HeadOfChain = I->getOperand(0);
5189 SeenChainsForSExt[HeadOfChain] = nullptr;
5190 ValToSExtendedUses[HeadOfChain].push_back(I);
5191 }
5192 // Update Inst as promotion happen.
5193 Inst = SpeculativelyMovedExts.pop_back_val();
5194 } else {
5195 // This is the first chain visited from the header, keep the current chain
5196 // as unhandled. Defer to promote this until we encounter another SExt
5197 // chain derived from the same header.
5198 for (auto I : SpeculativelyMovedExts) {
5199 Value *HeadOfChain = I->getOperand(0);
5200 SeenChainsForSExt[HeadOfChain] = Inst;
5201 }
5202 return false;
5203 }
5204
5205 if (!AllSeenFirst && !UnhandledExts.empty())
5206 for (auto VisitedSExt : UnhandledExts) {
5207 if (RemovedInsts.count(VisitedSExt))
5208 continue;
5209 TypePromotionTransaction TPT(RemovedInsts);
5210 SmallVector<Instruction *, 1> Exts;
5211 SmallVector<Instruction *, 2> Chains;
5212 Exts.push_back(VisitedSExt);
5213 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
5214 TPT.commit();
5215 if (HasPromoted)
5216 Promoted = true;
5217 for (auto I : Chains) {
5218 Value *HeadOfChain = I->getOperand(0);
5219 // Mark this as handled.
5220 SeenChainsForSExt[HeadOfChain] = nullptr;
5221 ValToSExtendedUses[HeadOfChain].push_back(I);
5222 }
5223 }
5224 return Promoted;
5225}
5226
5227bool CodeGenPrepare::optimizeExtUses(Instruction *I) {
5228 BasicBlock *DefBB = I->getParent();
5229
5230 // If the result of a {s|z}ext and its source are both live out, rewrite all
5231 // other uses of the source with result of extension.
5232 Value *Src = I->getOperand(0);
5233 if (Src->hasOneUse())
5234 return false;
5235
5236 // Only do this xform if truncating is free.
5237 if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
5238 return false;
5239
5240 // Only safe to perform the optimization if the source is also defined in
5241 // this block.
5242 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
5243 return false;
5244
5245 bool DefIsLiveOut = false;
5246 for (User *U : I->users()) {
5247 Instruction *UI = cast<Instruction>(U);
5248
5249 // Figure out which BB this ext is used in.
5250 BasicBlock *UserBB = UI->getParent();
5251 if (UserBB == DefBB) continue;
5252 DefIsLiveOut = true;
5253 break;
5254 }
5255 if (!DefIsLiveOut)
5256 return false;
5257
5258 // Make sure none of the uses are PHI nodes.
5259 for (User *U : Src->users()) {
5260 Instruction *UI = cast<Instruction>(U);
5261 BasicBlock *UserBB = UI->getParent();
5262 if (UserBB == DefBB) continue;
5263 // Be conservative. We don't want this xform to end up introducing
5264 // reloads just before load / store instructions.
5265 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
5266 return false;
5267 }
5268
5269 // InsertedTruncs - Only insert one trunc in each block once.
5270 DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
5271
5272 bool MadeChange = false;
5273 for (Use &U : Src->uses()) {
5274 Instruction *User = cast<Instruction>(U.getUser());
5275
5276 // Figure out which BB this ext is used in.
5277 BasicBlock *UserBB = User->getParent();
5278 if (UserBB == DefBB) continue;
5279
5280 // Both src and def are live in this block. Rewrite the use.
5281 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
5282
5283 if (!InsertedTrunc) {
5284 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
5285 assert(InsertPt != UserBB->end())(static_cast <bool> (InsertPt != UserBB->end()) ? void
(0) : __assert_fail ("InsertPt != UserBB->end()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5285, __extension__ __PRETTY_FUNCTION__))
;
5286 InsertedTrunc = new TruncInst(I, Src->getType(), "", &*InsertPt);
5287 InsertedInsts.insert(InsertedTrunc);
5288 }
5289
5290 // Replace a use of the {s|z}ext source with a use of the result.
5291 U = InsertedTrunc;
5292 ++NumExtUses;
5293 MadeChange = true;
5294 }
5295
5296 return MadeChange;
5297}
5298
5299// Find loads whose uses only use some of the loaded value's bits. Add an "and"
5300// just after the load if the target can fold this into one extload instruction,
5301// with the hope of eliminating some of the other later "and" instructions using
5302// the loaded value. "and"s that are made trivially redundant by the insertion
5303// of the new "and" are removed by this function, while others (e.g. those whose
5304// path from the load goes through a phi) are left for isel to potentially
5305// remove.
5306//
5307// For example:
5308//
5309// b0:
5310// x = load i32
5311// ...
5312// b1:
5313// y = and x, 0xff
5314// z = use y
5315//
5316// becomes:
5317//
5318// b0:
5319// x = load i32
5320// x' = and x, 0xff
5321// ...
5322// b1:
5323// z = use x'
5324//
5325// whereas:
5326//
5327// b0:
5328// x1 = load i32
5329// ...
5330// b1:
5331// x2 = load i32
5332// ...
5333// b2:
5334// x = phi x1, x2
5335// y = and x, 0xff
5336//
5337// becomes (after a call to optimizeLoadExt for each load):
5338//
5339// b0:
5340// x1 = load i32
5341// x1' = and x1, 0xff
5342// ...
5343// b1:
5344// x2 = load i32
5345// x2' = and x2, 0xff
5346// ...
5347// b2:
5348// x = phi x1', x2'
5349// y = and x, 0xff
5350bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) {
5351 if (!Load->isSimple() || !Load->getType()->isIntOrPtrTy())
5352 return false;
5353
5354 // Skip loads we've already transformed.
5355 if (Load->hasOneUse() &&
5356 InsertedInsts.count(cast<Instruction>(*Load->user_begin())))
5357 return false;
5358
5359 // Look at all uses of Load, looking through phis, to determine how many bits
5360 // of the loaded value are needed.
5361 SmallVector<Instruction *, 8> WorkList;
5362 SmallPtrSet<Instruction *, 16> Visited;
5363 SmallVector<Instruction *, 8> AndsToMaybeRemove;
5364 for (auto *U : Load->users())
5365 WorkList.push_back(cast<Instruction>(U));
5366
5367 EVT LoadResultVT = TLI->getValueType(*DL, Load->getType());
5368 unsigned BitWidth = LoadResultVT.getSizeInBits();
5369 APInt DemandBits(BitWidth, 0);
5370 APInt WidestAndBits(BitWidth, 0);
5371
5372 while (!WorkList.empty()) {
5373 Instruction *I = WorkList.back();
5374 WorkList.pop_back();
5375
5376 // Break use-def graph loops.
5377 if (!Visited.insert(I).second)
5378 continue;
5379
5380 // For a PHI node, push all of its users.
5381 if (auto *Phi = dyn_cast<PHINode>(I)) {
5382 for (auto *U : Phi->users())
5383 WorkList.push_back(cast<Instruction>(U));
5384 continue;
5385 }
5386
5387 switch (I->getOpcode()) {
5388 case Instruction::And: {
5389 auto *AndC = dyn_cast<ConstantInt>(I->getOperand(1));
5390 if (!AndC)
5391 return false;
5392 APInt AndBits = AndC->getValue();
5393 DemandBits |= AndBits;
5394 // Keep track of the widest and mask we see.
5395 if (AndBits.ugt(WidestAndBits))
5396 WidestAndBits = AndBits;
5397 if (AndBits == WidestAndBits && I->getOperand(0) == Load)
5398 AndsToMaybeRemove.push_back(I);
5399 break;
5400 }
5401
5402 case Instruction::Shl: {
5403 auto *ShlC = dyn_cast<ConstantInt>(I->getOperand(1));
5404 if (!ShlC)
5405 return false;
5406 uint64_t ShiftAmt = ShlC->getLimitedValue(BitWidth - 1);
5407 DemandBits.setLowBits(BitWidth - ShiftAmt);
5408 break;
5409 }
5410
5411 case Instruction::Trunc: {
5412 EVT TruncVT = TLI->getValueType(*DL, I->getType());
5413 unsigned TruncBitWidth = TruncVT.getSizeInBits();
5414 DemandBits.setLowBits(TruncBitWidth);
5415 break;
5416 }
5417
5418 default:
5419 return false;
5420 }
5421 }
5422
5423 uint32_t ActiveBits = DemandBits.getActiveBits();
5424 // Avoid hoisting (and (load x) 1) since it is unlikely to be folded by the
5425 // target even if isLoadExtLegal says an i1 EXTLOAD is valid. For example,
5426 // for the AArch64 target isLoadExtLegal(ZEXTLOAD, i32, i1) returns true, but
5427 // (and (load x) 1) is not matched as a single instruction, rather as a LDR
5428 // followed by an AND.
5429 // TODO: Look into removing this restriction by fixing backends to either
5430 // return false for isLoadExtLegal for i1 or have them select this pattern to
5431 // a single instruction.
5432 //
5433 // Also avoid hoisting if we didn't see any ands with the exact DemandBits
5434 // mask, since these are the only ands that will be removed by isel.
5435 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
5436 WidestAndBits != DemandBits)
5437 return false;
5438
5439 LLVMContext &Ctx = Load->getType()->getContext();
5440 Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits);
5441 EVT TruncVT = TLI->getValueType(*DL, TruncTy);
5442
5443 // Reject cases that won't be matched as extloads.
5444 if (!LoadResultVT.bitsGT(TruncVT) || !TruncVT.isRound() ||
5445 !TLI->isLoadExtLegal(ISD::ZEXTLOAD, LoadResultVT, TruncVT))
5446 return false;
5447
5448 IRBuilder<> Builder(Load->getNextNode());
5449 auto *NewAnd = dyn_cast<Instruction>(
5450 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
5451 // Mark this instruction as "inserted by CGP", so that other
5452 // optimizations don't touch it.
5453 InsertedInsts.insert(NewAnd);
5454
5455 // Replace all uses of load with new and (except for the use of load in the
5456 // new and itself).
5457 Load->replaceAllUsesWith(NewAnd);
5458 NewAnd->setOperand(0, Load);
5459
5460 // Remove any and instructions that are now redundant.
5461 for (auto *And : AndsToMaybeRemove)
5462 // Check that the and mask is the same as the one we decided to put on the
5463 // new and.
5464 if (cast<ConstantInt>(And->getOperand(1))->getValue() == DemandBits) {
5465 And->replaceAllUsesWith(NewAnd);
5466 if (&*CurInstIterator == And)
5467 CurInstIterator = std::next(And->getIterator());
5468 And->eraseFromParent();
5469 ++NumAndUses;
5470 }
5471
5472 ++NumAndsAdded;
5473 return true;
5474}
5475
5476/// Check if V (an operand of a select instruction) is an expensive instruction
5477/// that is only used once.
5478static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V) {
5479 auto *I = dyn_cast<Instruction>(V);
5480 // If it's safe to speculatively execute, then it should not have side
5481 // effects; therefore, it's safe to sink and possibly *not* execute.
5482 return I && I->hasOneUse() && isSafeToSpeculativelyExecute(I) &&
5483 TTI->getUserCost(I) >= TargetTransformInfo::TCC_Expensive;
5484}
5485
5486/// Returns true if a SelectInst should be turned into an explicit branch.
5487static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI,
5488 const TargetLowering *TLI,
5489 SelectInst *SI) {
5490 // If even a predictable select is cheap, then a branch can't be cheaper.
5491 if (!TLI->isPredictableSelectExpensive())
5492 return false;
5493
5494 // FIXME: This should use the same heuristics as IfConversion to determine
5495 // whether a select is better represented as a branch.
5496
5497 // If metadata tells us that the select condition is obviously predictable,
5498 // then we want to replace the select with a branch.
5499 uint64_t TrueWeight, FalseWeight;
5500 if (SI->extractProfMetadata(TrueWeight, FalseWeight)) {
5501 uint64_t Max = std::max(TrueWeight, FalseWeight);
5502 uint64_t Sum = TrueWeight + FalseWeight;
5503 if (Sum != 0) {
5504 auto Probability = BranchProbability::getBranchProbability(Max, Sum);
5505 if (Probability > TLI->getPredictableBranchThreshold())
5506 return true;
5507 }
5508 }
5509
5510 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
5511
5512 // If a branch is predictable, an out-of-order CPU can avoid blocking on its
5513 // comparison condition. If the compare has more than one use, there's
5514 // probably another cmov or setcc around, so it's not worth emitting a branch.
5515 if (!Cmp || !Cmp->hasOneUse())
5516 return false;
5517
5518 // If either operand of the select is expensive and only needed on one side
5519 // of the select, we should form a branch.
5520 if (sinkSelectOperand(TTI, SI->getTrueValue()) ||
5521 sinkSelectOperand(TTI, SI->getFalseValue()))
5522 return true;
5523
5524 return false;
5525}
5526
5527/// If \p isTrue is true, return the true value of \p SI, otherwise return
5528/// false value of \p SI. If the true/false value of \p SI is defined by any
5529/// select instructions in \p Selects, look through the defining select
5530/// instruction until the true/false value is not defined in \p Selects.
5531static Value *getTrueOrFalseValue(
5532 SelectInst *SI, bool isTrue,
5533 const SmallPtrSet<const Instruction *, 2> &Selects) {
5534 Value *V;
44
'V' declared without an initial value
5535
5536 for (SelectInst *DefSI = SI; DefSI != nullptr && Selects.count(DefSI);
45
Loop condition is false. Execution continues on line 5542
5537 DefSI = dyn_cast<SelectInst>(V)) {
5538 assert(DefSI->getCondition() == SI->getCondition() &&(static_cast <bool> (DefSI->getCondition() == SI->
getCondition() && "The condition of DefSI does not match with SI"
) ? void (0) : __assert_fail ("DefSI->getCondition() == SI->getCondition() && \"The condition of DefSI does not match with SI\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5539, __extension__ __PRETTY_FUNCTION__))
5539 "The condition of DefSI does not match with SI")(static_cast <bool> (DefSI->getCondition() == SI->
getCondition() && "The condition of DefSI does not match with SI"
) ? void (0) : __assert_fail ("DefSI->getCondition() == SI->getCondition() && \"The condition of DefSI does not match with SI\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5539, __extension__ __PRETTY_FUNCTION__))
;
5540 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
5541 }
5542 return V;
46
Undefined or garbage value returned to caller
5543}
5544
5545/// If we have a SelectInst that will likely profit from branch prediction,
5546/// turn it into a branch.
5547bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
5548 // Find all consecutive select instructions that share the same condition.
5549 SmallVector<SelectInst *, 2> ASI;
5550 ASI.push_back(SI);
5551 for (BasicBlock::iterator It = ++BasicBlock::iterator(SI);
29
Loop condition is false. Execution continues on line 5561
5552 It != SI->getParent()->end(); ++It) {
5553 SelectInst *I = dyn_cast<SelectInst>(&*It);
5554 if (I && SI->getCondition() == I->getCondition()) {
5555 ASI.push_back(I);
5556 } else {
5557 break;
5558 }
5559 }
5560
5561 SelectInst *LastSI = ASI.back();
5562 // Increment the current iterator to skip all the rest of select instructions
5563 // because they will be either "not lowered" or "all lowered" to branch.
5564 CurInstIterator = std::next(LastSI->getIterator());
5565
5566 bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
30
Assuming the condition is false
5567
5568 // Can we convert the 'select' to CF ?
5569 if (DisableSelectToBranch || OptSize || !TLI || VectorCond ||
31
Assuming the condition is false
32
Assuming the condition is false
33
Assuming the condition is false
35
Taking false branch
5570 SI->getMetadata(LLVMContext::MD_unpredictable))
34
Assuming the condition is false
5571 return false;
5572
5573 TargetLowering::SelectSupportKind SelectKind;
5574 if (VectorCond)
36
Taking false branch
5575 SelectKind = TargetLowering::VectorMaskSelect;
5576 else if (SI->getType()->isVectorTy())
37
Taking false branch
5577 SelectKind = TargetLowering::ScalarCondVectorVal;
5578 else
5579 SelectKind = TargetLowering::ScalarValSelect;
5580
5581 if (TLI->isSelectSupported(SelectKind) &&
38
Assuming the condition is false
5582 !isFormingBranchFromSelectProfitable(TTI, TLI, SI))
5583 return false;
5584
5585 ModifiedDT = true;
5586
5587 // Transform a sequence like this:
5588 // start:
5589 // %cmp = cmp uge i32 %a, %b
5590 // %sel = select i1 %cmp, i32 %c, i32 %d
5591 //
5592 // Into:
5593 // start:
5594 // %cmp = cmp uge i32 %a, %b
5595 // br i1 %cmp, label %select.true, label %select.false
5596 // select.true:
5597 // br label %select.end
5598 // select.false:
5599 // br label %select.end
5600 // select.end:
5601 // %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ]
5602 //
5603 // In addition, we may sink instructions that produce %c or %d from
5604 // the entry block into the destination(s) of the new branch.
5605 // If the true or false blocks do not contain a sunken instruction, that
5606 // block and its branch may be optimized away. In that case, one side of the
5607 // first branch will point directly to select.end, and the corresponding PHI
5608 // predecessor block will be the start block.
5609
5610 // First, we split the block containing the select into 2 blocks.
5611 BasicBlock *StartBlock = SI->getParent();
5612 BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(LastSI));
5613 BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
5614
5615 // Delete the unconditional branch that was just created by the split.
5616 StartBlock->getTerminator()->eraseFromParent();
5617
5618 // These are the new basic blocks for the conditional branch.
5619 // At least one will become an actual new basic block.
5620 BasicBlock *TrueBlock = nullptr;
5621 BasicBlock *FalseBlock = nullptr;
5622 BranchInst *TrueBranch = nullptr;
5623 BranchInst *FalseBranch = nullptr;
5624
5625 // Sink expensive instructions into the conditional blocks to avoid executing
5626 // them speculatively.
5627 for (SelectInst *SI : ASI) {
39
Assuming '__begin1' is equal to '__end1'
5628 if (sinkSelectOperand(TTI, SI->getTrueValue())) {
5629 if (TrueBlock == nullptr) {
5630 TrueBlock = BasicBlock::Create(SI->getContext(), "select.true.sink",
5631 EndBlock->getParent(), EndBlock);
5632 TrueBranch = BranchInst::Create(EndBlock, TrueBlock);
5633 }
5634 auto *TrueInst = cast<Instruction>(SI->getTrueValue());
5635 TrueInst->moveBefore(TrueBranch);
5636 }
5637 if (sinkSelectOperand(TTI, SI->getFalseValue())) {
5638 if (FalseBlock == nullptr) {
5639 FalseBlock = BasicBlock::Create(SI->getContext(), "select.false.sink",
5640 EndBlock->getParent(), EndBlock);
5641 FalseBranch = BranchInst::Create(EndBlock, FalseBlock);
5642 }
5643 auto *FalseInst = cast<Instruction>(SI->getFalseValue());
5644 FalseInst->moveBefore(FalseBranch);
5645 }
5646 }
5647
5648 // If there was nothing to sink, then arbitrarily choose the 'false' side
5649 // for a new input value to the PHI.
5650 if (TrueBlock == FalseBlock) {
40
Taking true branch
5651 assert(TrueBlock == nullptr &&(static_cast <bool> (TrueBlock == nullptr && "Unexpected basic block transform while optimizing select"
) ? void (0) : __assert_fail ("TrueBlock == nullptr && \"Unexpected basic block transform while optimizing select\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5652, __extension__ __PRETTY_FUNCTION__))
5652 "Unexpected basic block transform while optimizing select")(static_cast <bool> (TrueBlock == nullptr && "Unexpected basic block transform while optimizing select"
) ? void (0) : __assert_fail ("TrueBlock == nullptr && \"Unexpected basic block transform while optimizing select\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5652, __extension__ __PRETTY_FUNCTION__))
;
5653
5654 FalseBlock = BasicBlock::Create(SI->getContext(), "select.false",
5655 EndBlock->getParent(), EndBlock);
5656 BranchInst::Create(EndBlock, FalseBlock);
5657 }
5658
5659 // Insert the real conditional branch based on the original condition.
5660 // If we did not create a new block for one of the 'true' or 'false' paths
5661 // of the condition, it means that side of the branch goes to the end block
5662 // directly and the path originates from the start block from the point of
5663 // view of the new PHI.
5664 BasicBlock *TT, *FT;
5665 if (TrueBlock == nullptr) {
41
Taking true branch
5666 TT = EndBlock;
5667 FT = FalseBlock;
5668 TrueBlock = StartBlock;
5669 } else if (FalseBlock == nullptr) {
5670 TT = TrueBlock;
5671 FT = EndBlock;
5672 FalseBlock = StartBlock;
5673 } else {
5674 TT = TrueBlock;
5675 FT = FalseBlock;
5676 }
5677 IRBuilder<>(SI).CreateCondBr(SI->getCondition(), TT, FT, SI);
5678
5679 SmallPtrSet<const Instruction *, 2> INS;
5680 INS.insert(ASI.begin(), ASI.end());
5681 // Use reverse iterator because later select may use the value of the
5682 // earlier select, and we need to propagate value through earlier select
5683 // to get the PHI operand.
5684 for (auto It = ASI.rbegin(); It != ASI.rend(); ++It) {
42
Loop condition is true. Entering loop body
5685 SelectInst *SI = *It;
5686 // The select itself is replaced with a PHI Node.
5687 PHINode *PN = PHINode::Create(SI->getType(), 2, "", &EndBlock->front());
5688 PN->takeName(SI);
5689 PN->addIncoming(getTrueOrFalseValue(SI, true, INS), TrueBlock);
43
Calling 'getTrueOrFalseValue'
5690 PN->addIncoming(getTrueOrFalseValue(SI, false, INS), FalseBlock);
5691
5692 SI->replaceAllUsesWith(PN);
5693 SI->eraseFromParent();
5694 INS.erase(SI);
5695 ++NumSelectsExpanded;
5696 }
5697
5698 // Instruct OptimizeBlock to skip to the next block.
5699 CurInstIterator = StartBlock->end();
5700 return true;
5701}
5702
5703static bool isBroadcastShuffle(ShuffleVectorInst *SVI) {
5704 SmallVector<int, 16> Mask(SVI->getShuffleMask());
5705 int SplatElem = -1;
5706 for (unsigned i = 0; i < Mask.size(); ++i) {
5707 if (SplatElem != -1 && Mask[i] != -1 && Mask[i] != SplatElem)
5708 return false;
5709 SplatElem = Mask[i];
5710 }
5711
5712 return true;
5713}
5714
5715/// Some targets have expensive vector shifts if the lanes aren't all the same
5716/// (e.g. x86 only introduced "vpsllvd" and friends with AVX2). In these cases
5717/// it's often worth sinking a shufflevector splat down to its use so that
5718/// codegen can spot all lanes are identical.
5719bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
5720 BasicBlock *DefBB = SVI->getParent();
5721
5722 // Only do this xform if variable vector shifts are particularly expensive.
5723 if (!TLI || !TLI->isVectorShiftByScalarCheap(SVI->getType()))
5724 return false;
5725
5726 // We only expect better codegen by sinking a shuffle if we can recognise a
5727 // constant splat.
5728 if (!isBroadcastShuffle(SVI))
5729 return false;
5730
5731 // InsertedShuffles - Only insert a shuffle in each block once.
5732 DenseMap<BasicBlock*, Instruction*> InsertedShuffles;
5733
5734 bool MadeChange = false;
5735 for (User *U : SVI->users()) {
5736 Instruction *UI = cast<Instruction>(U);
5737
5738 // Figure out which BB this ext is used in.
5739 BasicBlock *UserBB = UI->getParent();
5740 if (UserBB == DefBB) continue;
5741
5742 // For now only apply this when the splat is used by a shift instruction.
5743 if (!UI->isShift()) continue;
5744
5745 // Everything checks out, sink the shuffle if the user's block doesn't
5746 // already have a copy.
5747 Instruction *&InsertedShuffle = InsertedShuffles[UserBB];
5748
5749 if (!InsertedShuffle) {
5750 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
5751 assert(InsertPt != UserBB->end())(static_cast <bool> (InsertPt != UserBB->end()) ? void
(0) : __assert_fail ("InsertPt != UserBB->end()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/CodeGenPrepare.cpp"
, 5751, __extension__ __PRETTY_FUNCTION__))
;
5752 InsertedShuffle =
5753 new ShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1),
5754 SVI->getOperand(2), "", &*InsertPt);
5755 }
5756
5757 UI->replaceUsesOfWith(SVI, InsertedShuffle);
5758 MadeChange = true;
5759 }
5760
5761 // If we removed all uses, nuke the shuffle.
5762 if (SVI->use_empty()) {
5763 SVI->eraseFromParent();
5764 MadeChange = true;
5765 }
5766
5767 return MadeChange;
5768}
5769
5770bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) {
5771 if (!TLI || !DL)
5772 return false;
5773
5774 Value *Cond = SI->getCondition();
5775 Type *OldType = Cond->getType();
5776 LLVMContext &Context = Cond->getContext();
5777 MVT RegType = TLI->getRegisterType(Context, TLI->getValueType(*DL, OldType));
5778 unsigned RegWidth = RegType.getSizeInBits();
5779
5780 if (RegWidth <= cast<IntegerType>(OldType)->getBitWidth())
5781 return false;
5782
5783 // If the register width is greater than the type width, expand the condition
5784 // of the switch instruction and each case constant to the width of the
5785 // register. By widening the type of the switch condition, subsequent
5786 // comparisons (for case comparisons) will not need to be extended to the
5787 // preferred register width, so we will potentially eliminate N-1 extends,
5788 // where N is the number of cases in the switch.
5789 auto *NewType = Type::getIntNTy(Context, RegWidth);
5790
5791 // Zero-extend the switch condition and case constants unless the switch
5792 // condition is a function argument that is already being sign-extended.
5793 // In that case, we can avoid an unnecessary mask/extension by sign-extending
5794 // everything instead.
5795 Instruction::CastOps ExtType = Instruction::ZExt;
5796 if (auto *Arg = dyn_cast<Argument>(Cond))
5797 if (Arg->hasSExtAttr())
5798 ExtType = Instruction::SExt;
5799
5800 auto *ExtInst = CastInst::Create(ExtType, Cond, NewType);
5801 ExtInst->insertBefore(SI);
5802 SI->setCondition(ExtInst);
5803 for (auto Case : SI->cases()) {
5804 APInt NarrowConst = Case.getCaseValue()->getValue();
5805 APInt WideConst = (ExtType == Instruction::ZExt) ?
5806 NarrowConst.zext(RegWidth) : NarrowConst.sext(RegWidth);
5807 Case.setValue(ConstantInt::get(Context, WideConst));
5808 }
5809
5810 return true;
5811}
5812
5813
5814namespace {
5815
5816/// Helper class to promote a scalar operation to a vector one.
5817/// This class is used to move downward extractelement transition.
5818/// E.g.,
5819/// a = vector_op <2 x i32>
5820/// b = extractelement <2 x i32> a, i32 0
5821/// c = scalar_op b
5822/// store c
5823///
5824/// =>
5825/// a = vector_op <2 x i32>
5826/// c = vector_op a (equivalent to scalar_op on the related lane)
5827/// * d = extractelement <2 x i32> c, i32 0
5828/// * store d
5829/// Assuming both extractelement and store can be combine, we get rid of the
5830/// transition.
5831class VectorPromoteHelper {
5832 /// DataLayout associated with the current module.
5833 const DataLayout &DL;
5834
5835 /// Used to perform some checks on the legality of vector operations.
5836