Bug Summary

File:build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/CodeGen/CodeGenPrepare.cpp
Warning:line 2386, column 10
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name CodeGenPrepare.cpp -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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/CodeGen -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/CodeGen -I include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-09-04-125545-48738-1 -x c++ /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/CodeGen/CodeGenPrepare.cpp

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/CodeGen/CodeGenPrepare.cpp

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