Bug Summary

File:llvm/include/llvm/IR/DataLayout.h
Warning:line 395, column 38
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 -disable-llvm-verifier -discard-value-names -main-file-name ScalarEvolutionExpander.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Transforms/Utils -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-28-092409-31635-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains the implementation of the scalar evolution expander,
10// which is used to generate the code corresponding to a given scalar evolution
11// expression.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallSet.h"
18#include "llvm/Analysis/InstructionSimplify.h"
19#include "llvm/Analysis/LoopInfo.h"
20#include "llvm/Analysis/TargetTransformInfo.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/Dominators.h"
23#include "llvm/IR/IntrinsicInst.h"
24#include "llvm/IR/LLVMContext.h"
25#include "llvm/IR/Module.h"
26#include "llvm/IR/PatternMatch.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30#include "llvm/Transforms/Utils/LoopUtils.h"
31
32using namespace llvm;
33
34cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
35 "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
36 cl::desc("When performing SCEV expansion only if it is cheap to do, this "
37 "controls the budget that is considered cheap (default = 4)"));
38
39using namespace PatternMatch;
40
41/// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
42/// reusing an existing cast if a suitable one (= dominating IP) exists, or
43/// creating a new one.
44Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
45 Instruction::CastOps Op,
46 BasicBlock::iterator IP) {
47 // This function must be called with the builder having a valid insertion
48 // point. It doesn't need to be the actual IP where the uses of the returned
49 // cast will be added, but it must dominate such IP.
50 // We use this precondition to produce a cast that will dominate all its
51 // uses. In particular, this is crucial for the case where the builder's
52 // insertion point *is* the point where we were asked to put the cast.
53 // Since we don't know the builder's insertion point is actually
54 // where the uses will be added (only that it dominates it), we are
55 // not allowed to move it.
56 BasicBlock::iterator BIP = Builder.GetInsertPoint();
57
58 Instruction *Ret = nullptr;
59
60 // Check to see if there is already a cast!
61 for (User *U : V->users()) {
62 if (U->getType() != Ty)
63 continue;
64 CastInst *CI = dyn_cast<CastInst>(U);
65 if (!CI || CI->getOpcode() != Op)
66 continue;
67
68 // Found a suitable cast that is at IP or comes before IP. Use it. Note that
69 // the cast must also properly dominate the Builder's insertion point.
70 if (IP->getParent() == CI->getParent() && &*BIP != CI &&
71 (&*IP == CI || CI->comesBefore(&*IP))) {
72 Ret = CI;
73 break;
74 }
75 }
76
77 // Create a new cast.
78 if (!Ret) {
79 Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
80 rememberInstruction(Ret);
81 }
82
83 // We assert at the end of the function since IP might point to an
84 // instruction with different dominance properties than a cast
85 // (an invoke for example) and not dominate BIP (but the cast does).
86 assert(SE.DT.dominates(Ret, &*BIP))((SE.DT.dominates(Ret, &*BIP)) ? static_cast<void> (
0) : __assert_fail ("SE.DT.dominates(Ret, &*BIP)", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 86, __PRETTY_FUNCTION__))
;
87
88 return Ret;
89}
90
91BasicBlock::iterator
92SCEVExpander::findInsertPointAfter(Instruction *I, Instruction *MustDominate) {
93 BasicBlock::iterator IP = ++I->getIterator();
94 if (auto *II = dyn_cast<InvokeInst>(I))
95 IP = II->getNormalDest()->begin();
96
97 while (isa<PHINode>(IP))
98 ++IP;
99
100 if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
101 ++IP;
102 } else if (isa<CatchSwitchInst>(IP)) {
103 IP = MustDominate->getParent()->getFirstInsertionPt();
104 } else {
105 assert(!IP->isEHPad() && "unexpected eh pad!")((!IP->isEHPad() && "unexpected eh pad!") ? static_cast
<void> (0) : __assert_fail ("!IP->isEHPad() && \"unexpected eh pad!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 105, __PRETTY_FUNCTION__))
;
106 }
107
108 // Adjust insert point to be after instructions inserted by the expander, so
109 // we can re-use already inserted instructions. Avoid skipping past the
110 // original \p MustDominate, in case it is an inserted instruction.
111 while (isInsertedInstruction(&*IP) && &*IP != MustDominate)
112 ++IP;
113
114 return IP;
115}
116
117/// InsertNoopCastOfTo - Insert a cast of V to the specified type,
118/// which must be possible with a noop cast, doing what we can to share
119/// the casts.
120Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
121 Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
122 assert((Op == Instruction::BitCast ||(((Op == Instruction::BitCast || Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!"
) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 125, __PRETTY_FUNCTION__))
12
Assuming 'Op' is not equal to BitCast
13
Assuming 'Op' is not equal to PtrToInt
14
Assuming 'Op' is equal to IntToPtr
15
'?' condition is true
123 Op == Instruction::PtrToInt ||(((Op == Instruction::BitCast || Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!"
) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 125, __PRETTY_FUNCTION__))
124 Op == Instruction::IntToPtr) &&(((Op == Instruction::BitCast || Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!"
) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 125, __PRETTY_FUNCTION__))
125 "InsertNoopCastOfTo cannot perform non-noop casts!")(((Op == Instruction::BitCast || Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!"
) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 125, __PRETTY_FUNCTION__))
;
126 assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&((SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits
(Ty) && "InsertNoopCastOfTo cannot change sizes!") ? static_cast
<void> (0) : __assert_fail ("SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && \"InsertNoopCastOfTo cannot change sizes!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 127, __PRETTY_FUNCTION__))
16
Assuming the condition is true
17
'?' condition is true
127 "InsertNoopCastOfTo cannot change sizes!")((SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits
(Ty) && "InsertNoopCastOfTo cannot change sizes!") ? static_cast
<void> (0) : __assert_fail ("SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && \"InsertNoopCastOfTo cannot change sizes!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 127, __PRETTY_FUNCTION__))
;
128
129 auto *PtrTy = dyn_cast<PointerType>(Ty);
18
Assuming 'Ty' is not a 'PointerType'
19
'PtrTy' initialized to a null pointer value
130 // inttoptr only works for integral pointers. For non-integral pointers, we
131 // can create a GEP on i8* null with the integral value as index. Note that
132 // it is safe to use GEP of null instead of inttoptr here, because only
133 // expressions already based on a GEP of null should be converted to pointers
134 // during expansion.
135 if (Op
19.1
'Op' is equal to IntToPtr
19.1
'Op' is equal to IntToPtr
== Instruction::IntToPtr && DL.isNonIntegralPointerType(PtrTy)) {
20
Passing null pointer value via 1st parameter 'PT'
21
Calling 'DataLayout::isNonIntegralPointerType'
136 auto *Int8PtrTy = Builder.getInt8PtrTy(PtrTy->getAddressSpace());
137 assert(DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&((DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&
"alloc size of i8 must by 1 byte for the GEP to be correct")
? static_cast<void> (0) : __assert_fail ("DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && \"alloc size of i8 must by 1 byte for the GEP to be correct\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 138, __PRETTY_FUNCTION__))
138 "alloc size of i8 must by 1 byte for the GEP to be correct")((DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&
"alloc size of i8 must by 1 byte for the GEP to be correct")
? static_cast<void> (0) : __assert_fail ("DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && \"alloc size of i8 must by 1 byte for the GEP to be correct\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 138, __PRETTY_FUNCTION__))
;
139 auto *GEP = Builder.CreateGEP(
140 Builder.getInt8Ty(), Constant::getNullValue(Int8PtrTy), V, "uglygep");
141 return Builder.CreateBitCast(GEP, Ty);
142 }
143 // Short-circuit unnecessary bitcasts.
144 if (Op == Instruction::BitCast) {
145 if (V->getType() == Ty)
146 return V;
147 if (CastInst *CI = dyn_cast<CastInst>(V)) {
148 if (CI->getOperand(0)->getType() == Ty)
149 return CI->getOperand(0);
150 }
151 }
152 // Short-circuit unnecessary inttoptr<->ptrtoint casts.
153 if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
154 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
155 if (CastInst *CI = dyn_cast<CastInst>(V))
156 if ((CI->getOpcode() == Instruction::PtrToInt ||
157 CI->getOpcode() == Instruction::IntToPtr) &&
158 SE.getTypeSizeInBits(CI->getType()) ==
159 SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
160 return CI->getOperand(0);
161 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
162 if ((CE->getOpcode() == Instruction::PtrToInt ||
163 CE->getOpcode() == Instruction::IntToPtr) &&
164 SE.getTypeSizeInBits(CE->getType()) ==
165 SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
166 return CE->getOperand(0);
167 }
168
169 // Fold a cast of a constant.
170 if (Constant *C = dyn_cast<Constant>(V))
171 return ConstantExpr::getCast(Op, C, Ty);
172
173 // Cast the argument at the beginning of the entry block, after
174 // any bitcasts of other arguments.
175 if (Argument *A = dyn_cast<Argument>(V)) {
176 BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();
177 while ((isa<BitCastInst>(IP) &&
178 isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
179 cast<BitCastInst>(IP)->getOperand(0) != A) ||
180 isa<DbgInfoIntrinsic>(IP))
181 ++IP;
182 return ReuseOrCreateCast(A, Ty, Op, IP);
183 }
184
185 // Cast the instruction immediately after the instruction.
186 Instruction *I = cast<Instruction>(V);
187 BasicBlock::iterator IP = findInsertPointAfter(I, &*Builder.GetInsertPoint());
188 return ReuseOrCreateCast(I, Ty, Op, IP);
189}
190
191/// InsertBinop - Insert the specified binary operator, doing a small amount
192/// of work to avoid inserting an obviously redundant operation, and hoisting
193/// to an outer loop when the opportunity is there and it is safe.
194Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
195 Value *LHS, Value *RHS,
196 SCEV::NoWrapFlags Flags, bool IsSafeToHoist) {
197 // Fold a binop with constant operands.
198 if (Constant *CLHS = dyn_cast<Constant>(LHS))
199 if (Constant *CRHS = dyn_cast<Constant>(RHS))
200 return ConstantExpr::get(Opcode, CLHS, CRHS);
201
202 // Do a quick scan to see if we have this binop nearby. If so, reuse it.
203 unsigned ScanLimit = 6;
204 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
205 // Scanning starts from the last instruction before the insertion point.
206 BasicBlock::iterator IP = Builder.GetInsertPoint();
207 if (IP != BlockBegin) {
208 --IP;
209 for (; ScanLimit; --IP, --ScanLimit) {
210 // Don't count dbg.value against the ScanLimit, to avoid perturbing the
211 // generated code.
212 if (isa<DbgInfoIntrinsic>(IP))
213 ScanLimit++;
214
215 auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) {
216 // Ensure that no-wrap flags match.
217 if (isa<OverflowingBinaryOperator>(I)) {
218 if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW))
219 return true;
220 if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW))
221 return true;
222 }
223 // Conservatively, do not use any instruction which has any of exact
224 // flags installed.
225 if (isa<PossiblyExactOperator>(I) && I->isExact())
226 return true;
227 return false;
228 };
229 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
230 IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP))
231 return &*IP;
232 if (IP == BlockBegin) break;
233 }
234 }
235
236 // Save the original insertion point so we can restore it when we're done.
237 DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
238 SCEVInsertPointGuard Guard(Builder, this);
239
240 if (IsSafeToHoist) {
241 // Move the insertion point out of as many loops as we can.
242 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
243 if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
244 BasicBlock *Preheader = L->getLoopPreheader();
245 if (!Preheader) break;
246
247 // Ok, move up a level.
248 Builder.SetInsertPoint(Preheader->getTerminator());
249 }
250 }
251
252 // If we haven't found this binop, insert it.
253 Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
254 BO->setDebugLoc(Loc);
255 if (Flags & SCEV::FlagNUW)
256 BO->setHasNoUnsignedWrap();
257 if (Flags & SCEV::FlagNSW)
258 BO->setHasNoSignedWrap();
259
260 return BO;
261}
262
263/// FactorOutConstant - Test if S is divisible by Factor, using signed
264/// division. If so, update S with Factor divided out and return true.
265/// S need not be evenly divisible if a reasonable remainder can be
266/// computed.
267static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder,
268 const SCEV *Factor, ScalarEvolution &SE,
269 const DataLayout &DL) {
270 // Everything is divisible by one.
271 if (Factor->isOne())
272 return true;
273
274 // x/x == 1.
275 if (S == Factor) {
276 S = SE.getConstant(S->getType(), 1);
277 return true;
278 }
279
280 // For a Constant, check for a multiple of the given factor.
281 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
282 // 0/x == 0.
283 if (C->isZero())
284 return true;
285 // Check for divisibility.
286 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
287 ConstantInt *CI =
288 ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
289 // If the quotient is zero and the remainder is non-zero, reject
290 // the value at this scale. It will be considered for subsequent
291 // smaller scales.
292 if (!CI->isZero()) {
293 const SCEV *Div = SE.getConstant(CI);
294 S = Div;
295 Remainder = SE.getAddExpr(
296 Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
297 return true;
298 }
299 }
300 }
301
302 // In a Mul, check if there is a constant operand which is a multiple
303 // of the given factor.
304 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
305 // Size is known, check if there is a constant operand which is a multiple
306 // of the given factor. If so, we can factor it.
307 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor))
308 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
309 if (!C->getAPInt().srem(FC->getAPInt())) {
310 SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end());
311 NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
312 S = SE.getMulExpr(NewMulOps);
313 return true;
314 }
315 }
316
317 // In an AddRec, check if both start and step are divisible.
318 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
319 const SCEV *Step = A->getStepRecurrence(SE);
320 const SCEV *StepRem = SE.getConstant(Step->getType(), 0);
321 if (!FactorOutConstant(Step, StepRem, Factor, SE, DL))
322 return false;
323 if (!StepRem->isZero())
324 return false;
325 const SCEV *Start = A->getStart();
326 if (!FactorOutConstant(Start, Remainder, Factor, SE, DL))
327 return false;
328 S = SE.getAddRecExpr(Start, Step, A->getLoop(),
329 A->getNoWrapFlags(SCEV::FlagNW));
330 return true;
331 }
332
333 return false;
334}
335
336/// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs
337/// is the number of SCEVAddRecExprs present, which are kept at the end of
338/// the list.
339///
340static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops,
341 Type *Ty,
342 ScalarEvolution &SE) {
343 unsigned NumAddRecs = 0;
344 for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i)
345 ++NumAddRecs;
346 // Group Ops into non-addrecs and addrecs.
347 SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs);
348 SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end());
349 // Let ScalarEvolution sort and simplify the non-addrecs list.
350 const SCEV *Sum = NoAddRecs.empty() ?
351 SE.getConstant(Ty, 0) :
352 SE.getAddExpr(NoAddRecs);
353 // If it returned an add, use the operands. Otherwise it simplified
354 // the sum into a single value, so just use that.
355 Ops.clear();
356 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
357 Ops.append(Add->op_begin(), Add->op_end());
358 else if (!Sum->isZero())
359 Ops.push_back(Sum);
360 // Then append the addrecs.
361 Ops.append(AddRecs.begin(), AddRecs.end());
362}
363
364/// SplitAddRecs - Flatten a list of add operands, moving addrec start values
365/// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}.
366/// This helps expose more opportunities for folding parts of the expressions
367/// into GEP indices.
368///
369static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops,
370 Type *Ty,
371 ScalarEvolution &SE) {
372 // Find the addrecs.
373 SmallVector<const SCEV *, 8> AddRecs;
374 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
375 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) {
376 const SCEV *Start = A->getStart();
377 if (Start->isZero()) break;
378 const SCEV *Zero = SE.getConstant(Ty, 0);
379 AddRecs.push_back(SE.getAddRecExpr(Zero,
380 A->getStepRecurrence(SE),
381 A->getLoop(),
382 A->getNoWrapFlags(SCEV::FlagNW)));
383 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
384 Ops[i] = Zero;
385 Ops.append(Add->op_begin(), Add->op_end());
386 e += Add->getNumOperands();
387 } else {
388 Ops[i] = Start;
389 }
390 }
391 if (!AddRecs.empty()) {
392 // Add the addrecs onto the end of the list.
393 Ops.append(AddRecs.begin(), AddRecs.end());
394 // Resort the operand list, moving any constants to the front.
395 SimplifyAddOperands(Ops, Ty, SE);
396 }
397}
398
399/// expandAddToGEP - Expand an addition expression with a pointer type into
400/// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps
401/// BasicAliasAnalysis and other passes analyze the result. See the rules
402/// for getelementptr vs. inttoptr in
403/// http://llvm.org/docs/LangRef.html#pointeraliasing
404/// for details.
405///
406/// Design note: The correctness of using getelementptr here depends on
407/// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as
408/// they may introduce pointer arithmetic which may not be safely converted
409/// into getelementptr.
410///
411/// Design note: It might seem desirable for this function to be more
412/// loop-aware. If some of the indices are loop-invariant while others
413/// aren't, it might seem desirable to emit multiple GEPs, keeping the
414/// loop-invariant portions of the overall computation outside the loop.
415/// However, there are a few reasons this is not done here. Hoisting simple
416/// arithmetic is a low-level optimization that often isn't very
417/// important until late in the optimization process. In fact, passes
418/// like InstructionCombining will combine GEPs, even if it means
419/// pushing loop-invariant computation down into loops, so even if the
420/// GEPs were split here, the work would quickly be undone. The
421/// LoopStrengthReduction pass, which is usually run quite late (and
422/// after the last InstructionCombining pass), takes care of hoisting
423/// loop-invariant portions of expressions, after considering what
424/// can be folded using target addressing modes.
425///
426Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
427 const SCEV *const *op_end,
428 PointerType *PTy,
429 Type *Ty,
430 Value *V) {
431 Type *OriginalElTy = PTy->getElementType();
432 Type *ElTy = OriginalElTy;
433 SmallVector<Value *, 4> GepIndices;
434 SmallVector<const SCEV *, 8> Ops(op_begin, op_end);
435 bool AnyNonZeroIndices = false;
436
437 // Split AddRecs up into parts as either of the parts may be usable
438 // without the other.
439 SplitAddRecs(Ops, Ty, SE);
440
441 Type *IntIdxTy = DL.getIndexType(PTy);
442
443 // Descend down the pointer's type and attempt to convert the other
444 // operands into GEP indices, at each level. The first index in a GEP
445 // indexes into the array implied by the pointer operand; the rest of
446 // the indices index into the element or field type selected by the
447 // preceding index.
448 for (;;) {
1
Loop condition is true. Entering loop body
449 // If the scale size is not 0, attempt to factor out a scale for
450 // array indexing.
451 SmallVector<const SCEV *, 8> ScaledOps;
452 if (ElTy->isSized()) {
2
Assuming the condition is false
3
Taking false branch
453 const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy);
454 if (!ElSize->isZero()) {
455 SmallVector<const SCEV *, 8> NewOps;
456 for (const SCEV *Op : Ops) {
457 const SCEV *Remainder = SE.getConstant(Ty, 0);
458 if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
459 // Op now has ElSize factored out.
460 ScaledOps.push_back(Op);
461 if (!Remainder->isZero())
462 NewOps.push_back(Remainder);
463 AnyNonZeroIndices = true;
464 } else {
465 // The operand was not divisible, so add it to the list of operands
466 // we'll scan next iteration.
467 NewOps.push_back(Op);
468 }
469 }
470 // If we made any changes, update Ops.
471 if (!ScaledOps.empty()) {
472 Ops = NewOps;
473 SimplifyAddOperands(Ops, Ty, SE);
474 }
475 }
476 }
477
478 // Record the scaled array index for this level of the type. If
479 // we didn't find any operands that could be factored, tentatively
480 // assume that element zero was selected (since the zero offset
481 // would obviously be folded away).
482 Value *Scaled =
483 ScaledOps.empty()
4
'?' condition is false
484 ? Constant::getNullValue(Ty)
485 : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty, false);
486 GepIndices.push_back(Scaled);
487
488 // Collect struct field index operands.
489 while (StructType *STy = dyn_cast<StructType>(ElTy)) {
5
Assuming 'ElTy' is not a 'StructType'
6
Loop condition is false. Execution continues on line 522
490 bool FoundFieldNo = false;
491 // An empty struct has no fields.
492 if (STy->getNumElements() == 0) break;
493 // Field offsets are known. See if a constant offset falls within any of
494 // the struct fields.
495 if (Ops.empty())
496 break;
497 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0]))
498 if (SE.getTypeSizeInBits(C->getType()) <= 64) {
499 const StructLayout &SL = *DL.getStructLayout(STy);
500 uint64_t FullOffset = C->getValue()->getZExtValue();
501 if (FullOffset < SL.getSizeInBytes()) {
502 unsigned ElIdx = SL.getElementContainingOffset(FullOffset);
503 GepIndices.push_back(
504 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx));
505 ElTy = STy->getTypeAtIndex(ElIdx);
506 Ops[0] =
507 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx));
508 AnyNonZeroIndices = true;
509 FoundFieldNo = true;
510 }
511 }
512 // If no struct field offsets were found, tentatively assume that
513 // field zero was selected (since the zero offset would obviously
514 // be folded away).
515 if (!FoundFieldNo) {
516 ElTy = STy->getTypeAtIndex(0u);
517 GepIndices.push_back(
518 Constant::getNullValue(Type::getInt32Ty(Ty->getContext())));
519 }
520 }
521
522 if (ArrayType *ATy
7.1
'ATy' is null
7.1
'ATy' is null
= dyn_cast<ArrayType>(ElTy))
7
Assuming 'ElTy' is not a 'ArrayType'
8
Taking false branch
523 ElTy = ATy->getElementType();
524 else
525 // FIXME: Handle VectorType.
526 // E.g., If ElTy is scalable vector, then ElSize is not a compile-time
527 // constant, therefore can not be factored out. The generated IR is less
528 // ideal with base 'V' cast to i8* and do ugly getelementptr over that.
529 break;
9
Execution continues on line 535
530 }
531
532 // If none of the operands were convertible to proper GEP indices, cast
533 // the base to i8* and do an ugly getelementptr with that. It's still
534 // better than ptrtoint+arithmetic+inttoptr at least.
535 if (!AnyNonZeroIndices
9.1
'AnyNonZeroIndices' is false
9.1
'AnyNonZeroIndices' is false
) {
10
Taking true branch
536 // Cast the base to i8*.
537 V = InsertNoopCastOfTo(V,
11
Calling 'SCEVExpander::InsertNoopCastOfTo'
538 Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
539
540 assert(!isa<Instruction>(V) ||((!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction
>(V), &*Builder.GetInsertPoint())) ? static_cast<void
> (0) : __assert_fail ("!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint())"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 541, __PRETTY_FUNCTION__))
541 SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()))((!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction
>(V), &*Builder.GetInsertPoint())) ? static_cast<void
> (0) : __assert_fail ("!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint())"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 541, __PRETTY_FUNCTION__))
;
542
543 // Expand the operands for a plain byte offset.
544 Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty, false);
545
546 // Fold a GEP with constant operands.
547 if (Constant *CLHS = dyn_cast<Constant>(V))
548 if (Constant *CRHS = dyn_cast<Constant>(Idx))
549 return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
550 CLHS, CRHS);
551
552 // Do a quick scan to see if we have this GEP nearby. If so, reuse it.
553 unsigned ScanLimit = 6;
554 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
555 // Scanning starts from the last instruction before the insertion point.
556 BasicBlock::iterator IP = Builder.GetInsertPoint();
557 if (IP != BlockBegin) {
558 --IP;
559 for (; ScanLimit; --IP, --ScanLimit) {
560 // Don't count dbg.value against the ScanLimit, to avoid perturbing the
561 // generated code.
562 if (isa<DbgInfoIntrinsic>(IP))
563 ScanLimit++;
564 if (IP->getOpcode() == Instruction::GetElementPtr &&
565 IP->getOperand(0) == V && IP->getOperand(1) == Idx)
566 return &*IP;
567 if (IP == BlockBegin) break;
568 }
569 }
570
571 // Save the original insertion point so we can restore it when we're done.
572 SCEVInsertPointGuard Guard(Builder, this);
573
574 // Move the insertion point out of as many loops as we can.
575 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
576 if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
577 BasicBlock *Preheader = L->getLoopPreheader();
578 if (!Preheader) break;
579
580 // Ok, move up a level.
581 Builder.SetInsertPoint(Preheader->getTerminator());
582 }
583
584 // Emit a GEP.
585 return Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
586 }
587
588 {
589 SCEVInsertPointGuard Guard(Builder, this);
590
591 // Move the insertion point out of as many loops as we can.
592 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
593 if (!L->isLoopInvariant(V)) break;
594
595 bool AnyIndexNotLoopInvariant = any_of(
596 GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); });
597
598 if (AnyIndexNotLoopInvariant)
599 break;
600
601 BasicBlock *Preheader = L->getLoopPreheader();
602 if (!Preheader) break;
603
604 // Ok, move up a level.
605 Builder.SetInsertPoint(Preheader->getTerminator());
606 }
607
608 // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
609 // because ScalarEvolution may have changed the address arithmetic to
610 // compute a value which is beyond the end of the allocated object.
611 Value *Casted = V;
612 if (V->getType() != PTy)
613 Casted = InsertNoopCastOfTo(Casted, PTy);
614 Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep");
615 Ops.push_back(SE.getUnknown(GEP));
616 }
617
618 return expand(SE.getAddExpr(Ops));
619}
620
621Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty,
622 Value *V) {
623 const SCEV *const Ops[1] = {Op};
624 return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
625}
626
627/// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
628/// SCEV expansion. If they are nested, this is the most nested. If they are
629/// neighboring, pick the later.
630static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
631 DominatorTree &DT) {
632 if (!A) return B;
633 if (!B) return A;
634 if (A->contains(B)) return B;
635 if (B->contains(A)) return A;
636 if (DT.dominates(A->getHeader(), B->getHeader())) return B;
637 if (DT.dominates(B->getHeader(), A->getHeader())) return A;
638 return A; // Arbitrarily break the tie.
639}
640
641/// getRelevantLoop - Get the most relevant loop associated with the given
642/// expression, according to PickMostRelevantLoop.
643const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
644 // Test whether we've already computed the most relevant loop for this SCEV.
645 auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
646 if (!Pair.second)
647 return Pair.first->second;
648
649 if (isa<SCEVConstant>(S))
650 // A constant has no relevant loops.
651 return nullptr;
652 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
653 if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
654 return Pair.first->second = SE.LI.getLoopFor(I->getParent());
655 // A non-instruction has no relevant loops.
656 return nullptr;
657 }
658 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
659 const Loop *L = nullptr;
660 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
661 L = AR->getLoop();
662 for (const SCEV *Op : N->operands())
663 L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
664 return RelevantLoops[N] = L;
665 }
666 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
667 const Loop *Result = getRelevantLoop(C->getOperand());
668 return RelevantLoops[C] = Result;
669 }
670 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
671 const Loop *Result = PickMostRelevantLoop(
672 getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
673 return RelevantLoops[D] = Result;
674 }
675 llvm_unreachable("Unexpected SCEV type!")::llvm::llvm_unreachable_internal("Unexpected SCEV type!", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 675)
;
676}
677
678namespace {
679
680/// LoopCompare - Compare loops by PickMostRelevantLoop.
681class LoopCompare {
682 DominatorTree &DT;
683public:
684 explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
685
686 bool operator()(std::pair<const Loop *, const SCEV *> LHS,
687 std::pair<const Loop *, const SCEV *> RHS) const {
688 // Keep pointer operands sorted at the end.
689 if (LHS.second->getType()->isPointerTy() !=
690 RHS.second->getType()->isPointerTy())
691 return LHS.second->getType()->isPointerTy();
692
693 // Compare loops with PickMostRelevantLoop.
694 if (LHS.first != RHS.first)
695 return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
696
697 // If one operand is a non-constant negative and the other is not,
698 // put the non-constant negative on the right so that a sub can
699 // be used instead of a negate and add.
700 if (LHS.second->isNonConstantNegative()) {
701 if (!RHS.second->isNonConstantNegative())
702 return false;
703 } else if (RHS.second->isNonConstantNegative())
704 return true;
705
706 // Otherwise they are equivalent according to this comparison.
707 return false;
708 }
709};
710
711}
712
713Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
714 Type *Ty = SE.getEffectiveSCEVType(S->getType());
715
716 // Collect all the add operands in a loop, along with their associated loops.
717 // Iterate in reverse so that constants are emitted last, all else equal, and
718 // so that pointer operands are inserted first, which the code below relies on
719 // to form more involved GEPs.
720 SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
721 for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
722 E(S->op_begin()); I != E; ++I)
723 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
724
725 // Sort by loop. Use a stable sort so that constants follow non-constants and
726 // pointer operands precede non-pointer operands.
727 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
728
729 // Emit instructions to add all the operands. Hoist as much as possible
730 // out of loops, and form meaningful getelementptrs where possible.
731 Value *Sum = nullptr;
732 for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
733 const Loop *CurLoop = I->first;
734 const SCEV *Op = I->second;
735 if (!Sum) {
736 // This is the first operand. Just expand it.
737 Sum = expand(Op);
738 ++I;
739 } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
740 // The running sum expression is a pointer. Try to form a getelementptr
741 // at this level with that as the base.
742 SmallVector<const SCEV *, 4> NewOps;
743 for (; I != E && I->first == CurLoop; ++I) {
744 // If the operand is SCEVUnknown and not instructions, peek through
745 // it, to enable more of it to be folded into the GEP.
746 const SCEV *X = I->second;
747 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
748 if (!isa<Instruction>(U->getValue()))
749 X = SE.getSCEV(U->getValue());
750 NewOps.push_back(X);
751 }
752 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
753 } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) {
754 // The running sum is an integer, and there's a pointer at this level.
755 // Try to form a getelementptr. If the running sum is instructions,
756 // use a SCEVUnknown to avoid re-analyzing them.
757 SmallVector<const SCEV *, 4> NewOps;
758 NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
759 SE.getSCEV(Sum));
760 for (++I; I != E && I->first == CurLoop; ++I)
761 NewOps.push_back(I->second);
762 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
763 } else if (Op->isNonConstantNegative()) {
764 // Instead of doing a negate and add, just do a subtract.
765 Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false);
766 Sum = InsertNoopCastOfTo(Sum, Ty);
767 Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
768 /*IsSafeToHoist*/ true);
769 ++I;
770 } else {
771 // A simple add.
772 Value *W = expandCodeForImpl(Op, Ty, false);
773 Sum = InsertNoopCastOfTo(Sum, Ty);
774 // Canonicalize a constant to the RHS.
775 if (isa<Constant>(Sum)) std::swap(Sum, W);
776 Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
777 /*IsSafeToHoist*/ true);
778 ++I;
779 }
780 }
781
782 return Sum;
783}
784
785Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
786 Type *Ty = SE.getEffectiveSCEVType(S->getType());
787
788 // Collect all the mul operands in a loop, along with their associated loops.
789 // Iterate in reverse so that constants are emitted last, all else equal.
790 SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
791 for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
792 E(S->op_begin()); I != E; ++I)
793 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
794
795 // Sort by loop. Use a stable sort so that constants follow non-constants.
796 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
797
798 // Emit instructions to mul all the operands. Hoist as much as possible
799 // out of loops.
800 Value *Prod = nullptr;
801 auto I = OpsAndLoops.begin();
802
803 // Expand the calculation of X pow N in the following manner:
804 // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
805 // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
806 const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
807 auto E = I;
808 // Calculate how many times the same operand from the same loop is included
809 // into this power.
810 uint64_t Exponent = 0;
811 const uint64_t MaxExponent = UINT64_MAX(18446744073709551615UL) >> 1;
812 // No one sane will ever try to calculate such huge exponents, but if we
813 // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
814 // below when the power of 2 exceeds our Exponent, and we want it to be
815 // 1u << 31 at most to not deal with unsigned overflow.
816 while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
817 ++Exponent;
818 ++E;
819 }
820 assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?")((Exponent > 0 && "Trying to calculate a zeroth exponent of operand?"
) ? static_cast<void> (0) : __assert_fail ("Exponent > 0 && \"Trying to calculate a zeroth exponent of operand?\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 820, __PRETTY_FUNCTION__))
;
821
822 // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
823 // that are needed into the result.
824 Value *P = expandCodeForImpl(I->second, Ty, false);
825 Value *Result = nullptr;
826 if (Exponent & 1)
827 Result = P;
828 for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
829 P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
830 /*IsSafeToHoist*/ true);
831 if (Exponent & BinExp)
832 Result = Result ? InsertBinop(Instruction::Mul, Result, P,
833 SCEV::FlagAnyWrap,
834 /*IsSafeToHoist*/ true)
835 : P;
836 }
837
838 I = E;
839 assert(Result && "Nothing was expanded?")((Result && "Nothing was expanded?") ? static_cast<
void> (0) : __assert_fail ("Result && \"Nothing was expanded?\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 839, __PRETTY_FUNCTION__))
;
840 return Result;
841 };
842
843 while (I != OpsAndLoops.end()) {
844 if (!Prod) {
845 // This is the first operand. Just expand it.
846 Prod = ExpandOpBinPowN();
847 } else if (I->second->isAllOnesValue()) {
848 // Instead of doing a multiply by negative one, just do a negate.
849 Prod = InsertNoopCastOfTo(Prod, Ty);
850 Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
851 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
852 ++I;
853 } else {
854 // A simple mul.
855 Value *W = ExpandOpBinPowN();
856 Prod = InsertNoopCastOfTo(Prod, Ty);
857 // Canonicalize a constant to the RHS.
858 if (isa<Constant>(Prod)) std::swap(Prod, W);
859 const APInt *RHS;
860 if (match(W, m_Power2(RHS))) {
861 // Canonicalize Prod*(1<<C) to Prod<<C.
862 assert(!Ty->isVectorTy() && "vector types are not SCEVable")((!Ty->isVectorTy() && "vector types are not SCEVable"
) ? static_cast<void> (0) : __assert_fail ("!Ty->isVectorTy() && \"vector types are not SCEVable\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 862, __PRETTY_FUNCTION__))
;
863 auto NWFlags = S->getNoWrapFlags();
864 // clear nsw flag if shl will produce poison value.
865 if (RHS->logBase2() == RHS->getBitWidth() - 1)
866 NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);
867 Prod = InsertBinop(Instruction::Shl, Prod,
868 ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
869 /*IsSafeToHoist*/ true);
870 } else {
871 Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
872 /*IsSafeToHoist*/ true);
873 }
874 }
875 }
876
877 return Prod;
878}
879
880Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
881 Type *Ty = SE.getEffectiveSCEVType(S->getType());
882
883 Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false);
884 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
885 const APInt &RHS = SC->getAPInt();
886 if (RHS.isPowerOf2())
887 return InsertBinop(Instruction::LShr, LHS,
888 ConstantInt::get(Ty, RHS.logBase2()),
889 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
890 }
891
892 Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false);
893 return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
894 /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
895}
896
897/// Move parts of Base into Rest to leave Base with the minimal
898/// expression that provides a pointer operand suitable for a
899/// GEP expansion.
900static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
901 ScalarEvolution &SE) {
902 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {
903 Base = A->getStart();
904 Rest = SE.getAddExpr(Rest,
905 SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
906 A->getStepRecurrence(SE),
907 A->getLoop(),
908 A->getNoWrapFlags(SCEV::FlagNW)));
909 }
910 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
911 Base = A->getOperand(A->getNumOperands()-1);
912 SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end());
913 NewAddOps.back() = Rest;
914 Rest = SE.getAddExpr(NewAddOps);
915 ExposePointerBase(Base, Rest, SE);
916 }
917}
918
919/// Determine if this is a well-behaved chain of instructions leading back to
920/// the PHI. If so, it may be reused by expanded expressions.
921bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
922 const Loop *L) {
923 if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
924 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
925 return false;
926 // If any of the operands don't dominate the insert position, bail.
927 // Addrec operands are always loop-invariant, so this can only happen
928 // if there are instructions which haven't been hoisted.
929 if (L == IVIncInsertLoop) {
930 for (User::op_iterator OI = IncV->op_begin()+1,
931 OE = IncV->op_end(); OI != OE; ++OI)
932 if (Instruction *OInst = dyn_cast<Instruction>(OI))
933 if (!SE.DT.dominates(OInst, IVIncInsertPos))
934 return false;
935 }
936 // Advance to the next instruction.
937 IncV = dyn_cast<Instruction>(IncV->getOperand(0));
938 if (!IncV)
939 return false;
940
941 if (IncV->mayHaveSideEffects())
942 return false;
943
944 if (IncV == PN)
945 return true;
946
947 return isNormalAddRecExprPHI(PN, IncV, L);
948}
949
950/// getIVIncOperand returns an induction variable increment's induction
951/// variable operand.
952///
953/// If allowScale is set, any type of GEP is allowed as long as the nonIV
954/// operands dominate InsertPos.
955///
956/// If allowScale is not set, ensure that a GEP increment conforms to one of the
957/// simple patterns generated by getAddRecExprPHILiterally and
958/// expandAddtoGEP. If the pattern isn't recognized, return NULL.
959Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
960 Instruction *InsertPos,
961 bool allowScale) {
962 if (IncV == InsertPos)
963 return nullptr;
964
965 switch (IncV->getOpcode()) {
966 default:
967 return nullptr;
968 // Check for a simple Add/Sub or GEP of a loop invariant step.
969 case Instruction::Add:
970 case Instruction::Sub: {
971 Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
972 if (!OInst || SE.DT.dominates(OInst, InsertPos))
973 return dyn_cast<Instruction>(IncV->getOperand(0));
974 return nullptr;
975 }
976 case Instruction::BitCast:
977 return dyn_cast<Instruction>(IncV->getOperand(0));
978 case Instruction::GetElementPtr:
979 for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) {
980 if (isa<Constant>(*I))
981 continue;
982 if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
983 if (!SE.DT.dominates(OInst, InsertPos))
984 return nullptr;
985 }
986 if (allowScale) {
987 // allow any kind of GEP as long as it can be hoisted.
988 continue;
989 }
990 // This must be a pointer addition of constants (pretty), which is already
991 // handled, or some number of address-size elements (ugly). Ugly geps
992 // have 2 operands. i1* is used by the expander to represent an
993 // address-size element.
994 if (IncV->getNumOperands() != 2)
995 return nullptr;
996 unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
997 if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
998 && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
999 return nullptr;
1000 break;
1001 }
1002 return dyn_cast<Instruction>(IncV->getOperand(0));
1003 }
1004}
1005
1006/// If the insert point of the current builder or any of the builders on the
1007/// stack of saved builders has 'I' as its insert point, update it to point to
1008/// the instruction after 'I'. This is intended to be used when the instruction
1009/// 'I' is being moved. If this fixup is not done and 'I' is moved to a
1010/// different block, the inconsistent insert point (with a mismatched
1011/// Instruction and Block) can lead to an instruction being inserted in a block
1012/// other than its parent.
1013void SCEVExpander::fixupInsertPoints(Instruction *I) {
1014 BasicBlock::iterator It(*I);
1015 BasicBlock::iterator NewInsertPt = std::next(It);
1016 if (Builder.GetInsertPoint() == It)
1017 Builder.SetInsertPoint(&*NewInsertPt);
1018 for (auto *InsertPtGuard : InsertPointGuards)
1019 if (InsertPtGuard->GetInsertPoint() == It)
1020 InsertPtGuard->SetInsertPoint(NewInsertPt);
1021}
1022
1023/// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
1024/// it available to other uses in this loop. Recursively hoist any operands,
1025/// until we reach a value that dominates InsertPos.
1026bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
1027 if (SE.DT.dominates(IncV, InsertPos))
1028 return true;
1029
1030 // InsertPos must itself dominate IncV so that IncV's new position satisfies
1031 // its existing users.
1032 if (isa<PHINode>(InsertPos) ||
1033 !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
1034 return false;
1035
1036 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1037 return false;
1038
1039 // Check that the chain of IV operands leading back to Phi can be hoisted.
1040 SmallVector<Instruction*, 4> IVIncs;
1041 for(;;) {
1042 Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
1043 if (!Oper)
1044 return false;
1045 // IncV is safe to hoist.
1046 IVIncs.push_back(IncV);
1047 IncV = Oper;
1048 if (SE.DT.dominates(IncV, InsertPos))
1049 break;
1050 }
1051 for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
1052 fixupInsertPoints(*I);
1053 (*I)->moveBefore(InsertPos);
1054 }
1055 return true;
1056}
1057
1058/// Determine if this cyclic phi is in a form that would have been generated by
1059/// LSR. We don't care if the phi was actually expanded in this pass, as long
1060/// as it is in a low-cost form, for example, no implied multiplication. This
1061/// should match any patterns generated by getAddRecExprPHILiterally and
1062/// expandAddtoGEP.
1063bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
1064 const Loop *L) {
1065 for(Instruction *IVOper = IncV;
1066 (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
1067 /*allowScale=*/false));) {
1068 if (IVOper == PN)
1069 return true;
1070 }
1071 return false;
1072}
1073
1074/// expandIVInc - Expand an IV increment at Builder's current InsertPos.
1075/// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
1076/// need to materialize IV increments elsewhere to handle difficult situations.
1077Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
1078 Type *ExpandTy, Type *IntTy,
1079 bool useSubtract) {
1080 Value *IncV;
1081 // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
1082 if (ExpandTy->isPointerTy()) {
1083 PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1084 // If the step isn't constant, don't use an implicitly scaled GEP, because
1085 // that would require a multiply inside the loop.
1086 if (!isa<ConstantInt>(StepV))
1087 GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
1088 GEPPtrTy->getAddressSpace());
1089 IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1090 if (IncV->getType() != PN->getType())
1091 IncV = Builder.CreateBitCast(IncV, PN->getType());
1092 } else {
1093 IncV = useSubtract ?
1094 Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
1095 Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
1096 }
1097 return IncV;
1098}
1099
1100/// Hoist the addrec instruction chain rooted in the loop phi above the
1101/// position. This routine assumes that this is possible (has been checked).
1102void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
1103 Instruction *Pos, PHINode *LoopPhi) {
1104 do {
1105 if (DT->dominates(InstToHoist, Pos))
1106 break;
1107 // Make sure the increment is where we want it. But don't move it
1108 // down past a potential existing post-inc user.
1109 fixupInsertPoints(InstToHoist);
1110 InstToHoist->moveBefore(Pos);
1111 Pos = InstToHoist;
1112 InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
1113 } while (InstToHoist != LoopPhi);
1114}
1115
1116/// Check whether we can cheaply express the requested SCEV in terms of
1117/// the available PHI SCEV by truncation and/or inversion of the step.
1118static bool canBeCheaplyTransformed(ScalarEvolution &SE,
1119 const SCEVAddRecExpr *Phi,
1120 const SCEVAddRecExpr *Requested,
1121 bool &InvertStep) {
1122 Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
1123 Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
1124
1125 if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
1126 return false;
1127
1128 // Try truncate it if necessary.
1129 Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
1130 if (!Phi)
1131 return false;
1132
1133 // Check whether truncation will help.
1134 if (Phi == Requested) {
1135 InvertStep = false;
1136 return true;
1137 }
1138
1139 // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
1140 if (SE.getAddExpr(Requested->getStart(),
1141 SE.getNegativeSCEV(Requested)) == Phi) {
1142 InvertStep = true;
1143 return true;
1144 }
1145
1146 return false;
1147}
1148
1149static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1150 if (!isa<IntegerType>(AR->getType()))
1151 return false;
1152
1153 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1154 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1155 const SCEV *Step = AR->getStepRecurrence(SE);
1156 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
1157 SE.getSignExtendExpr(AR, WideTy));
1158 const SCEV *ExtendAfterOp =
1159 SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1160 return ExtendAfterOp == OpAfterExtend;
1161}
1162
1163static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1164 if (!isa<IntegerType>(AR->getType()))
1165 return false;
1166
1167 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1168 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1169 const SCEV *Step = AR->getStepRecurrence(SE);
1170 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
1171 SE.getZeroExtendExpr(AR, WideTy));
1172 const SCEV *ExtendAfterOp =
1173 SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1174 return ExtendAfterOp == OpAfterExtend;
1175}
1176
1177/// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
1178/// the base addrec, which is the addrec without any non-loop-dominating
1179/// values, and return the PHI.
1180PHINode *
1181SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
1182 const Loop *L,
1183 Type *ExpandTy,
1184 Type *IntTy,
1185 Type *&TruncTy,
1186 bool &InvertStep) {
1187 assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position")(((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position"
) ? static_cast<void> (0) : __assert_fail ("(!IVIncInsertLoop||IVIncInsertPos) && \"Uninitialized insert position\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1187, __PRETTY_FUNCTION__))
;
1188
1189 // Reuse a previously-inserted PHI, if present.
1190 BasicBlock *LatchBlock = L->getLoopLatch();
1191 if (LatchBlock) {
1192 PHINode *AddRecPhiMatch = nullptr;
1193 Instruction *IncV = nullptr;
1194 TruncTy = nullptr;
1195 InvertStep = false;
1196
1197 // Only try partially matching scevs that need truncation and/or
1198 // step-inversion if we know this loop is outside the current loop.
1199 bool TryNonMatchingSCEV =
1200 IVIncInsertLoop &&
1201 SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1202
1203 for (PHINode &PN : L->getHeader()->phis()) {
1204 if (!SE.isSCEVable(PN.getType()))
1205 continue;
1206
1207 // We should not look for a incomplete PHI. Getting SCEV for a incomplete
1208 // PHI has no meaning at all.
1209 if (!PN.isComplete()) {
1210 DEBUG_WITH_TYPE(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "One incomplete PHI is found: "
<< PN << "\n"; } } while (false)
1211 DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "One incomplete PHI is found: "
<< PN << "\n"; } } while (false)
;
1212 continue;
1213 }
1214
1215 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1216 if (!PhiSCEV)
1217 continue;
1218
1219 bool IsMatchingSCEV = PhiSCEV == Normalized;
1220 // We only handle truncation and inversion of phi recurrences for the
1221 // expanded expression if the expanded expression's loop dominates the
1222 // loop we insert to. Check now, so we can bail out early.
1223 if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1224 continue;
1225
1226 // TODO: this possibly can be reworked to avoid this cast at all.
1227 Instruction *TempIncV =
1228 dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
1229 if (!TempIncV)
1230 continue;
1231
1232 // Check whether we can reuse this PHI node.
1233 if (LSRMode) {
1234 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1235 continue;
1236 if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
1237 continue;
1238 } else {
1239 if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1240 continue;
1241 }
1242
1243 // Stop if we have found an exact match SCEV.
1244 if (IsMatchingSCEV) {
1245 IncV = TempIncV;
1246 TruncTy = nullptr;
1247 InvertStep = false;
1248 AddRecPhiMatch = &PN;
1249 break;
1250 }
1251
1252 // Try whether the phi can be translated into the requested form
1253 // (truncated and/or offset by a constant).
1254 if ((!TruncTy || InvertStep) &&
1255 canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
1256 // Record the phi node. But don't stop we might find an exact match
1257 // later.
1258 AddRecPhiMatch = &PN;
1259 IncV = TempIncV;
1260 TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
1261 }
1262 }
1263
1264 if (AddRecPhiMatch) {
1265 // Potentially, move the increment. We have made sure in
1266 // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
1267 if (L == IVIncInsertLoop)
1268 hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
1269
1270 // Ok, the add recurrence looks usable.
1271 // Remember this PHI, even in post-inc mode.
1272 InsertedValues.insert(AddRecPhiMatch);
1273 // Remember the increment.
1274 rememberInstruction(IncV);
1275 // Those values were not actually inserted but re-used.
1276 ReusedValues.insert(AddRecPhiMatch);
1277 ReusedValues.insert(IncV);
1278 return AddRecPhiMatch;
1279 }
1280 }
1281
1282 // Save the original insertion point so we can restore it when we're done.
1283 SCEVInsertPointGuard Guard(Builder, this);
1284
1285 // Another AddRec may need to be recursively expanded below. For example, if
1286 // this AddRec is quadratic, the StepV may itself be an AddRec in this
1287 // loop. Remove this loop from the PostIncLoops set before expanding such
1288 // AddRecs. Otherwise, we cannot find a valid position for the step
1289 // (i.e. StepV can never dominate its loop header). Ideally, we could do
1290 // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
1291 // so it's not worth implementing SmallPtrSet::swap.
1292 PostIncLoopSet SavedPostIncLoops = PostIncLoops;
1293 PostIncLoops.clear();
1294
1295 // Expand code for the start value into the loop preheader.
1296 assert(L->getLoopPreheader() &&((L->getLoopPreheader() && "Can't expand add recurrences without a loop preheader!"
) ? static_cast<void> (0) : __assert_fail ("L->getLoopPreheader() && \"Can't expand add recurrences without a loop preheader!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1297, __PRETTY_FUNCTION__))
1297 "Can't expand add recurrences without a loop preheader!")((L->getLoopPreheader() && "Can't expand add recurrences without a loop preheader!"
) ? static_cast<void> (0) : __assert_fail ("L->getLoopPreheader() && \"Can't expand add recurrences without a loop preheader!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1297, __PRETTY_FUNCTION__))
;
1298 Value *StartV =
1299 expandCodeForImpl(Normalized->getStart(), ExpandTy,
1300 L->getLoopPreheader()->getTerminator(), false);
1301
1302 // StartV must have been be inserted into L's preheader to dominate the new
1303 // phi.
1304 assert(!isa<Instruction>(StartV) ||((!isa<Instruction>(StartV) || SE.DT.properlyDominates(
cast<Instruction>(StartV)->getParent(), L->getHeader
())) ? static_cast<void> (0) : __assert_fail ("!isa<Instruction>(StartV) || SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), L->getHeader())"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1306, __PRETTY_FUNCTION__))
1305 SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),((!isa<Instruction>(StartV) || SE.DT.properlyDominates(
cast<Instruction>(StartV)->getParent(), L->getHeader
())) ? static_cast<void> (0) : __assert_fail ("!isa<Instruction>(StartV) || SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), L->getHeader())"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1306, __PRETTY_FUNCTION__))
1306 L->getHeader()))((!isa<Instruction>(StartV) || SE.DT.properlyDominates(
cast<Instruction>(StartV)->getParent(), L->getHeader
())) ? static_cast<void> (0) : __assert_fail ("!isa<Instruction>(StartV) || SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), L->getHeader())"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1306, __PRETTY_FUNCTION__))
;
1307
1308 // Expand code for the step value. Do this before creating the PHI so that PHI
1309 // reuse code doesn't see an incomplete PHI.
1310 const SCEV *Step = Normalized->getStepRecurrence(SE);
1311 // If the stride is negative, insert a sub instead of an add for the increment
1312 // (unless it's a constant, because subtracts of constants are canonicalized
1313 // to adds).
1314 bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1315 if (useSubtract)
1316 Step = SE.getNegativeSCEV(Step);
1317 // Expand the step somewhere that dominates the loop header.
1318 Value *StepV = expandCodeForImpl(
1319 Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1320
1321 // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
1322 // we actually do emit an addition. It does not apply if we emit a
1323 // subtraction.
1324 bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
1325 bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
1326
1327 // Create the PHI.
1328 BasicBlock *Header = L->getHeader();
1329 Builder.SetInsertPoint(Header, Header->begin());
1330 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1331 PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1332 Twine(IVName) + ".iv");
1333
1334 // Create the step instructions and populate the PHI.
1335 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1336 BasicBlock *Pred = *HPI;
1337
1338 // Add a start value.
1339 if (!L->contains(Pred)) {
1340 PN->addIncoming(StartV, Pred);
1341 continue;
1342 }
1343
1344 // Create a step value and add it to the PHI.
1345 // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
1346 // instructions at IVIncInsertPos.
1347 Instruction *InsertPos = L == IVIncInsertLoop ?
1348 IVIncInsertPos : Pred->getTerminator();
1349 Builder.SetInsertPoint(InsertPos);
1350 Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1351
1352 if (isa<OverflowingBinaryOperator>(IncV)) {
1353 if (IncrementIsNUW)
1354 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1355 if (IncrementIsNSW)
1356 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1357 }
1358 PN->addIncoming(IncV, Pred);
1359 }
1360
1361 // After expanding subexpressions, restore the PostIncLoops set so the caller
1362 // can ensure that IVIncrement dominates the current uses.
1363 PostIncLoops = SavedPostIncLoops;
1364
1365 // Remember this PHI, even in post-inc mode.
1366 InsertedValues.insert(PN);
1367
1368 return PN;
1369}
1370
1371Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
1372 Type *STy = S->getType();
1373 Type *IntTy = SE.getEffectiveSCEVType(STy);
1374 const Loop *L = S->getLoop();
1375
1376 // Determine a normalized form of this expression, which is the expression
1377 // before any post-inc adjustment is made.
1378 const SCEVAddRecExpr *Normalized = S;
1379 if (PostIncLoops.count(L)) {
1380 PostIncLoopSet Loops;
1381 Loops.insert(L);
1382 Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
1383 }
1384
1385 // Strip off any non-loop-dominating component from the addrec start.
1386 const SCEV *Start = Normalized->getStart();
1387 const SCEV *PostLoopOffset = nullptr;
1388 if (!SE.properlyDominates(Start, L->getHeader())) {
1389 PostLoopOffset = Start;
1390 Start = SE.getConstant(Normalized->getType(), 0);
1391 Normalized = cast<SCEVAddRecExpr>(
1392 SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
1393 Normalized->getLoop(),
1394 Normalized->getNoWrapFlags(SCEV::FlagNW)));
1395 }
1396
1397 // Strip off any non-loop-dominating component from the addrec step.
1398 const SCEV *Step = Normalized->getStepRecurrence(SE);
1399 const SCEV *PostLoopScale = nullptr;
1400 if (!SE.dominates(Step, L->getHeader())) {
1401 PostLoopScale = Step;
1402 Step = SE.getConstant(Normalized->getType(), 1);
1403 if (!Start->isZero()) {
1404 // The normalization below assumes that Start is constant zero, so if
1405 // it isn't re-associate Start to PostLoopOffset.
1406 assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?")((!PostLoopOffset && "Start not-null but PostLoopOffset set?"
) ? static_cast<void> (0) : __assert_fail ("!PostLoopOffset && \"Start not-null but PostLoopOffset set?\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1406, __PRETTY_FUNCTION__))
;
1407 PostLoopOffset = Start;
1408 Start = SE.getConstant(Normalized->getType(), 0);
1409 }
1410 Normalized =
1411 cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1412 Start, Step, Normalized->getLoop(),
1413 Normalized->getNoWrapFlags(SCEV::FlagNW)));
1414 }
1415
1416 // Expand the core addrec. If we need post-loop scaling, force it to
1417 // expand to an integer type to avoid the need for additional casting.
1418 Type *ExpandTy = PostLoopScale ? IntTy : STy;
1419 // We can't use a pointer type for the addrec if the pointer type is
1420 // non-integral.
1421 Type *AddRecPHIExpandTy =
1422 DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
1423
1424 // In some cases, we decide to reuse an existing phi node but need to truncate
1425 // it and/or invert the step.
1426 Type *TruncTy = nullptr;
1427 bool InvertStep = false;
1428 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1429 IntTy, TruncTy, InvertStep);
1430
1431 // Accommodate post-inc mode, if necessary.
1432 Value *Result;
1433 if (!PostIncLoops.count(L))
1434 Result = PN;
1435 else {
1436 // In PostInc mode, use the post-incremented value.
1437 BasicBlock *LatchBlock = L->getLoopLatch();
1438 assert(LatchBlock && "PostInc mode requires a unique loop latch!")((LatchBlock && "PostInc mode requires a unique loop latch!"
) ? static_cast<void> (0) : __assert_fail ("LatchBlock && \"PostInc mode requires a unique loop latch!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1438, __PRETTY_FUNCTION__))
;
1439 Result = PN->getIncomingValueForBlock(LatchBlock);
1440
1441 // For an expansion to use the postinc form, the client must call
1442 // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
1443 // or dominated by IVIncInsertPos.
1444 if (isa<Instruction>(Result) &&
1445 !SE.DT.dominates(cast<Instruction>(Result),
1446 &*Builder.GetInsertPoint())) {
1447 // The induction variable's postinc expansion does not dominate this use.
1448 // IVUsers tries to prevent this case, so it is rare. However, it can
1449 // happen when an IVUser outside the loop is not dominated by the latch
1450 // block. Adjusting IVIncInsertPos before expansion begins cannot handle
1451 // all cases. Consider a phi outside whose operand is replaced during
1452 // expansion with the value of the postinc user. Without fundamentally
1453 // changing the way postinc users are tracked, the only remedy is
1454 // inserting an extra IV increment. StepV might fold into PostLoopOffset,
1455 // but hopefully expandCodeFor handles that.
1456 bool useSubtract =
1457 !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1458 if (useSubtract)
1459 Step = SE.getNegativeSCEV(Step);
1460 Value *StepV;
1461 {
1462 // Expand the step somewhere that dominates the loop header.
1463 SCEVInsertPointGuard Guard(Builder, this);
1464 StepV = expandCodeForImpl(
1465 Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1466 }
1467 Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1468 }
1469 }
1470
1471 // We have decided to reuse an induction variable of a dominating loop. Apply
1472 // truncation and/or inversion of the step.
1473 if (TruncTy) {
1474 Type *ResTy = Result->getType();
1475 // Normalize the result type.
1476 if (ResTy != SE.getEffectiveSCEVType(ResTy))
1477 Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1478 // Truncate the result.
1479 if (TruncTy != Result->getType())
1480 Result = Builder.CreateTrunc(Result, TruncTy);
1481
1482 // Invert the result.
1483 if (InvertStep)
1484 Result = Builder.CreateSub(
1485 expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result);
1486 }
1487
1488 // Re-apply any non-loop-dominating scale.
1489 if (PostLoopScale) {
1490 assert(S->isAffine() && "Can't linearly scale non-affine recurrences.")((S->isAffine() && "Can't linearly scale non-affine recurrences."
) ? static_cast<void> (0) : __assert_fail ("S->isAffine() && \"Can't linearly scale non-affine recurrences.\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1490, __PRETTY_FUNCTION__))
;
1491 Result = InsertNoopCastOfTo(Result, IntTy);
1492 Result = Builder.CreateMul(Result,
1493 expandCodeForImpl(PostLoopScale, IntTy, false));
1494 }
1495
1496 // Re-apply any non-loop-dominating offset.
1497 if (PostLoopOffset) {
1498 if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1499 if (Result->getType()->isIntegerTy()) {
1500 Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false);
1501 Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
1502 } else {
1503 Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1504 }
1505 } else {
1506 Result = InsertNoopCastOfTo(Result, IntTy);
1507 Result = Builder.CreateAdd(
1508 Result, expandCodeForImpl(PostLoopOffset, IntTy, false));
1509 }
1510 }
1511
1512 return Result;
1513}
1514
1515Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
1516 // In canonical mode we compute the addrec as an expression of a canonical IV
1517 // using evaluateAtIteration and expand the resulting SCEV expression. This
1518 // way we avoid introducing new IVs to carry on the comutation of the addrec
1519 // throughout the loop.
1520 //
1521 // For nested addrecs evaluateAtIteration might need a canonical IV of a
1522 // type wider than the addrec itself. Emitting a canonical IV of the
1523 // proper type might produce non-legal types, for example expanding an i64
1524 // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall
1525 // back to non-canonical mode for nested addrecs.
1526 if (!CanonicalMode || (S->getNumOperands() > 2))
1527 return expandAddRecExprLiterally(S);
1528
1529 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1530 const Loop *L = S->getLoop();
1531
1532 // First check for an existing canonical IV in a suitable type.
1533 PHINode *CanonicalIV = nullptr;
1534 if (PHINode *PN = L->getCanonicalInductionVariable())
1535 if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
1536 CanonicalIV = PN;
1537
1538 // Rewrite an AddRec in terms of the canonical induction variable, if
1539 // its type is more narrow.
1540 if (CanonicalIV &&
1541 SE.getTypeSizeInBits(CanonicalIV->getType()) >
1542 SE.getTypeSizeInBits(Ty)) {
1543 SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
1544 for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1545 NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
1546 Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
1547 S->getNoWrapFlags(SCEV::FlagNW)));
1548 BasicBlock::iterator NewInsertPt =
1549 findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
1550 V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
1551 &*NewInsertPt, false);
1552 return V;
1553 }
1554
1555 // {X,+,F} --> X + {0,+,F}
1556 if (!S->getStart()->isZero()) {
1557 SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());
1558 NewOps[0] = SE.getConstant(Ty, 0);
1559 const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1560 S->getNoWrapFlags(SCEV::FlagNW));
1561
1562 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
1563 // comments on expandAddToGEP for details.
1564 const SCEV *Base = S->getStart();
1565 // Dig into the expression to find the pointer base for a GEP.
1566 const SCEV *ExposedRest = Rest;
1567 ExposePointerBase(Base, ExposedRest, SE);
1568 // If we found a pointer, expand the AddRec with a GEP.
1569 if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
1570 // Make sure the Base isn't something exotic, such as a multiplied
1571 // or divided pointer value. In those cases, the result type isn't
1572 // actually a pointer type.
1573 if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
1574 Value *StartV = expand(Base);
1575 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!")((StartV->getType() == PTy && "Pointer type mismatch for GEP!"
) ? static_cast<void> (0) : __assert_fail ("StartV->getType() == PTy && \"Pointer type mismatch for GEP!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1575, __PRETTY_FUNCTION__))
;
1576 return expandAddToGEP(ExposedRest, PTy, Ty, StartV);
1577 }
1578 }
1579
1580 // Just do a normal add. Pre-expand the operands to suppress folding.
1581 //
1582 // The LHS and RHS values are factored out of the expand call to make the
1583 // output independent of the argument evaluation order.
1584 const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1585 const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1586 return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1587 }
1588
1589 // If we don't yet have a canonical IV, create one.
1590 if (!CanonicalIV) {
1591 // Create and insert the PHI node for the induction variable in the
1592 // specified loop.
1593 BasicBlock *Header = L->getHeader();
1594 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1595 CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
1596 &Header->front());
1597 rememberInstruction(CanonicalIV);
1598
1599 SmallSet<BasicBlock *, 4> PredSeen;
1600 Constant *One = ConstantInt::get(Ty, 1);
1601 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1602 BasicBlock *HP = *HPI;
1603 if (!PredSeen.insert(HP).second) {
1604 // There must be an incoming value for each predecessor, even the
1605 // duplicates!
1606 CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1607 continue;
1608 }
1609
1610 if (L->contains(HP)) {
1611 // Insert a unit add instruction right before the terminator
1612 // corresponding to the back-edge.
1613 Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1614 "indvar.next",
1615 HP->getTerminator());
1616 Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1617 rememberInstruction(Add);
1618 CanonicalIV->addIncoming(Add, HP);
1619 } else {
1620 CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1621 }
1622 }
1623 }
1624
1625 // {0,+,1} --> Insert a canonical induction variable into the loop!
1626 if (S->isAffine() && S->getOperand(1)->isOne()) {
1627 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&((Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
"IVs with types different from the canonical IV should " "already have been handled!"
) ? static_cast<void> (0) : __assert_fail ("Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && \"IVs with types different from the canonical IV should \" \"already have been handled!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1629, __PRETTY_FUNCTION__))
1628 "IVs with types different from the canonical IV should "((Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
"IVs with types different from the canonical IV should " "already have been handled!"
) ? static_cast<void> (0) : __assert_fail ("Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && \"IVs with types different from the canonical IV should \" \"already have been handled!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1629, __PRETTY_FUNCTION__))
1629 "already have been handled!")((Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
"IVs with types different from the canonical IV should " "already have been handled!"
) ? static_cast<void> (0) : __assert_fail ("Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && \"IVs with types different from the canonical IV should \" \"already have been handled!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1629, __PRETTY_FUNCTION__))
;
1630 return CanonicalIV;
1631 }
1632
1633 // {0,+,F} --> {0,+,1} * F
1634
1635 // If this is a simple linear addrec, emit it now as a special case.
1636 if (S->isAffine()) // {0,+,F} --> i*F
1637 return
1638 expand(SE.getTruncateOrNoop(
1639 SE.getMulExpr(SE.getUnknown(CanonicalIV),
1640 SE.getNoopOrAnyExtend(S->getOperand(1),
1641 CanonicalIV->getType())),
1642 Ty));
1643
1644 // If this is a chain of recurrences, turn it into a closed form, using the
1645 // folders, then expandCodeFor the closed form. This allows the folders to
1646 // simplify the expression without having to build a bunch of special code
1647 // into this folder.
1648 const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV.
1649
1650 // Promote S up to the canonical IV type, if the cast is foldable.
1651 const SCEV *NewS = S;
1652 const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
1653 if (isa<SCEVAddRecExpr>(Ext))
1654 NewS = Ext;
1655
1656 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1657 //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
1658
1659 // Truncate the result down to the original type, if needed.
1660 const SCEV *T = SE.getTruncateOrNoop(V, Ty);
1661 return expand(T);
1662}
1663
1664Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
1665 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1666 Value *V = expandCodeForImpl(
1667 S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1668 false);
1669 return Builder.CreateTrunc(V, Ty);
1670}
1671
1672Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
1673 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1674 Value *V = expandCodeForImpl(
1675 S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1676 false);
1677 return Builder.CreateZExt(V, Ty);
1678}
1679
1680Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
1681 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1682 Value *V = expandCodeForImpl(
1683 S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1684 false);
1685 return Builder.CreateSExt(V, Ty);
1686}
1687
1688Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
1689 Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1690 Type *Ty = LHS->getType();
1691 for (int i = S->getNumOperands()-2; i >= 0; --i) {
1692 // In the case of mixed integer and pointer types, do the
1693 // rest of the comparisons as integer.
1694 Type *OpTy = S->getOperand(i)->getType();
1695 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1696 Ty = SE.getEffectiveSCEVType(Ty);
1697 LHS = InsertNoopCastOfTo(LHS, Ty);
1698 }
1699 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1700 Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
1701 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
1702 LHS = Sel;
1703 }
1704 // In the case of mixed integer and pointer types, cast the
1705 // final result back to the pointer type.
1706 if (LHS->getType() != S->getType())
1707 LHS = InsertNoopCastOfTo(LHS, S->getType());
1708 return LHS;
1709}
1710
1711Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
1712 Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1713 Type *Ty = LHS->getType();
1714 for (int i = S->getNumOperands()-2; i >= 0; --i) {
1715 // In the case of mixed integer and pointer types, do the
1716 // rest of the comparisons as integer.
1717 Type *OpTy = S->getOperand(i)->getType();
1718 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1719 Ty = SE.getEffectiveSCEVType(Ty);
1720 LHS = InsertNoopCastOfTo(LHS, Ty);
1721 }
1722 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1723 Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
1724 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
1725 LHS = Sel;
1726 }
1727 // In the case of mixed integer and pointer types, cast the
1728 // final result back to the pointer type.
1729 if (LHS->getType() != S->getType())
1730 LHS = InsertNoopCastOfTo(LHS, S->getType());
1731 return LHS;
1732}
1733
1734Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
1735 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1736 Type *Ty = LHS->getType();
1737 for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1738 // In the case of mixed integer and pointer types, do the
1739 // rest of the comparisons as integer.
1740 Type *OpTy = S->getOperand(i)->getType();
1741 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1742 Ty = SE.getEffectiveSCEVType(Ty);
1743 LHS = InsertNoopCastOfTo(LHS, Ty);
1744 }
1745 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1746 Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
1747 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
1748 LHS = Sel;
1749 }
1750 // In the case of mixed integer and pointer types, cast the
1751 // final result back to the pointer type.
1752 if (LHS->getType() != S->getType())
1753 LHS = InsertNoopCastOfTo(LHS, S->getType());
1754 return LHS;
1755}
1756
1757Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
1758 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1759 Type *Ty = LHS->getType();
1760 for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1761 // In the case of mixed integer and pointer types, do the
1762 // rest of the comparisons as integer.
1763 Type *OpTy = S->getOperand(i)->getType();
1764 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1765 Ty = SE.getEffectiveSCEVType(Ty);
1766 LHS = InsertNoopCastOfTo(LHS, Ty);
1767 }
1768 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1769 Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
1770 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
1771 LHS = Sel;
1772 }
1773 // In the case of mixed integer and pointer types, cast the
1774 // final result back to the pointer type.
1775 if (LHS->getType() != S->getType())
1776 LHS = InsertNoopCastOfTo(LHS, S->getType());
1777 return LHS;
1778}
1779
1780Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
1781 Instruction *IP, bool Root) {
1782 setInsertPoint(IP);
1783 Value *V = expandCodeForImpl(SH, Ty, Root);
1784 return V;
1785}
1786
1787Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
1788 // Expand the code for this SCEV.
1789 Value *V = expand(SH);
1790
1791 if (PreserveLCSSA) {
1792 if (auto *Inst = dyn_cast<Instruction>(V)) {
1793 // Create a temporary instruction to at the current insertion point, so we
1794 // can hand it off to the helper to create LCSSA PHIs if required for the
1795 // new use.
1796 // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)
1797 // would accept a insertion point and return an LCSSA phi for that
1798 // insertion point, so there is no need to insert & remove the temporary
1799 // instruction.
1800 Instruction *Tmp;
1801 if (Inst->getType()->isIntegerTy())
1802 Tmp =
1803 cast<Instruction>(Builder.CreateAdd(Inst, Inst, "tmp.lcssa.user"));
1804 else {
1805 assert(Inst->getType()->isPointerTy())((Inst->getType()->isPointerTy()) ? static_cast<void
> (0) : __assert_fail ("Inst->getType()->isPointerTy()"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1805, __PRETTY_FUNCTION__))
;
1806 Tmp = cast<Instruction>(
1807 Builder.CreateGEP(Inst, Builder.getInt32(1), "tmp.lcssa.user"));
1808 }
1809 V = fixupLCSSAFormFor(Tmp, 0);
1810
1811 // Clean up temporary instruction.
1812 InsertedValues.erase(Tmp);
1813 InsertedPostIncValues.erase(Tmp);
1814 Tmp->eraseFromParent();
1815 }
1816 }
1817
1818 InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V;
1819 if (Ty) {
1820 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&((SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType
()) && "non-trivial casts should be done with the SCEVs directly!"
) ? static_cast<void> (0) : __assert_fail ("SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && \"non-trivial casts should be done with the SCEVs directly!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1821, __PRETTY_FUNCTION__))
1821 "non-trivial casts should be done with the SCEVs directly!")((SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType
()) && "non-trivial casts should be done with the SCEVs directly!"
) ? static_cast<void> (0) : __assert_fail ("SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && \"non-trivial casts should be done with the SCEVs directly!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1821, __PRETTY_FUNCTION__))
;
1822 V = InsertNoopCastOfTo(V, Ty);
1823 }
1824 return V;
1825}
1826
1827ScalarEvolution::ValueOffsetPair
1828SCEVExpander::FindValueInExprValueMap(const SCEV *S,
1829 const Instruction *InsertPt) {
1830 SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S);
1831 // If the expansion is not in CanonicalMode, and the SCEV contains any
1832 // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
1833 if (CanonicalMode || !SE.containsAddRecurrence(S)) {
1834 // If S is scConstant, it may be worse to reuse an existing Value.
1835 if (S->getSCEVType() != scConstant && Set) {
1836 // Choose a Value from the set which dominates the insertPt.
1837 // insertPt should be inside the Value's parent loop so as not to break
1838 // the LCSSA form.
1839 for (auto const &VOPair : *Set) {
1840 Value *V = VOPair.first;
1841 ConstantInt *Offset = VOPair.second;
1842 Instruction *EntInst = nullptr;
1843 if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
1844 S->getType() == V->getType() &&
1845 EntInst->getFunction() == InsertPt->getFunction() &&
1846 SE.DT.dominates(EntInst, InsertPt) &&
1847 (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1848 SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
1849 return {V, Offset};
1850 }
1851 }
1852 }
1853 return {nullptr, nullptr};
1854}
1855
1856// The expansion of SCEV will either reuse a previous Value in ExprValueMap,
1857// or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
1858// and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
1859// literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
1860// the expansion will try to reuse Value from ExprValueMap, and only when it
1861// fails, expand the SCEV literally.
1862Value *SCEVExpander::expand(const SCEV *S) {
1863 // Compute an insertion point for this SCEV object. Hoist the instructions
1864 // as far out in the loop nest as possible.
1865 Instruction *InsertPt = &*Builder.GetInsertPoint();
1866
1867 // We can move insertion point only if there is no div or rem operations
1868 // otherwise we are risky to move it over the check for zero denominator.
1869 auto SafeToHoist = [](const SCEV *S) {
1870 return !SCEVExprContains(S, [](const SCEV *S) {
1871 if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1872 if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
1873 // Division by non-zero constants can be hoisted.
1874 return SC->getValue()->isZero();
1875 // All other divisions should not be moved as they may be
1876 // divisions by zero and should be kept within the
1877 // conditions of the surrounding loops that guard their
1878 // execution (see PR35406).
1879 return true;
1880 }
1881 return false;
1882 });
1883 };
1884 if (SafeToHoist(S)) {
1885 for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1886 L = L->getParentLoop()) {
1887 if (SE.isLoopInvariant(S, L)) {
1888 if (!L) break;
1889 if (BasicBlock *Preheader = L->getLoopPreheader())
1890 InsertPt = Preheader->getTerminator();
1891 else
1892 // LSR sets the insertion point for AddRec start/step values to the
1893 // block start to simplify value reuse, even though it's an invalid
1894 // position. SCEVExpander must correct for this in all cases.
1895 InsertPt = &*L->getHeader()->getFirstInsertionPt();
1896 } else {
1897 // If the SCEV is computable at this level, insert it into the header
1898 // after the PHIs (and after any other instructions that we've inserted
1899 // there) so that it is guaranteed to dominate any user inside the loop.
1900 if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1901 InsertPt = &*L->getHeader()->getFirstInsertionPt();
1902
1903 while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
1904 (isInsertedInstruction(InsertPt) ||
1905 isa<DbgInfoIntrinsic>(InsertPt))) {
1906 InsertPt = &*std::next(InsertPt->getIterator());
1907 }
1908 break;
1909 }
1910 }
1911 }
1912
1913 // Check to see if we already expanded this here.
1914 auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
1915 if (I != InsertedExpressions.end())
1916 return I->second;
1917
1918 SCEVInsertPointGuard Guard(Builder, this);
1919 Builder.SetInsertPoint(InsertPt);
1920
1921 // Expand the expression into instructions.
1922 ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
1923 Value *V = VO.first;
1924
1925 if (!V)
1926 V = visit(S);
1927 else if (VO.second) {
1928 if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
1929 Type *Ety = Vty->getPointerElementType();
1930 int64_t Offset = VO.second->getSExtValue();
1931 int64_t ESize = SE.getTypeSizeInBits(Ety);
1932 if ((Offset * 8) % ESize == 0) {
1933 ConstantInt *Idx =
1934 ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
1935 V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
1936 } else {
1937 ConstantInt *Idx =
1938 ConstantInt::getSigned(VO.second->getType(), -Offset);
1939 unsigned AS = Vty->getAddressSpace();
1940 V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
1941 V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
1942 "uglygep");
1943 V = Builder.CreateBitCast(V, Vty);
1944 }
1945 } else {
1946 V = Builder.CreateSub(V, VO.second);
1947 }
1948 }
1949 // Remember the expanded value for this SCEV at this location.
1950 //
1951 // This is independent of PostIncLoops. The mapped value simply materializes
1952 // the expression at this insertion point. If the mapped value happened to be
1953 // a postinc expansion, it could be reused by a non-postinc user, but only if
1954 // its insertion point was already at the head of the loop.
1955 InsertedExpressions[std::make_pair(S, InsertPt)] = V;
1956 return V;
1957}
1958
1959void SCEVExpander::rememberInstruction(Value *I) {
1960 auto DoInsert = [this](Value *V) {
1961 if (!PostIncLoops.empty())
1962 InsertedPostIncValues.insert(V);
1963 else
1964 InsertedValues.insert(V);
1965 };
1966 DoInsert(I);
1967
1968 if (!PreserveLCSSA)
1969 return;
1970
1971 if (auto *Inst = dyn_cast<Instruction>(I)) {
1972 // A new instruction has been added, which might introduce new uses outside
1973 // a defining loop. Fix LCSSA from for each operand of the new instruction,
1974 // if required.
1975 for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd;
1976 OpIdx++)
1977 fixupLCSSAFormFor(Inst, OpIdx);
1978 }
1979}
1980
1981/// getOrInsertCanonicalInductionVariable - This method returns the
1982/// canonical induction variable of the specified type for the specified
1983/// loop (inserting one if there is none). A canonical induction variable
1984/// starts at zero and steps by one on each iteration.
1985PHINode *
1986SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
1987 Type *Ty) {
1988 assert(Ty->isIntegerTy() && "Can only insert integer induction variables!")((Ty->isIntegerTy() && "Can only insert integer induction variables!"
) ? static_cast<void> (0) : __assert_fail ("Ty->isIntegerTy() && \"Can only insert integer induction variables!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 1988, __PRETTY_FUNCTION__))
;
1989
1990 // Build a SCEV for {0,+,1}<L>.
1991 // Conservatively use FlagAnyWrap for now.
1992 const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0),
1993 SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
1994
1995 // Emit code for it.
1996 SCEVInsertPointGuard Guard(Builder, this);
1997 PHINode *V = cast<PHINode>(expandCodeForImpl(
1998 H, nullptr, &*L->getHeader()->getFirstInsertionPt(), false));
1999
2000 return V;
2001}
2002
2003/// replaceCongruentIVs - Check for congruent phis in this loop header and
2004/// replace them with their most canonical representative. Return the number of
2005/// phis eliminated.
2006///
2007/// This does not depend on any SCEVExpander state but should be used in
2008/// the same context that SCEVExpander is used.
2009unsigned
2010SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
2011 SmallVectorImpl<WeakTrackingVH> &DeadInsts,
2012 const TargetTransformInfo *TTI) {
2013 // Find integer phis in order of increasing width.
2014 SmallVector<PHINode*, 8> Phis;
2015 for (PHINode &PN : L->getHeader()->phis())
2016 Phis.push_back(&PN);
2017
2018 if (TTI)
2019 llvm::sort(Phis, [](Value *LHS, Value *RHS) {
2020 // Put pointers at the back and make sure pointer < pointer = false.
2021 if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
2022 return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
2023 return RHS->getType()->getPrimitiveSizeInBits() <
2024 LHS->getType()->getPrimitiveSizeInBits();
2025 });
2026
2027 unsigned NumElim = 0;
2028 DenseMap<const SCEV *, PHINode *> ExprToIVMap;
2029 // Process phis from wide to narrow. Map wide phis to their truncation
2030 // so narrow phis can reuse them.
2031 for (PHINode *Phi : Phis) {
2032 auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
2033 if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
2034 return V;
2035 if (!SE.isSCEVable(PN->getType()))
2036 return nullptr;
2037 auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
2038 if (!Const)
2039 return nullptr;
2040 return Const->getValue();
2041 };
2042
2043 // Fold constant phis. They may be congruent to other constant phis and
2044 // would confuse the logic below that expects proper IVs.
2045 if (Value *V = SimplifyPHINode(Phi)) {
2046 if (V->getType() != Phi->getType())
2047 continue;
2048 Phi->replaceAllUsesWith(V);
2049 DeadInsts.emplace_back(Phi);
2050 ++NumElim;
2051 DEBUG_WITH_TYPE(DebugType, dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated constant iv: "
<< *Phi << '\n'; } } while (false)
2052 << "INDVARS: Eliminated constant iv: " << *Phi << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated constant iv: "
<< *Phi << '\n'; } } while (false)
;
2053 continue;
2054 }
2055
2056 if (!SE.isSCEVable(Phi->getType()))
2057 continue;
2058
2059 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
2060 if (!OrigPhiRef) {
2061 OrigPhiRef = Phi;
2062 if (Phi->getType()->isIntegerTy() && TTI &&
2063 TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
2064 // This phi can be freely truncated to the narrowest phi type. Map the
2065 // truncated expression to it so it will be reused for narrow types.
2066 const SCEV *TruncExpr =
2067 SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
2068 ExprToIVMap[TruncExpr] = Phi;
2069 }
2070 continue;
2071 }
2072
2073 // Replacing a pointer phi with an integer phi or vice-versa doesn't make
2074 // sense.
2075 if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
2076 continue;
2077
2078 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2079 Instruction *OrigInc = dyn_cast<Instruction>(
2080 OrigPhiRef->getIncomingValueForBlock(LatchBlock));
2081 Instruction *IsomorphicInc =
2082 dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
2083
2084 if (OrigInc && IsomorphicInc) {
2085 // If this phi has the same width but is more canonical, replace the
2086 // original with it. As part of the "more canonical" determination,
2087 // respect a prior decision to use an IV chain.
2088 if (OrigPhiRef->getType() == Phi->getType() &&
2089 !(ChainedPhis.count(Phi) ||
2090 isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
2091 (ChainedPhis.count(Phi) ||
2092 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
2093 std::swap(OrigPhiRef, Phi);
2094 std::swap(OrigInc, IsomorphicInc);
2095 }
2096 // Replacing the congruent phi is sufficient because acyclic
2097 // redundancy elimination, CSE/GVN, should handle the
2098 // rest. However, once SCEV proves that a phi is congruent,
2099 // it's often the head of an IV user cycle that is isomorphic
2100 // with the original phi. It's worth eagerly cleaning up the
2101 // common case of a single IV increment so that DeleteDeadPHIs
2102 // can remove cycles that had postinc uses.
2103 const SCEV *TruncExpr =
2104 SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
2105 if (OrigInc != IsomorphicInc &&
2106 TruncExpr == SE.getSCEV(IsomorphicInc) &&
2107 SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2108 hoistIVInc(OrigInc, IsomorphicInc)) {
2109 DEBUG_WITH_TYPE(DebugType,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv.inc: "
<< *IsomorphicInc << '\n'; } } while (false)
2110 dbgs() << "INDVARS: Eliminated congruent iv.inc: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv.inc: "
<< *IsomorphicInc << '\n'; } } while (false)
2111 << *IsomorphicInc << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv.inc: "
<< *IsomorphicInc << '\n'; } } while (false)
;
2112 Value *NewInc = OrigInc;
2113 if (OrigInc->getType() != IsomorphicInc->getType()) {
2114 Instruction *IP = nullptr;
2115 if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
2116 IP = &*PN->getParent()->getFirstInsertionPt();
2117 else
2118 IP = OrigInc->getNextNode();
2119
2120 IRBuilder<> Builder(IP);
2121 Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
2122 NewInc = Builder.CreateTruncOrBitCast(
2123 OrigInc, IsomorphicInc->getType(), IVName);
2124 }
2125 IsomorphicInc->replaceAllUsesWith(NewInc);
2126 DeadInsts.emplace_back(IsomorphicInc);
2127 }
2128 }
2129 }
2130 DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv: "
<< *Phi << '\n'; } } while (false)
2131 << *Phi << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv: "
<< *Phi << '\n'; } } while (false)
;
2132 DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Original iv: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Original iv: " <<
*OrigPhiRef << '\n'; } } while (false)
2133 << *OrigPhiRef << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
(DebugType)) { dbgs() << "INDVARS: Original iv: " <<
*OrigPhiRef << '\n'; } } while (false)
;
2134 ++NumElim;
2135 Value *NewIV = OrigPhiRef;
2136 if (OrigPhiRef->getType() != Phi->getType()) {
2137 IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
2138 Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2139 NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
2140 }
2141 Phi->replaceAllUsesWith(NewIV);
2142 DeadInsts.emplace_back(Phi);
2143 }
2144 return NumElim;
2145}
2146
2147Value *SCEVExpander::getExactExistingExpansion(const SCEV *S,
2148 const Instruction *At, Loop *L) {
2149 Optional<ScalarEvolution::ValueOffsetPair> VO =
2150 getRelatedExistingExpansion(S, At, L);
2151 if (VO && VO.getValue().second == nullptr)
2152 return VO.getValue().first;
2153 return nullptr;
2154}
2155
2156Optional<ScalarEvolution::ValueOffsetPair>
2157SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
2158 Loop *L) {
2159 using namespace llvm::PatternMatch;
2160
2161 SmallVector<BasicBlock *, 4> ExitingBlocks;
2162 L->getExitingBlocks(ExitingBlocks);
2163
2164 // Look for suitable value in simple conditions at the loop exits.
2165 for (BasicBlock *BB : ExitingBlocks) {
2166 ICmpInst::Predicate Pred;
2167 Instruction *LHS, *RHS;
2168
2169 if (!match(BB->getTerminator(),
2170 m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
2171 m_BasicBlock(), m_BasicBlock())))
2172 continue;
2173
2174 if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
2175 return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
2176
2177 if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
2178 return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
2179 }
2180
2181 // Use expand's logic which is used for reusing a previous Value in
2182 // ExprValueMap.
2183 ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
2184 if (VO.first)
2185 return VO;
2186
2187 // There is potential to make this significantly smarter, but this simple
2188 // heuristic already gets some interesting cases.
2189
2190 // Can not find suitable value.
2191 return None;
2192}
2193
2194template<typename T> static int costAndCollectOperands(
2195 const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
2196 TargetTransformInfo::TargetCostKind CostKind,
2197 SmallVectorImpl<SCEVOperand> &Worklist) {
2198
2199 const T *S = cast<T>(WorkItem.S);
2200 int Cost = 0;
2201 // Object to help map SCEV operands to expanded IR instructions.
2202 struct OperationIndices {
2203 OperationIndices(unsigned Opc, size_t min, size_t max) :
2204 Opcode(Opc), MinIdx(min), MaxIdx(max) { }
2205 unsigned Opcode;
2206 size_t MinIdx;
2207 size_t MaxIdx;
2208 };
2209
2210 // Collect the operations of all the instructions that will be needed to
2211 // expand the SCEVExpr. This is so that when we come to cost the operands,
2212 // we know what the generated user(s) will be.
2213 SmallVector<OperationIndices, 2> Operations;
2214
2215 auto CastCost = [&](unsigned Opcode) {
2216 Operations.emplace_back(Opcode, 0, 0);
2217 return TTI.getCastInstrCost(Opcode, S->getType(),
2218 S->getOperand(0)->getType(),
2219 TTI::CastContextHint::None, CostKind);
2220 };
2221
2222 auto ArithCost = [&](unsigned Opcode, unsigned NumRequired,
2223 unsigned MinIdx = 0, unsigned MaxIdx = 1) {
2224 Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2225 return NumRequired *
2226 TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);
2227 };
2228
2229 auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired,
2230 unsigned MinIdx, unsigned MaxIdx) {
2231 Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2232 Type *OpType = S->getOperand(0)->getType();
2233 return NumRequired *
2234 TTI.getCmpSelInstrCost(Opcode, OpType,
2235 CmpInst::makeCmpResultType(OpType), CostKind);
2236 };
2237
2238 switch (S->getSCEVType()) {
2239 default:
2240 llvm_unreachable("No other scev expressions possible.")::llvm::llvm_unreachable_internal("No other scev expressions possible."
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2240)
;
2241 case scUnknown:
2242 case scConstant:
2243 return 0;
2244 case scTruncate:
2245 Cost = CastCost(Instruction::Trunc);
2246 break;
2247 case scZeroExtend:
2248 Cost = CastCost(Instruction::ZExt);
2249 break;
2250 case scSignExtend:
2251 Cost = CastCost(Instruction::SExt);
2252 break;
2253 case scUDivExpr: {
2254 unsigned Opcode = Instruction::UDiv;
2255 if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
2256 if (SC->getAPInt().isPowerOf2())
2257 Opcode = Instruction::LShr;
2258 Cost = ArithCost(Opcode, 1);
2259 break;
2260 }
2261 case scAddExpr:
2262 Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
2263 break;
2264 case scMulExpr:
2265 // TODO: this is a very pessimistic cost modelling for Mul,
2266 // because of Bin Pow algorithm actually used by the expander,
2267 // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
2268 Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
2269 break;
2270 case scSMaxExpr:
2271 case scUMaxExpr:
2272 case scSMinExpr:
2273 case scUMinExpr: {
2274 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
2275 Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
2276 break;
2277 }
2278 case scAddRecExpr: {
2279 // In this polynominal, we may have some zero operands, and we shouldn't
2280 // really charge for those. So how many non-zero coeffients are there?
2281 int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
2282 return !Op->isZero();
2283 });
2284
2285 assert(NumTerms >= 1 && "Polynominal should have at least one term.")((NumTerms >= 1 && "Polynominal should have at least one term."
) ? static_cast<void> (0) : __assert_fail ("NumTerms >= 1 && \"Polynominal should have at least one term.\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2285, __PRETTY_FUNCTION__))
;
2286 assert(!(*std::prev(S->operands().end()))->isZero() &&((!(*std::prev(S->operands().end()))->isZero() &&
"Last operand should not be zero") ? static_cast<void>
(0) : __assert_fail ("!(*std::prev(S->operands().end()))->isZero() && \"Last operand should not be zero\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2287, __PRETTY_FUNCTION__))
2287 "Last operand should not be zero")((!(*std::prev(S->operands().end()))->isZero() &&
"Last operand should not be zero") ? static_cast<void>
(0) : __assert_fail ("!(*std::prev(S->operands().end()))->isZero() && \"Last operand should not be zero\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2287, __PRETTY_FUNCTION__))
;
2288
2289 // Ignoring constant term (operand 0), how many of the coeffients are u> 1?
2290 int NumNonZeroDegreeNonOneTerms =
2291 llvm::count_if(S->operands(), [](const SCEV *Op) {
2292 auto *SConst = dyn_cast<SCEVConstant>(Op);
2293 return !SConst || SConst->getAPInt().ugt(1);
2294 });
2295
2296 // Much like with normal add expr, the polynominal will require
2297 // one less addition than the number of it's terms.
2298 int AddCost = ArithCost(Instruction::Add, NumTerms - 1,
2299 /*MinIdx*/1, /*MaxIdx*/1);
2300 // Here, *each* one of those will require a multiplication.
2301 int MulCost = ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms);
2302 Cost = AddCost + MulCost;
2303
2304 // What is the degree of this polynominal?
2305 int PolyDegree = S->getNumOperands() - 1;
2306 assert(PolyDegree >= 1 && "Should be at least affine.")((PolyDegree >= 1 && "Should be at least affine.")
? static_cast<void> (0) : __assert_fail ("PolyDegree >= 1 && \"Should be at least affine.\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2306, __PRETTY_FUNCTION__))
;
2307
2308 // The final term will be:
2309 // Op_{PolyDegree} * x ^ {PolyDegree}
2310 // Where x ^ {PolyDegree} will again require PolyDegree-1 mul operations.
2311 // Note that x ^ {PolyDegree} = x * x ^ {PolyDegree-1} so charging for
2312 // x ^ {PolyDegree} will give us x ^ {2} .. x ^ {PolyDegree-1} for free.
2313 // FIXME: this is conservatively correct, but might be overly pessimistic.
2314 Cost += MulCost * (PolyDegree - 1);
2315 break;
2316 }
2317 }
2318
2319 for (auto &CostOp : Operations) {
2320 for (auto SCEVOp : enumerate(S->operands())) {
2321 // Clamp the index to account for multiple IR operations being chained.
2322 size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
2323 size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
2324 Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2325 }
2326 }
2327 return Cost;
2328}
2329
2330bool SCEVExpander::isHighCostExpansionHelper(
2331 const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
2332 int &BudgetRemaining, const TargetTransformInfo &TTI,
2333 SmallPtrSetImpl<const SCEV *> &Processed,
2334 SmallVectorImpl<SCEVOperand> &Worklist) {
2335 if (BudgetRemaining < 0)
2336 return true; // Already run out of budget, give up.
2337
2338 const SCEV *S = WorkItem.S;
2339 // Was the cost of expansion of this expression already accounted for?
2340 if (!isa<SCEVConstant>(S) && !Processed.insert(S).second)
2341 return false; // We have already accounted for this expression.
2342
2343 // If we can find an existing value for this scev available at the point "At"
2344 // then consider the expression cheap.
2345 if (getRelatedExistingExpansion(S, &At, L))
2346 return false; // Consider the expression to be free.
2347
2348 // Assume to be zero-cost.
2349 if (isa<SCEVUnknown>(S))
2350 return false;
2351
2352 TargetTransformInfo::TargetCostKind CostKind =
2353 L->getHeader()->getParent()->hasMinSize()
2354 ? TargetTransformInfo::TCK_CodeSize
2355 : TargetTransformInfo::TCK_RecipThroughput;
2356
2357 if (auto *Constant = dyn_cast<SCEVConstant>(S)) {
2358 // Only evalulate the costs of constants when optimizing for size.
2359 if (CostKind != TargetTransformInfo::TCK_CodeSize)
2360 return 0;
2361 const APInt &Imm = Constant->getAPInt();
2362 Type *Ty = S->getType();
2363 BudgetRemaining -=
2364 TTI.getIntImmCostInst(WorkItem.ParentOpcode, WorkItem.OperandIdx,
2365 Imm, Ty, CostKind);
2366 return BudgetRemaining < 0;
2367 } else if (isa<SCEVCastExpr>(S)) {
2368 int Cost =
2369 costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
2370 BudgetRemaining -= Cost;
2371 return false; // Will answer upon next entry into this function.
2372 } else if (isa<SCEVUDivExpr>(S)) {
2373 // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
2374 // HowManyLessThans produced to compute a precise expression, rather than a
2375 // UDiv from the user's code. If we can't find a UDiv in the code with some
2376 // simple searching, we need to account for it's cost.
2377
2378 // At the beginning of this function we already tried to find existing
2379 // value for plain 'S'. Now try to lookup 'S + 1' since it is common
2380 // pattern involving division. This is just a simple search heuristic.
2381 if (getRelatedExistingExpansion(
2382 SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
2383 return false; // Consider it to be free.
2384
2385 int Cost =
2386 costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
2387 // Need to count the cost of this UDiv.
2388 BudgetRemaining -= Cost;
2389 return false; // Will answer upon next entry into this function.
2390 } else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
2391 assert(NAry->getNumOperands() > 1 &&((NAry->getNumOperands() > 1 && "Nary expr should have more than 1 operand."
) ? static_cast<void> (0) : __assert_fail ("NAry->getNumOperands() > 1 && \"Nary expr should have more than 1 operand.\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2392, __PRETTY_FUNCTION__))
2392 "Nary expr should have more than 1 operand.")((NAry->getNumOperands() > 1 && "Nary expr should have more than 1 operand."
) ? static_cast<void> (0) : __assert_fail ("NAry->getNumOperands() > 1 && \"Nary expr should have more than 1 operand.\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2392, __PRETTY_FUNCTION__))
;
2393 // The simple nary expr will require one less op (or pair of ops)
2394 // than the number of it's terms.
2395 int Cost =
2396 costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
2397 BudgetRemaining -= Cost;
2398 return BudgetRemaining < 0;
2399 } else if (isa<SCEVAddRecExpr>(S)) {
2400 assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&((cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
"Polynomial should be at least linear") ? static_cast<void
> (0) : __assert_fail ("cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && \"Polynomial should be at least linear\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2401, __PRETTY_FUNCTION__))
2401 "Polynomial should be at least linear")((cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
"Polynomial should be at least linear") ? static_cast<void
> (0) : __assert_fail ("cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && \"Polynomial should be at least linear\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2401, __PRETTY_FUNCTION__))
;
2402 BudgetRemaining -= costAndCollectOperands<SCEVAddRecExpr>(
2403 WorkItem, TTI, CostKind, Worklist);
2404 return BudgetRemaining < 0;
2405 } else
2406 llvm_unreachable("No other scev expressions possible.")::llvm::llvm_unreachable_internal("No other scev expressions possible."
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2406)
;
2407}
2408
2409Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
2410 Instruction *IP) {
2411 assert(IP)((IP) ? static_cast<void> (0) : __assert_fail ("IP", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2411, __PRETTY_FUNCTION__))
;
2412 switch (Pred->getKind()) {
2413 case SCEVPredicate::P_Union:
2414 return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
2415 case SCEVPredicate::P_Equal:
2416 return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
2417 case SCEVPredicate::P_Wrap: {
2418 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2419 return expandWrapPredicate(AddRecPred, IP);
2420 }
2421 }
2422 llvm_unreachable("Unknown SCEV predicate type")::llvm::llvm_unreachable_internal("Unknown SCEV predicate type"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2422)
;
2423}
2424
2425Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
2426 Instruction *IP) {
2427 Value *Expr0 =
2428 expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
2429 Value *Expr1 =
2430 expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
2431
2432 Builder.SetInsertPoint(IP);
2433 auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
2434 return I;
2435}
2436
2437Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
2438 Instruction *Loc, bool Signed) {
2439 assert(AR->isAffine() && "Cannot generate RT check for "((AR->isAffine() && "Cannot generate RT check for "
"non-affine expression") ? static_cast<void> (0) : __assert_fail
("AR->isAffine() && \"Cannot generate RT check for \" \"non-affine expression\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2440, __PRETTY_FUNCTION__))
2440 "non-affine expression")((AR->isAffine() && "Cannot generate RT check for "
"non-affine expression") ? static_cast<void> (0) : __assert_fail
("AR->isAffine() && \"Cannot generate RT check for \" \"non-affine expression\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2440, __PRETTY_FUNCTION__))
;
2441
2442 SCEVUnionPredicate Pred;
2443 const SCEV *ExitCount =
2444 SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);
2445
2446 assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count")((ExitCount != SE.getCouldNotCompute() && "Invalid loop count"
) ? static_cast<void> (0) : __assert_fail ("ExitCount != SE.getCouldNotCompute() && \"Invalid loop count\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2446, __PRETTY_FUNCTION__))
;
2447
2448 const SCEV *Step = AR->getStepRecurrence(SE);
2449 const SCEV *Start = AR->getStart();
2450
2451 Type *ARTy = AR->getType();
2452 unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
2453 unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2454
2455 // The expression {Start,+,Step} has nusw/nssw if
2456 // Step < 0, Start - |Step| * Backedge <= Start
2457 // Step >= 0, Start + |Step| * Backedge > Start
2458 // and |Step| * Backedge doesn't unsigned overflow.
2459
2460 IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
2461 Builder.SetInsertPoint(Loc);
2462 Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false);
2463
2464 IntegerType *Ty =
2465 IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
2466 Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty;
2467
2468 Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false);
2469 Value *NegStepValue =
2470 expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false);
2471 Value *StartValue = expandCodeForImpl(Start, ARExpandTy, Loc, false);
2472
2473 ConstantInt *Zero =
2474 ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits));
2475
2476 Builder.SetInsertPoint(Loc);
2477 // Compute |Step|
2478 Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2479 Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2480
2481 // Get the backedge taken count and truncate or extended to the AR type.
2482 Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2483 auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
2484 Intrinsic::umul_with_overflow, Ty);
2485
2486 // Compute |Step| * Backedge
2487 CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
2488 Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2489 Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
2490
2491 // Compute:
2492 // Start + |Step| * Backedge < Start
2493 // Start - |Step| * Backedge > Start
2494 Value *Add = nullptr, *Sub = nullptr;
2495 if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) {
2496 const SCEV *MulS = SE.getSCEV(MulV);
2497 const SCEV *NegMulS = SE.getNegativeSCEV(MulS);
2498 Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue),
2499 ARPtrTy);
2500 Sub = Builder.CreateBitCast(
2501 expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy);
2502 } else {
2503 Add = Builder.CreateAdd(StartValue, MulV);
2504 Sub = Builder.CreateSub(StartValue, MulV);
2505 }
2506
2507 Value *EndCompareGT = Builder.CreateICmp(
2508 Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
2509
2510 Value *EndCompareLT = Builder.CreateICmp(
2511 Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);
2512
2513 // Select the answer based on the sign of Step.
2514 Value *EndCheck =
2515 Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2516
2517 // If the backedge taken count type is larger than the AR type,
2518 // check that we don't drop any bits by truncating it. If we are
2519 // dropping bits, then we have overflow (unless the step is zero).
2520 if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2521 auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
2522 auto *BackedgeCheck =
2523 Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2524 ConstantInt::get(Loc->getContext(), MaxVal));
2525 BackedgeCheck = Builder.CreateAnd(
2526 BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2527
2528 EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2529 }
2530
2531 return Builder.CreateOr(EndCheck, OfMul);
2532}
2533
2534Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred,
2535 Instruction *IP) {
2536 const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2537 Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2538
2539 // Add a check for NUSW
2540 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)
2541 NUSWCheck = generateOverflowCheck(A, IP, false);
2542
2543 // Add a check for NSSW
2544 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)
2545 NSSWCheck = generateOverflowCheck(A, IP, true);
2546
2547 if (NUSWCheck && NSSWCheck)
2548 return Builder.CreateOr(NUSWCheck, NSSWCheck);
2549
2550 if (NUSWCheck)
2551 return NUSWCheck;
2552
2553 if (NSSWCheck)
2554 return NSSWCheck;
2555
2556 return ConstantInt::getFalse(IP->getContext());
2557}
2558
2559Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
2560 Instruction *IP) {
2561 auto *BoolType = IntegerType::get(IP->getContext(), 1);
2562 Value *Check = ConstantInt::getNullValue(BoolType);
2563
2564 // Loop over all checks in this set.
2565 for (auto Pred : Union->getPredicates()) {
2566 auto *NextCheck = expandCodeForPredicate(Pred, IP);
2567 Builder.SetInsertPoint(IP);
2568 Check = Builder.CreateOr(Check, NextCheck);
2569 }
2570
2571 return Check;
2572}
2573
2574Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) {
2575 assert(PreserveLCSSA)((PreserveLCSSA) ? static_cast<void> (0) : __assert_fail
("PreserveLCSSA", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2575, __PRETTY_FUNCTION__))
;
2576 SmallVector<Instruction *, 1> ToUpdate;
2577
2578 auto *OpV = User->getOperand(OpIdx);
2579 auto *OpI = dyn_cast<Instruction>(OpV);
2580 if (!OpI)
2581 return OpV;
2582
2583 Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent());
2584 Loop *UseLoop = SE.LI.getLoopFor(User->getParent());
2585 if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))
2586 return OpV;
2587
2588 ToUpdate.push_back(OpI);
2589 SmallVector<PHINode *, 16> PHIsToRemove;
2590 formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove);
2591 for (PHINode *PN : PHIsToRemove) {
2592 if (!PN->use_empty())
2593 continue;
2594 InsertedValues.erase(PN);
2595 InsertedPostIncValues.erase(PN);
2596 PN->eraseFromParent();
2597 }
2598
2599 return User->getOperand(OpIdx);
2600}
2601
2602namespace {
2603// Search for a SCEV subexpression that is not safe to expand. Any expression
2604// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
2605// UDiv expressions. We don't know if the UDiv is derived from an IR divide
2606// instruction, but the important thing is that we prove the denominator is
2607// nonzero before expansion.
2608//
2609// IVUsers already checks that IV-derived expressions are safe. So this check is
2610// only needed when the expression includes some subexpression that is not IV
2611// derived.
2612//
2613// Currently, we only allow division by a nonzero constant here. If this is
2614// inadequate, we could easily allow division by SCEVUnknown by using
2615// ValueTracking to check isKnownNonZero().
2616//
2617// We cannot generally expand recurrences unless the step dominates the loop
2618// header. The expander handles the special case of affine recurrences by
2619// scaling the recurrence outside the loop, but this technique isn't generally
2620// applicable. Expanding a nested recurrence outside a loop requires computing
2621// binomial coefficients. This could be done, but the recurrence has to be in a
2622// perfectly reduced form, which can't be guaranteed.
2623struct SCEVFindUnsafe {
2624 ScalarEvolution &SE;
2625 bool IsUnsafe;
2626
2627 SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
2628
2629 bool follow(const SCEV *S) {
2630 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2631 const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
2632 if (!SC || SC->getValue()->isZero()) {
2633 IsUnsafe = true;
2634 return false;
2635 }
2636 }
2637 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2638 const SCEV *Step = AR->getStepRecurrence(SE);
2639 if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
2640 IsUnsafe = true;
2641 return false;
2642 }
2643 }
2644 return true;
2645 }
2646 bool isDone() const { return IsUnsafe; }
2647};
2648}
2649
2650namespace llvm {
2651bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
2652 SCEVFindUnsafe Search(SE);
2653 visitAll(S, Search);
2654 return !Search.IsUnsafe;
2655}
2656
2657bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
2658 ScalarEvolution &SE) {
2659 if (!isSafeToExpand(S, SE))
2660 return false;
2661 // We have to prove that the expanded site of S dominates InsertionPoint.
2662 // This is easy when not in the same block, but hard when S is an instruction
2663 // to be expanded somewhere inside the same block as our insertion point.
2664 // What we really need here is something analogous to an OrderedBasicBlock,
2665 // but for the moment, we paper over the problem by handling two common and
2666 // cheap to check cases.
2667 if (SE.properlyDominates(S, InsertionPoint->getParent()))
2668 return true;
2669 if (SE.dominates(S, InsertionPoint->getParent())) {
2670 if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2671 return true;
2672 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2673 for (const Value *V : InsertionPoint->operand_values())
2674 if (V == U->getValue())
2675 return true;
2676 }
2677 return false;
2678}
2679
2680SCEVExpanderCleaner::~SCEVExpanderCleaner() {
2681 // Result is used, nothing to remove.
2682 if (ResultUsed)
2683 return;
2684
2685 auto InsertedInstructions = Expander.getAllInsertedInstructions();
2686#ifndef NDEBUG
2687 SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
2688 InsertedInstructions.end());
2689 (void)InsertedSet;
2690#endif
2691 // Remove sets with value handles.
2692 Expander.clear();
2693
2694 // Sort so that earlier instructions do not dominate later instructions.
2695 stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) {
2696 return DT.dominates(B, A);
2697 });
2698 // Remove all inserted instructions.
2699 for (Instruction *I : InsertedInstructions) {
2700
2701#ifndef NDEBUG
2702 assert(all_of(I->users(),((all_of(I->users(), [&InsertedSet](Value *U) { return
InsertedSet.contains(cast<Instruction>(U)); }) &&
"removed instruction should only be used by instructions inserted "
"during expansion") ? static_cast<void> (0) : __assert_fail
("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2707, __PRETTY_FUNCTION__))
2703 [&InsertedSet](Value *U) {((all_of(I->users(), [&InsertedSet](Value *U) { return
InsertedSet.contains(cast<Instruction>(U)); }) &&
"removed instruction should only be used by instructions inserted "
"during expansion") ? static_cast<void> (0) : __assert_fail
("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2707, __PRETTY_FUNCTION__))
2704 return InsertedSet.contains(cast<Instruction>(U));((all_of(I->users(), [&InsertedSet](Value *U) { return
InsertedSet.contains(cast<Instruction>(U)); }) &&
"removed instruction should only be used by instructions inserted "
"during expansion") ? static_cast<void> (0) : __assert_fail
("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2707, __PRETTY_FUNCTION__))
2705 }) &&((all_of(I->users(), [&InsertedSet](Value *U) { return
InsertedSet.contains(cast<Instruction>(U)); }) &&
"removed instruction should only be used by instructions inserted "
"during expansion") ? static_cast<void> (0) : __assert_fail
("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2707, __PRETTY_FUNCTION__))
2706 "removed instruction should only be used by instructions inserted "((all_of(I->users(), [&InsertedSet](Value *U) { return
InsertedSet.contains(cast<Instruction>(U)); }) &&
"removed instruction should only be used by instructions inserted "
"during expansion") ? static_cast<void> (0) : __assert_fail
("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2707, __PRETTY_FUNCTION__))
2707 "during expansion")((all_of(I->users(), [&InsertedSet](Value *U) { return
InsertedSet.contains(cast<Instruction>(U)); }) &&
"removed instruction should only be used by instructions inserted "
"during expansion") ? static_cast<void> (0) : __assert_fail
("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2707, __PRETTY_FUNCTION__))
;
2708#endif
2709 assert(!I->getType()->isVoidTy() &&((!I->getType()->isVoidTy() && "inserted instruction should have non-void types"
) ? static_cast<void> (0) : __assert_fail ("!I->getType()->isVoidTy() && \"inserted instruction should have non-void types\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2710, __PRETTY_FUNCTION__))
2710 "inserted instruction should have non-void types")((!I->getType()->isVoidTy() && "inserted instruction should have non-void types"
) ? static_cast<void> (0) : __assert_fail ("!I->getType()->isVoidTy() && \"inserted instruction should have non-void types\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp"
, 2710, __PRETTY_FUNCTION__))
;
2711 I->replaceAllUsesWith(UndefValue::get(I->getType()));
2712 I->eraseFromParent();
2713 }
2714}
2715}

/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h

1//===- llvm/DataLayout.h - Data size & alignment info -----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines layout properties related to datatype size/offset/alignment
10// information. It uses lazy annotations to cache information about how
11// structure types are laid out and used.
12//
13// This structure should be created once, filled in if the defaults are not
14// correct and then passed around by const&. None of the members functions
15// require modification to the object.
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_IR_DATALAYOUT_H
20#define LLVM_IR_DATALAYOUT_H
21
22#include "llvm/ADT/ArrayRef.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/StringRef.h"
26#include "llvm/IR/DerivedTypes.h"
27#include "llvm/IR/Type.h"
28#include "llvm/Support/Casting.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/MathExtras.h"
31#include "llvm/Support/Alignment.h"
32#include "llvm/Support/TypeSize.h"
33#include <cassert>
34#include <cstdint>
35#include <string>
36
37// This needs to be outside of the namespace, to avoid conflict with llvm-c
38// decl.
39using LLVMTargetDataRef = struct LLVMOpaqueTargetData *;
40
41namespace llvm {
42
43class GlobalVariable;
44class LLVMContext;
45class Module;
46class StructLayout;
47class Triple;
48class Value;
49
50/// Enum used to categorize the alignment types stored by LayoutAlignElem
51enum AlignTypeEnum {
52 INVALID_ALIGN = 0,
53 INTEGER_ALIGN = 'i',
54 VECTOR_ALIGN = 'v',
55 FLOAT_ALIGN = 'f',
56 AGGREGATE_ALIGN = 'a'
57};
58
59// FIXME: Currently the DataLayout string carries a "preferred alignment"
60// for types. As the DataLayout is module/global, this should likely be
61// sunk down to an FTTI element that is queried rather than a global
62// preference.
63
64/// Layout alignment element.
65///
66/// Stores the alignment data associated with a given alignment type (integer,
67/// vector, float) and type bit width.
68///
69/// \note The unusual order of elements in the structure attempts to reduce
70/// padding and make the structure slightly more cache friendly.
71struct LayoutAlignElem {
72 /// Alignment type from \c AlignTypeEnum
73 unsigned AlignType : 8;
74 unsigned TypeBitWidth : 24;
75 Align ABIAlign;
76 Align PrefAlign;
77
78 static LayoutAlignElem get(AlignTypeEnum align_type, Align abi_align,
79 Align pref_align, uint32_t bit_width);
80
81 bool operator==(const LayoutAlignElem &rhs) const;
82};
83
84/// Layout pointer alignment element.
85///
86/// Stores the alignment data associated with a given pointer and address space.
87///
88/// \note The unusual order of elements in the structure attempts to reduce
89/// padding and make the structure slightly more cache friendly.
90struct PointerAlignElem {
91 Align ABIAlign;
92 Align PrefAlign;
93 uint32_t TypeByteWidth;
94 uint32_t AddressSpace;
95 uint32_t IndexWidth;
96
97 /// Initializer
98 static PointerAlignElem get(uint32_t AddressSpace, Align ABIAlign,
99 Align PrefAlign, uint32_t TypeByteWidth,
100 uint32_t IndexWidth);
101
102 bool operator==(const PointerAlignElem &rhs) const;
103};
104
105/// A parsed version of the target data layout string in and methods for
106/// querying it.
107///
108/// The target data layout string is specified *by the target* - a frontend
109/// generating LLVM IR is required to generate the right target data for the
110/// target being codegen'd to.
111class DataLayout {
112public:
113 enum class FunctionPtrAlignType {
114 /// The function pointer alignment is independent of the function alignment.
115 Independent,
116 /// The function pointer alignment is a multiple of the function alignment.
117 MultipleOfFunctionAlign,
118 };
119private:
120 /// Defaults to false.
121 bool BigEndian;
122
123 unsigned AllocaAddrSpace;
124 MaybeAlign StackNaturalAlign;
125 unsigned ProgramAddrSpace;
126
127 MaybeAlign FunctionPtrAlign;
128 FunctionPtrAlignType TheFunctionPtrAlignType;
129
130 enum ManglingModeT {
131 MM_None,
132 MM_ELF,
133 MM_MachO,
134 MM_WinCOFF,
135 MM_WinCOFFX86,
136 MM_Mips,
137 MM_XCOFF
138 };
139 ManglingModeT ManglingMode;
140
141 SmallVector<unsigned char, 8> LegalIntWidths;
142
143 /// Primitive type alignment data. This is sorted by type and bit
144 /// width during construction.
145 using AlignmentsTy = SmallVector<LayoutAlignElem, 16>;
146 AlignmentsTy Alignments;
147
148 AlignmentsTy::const_iterator
149 findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth) const {
150 return const_cast<DataLayout *>(this)->findAlignmentLowerBound(AlignType,
151 BitWidth);
152 }
153
154 AlignmentsTy::iterator
155 findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth);
156
157 /// The string representation used to create this DataLayout
158 std::string StringRepresentation;
159
160 using PointersTy = SmallVector<PointerAlignElem, 8>;
161 PointersTy Pointers;
162
163 PointersTy::const_iterator
164 findPointerLowerBound(uint32_t AddressSpace) const {
165 return const_cast<DataLayout *>(this)->findPointerLowerBound(AddressSpace);
166 }
167
168 PointersTy::iterator findPointerLowerBound(uint32_t AddressSpace);
169
170 // The StructType -> StructLayout map.
171 mutable void *LayoutMap = nullptr;
172
173 /// Pointers in these address spaces are non-integral, and don't have a
174 /// well-defined bitwise representation.
175 SmallVector<unsigned, 8> NonIntegralAddressSpaces;
176
177 /// Attempts to set the alignment of the given type. Returns an error
178 /// description on failure.
179 Error setAlignment(AlignTypeEnum align_type, Align abi_align,
180 Align pref_align, uint32_t bit_width);
181
182 Align getAlignmentInfo(AlignTypeEnum align_type, uint32_t bit_width,
183 bool ABIAlign, Type *Ty) const;
184
185 /// Attempts to set the alignment of a pointer in the given address space.
186 /// Returns an error description on failure.
187 Error setPointerAlignment(uint32_t AddrSpace, Align ABIAlign, Align PrefAlign,
188 uint32_t TypeByteWidth, uint32_t IndexWidth);
189
190 /// Internal helper method that returns requested alignment for type.
191 Align getAlignment(Type *Ty, bool abi_or_pref) const;
192
193 /// Attempts to parse a target data specification string and reports an error
194 /// if the string is malformed.
195 Error parseSpecifier(StringRef Desc);
196
197 // Free all internal data structures.
198 void clear();
199
200public:
201 /// Constructs a DataLayout from a specification string. See reset().
202 explicit DataLayout(StringRef LayoutDescription) {
203 reset(LayoutDescription);
204 }
205
206 /// Initialize target data from properties stored in the module.
207 explicit DataLayout(const Module *M);
208
209 DataLayout(const DataLayout &DL) { *this = DL; }
210
211 ~DataLayout(); // Not virtual, do not subclass this class
212
213 DataLayout &operator=(const DataLayout &DL) {
214 clear();
215 StringRepresentation = DL.StringRepresentation;
216 BigEndian = DL.isBigEndian();
217 AllocaAddrSpace = DL.AllocaAddrSpace;
218 StackNaturalAlign = DL.StackNaturalAlign;
219 FunctionPtrAlign = DL.FunctionPtrAlign;
220 TheFunctionPtrAlignType = DL.TheFunctionPtrAlignType;
221 ProgramAddrSpace = DL.ProgramAddrSpace;
222 ManglingMode = DL.ManglingMode;
223 LegalIntWidths = DL.LegalIntWidths;
224 Alignments = DL.Alignments;
225 Pointers = DL.Pointers;
226 NonIntegralAddressSpaces = DL.NonIntegralAddressSpaces;
227 return *this;
228 }
229
230 bool operator==(const DataLayout &Other) const;
231 bool operator!=(const DataLayout &Other) const { return !(*this == Other); }
232
233 void init(const Module *M);
234
235 /// Parse a data layout string (with fallback to default values).
236 void reset(StringRef LayoutDescription);
237
238 /// Parse a data layout string and return the layout. Return an error
239 /// description on failure.
240 static Expected<DataLayout> parse(StringRef LayoutDescription);
241
242 /// Layout endianness...
243 bool isLittleEndian() const { return !BigEndian; }
244 bool isBigEndian() const { return BigEndian; }
245
246 /// Returns the string representation of the DataLayout.
247 ///
248 /// This representation is in the same format accepted by the string
249 /// constructor above. This should not be used to compare two DataLayout as
250 /// different string can represent the same layout.
251 const std::string &getStringRepresentation() const {
252 return StringRepresentation;
253 }
254
255 /// Test if the DataLayout was constructed from an empty string.
256 bool isDefault() const { return StringRepresentation.empty(); }
257
258 /// Returns true if the specified type is known to be a native integer
259 /// type supported by the CPU.
260 ///
261 /// For example, i64 is not native on most 32-bit CPUs and i37 is not native
262 /// on any known one. This returns false if the integer width is not legal.
263 ///
264 /// The width is specified in bits.
265 bool isLegalInteger(uint64_t Width) const {
266 for (unsigned LegalIntWidth : LegalIntWidths)
267 if (LegalIntWidth == Width)
268 return true;
269 return false;
270 }
271
272 bool isIllegalInteger(uint64_t Width) const { return !isLegalInteger(Width); }
273
274 /// Returns true if the given alignment exceeds the natural stack alignment.
275 bool exceedsNaturalStackAlignment(Align Alignment) const {
276 return StackNaturalAlign && (Alignment > *StackNaturalAlign);
277 }
278
279 Align getStackAlignment() const {
280 assert(StackNaturalAlign && "StackNaturalAlign must be defined")((StackNaturalAlign && "StackNaturalAlign must be defined"
) ? static_cast<void> (0) : __assert_fail ("StackNaturalAlign && \"StackNaturalAlign must be defined\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h"
, 280, __PRETTY_FUNCTION__))
;
281 return *StackNaturalAlign;
282 }
283
284 unsigned getAllocaAddrSpace() const { return AllocaAddrSpace; }
285
286 /// Returns the alignment of function pointers, which may or may not be
287 /// related to the alignment of functions.
288 /// \see getFunctionPtrAlignType
289 MaybeAlign getFunctionPtrAlign() const { return FunctionPtrAlign; }
290
291 /// Return the type of function pointer alignment.
292 /// \see getFunctionPtrAlign
293 FunctionPtrAlignType getFunctionPtrAlignType() const {
294 return TheFunctionPtrAlignType;
295 }
296
297 unsigned getProgramAddressSpace() const { return ProgramAddrSpace; }
298
299 bool hasMicrosoftFastStdCallMangling() const {
300 return ManglingMode == MM_WinCOFFX86;
301 }
302
303 /// Returns true if symbols with leading question marks should not receive IR
304 /// mangling. True for Windows mangling modes.
305 bool doNotMangleLeadingQuestionMark() const {
306 return ManglingMode == MM_WinCOFF || ManglingMode == MM_WinCOFFX86;
307 }
308
309 bool hasLinkerPrivateGlobalPrefix() const { return ManglingMode == MM_MachO; }
310
311 StringRef getLinkerPrivateGlobalPrefix() const {
312 if (ManglingMode == MM_MachO)
313 return "l";
314 return "";
315 }
316
317 char getGlobalPrefix() const {
318 switch (ManglingMode) {
319 case MM_None:
320 case MM_ELF:
321 case MM_Mips:
322 case MM_WinCOFF:
323 case MM_XCOFF:
324 return '\0';
325 case MM_MachO:
326 case MM_WinCOFFX86:
327 return '_';
328 }
329 llvm_unreachable("invalid mangling mode")::llvm::llvm_unreachable_internal("invalid mangling mode", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h"
, 329)
;
330 }
331
332 StringRef getPrivateGlobalPrefix() const {
333 switch (ManglingMode) {
334 case MM_None:
335 return "";
336 case MM_ELF:
337 case MM_WinCOFF:
338 return ".L";
339 case MM_Mips:
340 return "$";
341 case MM_MachO:
342 case MM_WinCOFFX86:
343 return "L";
344 case MM_XCOFF:
345 return "L..";
346 }
347 llvm_unreachable("invalid mangling mode")::llvm::llvm_unreachable_internal("invalid mangling mode", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h"
, 347)
;
348 }
349
350 static const char *getManglingComponent(const Triple &T);
351
352 /// Returns true if the specified type fits in a native integer type
353 /// supported by the CPU.
354 ///
355 /// For example, if the CPU only supports i32 as a native integer type, then
356 /// i27 fits in a legal integer type but i45 does not.
357 bool fitsInLegalInteger(unsigned Width) const {
358 for (unsigned LegalIntWidth : LegalIntWidths)
359 if (Width <= LegalIntWidth)
360 return true;
361 return false;
362 }
363
364 /// Layout pointer alignment
365 Align getPointerABIAlignment(unsigned AS) const;
366
367 /// Return target's alignment for stack-based pointers
368 /// FIXME: The defaults need to be removed once all of
369 /// the backends/clients are updated.
370 Align getPointerPrefAlignment(unsigned AS = 0) const;
371
372 /// Layout pointer size
373 /// FIXME: The defaults need to be removed once all of
374 /// the backends/clients are updated.
375 unsigned getPointerSize(unsigned AS = 0) const;
376
377 /// Returns the maximum pointer size over all address spaces.
378 unsigned getMaxPointerSize() const;
379
380 // Index size used for address calculation.
381 unsigned getIndexSize(unsigned AS) const;
382
383 /// Return the address spaces containing non-integral pointers. Pointers in
384 /// this address space don't have a well-defined bitwise representation.
385 ArrayRef<unsigned> getNonIntegralAddressSpaces() const {
386 return NonIntegralAddressSpaces;
387 }
388
389 bool isNonIntegralAddressSpace(unsigned AddrSpace) const {
390 ArrayRef<unsigned> NonIntegralSpaces = getNonIntegralAddressSpaces();
391 return find(NonIntegralSpaces, AddrSpace) != NonIntegralSpaces.end();
392 }
393
394 bool isNonIntegralPointerType(PointerType *PT) const {
395 return isNonIntegralAddressSpace(PT->getAddressSpace());
22
Called C++ object pointer is null
396 }
397
398 bool isNonIntegralPointerType(Type *Ty) const {
399 auto *PTy = dyn_cast<PointerType>(Ty);
400 return PTy && isNonIntegralPointerType(PTy);
401 }
402
403 /// Layout pointer size, in bits
404 /// FIXME: The defaults need to be removed once all of
405 /// the backends/clients are updated.
406 unsigned getPointerSizeInBits(unsigned AS = 0) const {
407 return getPointerSize(AS) * 8;
408 }
409
410 /// Returns the maximum pointer size over all address spaces.
411 unsigned getMaxPointerSizeInBits() const {
412 return getMaxPointerSize() * 8;
413 }
414
415 /// Size in bits of index used for address calculation in getelementptr.
416 unsigned getIndexSizeInBits(unsigned AS) const {
417 return getIndexSize(AS) * 8;
418 }
419
420 /// Layout pointer size, in bits, based on the type. If this function is
421 /// called with a pointer type, then the type size of the pointer is returned.
422 /// If this function is called with a vector of pointers, then the type size
423 /// of the pointer is returned. This should only be called with a pointer or
424 /// vector of pointers.
425 unsigned getPointerTypeSizeInBits(Type *) const;
426
427 /// Layout size of the index used in GEP calculation.
428 /// The function should be called with pointer or vector of pointers type.
429 unsigned getIndexTypeSizeInBits(Type *Ty) const;
430
431 unsigned getPointerTypeSize(Type *Ty) const {
432 return getPointerTypeSizeInBits(Ty) / 8;
433 }
434
435 /// Size examples:
436 ///
437 /// Type SizeInBits StoreSizeInBits AllocSizeInBits[*]
438 /// ---- ---------- --------------- ---------------
439 /// i1 1 8 8
440 /// i8 8 8 8
441 /// i19 19 24 32
442 /// i32 32 32 32
443 /// i100 100 104 128
444 /// i128 128 128 128
445 /// Float 32 32 32
446 /// Double 64 64 64
447 /// X86_FP80 80 80 96
448 ///
449 /// [*] The alloc size depends on the alignment, and thus on the target.
450 /// These values are for x86-32 linux.
451
452 /// Returns the number of bits necessary to hold the specified type.
453 ///
454 /// If Ty is a scalable vector type, the scalable property will be set and
455 /// the runtime size will be a positive integer multiple of the base size.
456 ///
457 /// For example, returns 36 for i36 and 80 for x86_fp80. The type passed must
458 /// have a size (Type::isSized() must return true).
459 TypeSize getTypeSizeInBits(Type *Ty) const;
460
461 /// Returns the maximum number of bytes that may be overwritten by
462 /// storing the specified type.
463 ///
464 /// If Ty is a scalable vector type, the scalable property will be set and
465 /// the runtime size will be a positive integer multiple of the base size.
466 ///
467 /// For example, returns 5 for i36 and 10 for x86_fp80.
468 TypeSize getTypeStoreSize(Type *Ty) const {
469 TypeSize BaseSize = getTypeSizeInBits(Ty);
470 return { (BaseSize.getKnownMinSize() + 7) / 8, BaseSize.isScalable() };
471 }
472
473 /// Returns the maximum number of bits that may be overwritten by
474 /// storing the specified type; always a multiple of 8.
475 ///
476 /// If Ty is a scalable vector type, the scalable property will be set and
477 /// the runtime size will be a positive integer multiple of the base size.
478 ///
479 /// For example, returns 40 for i36 and 80 for x86_fp80.
480 TypeSize getTypeStoreSizeInBits(Type *Ty) const {
481 return 8 * getTypeStoreSize(Ty);
482 }
483
484 /// Returns true if no extra padding bits are needed when storing the
485 /// specified type.
486 ///
487 /// For example, returns false for i19 that has a 24-bit store size.
488 bool typeSizeEqualsStoreSize(Type *Ty) const {
489 return getTypeSizeInBits(Ty) == getTypeStoreSizeInBits(Ty);
490 }
491
492 /// Returns the offset in bytes between successive objects of the
493 /// specified type, including alignment padding.
494 ///
495 /// If Ty is a scalable vector type, the scalable property will be set and
496 /// the runtime size will be a positive integer multiple of the base size.
497 ///
498 /// This is the amount that alloca reserves for this type. For example,
499 /// returns 12 or 16 for x86_fp80, depending on alignment.
500 TypeSize getTypeAllocSize(Type *Ty) const {
501 // Round up to the next alignment boundary.
502 return alignTo(getTypeStoreSize(Ty), getABITypeAlignment(Ty));
503 }
504
505 /// Returns the offset in bits between successive objects of the
506 /// specified type, including alignment padding; always a multiple of 8.
507 ///
508 /// If Ty is a scalable vector type, the scalable property will be set and
509 /// the runtime size will be a positive integer multiple of the base size.
510 ///
511 /// This is the amount that alloca reserves for this type. For example,
512 /// returns 96 or 128 for x86_fp80, depending on alignment.
513 TypeSize getTypeAllocSizeInBits(Type *Ty) const {
514 return 8 * getTypeAllocSize(Ty);
515 }
516
517 /// Returns the minimum ABI-required alignment for the specified type.
518 /// FIXME: Deprecate this function once migration to Align is over.
519 unsigned getABITypeAlignment(Type *Ty) const;
520
521 /// Returns the minimum ABI-required alignment for the specified type.
522 Align getABITypeAlign(Type *Ty) const;
523
524 /// Helper function to return `Alignment` if it's set or the result of
525 /// `getABITypeAlignment(Ty)`, in any case the result is a valid alignment.
526 inline Align getValueOrABITypeAlignment(MaybeAlign Alignment,
527 Type *Ty) const {
528 return Alignment ? *Alignment : getABITypeAlign(Ty);
529 }
530
531 /// Returns the minimum ABI-required alignment for an integer type of
532 /// the specified bitwidth.
533 Align getABIIntegerTypeAlignment(unsigned BitWidth) const;
534
535 /// Returns the preferred stack/global alignment for the specified
536 /// type.
537 ///
538 /// This is always at least as good as the ABI alignment.
539 /// FIXME: Deprecate this function once migration to Align is over.
540 unsigned getPrefTypeAlignment(Type *Ty) const;
541
542 /// Returns the preferred stack/global alignment for the specified
543 /// type.
544 ///
545 /// This is always at least as good as the ABI alignment.
546 Align getPrefTypeAlign(Type *Ty) const;
547
548 /// Returns an integer type with size at least as big as that of a
549 /// pointer in the given address space.
550 IntegerType *getIntPtrType(LLVMContext &C, unsigned AddressSpace = 0) const;
551
552 /// Returns an integer (vector of integer) type with size at least as
553 /// big as that of a pointer of the given pointer (vector of pointer) type.
554 Type *getIntPtrType(Type *) const;
555
556 /// Returns the smallest integer type with size at least as big as
557 /// Width bits.
558 Type *getSmallestLegalIntType(LLVMContext &C, unsigned Width = 0) const;
559
560 /// Returns the largest legal integer type, or null if none are set.
561 Type *getLargestLegalIntType(LLVMContext &C) const {
562 unsigned LargestSize = getLargestLegalIntTypeSizeInBits();
563 return (LargestSize == 0) ? nullptr : Type::getIntNTy(C, LargestSize);
564 }
565
566 /// Returns the size of largest legal integer type size, or 0 if none
567 /// are set.
568 unsigned getLargestLegalIntTypeSizeInBits() const;
569
570 /// Returns the type of a GEP index.
571 /// If it was not specified explicitly, it will be the integer type of the
572 /// pointer width - IntPtrType.
573 Type *getIndexType(Type *PtrTy) const;
574
575 /// Returns the offset from the beginning of the type for the specified
576 /// indices.
577 ///
578 /// Note that this takes the element type, not the pointer type.
579 /// This is used to implement getelementptr.
580 int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef<Value *> Indices) const;
581
582 /// Returns a StructLayout object, indicating the alignment of the
583 /// struct, its size, and the offsets of its fields.
584 ///
585 /// Note that this information is lazily cached.
586 const StructLayout *getStructLayout(StructType *Ty) const;
587
588 /// Returns the preferred alignment of the specified global.
589 ///
590 /// This includes an explicitly requested alignment (if the global has one).
591 Align getPreferredAlign(const GlobalVariable *GV) const;
592
593 /// Returns the preferred alignment of the specified global.
594 ///
595 /// This includes an explicitly requested alignment (if the global has one).
596 LLVM_ATTRIBUTE_DEPRECATED(inline unsigned getPreferredAlignment(const GlobalVariable *GV
) const __attribute__((deprecated("Use getPreferredAlign instead"
)))
597 inline unsigned getPreferredAlignment(const GlobalVariable *GV) const,inline unsigned getPreferredAlignment(const GlobalVariable *GV
) const __attribute__((deprecated("Use getPreferredAlign instead"
)))
598 "Use getPreferredAlign instead")inline unsigned getPreferredAlignment(const GlobalVariable *GV
) const __attribute__((deprecated("Use getPreferredAlign instead"
)))
{
599 return getPreferredAlign(GV).value();
600 }
601
602 /// Returns the preferred alignment of the specified global, returned
603 /// in log form.
604 ///
605 /// This includes an explicitly requested alignment (if the global has one).
606 LLVM_ATTRIBUTE_DEPRECATED(inline unsigned getPreferredAlignmentLog(const GlobalVariable
*GV) const __attribute__((deprecated("Inline where needed"))
)
607 inline unsigned getPreferredAlignmentLog(const GlobalVariable *GV) const,inline unsigned getPreferredAlignmentLog(const GlobalVariable
*GV) const __attribute__((deprecated("Inline where needed"))
)
608 "Inline where needed")inline unsigned getPreferredAlignmentLog(const GlobalVariable
*GV) const __attribute__((deprecated("Inline where needed"))
)
{
609 return Log2(getPreferredAlign(GV));
610 }
611};
612
613inline DataLayout *unwrap(LLVMTargetDataRef P) {
614 return reinterpret_cast<DataLayout *>(P);
615}
616
617inline LLVMTargetDataRef wrap(const DataLayout *P) {
618 return reinterpret_cast<LLVMTargetDataRef>(const_cast<DataLayout *>(P));
619}
620
621/// Used to lazily calculate structure layout information for a target machine,
622/// based on the DataLayout structure.
623class StructLayout {
624 uint64_t StructSize;
625 Align StructAlignment;
626 unsigned IsPadded : 1;
627 unsigned NumElements : 31;
628 uint64_t MemberOffsets[1]; // variable sized array!
629
630public:
631 uint64_t getSizeInBytes() const { return StructSize; }
632
633 uint64_t getSizeInBits() const { return 8 * StructSize; }
634
635 Align getAlignment() const { return StructAlignment; }
636
637 /// Returns whether the struct has padding or not between its fields.
638 /// NB: Padding in nested element is not taken into account.
639 bool hasPadding() const { return IsPadded; }
640
641 /// Given a valid byte offset into the structure, returns the structure
642 /// index that contains it.
643 unsigned getElementContainingOffset(uint64_t Offset) const;
644
645 uint64_t getElementOffset(unsigned Idx) const {
646 assert(Idx < NumElements && "Invalid element idx!")((Idx < NumElements && "Invalid element idx!") ? static_cast
<void> (0) : __assert_fail ("Idx < NumElements && \"Invalid element idx!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h"
, 646, __PRETTY_FUNCTION__))
;
647 return MemberOffsets[Idx];
648 }
649
650 uint64_t getElementOffsetInBits(unsigned Idx) const {
651 return getElementOffset(Idx) * 8;
652 }
653
654private:
655 friend class DataLayout; // Only DataLayout can create this class
656
657 StructLayout(StructType *ST, const DataLayout &DL);
658};
659
660// The implementation of this method is provided inline as it is particularly
661// well suited to constant folding when called on a specific Type subclass.
662inline TypeSize DataLayout::getTypeSizeInBits(Type *Ty) const {
663 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!")((Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!"
) ? static_cast<void> (0) : __assert_fail ("Ty->isSized() && \"Cannot getTypeInfo() on a type that is unsized!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h"
, 663, __PRETTY_FUNCTION__))
;
664 switch (Ty->getTypeID()) {
665 case Type::LabelTyID:
666 return TypeSize::Fixed(getPointerSizeInBits(0));
667 case Type::PointerTyID:
668 return TypeSize::Fixed(getPointerSizeInBits(Ty->getPointerAddressSpace()));
669 case Type::ArrayTyID: {
670 ArrayType *ATy = cast<ArrayType>(Ty);
671 return ATy->getNumElements() *
672 getTypeAllocSizeInBits(ATy->getElementType());
673 }
674 case Type::StructTyID:
675 // Get the layout annotation... which is lazily created on demand.
676 return TypeSize::Fixed(
677 getStructLayout(cast<StructType>(Ty))->getSizeInBits());
678 case Type::IntegerTyID:
679 return TypeSize::Fixed(Ty->getIntegerBitWidth());
680 case Type::HalfTyID:
681 case Type::BFloatTyID:
682 return TypeSize::Fixed(16);
683 case Type::FloatTyID:
684 return TypeSize::Fixed(32);
685 case Type::DoubleTyID:
686 case Type::X86_MMXTyID:
687 return TypeSize::Fixed(64);
688 case Type::PPC_FP128TyID:
689 case Type::FP128TyID:
690 return TypeSize::Fixed(128);
691 // In memory objects this is always aligned to a higher boundary, but
692 // only 80 bits contain information.
693 case Type::X86_FP80TyID:
694 return TypeSize::Fixed(80);
695 case Type::FixedVectorTyID:
696 case Type::ScalableVectorTyID: {
697 VectorType *VTy = cast<VectorType>(Ty);
698 auto EltCnt = VTy->getElementCount();
699 uint64_t MinBits = EltCnt.getKnownMinValue() *
700 getTypeSizeInBits(VTy->getElementType()).getFixedSize();
701 return TypeSize(MinBits, EltCnt.isScalable());
702 }
703 default:
704 llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type")::llvm::llvm_unreachable_internal("DataLayout::getTypeSizeInBits(): Unsupported type"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/DataLayout.h"
, 704)
;
705 }
706}
707
708} // end namespace llvm
709
710#endif // LLVM_IR_DATALAYOUT_H