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