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