1//===- SeparateConstOffsetFromGEP.cpp -------------------------------------===//
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// Loop unrolling may create many similar GEPs for array accesses.
10// e.g., a 2-level loop
11//
12// float a[32][32]; // global variable
13//
14// for (int i = 0; i < 2; ++i) {
15// for (int j = 0; j < 2; ++j) {
16// ...
17// ... = a[x + i][y + j];
18// ...
19// }
20// }
21//
22// will probably be unrolled to:
23//
24// gep %a, 0, %x, %y; load
25// gep %a, 0, %x, %y + 1; load
26// gep %a, 0, %x + 1, %y; load
27// gep %a, 0, %x + 1, %y + 1; load
28//
29// LLVM's GVN does not use partial redundancy elimination yet, and is thus
30// unable to reuse (gep %a, 0, %x, %y). As a result, this misoptimization incurs
31// significant slowdown in targets with limited addressing modes. For instance,
32// because the PTX target does not support the reg+reg addressing mode, the
33// NVPTX backend emits PTX code that literally computes the pointer address of
34// each GEP, wasting tons of registers. It emits the following PTX for the
35// first load and similar PTX for other loads.
36//
37// mov.u32 %r1, %x;
38// mov.u32 %r2, %y;
39// mul.wide.u32 %rl2, %r1, 128;
40// mov.u64 %rl3, a;
41// add.s64 %rl4, %rl3, %rl2;
42// mul.wide.u32 %rl5, %r2, 4;
43// add.s64 %rl6, %rl4, %rl5;
44// ld.global.f32 %f1, [%rl6];
45//
46// To reduce the register pressure, the optimization implemented in this file
47// merges the common part of a group of GEPs, so we can compute each pointer
48// address by adding a simple offset to the common part, saving many registers.
49//
50// It works by splitting each GEP into a variadic base and a constant offset.
51// The variadic base can be computed once and reused by multiple GEPs, and the
52// constant offsets can be nicely folded into the reg+immediate addressing mode
53// (supported by most targets) without using any extra register.
54//
55// For instance, we transform the four GEPs and four loads in the above example
56// into:
57//
58// base = gep a, 0, x, y
59// load base
60// load base + 1 * sizeof(float)
61// load base + 32 * sizeof(float)
62// load base + 33 * sizeof(float)
63//
64// Given the transformed IR, a backend that supports the reg+immediate
65// addressing mode can easily fold the pointer arithmetics into the loads. For
66// example, the NVPTX backend can easily fold the pointer arithmetics into the
67// ld.global.f32 instructions, and the resultant PTX uses much fewer registers.
68//
69// mov.u32 %r1, %tid.x;
70// mov.u32 %r2, %tid.y;
71// mul.wide.u32 %rl2, %r1, 128;
72// mov.u64 %rl3, a;
73// add.s64 %rl4, %rl3, %rl2;
74// mul.wide.u32 %rl5, %r2, 4;
75// add.s64 %rl6, %rl4, %rl5;
76// ld.global.f32 %f1, [%rl6]; // so far the same as unoptimized PTX
77// ld.global.f32 %f2, [%rl6+4]; // much better
78// ld.global.f32 %f3, [%rl6+128]; // much better
79// ld.global.f32 %f4, [%rl6+132]; // much better
80//
81// Another improvement enabled by the LowerGEP flag is to lower a GEP with
82// multiple indices to multiple GEPs with a single index.
83// Such transformation can have following benefits:
84// (1) It can always extract constants in the indices of structure type.
85// (2) After such Lowering, there are more optimization opportunities such as
86// CSE, LICM and CGP.
87//
88// E.g. The following GEPs have multiple indices:
89// BB1:
90// %p = getelementptr [10 x %struct], ptr %ptr, i64 %i, i64 %j1, i32 3
91// load %p
92// ...
93// BB2:
94// %p2 = getelementptr [10 x %struct], ptr %ptr, i64 %i, i64 %j1, i32 2
95// load %p2
96// ...
97//
98// We can not do CSE to the common part related to index "i64 %i". Lowering
99// GEPs can achieve such goals.
100//
101// This pass will lower a GEP with multiple indices into multiple GEPs with a
102// single index:
103// BB1:
104// %2 = mul i64 %i, length_of_10xstruct ; CSE opportunity
105// %3 = getelementptr i8, ptr %ptr, i64 %2 ; CSE opportunity
106// %4 = mul i64 %j1, length_of_struct
107// %5 = getelementptr i8, ptr %3, i64 %4
108// %p = getelementptr i8, ptr %5, struct_field_3 ; Constant offset
109// load %p
110// ...
111// BB2:
112// %8 = mul i64 %i, length_of_10xstruct ; CSE opportunity
113// %9 = getelementptr i8, ptr %ptr, i64 %8 ; CSE opportunity
114// %10 = mul i64 %j2, length_of_struct
115// %11 = getelementptr i8, ptr %9, i64 %10
116// %p2 = getelementptr i8, ptr %11, struct_field_2 ; Constant offset
117// load %p2
118// ...
119//
120// Lowering GEPs can also benefit other passes such as LICM and CGP.
121// LICM (Loop Invariant Code Motion) can not hoist/sink a GEP of multiple
122// indices if one of the index is variant. If we lower such GEP into invariant
123// parts and variant parts, LICM can hoist/sink those invariant parts.
124// CGP (CodeGen Prepare) tries to sink address calculations that match the
125// target's addressing modes. A GEP with multiple indices may not match and will
126// not be sunk. If we lower such GEP into smaller parts, CGP may sink some of
127// them. So we end up with a better addressing mode.
128//
129//===----------------------------------------------------------------------===//
130
131#include "llvm/Transforms/Scalar/SeparateConstOffsetFromGEP.h"
132#include "ScalarOptions.h"
133#include "llvm/ADT/APInt.h"
134#include "llvm/ADT/DenseMap.h"
135#include "llvm/ADT/DepthFirstIterator.h"
136#include "llvm/ADT/SmallVector.h"
137#include "llvm/Analysis/LoopInfo.h"
138#include "llvm/Analysis/MemoryBuiltins.h"
139#include "llvm/Analysis/TargetLibraryInfo.h"
140#include "llvm/Analysis/TargetTransformInfo.h"
141#include "llvm/Analysis/ValueTracking.h"
142#include "llvm/IR/BasicBlock.h"
143#include "llvm/IR/Constant.h"
144#include "llvm/IR/Constants.h"
145#include "llvm/IR/DataLayout.h"
146#include "llvm/IR/DerivedTypes.h"
147#include "llvm/IR/Dominators.h"
148#include "llvm/IR/Function.h"
149#include "llvm/IR/GetElementPtrTypeIterator.h"
150#include "llvm/IR/IRBuilder.h"
151#include "llvm/IR/InstrTypes.h"
152#include "llvm/IR/Instruction.h"
153#include "llvm/IR/Instructions.h"
154#include "llvm/IR/Module.h"
155#include "llvm/IR/PassManager.h"
156#include "llvm/IR/PatternMatch.h"
157#include "llvm/IR/Type.h"
158#include "llvm/IR/User.h"
159#include "llvm/IR/Value.h"
160#include "llvm/InitializePasses.h"
161#include "llvm/Pass.h"
162#include "llvm/Support/Casting.h"
163#include "llvm/Support/ErrorHandling.h"
164#include "llvm/Support/KnownBits.h"
165#include "llvm/Support/raw_ostream.h"
166#include "llvm/Transforms/Scalar.h"
167#include "llvm/Transforms/Utils/Local.h"
168#include <cassert>
169#include <cstdint>
170#include <iterator>
171#include <optional>
172#include <string>
173
174using namespace llvm;
175using namespace llvm::PatternMatch;
176
177namespace {
178
179/// A helper class for separating a constant offset from a GEP index.
180///
181/// In real programs, a GEP index may be more complicated than a simple addition
182/// of something and a constant integer which can be trivially splitted. For
183/// example, to split ((a << 3) | 5) + b, we need to search deeper for the
184/// constant offset, so that we can separate the index to (a << 3) + b and 5.
185///
186/// Therefore, this class looks into the expression that computes a given GEP
187/// index, and tries to find a constant integer that can be hoisted to the
188/// outermost level of the expression as an addition. Not every constant in an
189/// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a +
190/// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case,
191/// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15).
192class ConstantOffsetExtractor {
193public:
194 /// Extracts a constant offset from the given GEP index. It returns the
195 /// new index representing the remainder (equal to the original index minus
196 /// the constant offset), or nullptr if we cannot extract a constant offset.
197 /// \p Idx The given GEP index use
198 /// \p UserChainTail Outputs the tail of UserChain so that we can
199 /// garbage-collect unused instructions in UserChain.
200 /// \p PreservesNUW Outputs whether the extraction allows preserving the
201 /// GEP's nuw flag, if it has one.
202 static Value *Extract(const Use &Idx, User *&UserChainTail,
203 bool &PreservesNUW);
204
205 /// Looks for a constant offset from the given GEP index without extracting
206 /// it. It returns the numeric value of the extracted constant offset, or
207 /// std::nullopt on failure. The arguments have the same meaning as Extract.
208 static std::optional<APInt> Find(const Use &Idx);
209
210private:
211 struct CastState {
212 SmallVector<CastInst *, 4> Casts;
213
214 void pushCast(CastInst *Cast) {
215 assert((isa<SExtInst, ZExtInst, TruncInst>(Cast)) && "Unexpected cast");
216 Casts.push_back(Elt: Cast);
217 }
218
219 void popCast() { Casts.pop_back(); }
220
221 bool hasSignExtension() const {
222 // The innermost extension determines whether signed overflow matters:
223 // sext(zext(a)) = zext(a).
224 for (CastInst *C : reverse(C: Casts))
225 if (isa<SExtInst, ZExtInst>(Val: C))
226 return isa<SExtInst>(Val: C);
227 return false;
228 }
229
230 bool hasZeroExtension() const { return any_of(Range: Casts, P: IsaPred<ZExtInst>); }
231
232 bool hasExtensions() const {
233 return any_of(Range: Casts, P: IsaPred<SExtInst, ZExtInst>);
234 }
235
236 APInt apply(APInt Offset) const {
237 for (CastInst *Cast : llvm::reverse(C: Casts)) {
238 unsigned BitWidth = cast<IntegerType>(Val: Cast->getType())->getBitWidth();
239 if (isa<SExtInst>(Val: Cast))
240 Offset = Offset.sext(width: BitWidth);
241 else if (isa<ZExtInst>(Val: Cast))
242 Offset = Offset.zext(width: BitWidth);
243 else {
244 assert(isa<TruncInst>(Cast) && "Unexpected cast");
245 Offset = Offset.trunc(width: BitWidth);
246 }
247 }
248 return Offset;
249 }
250 };
251
252 ConstantOffsetExtractor(BasicBlock::iterator InsertionPt)
253 : IP(InsertionPt), DL(InsertionPt->getDataLayout()), SQ(DL) {}
254
255 /// Searches the expression that computes V for a constant offset C s.t.
256 /// V can be reassociated into the form V' + C. If the searching is
257 /// successful, returns C and update UserChain as a def-use chain from C to V;
258 /// otherwise, returns std::nullopt and UserChain is empty.
259 /// \p V The given expression
260 /// \p Idx The original index use of the GEP, or nullptr if its
261 /// sign and bounds information no longer applies
262 /// \p Casts The casts surrounding V in the original expression.
263 std::optional<APInt> find(Value *V, const Use *Idx, CastState &Casts);
264
265 /// A helper function to look into both operands of a binary operator.
266 std::optional<APInt> findInEitherOperand(BinaryOperator *BO,
267 CastState &Casts);
268
269 /// After finding the constant offset C from the GEP index I, we build a new
270 /// index I' s.t. I' + C = I. This function builds and returns the new
271 /// index I' according to UserChain produced by function "find".
272 ///
273 /// While rebuilding, distribute the casts recorded in \p Casts to each
274 /// operand that remains in the expression, then reassociate the expression to
275 /// the form I' + C and return I'.
276 Value *rebuildWithoutConstOffset(unsigned ChainIndex, CastState &Casts);
277
278 Value *rebuildWithoutConstOffset() {
279 CastState Casts;
280 return rebuildWithoutConstOffset(ChainIndex: UserChain.size() - 1, Casts);
281 }
282
283 /// A helper function to apply a list of sext/zext/trunc casts to value
284 /// V. e.g., if Casts = [sext i32 to i64, zext i16 to i32], this function
285 /// returns "sext i32 (zext i16 V to i32) to i64".
286 Value *applyCasts(Value *V, const CastState &Casts);
287
288 /// A helper function that returns whether we can trace into the operands
289 /// of binary operator BO for a constant offset.
290 ///
291 /// \p Casts The casts surrounding BO.
292 /// \p Idx The original index use of the GEP, or nullptr if its
293 /// sign and bounds information no longer applies
294 bool canTraceInto(const CastState &Casts, BinaryOperator *BO, const Use *Idx);
295
296 /// Analyze a xor expression, and identify the bits in the constant operand
297 /// that are disjoint from the base operand's known set bits. For these
298 /// disjoint bits, a xor is equivalent to an addition, which allows us to
299 /// extract them as constant offsets that can be folded into the immediate
300 /// field of addressing operations. The transformation is the following one:
301 ///
302 /// Base ^ Const becomes (Base ^ NonDisjointBits) + DisjointBits
303 ///
304 /// where DisjointBits = Const & KnownZeros(Base) and
305 /// NonDisjointBits = Const & ~DisjointBits.
306 ///
307 /// Example with ptr having known-zero low bit:
308 /// Original: `xor %ptr, 3` ; 3 = 0b11
309 /// Analysis: DisjointBits = 3 & KnownZeros(%ptr) = 0b11 & 0b01 = 0b01
310 /// Result: `(xor %ptr, 2) + 1` where 1 can be folded into address mode
311 ///
312 /// \param XorInst The XOR binary operator to analyze
313 /// \return Returns the disjoint bits (the extractable offset), or
314 /// std::nullopt if none exist. On success, stores NonDisjointBits in
315 /// NonDisjointXorConstantBits.
316 std::optional<APInt> extractDisjointBitsFromXor(BinaryOperator *XorInst);
317
318 /// The non-disjoint bits remaining after xor decomposition in
319 /// `extractDisjointBitsFromXor`, which are later used while replacing the
320 /// original xor constant operand.
321 ConstantInt *NonDisjointXorConstantBits = nullptr;
322
323 /// The path from the constant offset to the old GEP index. e.g., if the GEP
324 /// index is "a * b + (c + 5)". After running function find, UserChain[0] will
325 /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and
326 /// UserChain[2] will be the entire expression "a * b + (c + 5)".
327 ///
328 /// This path helps to rebuild the new GEP index.
329 SmallVector<User *, 8> UserChain;
330
331 /// Insertion position of cloned instructions.
332 BasicBlock::iterator IP;
333
334 const DataLayout &DL;
335 const SimplifyQuery SQ;
336};
337
338/// A pass that tries to split every GEP in the function into a variadic
339/// base and a constant offset. It is a FunctionPass because searching for the
340/// constant offset may inspect other basic blocks.
341class SeparateConstOffsetFromGEPLegacyPass : public FunctionPass {
342public:
343 static char ID;
344
345 SeparateConstOffsetFromGEPLegacyPass(bool LowerGEP = false)
346 : FunctionPass(ID), LowerGEP(LowerGEP) {
347 initializeSeparateConstOffsetFromGEPLegacyPassPass(
348 *PassRegistry::getPassRegistry());
349 }
350
351 void getAnalysisUsage(AnalysisUsage &AU) const override {
352 AU.addRequired<DominatorTreeWrapperPass>();
353 AU.addRequired<TargetTransformInfoWrapperPass>();
354 AU.addRequired<LoopInfoWrapperPass>();
355 AU.setPreservesCFG();
356 AU.addRequired<TargetLibraryInfoWrapperPass>();
357 }
358
359 bool runOnFunction(Function &F) override;
360
361private:
362 bool LowerGEP;
363};
364
365/// A pass that tries to split every GEP in the function into a variadic
366/// base and a constant offset. It is a FunctionPass because searching for the
367/// constant offset may inspect other basic blocks.
368class SeparateConstOffsetFromGEP {
369public:
370 SeparateConstOffsetFromGEP(
371 DominatorTree *DT, LoopInfo *LI, TargetLibraryInfo *TLI,
372 function_ref<TargetTransformInfo &(Function &)> GetTTI, bool LowerGEP)
373 : DT(DT), LI(LI), TLI(TLI), GetTTI(GetTTI), LowerGEP(LowerGEP) {}
374
375 bool run(Function &F);
376
377private:
378 /// Track the operands of an add or sub.
379 using ExprKey = std::pair<Value *, Value *>;
380
381 /// Create a pair for use as a map key for a commutable operation.
382 static ExprKey createNormalizedCommutablePair(Value *A, Value *B) {
383 if (A < B)
384 return {A, B};
385 return {B, A};
386 }
387
388 /// Tries to split the given GEP into a variadic base and a constant offset,
389 /// and returns true if the splitting succeeds.
390 bool splitGEP(GetElementPtrInst *GEP);
391
392 /// Tries to reorder the given GEP with the GEP that produces the base if
393 /// doing so results in producing a constant offset as the outermost
394 /// index.
395 bool reorderGEP(GetElementPtrInst *GEP, TargetTransformInfo &TTI);
396
397 /// Lower a GEP with multiple indices into multiple GEPs with a single index.
398 /// Function splitGEP already split the original GEP into a variadic part and
399 /// a constant offset (i.e., AccumulativeByteOffset). This function lowers the
400 /// variadic part into a set of GEPs with a single index and applies
401 /// AccumulativeByteOffset to it.
402 /// \p Variadic The variadic part of the original GEP.
403 /// \p AccumulativeByteOffset The constant offset.
404 void lowerToSingleIndexGEPs(GetElementPtrInst *Variadic,
405 const APInt &AccumulativeByteOffset);
406
407 /// Finds the constant offset within each index and accumulates them. If
408 /// LowerGEP is true, it finds in indices of both sequential and structure
409 /// types, otherwise it only finds in sequential indices. The output
410 /// NeedsExtraction indicates whether we successfully find a constant
411 /// offset, and SignedOverflow indicates if there was signed overflow in
412 /// offset calculation.
413 APInt accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction,
414 bool &SignedOverflow);
415
416 /// Canonicalize array indices to pointer-size integers. This helps to
417 /// simplify the logic of splitting a GEP. For example, if a + b is a
418 /// pointer-size integer, we have
419 /// gep base, a + b = gep (gep base, a), b
420 /// However, this equality may not hold if the size of a + b is smaller than
421 /// the pointer size, because LLVM conceptually sign-extends GEP indices to
422 /// pointer size before computing the address
423 /// (http://llvm.org/docs/LangRef.html#id181).
424 ///
425 /// This canonicalization is very likely already done in clang and
426 /// instcombine. Therefore, the program will probably remain the same.
427 ///
428 /// Returns true if the module changes.
429 ///
430 /// Verified in @i32_add in split-gep.ll
431 bool canonicalizeArrayIndicesToIndexSize(GetElementPtrInst *GEP);
432
433 /// Optimize sext(a)+sext(b) to sext(a+b) when a+b can't sign overflow.
434 /// SeparateConstOffsetFromGEP distributes a sext to leaves before extracting
435 /// the constant offset. After extraction, it becomes desirable to reunion the
436 /// distributed sexts. For example,
437 ///
438 /// &a[sext(i +nsw (j +nsw 5)]
439 /// => distribute &a[sext(i) +nsw (sext(j) +nsw 5)]
440 /// => constant extraction &a[sext(i) + sext(j)] + 5
441 /// => reunion &a[sext(i +nsw j)] + 5
442 bool reuniteExts(Function &F);
443
444 /// A helper that reunites sexts in an instruction.
445 bool reuniteExts(Instruction *I);
446
447 /// Find the closest dominator of <Dominatee> that is equivalent to <Key>.
448 Instruction *findClosestMatchingDominator(
449 ExprKey Key, Instruction *Dominatee,
450 DenseMap<ExprKey, SmallVector<Instruction *, 2>> &DominatingExprs);
451
452 /// Verify F is free of dead code.
453 void verifyNoDeadCode(Function &F);
454
455 bool hasMoreThanOneUseInLoop(Value *v, Loop *L);
456
457 // Swap the index operand of two GEP.
458 void swapGEPOperand(GetElementPtrInst *First, GetElementPtrInst *Second);
459
460 // Check if it is safe to swap operand of two GEP.
461 bool isLegalToSwapOperand(GetElementPtrInst *First, GetElementPtrInst *Second,
462 Loop *CurLoop);
463
464 const DataLayout *DL = nullptr;
465 DominatorTree *DT = nullptr;
466 LoopInfo *LI;
467 TargetLibraryInfo *TLI;
468 // Retrieved lazily since not always used.
469 function_ref<TargetTransformInfo &(Function &)> GetTTI;
470
471 /// Whether to lower a GEP with multiple indices into arithmetic operations or
472 /// multiple GEPs with a single index.
473 bool LowerGEP;
474
475 DenseMap<ExprKey, SmallVector<Instruction *, 2>> DominatingAdds;
476 DenseMap<ExprKey, SmallVector<Instruction *, 2>> DominatingSubs;
477};
478
479} // end anonymous namespace
480
481char SeparateConstOffsetFromGEPLegacyPass::ID = 0;
482
483INITIALIZE_PASS_BEGIN(
484 SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep",
485 "Split GEPs to a variadic base and a constant offset for better CSE", false,
486 false)
487INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
488INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
489INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
490INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
491INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
492INITIALIZE_PASS_END(
493 SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep",
494 "Split GEPs to a variadic base and a constant offset for better CSE", false,
495 false)
496
497FunctionPass *llvm::createSeparateConstOffsetFromGEPPass(bool LowerGEP) {
498 return new SeparateConstOffsetFromGEPLegacyPass(LowerGEP);
499}
500
501// Checks if it is safe to reorder an add/sext result used in a GEP.
502//
503// An inbounds GEP does not guarantee that the index is non-negative.
504// This helper first checks whether value tracking proves that the add cannot
505// have signed overflow. If so, the transform is safe.
506// Second, it checks whether the GEP is inbounds and directly based on a global
507// or an alloca, which are required to prove futher transform validity.
508// If the GEP:
509// - Has a zero offset from the base and Idx is its first index, the index is
510// non-negative (any negative value would produce poison/UB)
511// - Has ObjectSize < (2^(N-1) - C + 1) * stride, where C is a constant from the
512// add, stride is the element size of Idx, and N is bitwidth of the add.
513// This is because with this pattern:
514// %add = add iN %val, C
515// %sext = sext iN %add to i64
516// %gep = getelementptr inbounds TYPE, %sext
517// The worst-case is when %val sign-flips to produce the smallest magnitude
518// negative value, at 2^(N-1)-1. In this case, the add/sext is -(2^(N-1)-C+1),
519// and the sext/add is 2^(N-1)+C-1 (2^N difference). The original add/sext
520// only produces a defined GEP when -(2^(N-1)-C+1) is inbounds. So, if
521// ObjectSize < (2^(N-1) - C + 1) * stride, it is impossible for the
522// worst-case sign-flip to be defined.
523// Note that in this case the GEP is not neccesarily non-negative, but any
524// negative results will still produce the same behavior in the reordered
525// version with a defined GEP.
526// This can also work for negative C, but the threshold is instead
527// (2^(N-1)+C)*stride, since the sign-flip is done in reverse and is instead
528// producing a large positive value that still needs to be inbounds to the
529// object size. If C is negative, we cannot make any useful assumptions based
530// on the offset, since it would need to be extremely large.
531static bool canReorderAddSextToGEP(const Use *Idx, const BinaryOperator *Add,
532 const DataLayout &DL) {
533 if (computeOverflowForSignedAdd(Add: cast<AddOperator>(Val: Add), SQ: DL) ==
534 OverflowResult::NeverOverflows)
535 return true;
536
537 const auto *GEP = cast<GetElementPtrInst>(Val: Idx->getUser());
538 if (!GEP->isInBounds())
539 return false;
540
541 const Value *Ptr = GEP->getPointerOperand();
542 int64_t Offset = 0;
543 const Value *Base =
544 GetPointerBaseWithConstantOffset(Ptr: const_cast<Value *>(Ptr), Offset, DL);
545
546 // We need one of the operands to be a constant to be able to trace into the
547 // operator.
548 const ConstantInt *CI = dyn_cast<ConstantInt>(Val: Add->getOperand(i_nocapture: 0));
549 if (!CI)
550 CI = dyn_cast<ConstantInt>(Val: Add->getOperand(i_nocapture: 1));
551 if (!CI)
552 return false;
553 // Calculate the threshold
554 APInt Threshold;
555 unsigned N = Add->getType()->getIntegerBitWidth();
556 // Track the use: the same value may index different types in this GEP.
557 auto GTI = std::next(x: gep_type_begin(GEP), n: Idx->getOperandNo() - 1);
558 TypeSize ElemSize = GTI.getSequentialElementStride(DL);
559 if (ElemSize.isScalable())
560 return false;
561 uint64_t Stride = ElemSize.getFixedValue();
562 if (!CI->isNegative()) {
563 // (2^(N-1) - C + 1) * stride
564 Threshold = (APInt::getSignedMinValue(numBits: N).zext(width: 128) -
565 CI->getValue().zextOrTrunc(width: 128) + 1) *
566 APInt(128, Stride);
567 } else {
568 // (2^(N-1) + C) * stride
569 Threshold = (APInt::getSignedMinValue(numBits: N).zext(width: 128) +
570 CI->getValue().sextOrTrunc(width: 128)) *
571 APInt(128, Stride);
572 }
573
574 // Only the first index is relative to Ptr. Earlier indices may move the
575 // pointer within the object, so later indices must use the object-size proof.
576 if (Idx->getOperandNo() == 1 && Base &&
577 (isa<AllocaInst>(Val: Base) || isa<GlobalObject>(Val: Base)) && !CI->isNegative()) {
578 // If the offset is zero from an alloca or global, inbounds is sufficient to
579 // prove non-negativity if one add operand is non-negative
580 if (Offset == 0)
581 return true;
582
583 // Check if the Offset < Threshold (positive CI only) otherwise
584 if (Offset < 0)
585 return true;
586 if (APInt(128, (uint64_t)Offset).ult(RHS: Threshold))
587 return true;
588 } else {
589 // If we can't determine the offset from the base object, we can still use
590 // the underlying object and type size constraints
591 Base = getUnderlyingObject(V: Ptr);
592 // Can only prove non-negativity if the base object is known
593 if (!(isa<AllocaInst>(Val: Base) || isa<GlobalObject>(Val: Base)))
594 return false;
595 }
596
597 // Check if the ObjectSize < Threshold (for both positive or negative C)
598 uint64_t ObjSize = 0;
599 if (const auto *AI = dyn_cast<AllocaInst>(Val: Base)) {
600 if (auto AllocSize = AI->getAllocationSize(DL))
601 if (!AllocSize->isScalable())
602 ObjSize = AllocSize->getFixedValue();
603 } else if (const auto *GV = dyn_cast<GlobalVariable>(Val: Base)) {
604 TypeSize GVSize = DL.getTypeAllocSize(Ty: GV->getValueType());
605 if (!GVSize.isScalable())
606 ObjSize = GVSize.getFixedValue();
607 }
608 if (ObjSize > 0 && APInt(128, ObjSize).ult(RHS: Threshold))
609 return true;
610
611 return false;
612}
613
614bool ConstantOffsetExtractor::canTraceInto(const CastState &Casts,
615 BinaryOperator *BO, const Use *Idx) {
616 bool SignExtended = Casts.hasSignExtension();
617 bool ZeroExtended = Casts.hasZeroExtension();
618 // Do not trace into "or" unless it is equivalent to "add nuw nsw".
619 // This is the case if the or's disjoint flag is set.
620 if (BO->getOpcode() == Instruction::Or)
621 return cast<PossiblyDisjointInst>(Val: BO)->isDisjoint();
622
623 // We only consider ADD and SUB here, because a non-zero constant found in
624 // expressions composed of these operations can be easily hoisted as a
625 // constant offset by reassociation.
626 if (BO->getOpcode() != Instruction::Add &&
627 BO->getOpcode() != Instruction::Sub)
628 return false;
629
630 // In addition, tracing into BO requires that its surrounding sext/zext/trunc
631 // (if any) is distributable to both operands.
632 //
633 // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B)
634 // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B)
635 if ((!SignExtended || BO->hasNoSignedWrap()) &&
636 (!ZeroExtended || BO->hasNoUnsignedWrap()))
637 return true;
638
639 if (BO->getOpcode() == Instruction::Add && !ZeroExtended && Idx) {
640 const auto *GEP = cast<GetElementPtrInst>(Val: Idx->getUser());
641 // For a sext(add nuw), allow tracing through when the enclosing GEP is both
642 // inbounds and nuw.
643 if (SignExtended && BO->hasNoUnsignedWrap() && GEP->isInBounds() &&
644 GEP->hasNoUnsignedWrap())
645 return true;
646
647 // Trace through sext when value tracking or the GEP's bounds prove that
648 // the addition cannot have signed overflow.
649 //
650 // Verified in @sext_add in split-gep.ll.
651 if (canReorderAddSextToGEP(Idx, Add: BO, DL))
652 return true;
653 }
654
655 return false;
656}
657
658std::optional<APInt>
659ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,
660 CastState &Casts) {
661 // Save off the current height of the chain, in case we need to restore it.
662 size_t ChainLength = UserChain.size();
663
664 // An intervening binary operator invalidates the GEP's index sign and bounds
665 // information, so do not pass it to either operand.
666 std::optional<APInt> ConstantOffset = find(V: BO->getOperand(i_nocapture: 0), Idx: nullptr, Casts);
667 // If we found a constant offset in the left operand, stop and return that.
668 // This shortcut might cause us to miss opportunities of combining the
669 // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9.
670 // However, such cases are probably already handled by -instcombine,
671 // given this pass runs after the standard optimizations.
672 if (ConstantOffset)
673 return ConstantOffset;
674
675 // Reset the chain back to where it was when we started exploring this node,
676 // since visiting the LHS didn't pan out.
677 UserChain.resize(N: ChainLength);
678
679 ConstantOffset = find(V: BO->getOperand(i_nocapture: 1), Idx: nullptr, Casts);
680 // If U is a sub operator, negate the constant offset found in the right
681 // operand.
682 if (ConstantOffset && BO->getOpcode() == Instruction::Sub)
683 *ConstantOffset = -*ConstantOffset;
684
685 // If RHS wasn't a suitable candidate either, reset the chain again.
686 if (!ConstantOffset)
687 UserChain.resize(N: ChainLength);
688
689 return ConstantOffset;
690}
691
692std::optional<APInt> ConstantOffsetExtractor::find(Value *V, const Use *Idx,
693 CastState &Casts) {
694 // TODO(jingyue): We could trace into integer/pointer casts, such as
695 // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only
696 // integers because it gives good enough results for our benchmarks.
697
698 // We cannot do much with Values that are not a User, such as an Argument.
699 User *U = dyn_cast<User>(Val: V);
700 if (U == nullptr)
701 return std::nullopt;
702
703 std::optional<APInt> ConstantOffset;
704 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) {
705 // Leave literal zero offsets alone.
706 if (CI->isZero())
707 return std::nullopt;
708 // Hooray, we found it!
709 ConstantOffset = Casts.apply(Offset: CI->getValue());
710 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: V)) {
711 // Trace into subexpressions for more hoisting opportunities.
712 if (canTraceInto(Casts, BO, Idx))
713 ConstantOffset = findInEitherOperand(BO, Casts);
714 else if (BO->getOpcode() == Instruction::Xor) {
715 ConstantOffset = extractDisjointBitsFromXor(XorInst: BO);
716 if (ConstantOffset)
717 *ConstantOffset = Casts.apply(Offset: *ConstantOffset);
718 }
719 } else if (isa<SExtInst, ZExtInst>(Val: V) ||
720 (isa<TruncInst>(Val: V) && !Casts.hasExtensions())) {
721 Casts.pushCast(Cast: cast<CastInst>(Val: V));
722 ConstantOffset = find(V: U->getOperand(i: 0), Idx, Casts);
723 Casts.popCast();
724 }
725
726 // If we found a constant offset, add it to the path for
727 // rebuildWithoutConstOffset.
728 if (ConstantOffset)
729 UserChain.push_back(Elt: U);
730 return ConstantOffset;
731}
732
733Value *ConstantOffsetExtractor::applyCasts(Value *V, const CastState &Casts) {
734 Value *Current = V;
735 // Casts is built in the use-def order. Therefore, we apply them to V in the
736 // reversed order.
737 for (CastInst *I : llvm::reverse(C: Casts.Casts)) {
738 if (Constant *C = dyn_cast<Constant>(Val: Current)) {
739 // Try to constant fold the cast.
740 Current = ConstantFoldCastOperand(Opcode: I->getOpcode(), C, DestTy: I->getType(), DL);
741 if (Current)
742 continue;
743 }
744
745 Instruction *Cast = I->clone();
746 Cast->setOperand(i: 0, Val: Current);
747 // In ConstantOffsetExtractor::find we do not analyze nuw/nsw for trunc, so
748 // we assume that it is ok to redistribute trunc over add/sub/or. But for
749 // example (add (trunc nuw A), (trunc nuw B)) is more poisonous than (trunc
750 // nuw (add A, B))). To make such redistributions legal we drop all the
751 // poison generating flags from cloned trunc instructions here.
752 if (isa<TruncInst>(Val: Cast))
753 Cast->dropPoisonGeneratingFlags();
754 Cast->insertBefore(BB&: *IP->getParent(), InsertPos: IP);
755 Current = Cast;
756 }
757 return Current;
758}
759
760Value *ConstantOffsetExtractor::rebuildWithoutConstOffset(unsigned ChainIndex,
761 CastState &Casts) {
762 User *U = UserChain[ChainIndex];
763 if (ChainIndex == 0) {
764 assert(isa<ConstantInt>(U));
765 return applyCasts(V: ConstantInt::getNullValue(Ty: U->getType()), Casts);
766 }
767
768 if (CastInst *Cast = dyn_cast<CastInst>(Val: U)) {
769 assert(
770 (isa<SExtInst>(Cast) || isa<ZExtInst>(Cast) || isa<TruncInst>(Cast)) &&
771 "Only following instructions can be traced: sext, zext & trunc");
772 Casts.pushCast(Cast);
773 Value *Result = rebuildWithoutConstOffset(ChainIndex: ChainIndex - 1, Casts);
774 Casts.popCast();
775 return Result;
776 }
777
778 BinaryOperator *BO = cast<BinaryOperator>(Val: U);
779 unsigned OpNo = (BO->getOperand(i_nocapture: 0) == UserChain[ChainIndex - 1] ? 0 : 1);
780 assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]);
781 Value *TheOther = applyCasts(V: BO->getOperand(i_nocapture: 1 - OpNo), Casts);
782 Value *NextInChain;
783 if (BO->getOpcode() == Instruction::Xor) {
784 // When rewriting xor(TheOther, NextInChain) expressions, the original
785 // constant operand is replaced with the non-disjoint bits, which are the
786 // non-extractable bits, i.e., those that must remain in the xor (the other
787 // bits have already compounded the GEP offset).
788 assert(NonDisjointXorConstantBits &&
789 "XOR in UserChain without recorded non-disjoint bits");
790 NextInChain = applyCasts(V: NonDisjointXorConstantBits, Casts);
791 } else {
792 NextInChain = rebuildWithoutConstOffset(ChainIndex: ChainIndex - 1, Casts);
793 }
794
795 Value *LHS = OpNo == 0 ? NextInChain : TheOther;
796 Value *RHS = OpNo == 0 ? TheOther : NextInChain;
797
798 // Zero is a right identity for all supported operators, and a left identity
799 // for all except subtraction.
800 if (match(V: RHS, P: m_Zero()))
801 return LHS;
802 if (match(V: LHS, P: m_Zero()) && BO->getOpcode() != Instruction::Sub)
803 return RHS;
804
805 BinaryOperator::BinaryOps NewOp = BO->getOpcode();
806 if (BO->getOpcode() == Instruction::Or) {
807 // Rebuild "or" as "add", because "or" may be invalid for the new
808 // expression.
809 //
810 // For instance, given
811 // a | (b + 5) where a and b + 5 have no common bits,
812 // we can extract 5 as the constant offset.
813 //
814 // However, reusing the "or" in the new index would give us
815 // (a | b) + 5
816 // which does not equal a | (b + 5).
817 //
818 // Replacing the "or" with "add" is fine, because
819 // a | (b + 5) = a + (b + 5) = (a + b) + 5
820 NewOp = Instruction::Add;
821 }
822
823 BinaryOperator *NewBO = BinaryOperator::Create(Op: NewOp, S1: LHS, S2: RHS, Name: "", InsertBefore: IP);
824 NewBO->takeName(V: BO);
825 return NewBO;
826}
827
828std::optional<APInt>
829ConstantOffsetExtractor::extractDisjointBitsFromXor(BinaryOperator *XorInst) {
830 assert(XorInst && XorInst->getOpcode() == Instruction::Xor &&
831 "Expected XOR instruction");
832
833 Value *BaseOp;
834 ConstantInt *XorConstantOp;
835
836 if (!match(V: XorInst, P: m_Xor(L: m_Value(V&: BaseOp), R: m_ConstantInt(CI&: XorConstantOp))))
837 return std::nullopt;
838
839 const KnownBits BaseKnownBits = computeKnownBits(V: BaseOp, Q: SQ);
840 const APInt &ConstantValue = XorConstantOp->getValue();
841
842 // Compute the disjoint bits, i.e., those bits of the constant operand that
843 // are known-zero in the base. These disjoint bits will contribute to the
844 // final GEP offset. If there are no disjoint bits, there isn't any offset to
845 // extract from the xor.
846 const APInt DisjointBits = ConstantValue & BaseKnownBits.Zero;
847 if (DisjointBits.isZero())
848 return std::nullopt;
849
850 // Avoid a pessimizing rewrite if the disjoint bits include the sign bit.
851 if (DisjointBits.isSignBitSet())
852 return std::nullopt;
853
854 // Compute the remaining bits, i.e., the non-disjoint ones, which are those
855 // that must be preserved in the xor.
856 const APInt NonDisjointBits = ConstantValue & ~DisjointBits;
857 NonDisjointXorConstantBits =
858 ConstantInt::get(Context&: XorInst->getContext(), V: NonDisjointBits);
859
860 // UserChain maintains a path from the constant up to the GEP index. Push the
861 // xor constant operand, which is the constant leaf of the chain. Such a
862 // chained operand is the one to be replaced with the non-disjoint bits, while
863 // rebuilding the xor afterwards. The xor instruction itself is pushed upon
864 // returning.
865 UserChain.push_back(Elt: XorConstantOp);
866
867 return DisjointBits;
868}
869
870/// A helper function to check if reassociating through an entry in the user
871/// chain would invalidate the GEP's nuw flag.
872static bool allowsPreservingNUW(const User *U) {
873 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: U)) {
874 // Binary operations need to be effectively add nuw.
875 auto Opcode = BO->getOpcode();
876 if (Opcode == BinaryOperator::Or) {
877 // Ors are only considered here if they are disjoint. The addition that
878 // they represent in this case is NUW.
879 assert(cast<PossiblyDisjointInst>(BO)->isDisjoint());
880 return true;
881 }
882 return Opcode == BinaryOperator::Add && BO->hasNoUnsignedWrap();
883 }
884 // UserChain can only contain ConstantInt, CastInst, or BinaryOperator.
885 // Among the possible CastInsts, only trunc without nuw is a problem: If it
886 // is distributed through an add nuw, wrapping may occur:
887 // "add nuw trunc(a), trunc(b)" is more poisonous than "trunc(add nuw a, b)"
888 if (const TruncInst *TI = dyn_cast<TruncInst>(Val: U))
889 return TI->hasNoUnsignedWrap();
890 assert((isa<CastInst>(U) || isa<ConstantInt>(U)) && "Unexpected User.");
891 return true;
892}
893
894static BasicBlock::iterator getIndexInsertionPoint(const Use &Idx) {
895 if (auto *I = dyn_cast<Instruction>(Val: Idx.get()))
896 if (auto IP = I->getInsertionPointAfterDef())
897 return *IP;
898 return cast<GetElementPtrInst>(Val: Idx.getUser())->getIterator();
899}
900
901Value *ConstantOffsetExtractor::Extract(const Use &Idx, User *&UserChainTail,
902 bool &PreservesNUW) {
903 ConstantOffsetExtractor Extractor(getIndexInsertionPoint(Idx));
904 // Find a constant offset first.
905 CastState Casts;
906 if (!Extractor.find(V: Idx, Idx: &Idx, Casts)) {
907 UserChainTail = nullptr;
908 PreservesNUW = true;
909 return nullptr;
910 }
911
912 PreservesNUW = all_of(Range&: Extractor.UserChain, P: allowsPreservingNUW);
913
914 // Separates the constant offset from the GEP index.
915 Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset();
916 UserChainTail = dyn_cast<User>(Val: IdxWithoutConstOffset);
917 return IdxWithoutConstOffset;
918}
919
920std::optional<APInt> ConstantOffsetExtractor::Find(const Use &Idx) {
921 auto *GEP = cast<GetElementPtrInst>(Val: Idx.getUser());
922 CastState Casts;
923 return ConstantOffsetExtractor(GEP->getIterator()).find(V: Idx, Idx: &Idx, Casts);
924}
925
926bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToIndexSize(
927 GetElementPtrInst *GEP) {
928 bool Changed = false;
929 Type *PtrIdxTy = DL->getIndexType(PtrTy: GEP->getType());
930 gep_type_iterator GTI = gep_type_begin(GEP: *GEP);
931 for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end();
932 I != E; ++I, ++GTI) {
933 // Skip struct member indices which must be i32.
934 if (GTI.isSequential()) {
935 if ((*I)->getType() != PtrIdxTy) {
936 *I = CastInst::CreateIntegerCast(S: *I, Ty: PtrIdxTy, isSigned: true, Name: "idxprom",
937 InsertBefore: getIndexInsertionPoint(Idx: *I));
938 Changed = true;
939 }
940 }
941 }
942 return Changed;
943}
944
945APInt SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP,
946 bool &NeedsExtraction,
947 bool &SignedOverflow) {
948 NeedsExtraction = false;
949 SignedOverflow = false;
950 unsigned IdxWidth = DL->getIndexTypeSizeInBits(Ty: GEP->getType());
951 APInt AccumulativeByteOffset(IdxWidth, 0);
952 gep_type_iterator GTI = gep_type_begin(GEP: *GEP);
953 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
954 if (GTI.isSequential()) {
955 // Constant offsets of scalable types are not really constant.
956 if (GTI.getIndexedType()->isScalableTy())
957 continue;
958
959 // Tries to extract a constant offset from this GEP index.
960 if (std::optional<APInt> ConstantOffset =
961 ConstantOffsetExtractor::Find(Idx: GEP->getOperandUse(i: I))) {
962 NeedsExtraction = true;
963 // A GEP may have multiple indices. We accumulate the extracted
964 // constant offset to a byte offset, and later offset the remainder of
965 // the original GEP with this byte offset.
966 bool Overflow;
967 auto ByteOffset = ConstantOffset->sextOrTrunc(width: IdxWidth).smul_ov(
968 RHS: APInt(IdxWidth, GTI.getSequentialElementStride(DL: *DL),
969 /*IsSigned=*/true, /*ImplicitTrunc=*/true),
970 Overflow);
971 SignedOverflow |= Overflow;
972 AccumulativeByteOffset =
973 AccumulativeByteOffset.sadd_ov(RHS: ByteOffset, Overflow);
974 SignedOverflow |= Overflow;
975 }
976 } else if (LowerGEP) {
977 StructType *StTy = GTI.getStructType();
978 uint64_t Field = cast<ConstantInt>(Val: GEP->getOperand(i_nocapture: I))->getZExtValue();
979 // Skip field 0 as the offset is always 0.
980 if (Field != 0) {
981 NeedsExtraction = true;
982 AccumulativeByteOffset +=
983 APInt(IdxWidth, DL->getStructLayout(Ty: StTy)->getElementOffset(Idx: Field),
984 /*IsSigned=*/true, /*ImplicitTrunc=*/true);
985 }
986 }
987 }
988 return AccumulativeByteOffset;
989}
990
991void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs(
992 GetElementPtrInst *Variadic, const APInt &AccumulativeByteOffset) {
993 IRBuilder<> Builder(Variadic);
994 Type *PtrIndexTy = DL->getIndexType(PtrTy: Variadic->getType());
995
996 Value *ResultPtr = Variadic->getOperand(i_nocapture: 0);
997 Loop *L = LI->getLoopFor(BB: Variadic->getParent());
998 // Check if the base is not loop invariant or used more than once.
999 bool isSwapCandidate =
1000 L && L->isLoopInvariant(V: ResultPtr) &&
1001 !hasMoreThanOneUseInLoop(v: ResultPtr, L);
1002 Value *FirstResult = nullptr;
1003
1004 gep_type_iterator GTI = gep_type_begin(GEP: *Variadic);
1005 // Create an ugly GEP for each sequential index. We don't create GEPs for
1006 // structure indices, as they are accumulated in the constant offset index.
1007 for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) {
1008 if (GTI.isSequential()) {
1009 Value *Idx = Variadic->getOperand(i_nocapture: I);
1010 // Skip zero indices.
1011 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Idx))
1012 if (CI->isZero())
1013 continue;
1014
1015 APInt ElementSize = APInt(PtrIndexTy->getIntegerBitWidth(),
1016 GTI.getSequentialElementStride(DL: *DL));
1017 // Scale the index by element size.
1018 if (ElementSize != 1) {
1019 if (ElementSize.isPowerOf2()) {
1020 Idx = Builder.CreateShl(
1021 LHS: Idx, RHS: ConstantInt::get(Ty: PtrIndexTy, V: ElementSize.logBase2()));
1022 } else {
1023 Idx =
1024 Builder.CreateMul(LHS: Idx, RHS: ConstantInt::get(Ty: PtrIndexTy, V: ElementSize));
1025 }
1026 }
1027 // Create an ugly GEP with a single index for each index.
1028 ResultPtr = Builder.CreatePtrAdd(Ptr: ResultPtr, Offset: Idx, Name: "uglygep");
1029 if (FirstResult == nullptr)
1030 FirstResult = ResultPtr;
1031 }
1032 }
1033
1034 // Create a GEP with the constant offset index.
1035 if (AccumulativeByteOffset != 0) {
1036 Value *Offset = ConstantInt::get(Ty: PtrIndexTy, V: AccumulativeByteOffset);
1037 ResultPtr = Builder.CreatePtrAdd(Ptr: ResultPtr, Offset, Name: "uglygep");
1038 } else
1039 isSwapCandidate = false;
1040
1041 // If we created a GEP with constant index, and the base is loop invariant,
1042 // then we swap the first one with it, so LICM can move constant GEP out
1043 // later.
1044 auto *FirstGEP = dyn_cast_or_null<GetElementPtrInst>(Val: FirstResult);
1045 auto *SecondGEP = dyn_cast<GetElementPtrInst>(Val: ResultPtr);
1046 if (isSwapCandidate && isLegalToSwapOperand(First: FirstGEP, Second: SecondGEP, CurLoop: L))
1047 swapGEPOperand(First: FirstGEP, Second: SecondGEP);
1048
1049 Variadic->replaceAllUsesWith(V: ResultPtr);
1050 Variadic->eraseFromParent();
1051}
1052
1053bool SeparateConstOffsetFromGEP::reorderGEP(GetElementPtrInst *GEP,
1054 TargetTransformInfo &TTI) {
1055 auto PtrGEP = dyn_cast<GetElementPtrInst>(Val: GEP->getPointerOperand());
1056 if (!PtrGEP)
1057 return false;
1058
1059 bool NestedNeedsExtraction, OffsetOverflow;
1060 APInt NestedByteOffset =
1061 accumulateByteOffset(GEP: PtrGEP, NeedsExtraction&: NestedNeedsExtraction, SignedOverflow&: OffsetOverflow);
1062 if (!NestedNeedsExtraction)
1063 return false;
1064
1065 unsigned AddrSpace = PtrGEP->getPointerAddressSpace();
1066 if (!TTI.isLegalAddressingMode(Ty: GEP->getResultElementType(),
1067 /*BaseGV=*/nullptr,
1068 BaseOffset: NestedByteOffset.getSExtValue(),
1069 /*HasBaseReg=*/true, /*Scale=*/0, AddrSpace))
1070 return false;
1071
1072 bool GEPInBounds = GEP->isInBounds();
1073 bool PtrGEPInBounds = PtrGEP->isInBounds();
1074 bool IsChainInBounds = GEPInBounds && PtrGEPInBounds;
1075 if (IsChainInBounds) {
1076 auto IsKnownNonNegative = [this](Value *V) {
1077 return isKnownNonNegative(V, SQ: *DL);
1078 };
1079 IsChainInBounds &= all_of(Range: GEP->indices(), P: IsKnownNonNegative);
1080 if (IsChainInBounds)
1081 IsChainInBounds &= all_of(Range: PtrGEP->indices(), P: IsKnownNonNegative);
1082 }
1083
1084 IRBuilder<> Builder(GEP);
1085 // For trivial GEP chains, we can swap the indices.
1086 Value *NewSrc = Builder.CreateGEP(
1087 Ty: GEP->getSourceElementType(), Ptr: PtrGEP->getPointerOperand(),
1088 IdxList: SmallVector<Value *, 4>(GEP->indices()), Name: "", NW: IsChainInBounds);
1089 Value *NewGEP = Builder.CreateGEP(Ty: PtrGEP->getSourceElementType(), Ptr: NewSrc,
1090 IdxList: SmallVector<Value *, 4>(PtrGEP->indices()),
1091 Name: "", NW: IsChainInBounds);
1092 GEP->replaceAllUsesWith(V: NewGEP);
1093 RecursivelyDeleteTriviallyDeadInstructions(V: GEP);
1094 return true;
1095}
1096
1097bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) {
1098 // Skip vector GEPs.
1099 if (GEP->getType()->isVectorTy())
1100 return false;
1101
1102 // If the base of this GEP is a ptradd of a constant, lets pass the constant
1103 // along. This ensures that when we have a chain of GEPs the constant
1104 // offset from each is accumulated.
1105 Value *NewBase;
1106 const APInt *BaseOffset;
1107 bool ExtractBase = match(V: GEP->getPointerOperand(),
1108 P: m_PtrAdd(PointerOp: m_Value(V&: NewBase), OffsetOp: m_APInt(Res&: BaseOffset)));
1109
1110 unsigned IdxWidth = DL->getIndexTypeSizeInBits(Ty: GEP->getType());
1111 APInt BaseByteOffset =
1112 ExtractBase ? BaseOffset->sextOrTrunc(width: IdxWidth) : APInt(IdxWidth, 0);
1113
1114 // The backend can already nicely handle the case where all indices are
1115 // constant.
1116 if (GEP->hasAllConstantIndices() && !ExtractBase)
1117 return false;
1118
1119 bool Changed = canonicalizeArrayIndicesToIndexSize(GEP);
1120
1121 bool NeedsExtraction, OffsetOverflow;
1122 APInt NonBaseByteOffset =
1123 accumulateByteOffset(GEP, NeedsExtraction, SignedOverflow&: OffsetOverflow);
1124 bool AddOverflow;
1125 APInt AccumulativeByteOffset =
1126 BaseByteOffset.sadd_ov(RHS: NonBaseByteOffset, Overflow&: AddOverflow);
1127 OffsetOverflow |= AddOverflow;
1128
1129 TargetTransformInfo &TTI = GetTTI(*GEP->getFunction());
1130
1131 if (!NeedsExtraction && !ExtractBase) {
1132 Changed |= reorderGEP(GEP, TTI);
1133 return Changed;
1134 }
1135
1136 // If LowerGEP is disabled, before really splitting the GEP, check whether the
1137 // backend supports the addressing mode we are about to produce. If no, this
1138 // splitting probably won't be beneficial.
1139 // If LowerGEP is enabled, even the extracted constant offset can not match
1140 // the addressing mode, we can still do optimizations to other lowered parts
1141 // of variable indices. Therefore, we don't check for addressing modes in that
1142 // case.
1143 if (!LowerGEP) {
1144 unsigned AddrSpace = GEP->getPointerAddressSpace();
1145 if (!TTI.isLegalAddressingMode(
1146 Ty: GEP->getResultElementType(),
1147 /*BaseGV=*/nullptr, BaseOffset: AccumulativeByteOffset.getSExtValue(),
1148 /*HasBaseReg=*/true, /*Scale=*/0, AddrSpace)) {
1149 // If the addressing mode was not legal and the base byte offset was not
1150 // 0, it could be a case where the total offset became too large for
1151 // the addressing mode. Try again without extracting the base offset.
1152 if (!ExtractBase)
1153 return Changed;
1154 ExtractBase = false;
1155 BaseByteOffset = APInt(IdxWidth, 0);
1156 AccumulativeByteOffset = NonBaseByteOffset;
1157 if (!TTI.isLegalAddressingMode(
1158 Ty: GEP->getResultElementType(),
1159 /*BaseGV=*/nullptr, BaseOffset: AccumulativeByteOffset.getSExtValue(),
1160 /*HasBaseReg=*/true, /*Scale=*/0, AddrSpace))
1161 return Changed;
1162 // We can proceed with just extracting the other (non-base) offsets.
1163 NeedsExtraction = true;
1164 }
1165 }
1166
1167 // Track information for preserving GEP flags.
1168 bool AllOffsetsNonNegative =
1169 AccumulativeByteOffset.isNonNegative() && !OffsetOverflow;
1170 bool AllNUWPreserved = GEP->hasNoUnsignedWrap();
1171 bool NewGEPInBounds = GEP->isInBounds();
1172 bool NewGEPNUSW = GEP->hasNoUnsignedSignedWrap();
1173
1174 // Remove the constant offset in each sequential index. The resultant GEP
1175 // computes the variadic base.
1176 // Notice that we don't remove struct field indices here. If LowerGEP is
1177 // disabled, a structure index is not accumulated and we still use the old
1178 // one. If LowerGEP is enabled, a structure index is accumulated in the
1179 // constant offset. LowerToSingleIndexGEPs will later handle the constant
1180 // offset and won't need a new structure index.
1181 gep_type_iterator GTI = gep_type_begin(GEP: *GEP);
1182 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
1183 if (GTI.isSequential()) {
1184 // Constant offsets of scalable types are not really constant.
1185 if (GTI.getIndexedType()->isScalableTy())
1186 continue;
1187
1188 // Splits this GEP index into a variadic part and a constant offset, and
1189 // uses the variadic part as the new index.
1190 Value *Idx = GEP->getOperand(i_nocapture: I);
1191 User *UserChainTail;
1192 bool PreservesNUW;
1193 Value *NewIdx = ConstantOffsetExtractor::Extract(
1194 Idx: GEP->getOperandUse(i: I), UserChainTail, PreservesNUW);
1195 if (NewIdx != nullptr) {
1196 // Switches to the index with the constant offset removed.
1197 GEP->setOperand(i_nocapture: I, Val_nocapture: NewIdx);
1198 // After switching to the new index, we can garbage-collect UserChain
1199 // and the old index if they are not used.
1200 if (auto *I = dyn_cast_or_null<Instruction>(Val: UserChainTail))
1201 RecursivelyDeleteTriviallyDeadInstructions(V: I);
1202 if (auto *I = dyn_cast<Instruction>(Val: Idx))
1203 RecursivelyDeleteTriviallyDeadInstructions(V: I);
1204 Idx = NewIdx;
1205 AllNUWPreserved &= PreservesNUW;
1206 }
1207 AllOffsetsNonNegative =
1208 AllOffsetsNonNegative && isKnownNonNegative(V: Idx, SQ: *DL);
1209 }
1210 }
1211 if (ExtractBase) {
1212 GEPOperator *Base = cast<GEPOperator>(Val: GEP->getPointerOperand());
1213 AllNUWPreserved &= Base->hasNoUnsignedWrap();
1214 NewGEPInBounds &= Base->isInBounds();
1215 NewGEPNUSW &= Base->hasNoUnsignedSignedWrap();
1216 AllOffsetsNonNegative &= BaseByteOffset.isNonNegative();
1217
1218 GEP->setOperand(i_nocapture: 0, Val_nocapture: NewBase);
1219 RecursivelyDeleteTriviallyDeadInstructions(V: Base);
1220 }
1221
1222 // Clear the inbounds attribute because the new index may be off-bound.
1223 // e.g.,
1224 //
1225 // b = add i64 a, 5
1226 // addr = gep inbounds float, float* p, i64 b
1227 //
1228 // is transformed to:
1229 //
1230 // addr2 = gep float, float* p, i64 a ; inbounds removed
1231 // addr = gep float, float* addr2, i64 5 ; inbounds removed
1232 //
1233 // If a is -4, although the old index b is in bounds, the new index a is
1234 // off-bound. http://llvm.org/docs/LangRef.html#id181 says "if the
1235 // inbounds keyword is not present, the offsets are added to the base
1236 // address with silently-wrapping two's complement arithmetic".
1237 // Therefore, the final code will be a semantically equivalent.
1238 GEPNoWrapFlags NewGEPFlags = GEPNoWrapFlags::none();
1239
1240 // If the initial GEP was inbounds/nusw and all variable indices and the
1241 // accumulated offsets are non-negative, they can be added in any order and
1242 // the intermediate results are in bounds and don't overflow in a nusw sense.
1243 // So, we can preserve the inbounds/nusw flag for both GEPs.
1244 bool CanPreserveInBoundsNUSW = AllOffsetsNonNegative;
1245
1246 // If the initial GEP was NUW and all operations that we reassociate were NUW
1247 // additions, the resulting GEPs are also NUW.
1248 if (AllNUWPreserved) {
1249 NewGEPFlags |= GEPNoWrapFlags::noUnsignedWrap();
1250 // If the initial GEP additionally had NUSW (or inbounds, which implies
1251 // NUSW), we know that the indices in the initial GEP must all have their
1252 // signbit not set. For indices that are the result of NUW adds, the
1253 // add-operands therefore also don't have their signbit set. Therefore, all
1254 // indices of the resulting GEPs are non-negative -> we can preserve
1255 // the inbounds/nusw flag.
1256 CanPreserveInBoundsNUSW |= NewGEPNUSW;
1257 }
1258
1259 if (CanPreserveInBoundsNUSW) {
1260 if (NewGEPInBounds)
1261 NewGEPFlags |= GEPNoWrapFlags::inBounds();
1262 else if (NewGEPNUSW)
1263 NewGEPFlags |= GEPNoWrapFlags::noUnsignedSignedWrap();
1264 }
1265
1266 GEP->setNoWrapFlags(NewGEPFlags);
1267
1268 // Lowers a GEP to GEPs with a single index.
1269 if (LowerGEP) {
1270 lowerToSingleIndexGEPs(Variadic: GEP, AccumulativeByteOffset);
1271 return true;
1272 }
1273
1274 // No need to create another GEP if the accumulative byte offset is 0.
1275 if (AccumulativeByteOffset == 0)
1276 return true;
1277
1278 // Offsets the base with the accumulative byte offset.
1279 //
1280 // %gep ; the base
1281 // ... %gep ...
1282 //
1283 // => add the offset
1284 //
1285 // %gep2 ; clone of %gep
1286 // %new.gep = gep i8, %gep2, %offset
1287 // %gep ; will be removed
1288 // ... %gep ...
1289 //
1290 // => replace all uses of %gep with %new.gep and remove %gep
1291 //
1292 // %gep2 ; clone of %gep
1293 // %new.gep = gep i8, %gep2, %offset
1294 // ... %new.gep ...
1295 Instruction *NewGEP = GEP->clone();
1296 NewGEP->insertBefore(InsertPos: GEP->getIterator());
1297
1298 Type *PtrIdxTy = DL->getIndexType(PtrTy: GEP->getType());
1299 IRBuilder<> Builder(GEP);
1300 NewGEP = cast<Instruction>(Val: Builder.CreatePtrAdd(
1301 Ptr: NewGEP, Offset: ConstantInt::get(Ty: PtrIdxTy, V: AccumulativeByteOffset),
1302 Name: GEP->getName(), NW: NewGEPFlags));
1303 NewGEP->copyMetadata(SrcInst: *GEP);
1304
1305 GEP->replaceAllUsesWith(V: NewGEP);
1306 GEP->eraseFromParent();
1307
1308 return true;
1309}
1310
1311bool SeparateConstOffsetFromGEPLegacyPass::runOnFunction(Function &F) {
1312 if (skipFunction(F))
1313 return false;
1314 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1315 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1316 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1317 auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
1318 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1319 };
1320 SeparateConstOffsetFromGEP Impl(DT, LI, TLI, GetTTI, LowerGEP);
1321 return Impl.run(F);
1322}
1323
1324bool SeparateConstOffsetFromGEP::run(Function &F) {
1325 const ScalarOptions &Opts = ScalarOptions::Global;
1326 if (Opts.disable_separate_const_offset_from_gep)
1327 return false;
1328
1329 DL = &F.getDataLayout();
1330 bool Changed = false;
1331
1332 ReversePostOrderTraversal<Function *> RPOT(&F);
1333 for (BasicBlock *B : RPOT) {
1334 if (!DT->isReachableFromEntry(A: B))
1335 continue;
1336
1337 for (Instruction &I : llvm::make_early_inc_range(Range&: *B))
1338 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: &I))
1339 Changed |= splitGEP(GEP);
1340 // No need to split GEP ConstantExprs because all its indices are constant
1341 // already.
1342 }
1343
1344 Changed |= reuniteExts(F);
1345
1346 if (Opts.reassociate_geps_verify_no_dead_code)
1347 verifyNoDeadCode(F);
1348
1349 return Changed;
1350}
1351
1352Instruction *SeparateConstOffsetFromGEP::findClosestMatchingDominator(
1353 ExprKey Key, Instruction *Dominatee,
1354 DenseMap<ExprKey, SmallVector<Instruction *, 2>> &DominatingExprs) {
1355 auto Pos = DominatingExprs.find(Val: Key);
1356 if (Pos == DominatingExprs.end())
1357 return nullptr;
1358
1359 auto &Candidates = Pos->second;
1360 // Because we process the basic blocks in pre-order of the dominator tree, a
1361 // candidate that doesn't dominate the current instruction won't dominate any
1362 // future instruction either. Therefore, we pop it out of the stack. This
1363 // optimization makes the algorithm O(n).
1364 while (!Candidates.empty()) {
1365 Instruction *Candidate = Candidates.back();
1366 if (DT->dominates(Def: Candidate, User: Dominatee))
1367 return Candidate;
1368 Candidates.pop_back();
1369 }
1370 return nullptr;
1371}
1372
1373bool SeparateConstOffsetFromGEP::reuniteExts(Instruction *I) {
1374 if (!I->getType()->isIntOrIntVectorTy())
1375 return false;
1376
1377 // Dom: LHS+RHS
1378 // I: sext(LHS)+sext(RHS)
1379 // If Dom can't sign overflow and Dom dominates I, optimize I to sext(Dom).
1380 // TODO: handle zext
1381 Value *LHS = nullptr, *RHS = nullptr;
1382 if (match(V: I, P: m_Add(L: m_SExt(Op: m_Value(V&: LHS)), R: m_SExt(Op: m_Value(V&: RHS))))) {
1383 if (LHS->getType() == RHS->getType()) {
1384 ExprKey Key = createNormalizedCommutablePair(A: LHS, B: RHS);
1385 if (auto *Dom = findClosestMatchingDominator(Key, Dominatee: I, DominatingExprs&: DominatingAdds)) {
1386 Instruction *NewSExt =
1387 new SExtInst(Dom, I->getType(), "", I->getIterator());
1388 NewSExt->takeName(V: I);
1389 I->replaceAllUsesWith(V: NewSExt);
1390 NewSExt->setDebugLoc(I->getDebugLoc());
1391 RecursivelyDeleteTriviallyDeadInstructions(V: I);
1392 return true;
1393 }
1394 }
1395 } else if (match(V: I, P: m_Sub(L: m_SExt(Op: m_Value(V&: LHS)), R: m_SExt(Op: m_Value(V&: RHS))))) {
1396 if (LHS->getType() == RHS->getType()) {
1397 if (auto *Dom =
1398 findClosestMatchingDominator(Key: {LHS, RHS}, Dominatee: I, DominatingExprs&: DominatingSubs)) {
1399 Instruction *NewSExt =
1400 new SExtInst(Dom, I->getType(), "", I->getIterator());
1401 NewSExt->takeName(V: I);
1402 I->replaceAllUsesWith(V: NewSExt);
1403 NewSExt->setDebugLoc(I->getDebugLoc());
1404 RecursivelyDeleteTriviallyDeadInstructions(V: I);
1405 return true;
1406 }
1407 }
1408 }
1409
1410 // Add I to DominatingExprs if it's an add/sub that can't sign overflow.
1411 if (match(V: I, P: m_NSWAdd(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
1412 if (programUndefinedIfPoison(Inst: I)) {
1413 ExprKey Key = createNormalizedCommutablePair(A: LHS, B: RHS);
1414 DominatingAdds[Key].push_back(Elt: I);
1415 }
1416 } else if (match(V: I, P: m_NSWSub(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
1417 if (programUndefinedIfPoison(Inst: I))
1418 DominatingSubs[{LHS, RHS}].push_back(Elt: I);
1419 }
1420 return false;
1421}
1422
1423bool SeparateConstOffsetFromGEP::reuniteExts(Function &F) {
1424 bool Changed = false;
1425 DominatingAdds.clear();
1426 DominatingSubs.clear();
1427 for (const auto Node : depth_first(G: DT)) {
1428 BasicBlock *BB = Node->getBlock();
1429 for (Instruction &I : llvm::make_early_inc_range(Range&: *BB))
1430 Changed |= reuniteExts(I: &I);
1431 }
1432 return Changed;
1433}
1434
1435void SeparateConstOffsetFromGEP::verifyNoDeadCode(Function &F) {
1436 for (BasicBlock &B : F) {
1437 for (Instruction &I : B) {
1438 if (isInstructionTriviallyDead(I: &I)) {
1439 std::string ErrMessage;
1440 raw_string_ostream RSO(ErrMessage);
1441 RSO << "Dead instruction detected!\n" << I << "\n";
1442 llvm_unreachable(RSO.str().c_str());
1443 }
1444 }
1445 }
1446}
1447
1448bool SeparateConstOffsetFromGEP::isLegalToSwapOperand(
1449 GetElementPtrInst *FirstGEP, GetElementPtrInst *SecondGEP, Loop *CurLoop) {
1450 if (!FirstGEP || !FirstGEP->hasOneUse())
1451 return false;
1452
1453 if (!SecondGEP || FirstGEP->getParent() != SecondGEP->getParent())
1454 return false;
1455
1456 if (FirstGEP == SecondGEP)
1457 return false;
1458
1459 unsigned FirstNum = FirstGEP->getNumOperands();
1460 unsigned SecondNum = SecondGEP->getNumOperands();
1461 // Give up if the number of operands are not 2.
1462 if (FirstNum != SecondNum || FirstNum != 2)
1463 return false;
1464
1465 Value *FirstBase = FirstGEP->getOperand(i_nocapture: 0);
1466 Value *SecondBase = SecondGEP->getOperand(i_nocapture: 0);
1467 Value *FirstOffset = FirstGEP->getOperand(i_nocapture: 1);
1468 // Give up if the index of the first GEP is loop invariant.
1469 if (CurLoop->isLoopInvariant(V: FirstOffset))
1470 return false;
1471
1472 // Give up if base doesn't have same type.
1473 if (FirstBase->getType() != SecondBase->getType())
1474 return false;
1475
1476 Instruction *FirstOffsetDef = dyn_cast<Instruction>(Val: FirstOffset);
1477
1478 // Check if the second operand of first GEP has constant coefficient.
1479 // For an example, for the following code, we won't gain anything by
1480 // hoisting the second GEP out because the second GEP can be folded away.
1481 // %scevgep.sum.ur159 = add i64 %idxprom48.ur, 256
1482 // %67 = shl i64 %scevgep.sum.ur159, 2
1483 // %uglygep160 = getelementptr i8* %65, i64 %67
1484 // %uglygep161 = getelementptr i8* %uglygep160, i64 -1024
1485
1486 // Skip constant shift instruction which may be generated by Splitting GEPs.
1487 if (FirstOffsetDef && FirstOffsetDef->isShift() &&
1488 isa<ConstantInt>(Val: FirstOffsetDef->getOperand(i: 1)))
1489 FirstOffsetDef = dyn_cast<Instruction>(Val: FirstOffsetDef->getOperand(i: 0));
1490
1491 // Give up if FirstOffsetDef is an Add or Sub with constant.
1492 // Because it may not profitable at all due to constant folding.
1493 if (FirstOffsetDef)
1494 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: FirstOffsetDef)) {
1495 unsigned opc = BO->getOpcode();
1496 if ((opc == Instruction::Add || opc == Instruction::Sub) &&
1497 (isa<ConstantInt>(Val: BO->getOperand(i_nocapture: 0)) ||
1498 isa<ConstantInt>(Val: BO->getOperand(i_nocapture: 1))))
1499 return false;
1500 }
1501 return true;
1502}
1503
1504bool SeparateConstOffsetFromGEP::hasMoreThanOneUseInLoop(Value *V, Loop *L) {
1505 // TODO: Could look at uses of globals, but we need to make sure we are
1506 // looking at the correct function.
1507 if (isa<Constant>(Val: V))
1508 return false;
1509
1510 int UsesInLoop = 0;
1511 for (User *U : V->users()) {
1512 if (Instruction *User = dyn_cast<Instruction>(Val: U))
1513 if (L->contains(Inst: User))
1514 if (++UsesInLoop > 1)
1515 return true;
1516 }
1517 return false;
1518}
1519
1520void SeparateConstOffsetFromGEP::swapGEPOperand(GetElementPtrInst *First,
1521 GetElementPtrInst *Second) {
1522 Value *Offset1 = First->getOperand(i_nocapture: 1);
1523 Value *Offset2 = Second->getOperand(i_nocapture: 1);
1524 First->setOperand(i_nocapture: 1, Val_nocapture: Offset2);
1525 Second->setOperand(i_nocapture: 1, Val_nocapture: Offset1);
1526
1527 // After changing (p+o)+c to (p+c)+o, the inner GEP may not be inbounds
1528 // anymore.
1529 const DataLayout &DAL = First->getDataLayout();
1530 unsigned IdxBits = DAL.getIndexSizeInBits(
1531 AS: cast<PointerType>(Val: First->getType())->getAddressSpace());
1532
1533 auto ClearNoWrapFlags = [&] {
1534 // TODO(gep_nowrap): Make flag preservation more precise.
1535 First->setNoWrapFlags(GEPNoWrapFlags::none());
1536 Second->setNoWrapFlags(GEPNoWrapFlags::none());
1537 };
1538
1539 APInt FirstOffset(IdxBits, 0);
1540 if (!First->accumulateConstantOffset(DL: DAL, Offset&: FirstOffset)) {
1541 ClearNoWrapFlags();
1542 return;
1543 }
1544
1545 APInt BaseOffset(IdxBits, 0);
1546 Value *NewBase =
1547 First->getOperand(i_nocapture: 0)->stripAndAccumulateInBoundsConstantOffsets(
1548 DL: DAL, Offset&: BaseOffset);
1549
1550 bool Overflow = false;
1551 APInt TotalOffset = BaseOffset.uadd_ov(RHS: FirstOffset, Overflow);
1552 uint64_t ObjectSize;
1553 if (Overflow || !getObjectSize(Ptr: NewBase, Size&: ObjectSize, DL: DAL, TLI) ||
1554 TotalOffset.ugt(RHS: ObjectSize)) {
1555 ClearNoWrapFlags();
1556 return;
1557 }
1558
1559 First->setIsInBounds(true);
1560}
1561
1562void SeparateConstOffsetFromGEPPass::printPipeline(
1563 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1564 static_cast<PassInfoMixin<SeparateConstOffsetFromGEPPass> *>(this)
1565 ->printPipeline(OS, MapClassName2PassName);
1566 OS << '<';
1567 if (LowerGEP)
1568 OS << "lower-gep";
1569 OS << '>';
1570}
1571
1572PreservedAnalyses
1573SeparateConstOffsetFromGEPPass::run(Function &F, FunctionAnalysisManager &AM) {
1574 auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
1575 auto *LI = &AM.getResult<LoopAnalysis>(IR&: F);
1576 auto *TLI = &AM.getResult<TargetLibraryAnalysis>(IR&: F);
1577 auto GetTTI = [&AM](Function &F) -> TargetTransformInfo & {
1578 return AM.getResult<TargetIRAnalysis>(IR&: F);
1579 };
1580 SeparateConstOffsetFromGEP Impl(DT, LI, TLI, GetTTI, LowerGEP);
1581 if (!Impl.run(F))
1582 return PreservedAnalyses::all();
1583 PreservedAnalyses PA;
1584 PA.preserveSet<CFGAnalyses>();
1585 return PA;
1586}
1587