1 //===-- SeparateConstOffsetFromGEP.cpp - ------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Loop unrolling may create many similar GEPs for array accesses.
11 // e.g., a 2-level loop
13 // float a[32][32]; // global variable
15 // for (int i = 0; i < 2; ++i) {
16 // for (int j = 0; j < 2; ++j) {
18 // ... = a[x + i][y + j];
23 // will probably be unrolled to:
25 // gep %a, 0, %x, %y; load
26 // gep %a, 0, %x, %y + 1; load
27 // gep %a, 0, %x + 1, %y; load
28 // gep %a, 0, %x + 1, %y + 1; load
30 // LLVM's GVN does not use partial redundancy elimination yet, and is thus
31 // unable to reuse (gep %a, 0, %x, %y). As a result, this misoptimization incurs
32 // significant slowdown in targets with limited addressing modes. For instance,
33 // because the PTX target does not support the reg+reg addressing mode, the
34 // NVPTX backend emits PTX code that literally computes the pointer address of
35 // each GEP, wasting tons of registers. It emits the following PTX for the
36 // first load and similar PTX for other loads.
40 // mul.wide.u32 %rl2, %r1, 128;
42 // add.s64 %rl4, %rl3, %rl2;
43 // mul.wide.u32 %rl5, %r2, 4;
44 // add.s64 %rl6, %rl4, %rl5;
45 // ld.global.f32 %f1, [%rl6];
47 // To reduce the register pressure, the optimization implemented in this file
48 // merges the common part of a group of GEPs, so we can compute each pointer
49 // address by adding a simple offset to the common part, saving many registers.
51 // It works by splitting each GEP into a variadic base and a constant offset.
52 // The variadic base can be computed once and reused by multiple GEPs, and the
53 // constant offsets can be nicely folded into the reg+immediate addressing mode
54 // (supported by most targets) without using any extra register.
56 // For instance, we transform the four GEPs and four loads in the above example
59 // base = gep a, 0, x, y
61 // laod base + 1 * sizeof(float)
62 // load base + 32 * sizeof(float)
63 // load base + 33 * sizeof(float)
65 // Given the transformed IR, a backend that supports the reg+immediate
66 // addressing mode can easily fold the pointer arithmetics into the loads. For
67 // example, the NVPTX backend can easily fold the pointer arithmetics into the
68 // ld.global.f32 instructions, and the resultant PTX uses much fewer registers.
70 // mov.u32 %r1, %tid.x;
71 // mov.u32 %r2, %tid.y;
72 // mul.wide.u32 %rl2, %r1, 128;
74 // add.s64 %rl4, %rl3, %rl2;
75 // mul.wide.u32 %rl5, %r2, 4;
76 // add.s64 %rl6, %rl4, %rl5;
77 // ld.global.f32 %f1, [%rl6]; // so far the same as unoptimized PTX
78 // ld.global.f32 %f2, [%rl6+4]; // much better
79 // ld.global.f32 %f3, [%rl6+128]; // much better
80 // ld.global.f32 %f4, [%rl6+132]; // much better
82 //===----------------------------------------------------------------------===//
84 #include "llvm/Analysis/TargetTransformInfo.h"
85 #include "llvm/Analysis/ValueTracking.h"
86 #include "llvm/IR/Constants.h"
87 #include "llvm/IR/DataLayout.h"
88 #include "llvm/IR/Instructions.h"
89 #include "llvm/IR/LLVMContext.h"
90 #include "llvm/IR/Module.h"
91 #include "llvm/IR/Operator.h"
92 #include "llvm/Support/CommandLine.h"
93 #include "llvm/Support/raw_ostream.h"
94 #include "llvm/Transforms/Scalar.h"
98 static cl::opt<bool> DisableSeparateConstOffsetFromGEP(
99 "disable-separate-const-offset-from-gep", cl::init(false),
100 cl::desc("Do not separate the constant offset from a GEP instruction"),
105 /// \brief A helper class for separating a constant offset from a GEP index.
107 /// In real programs, a GEP index may be more complicated than a simple addition
108 /// of something and a constant integer which can be trivially splitted. For
109 /// example, to split ((a << 3) | 5) + b, we need to search deeper for the
110 /// constant offset, so that we can separate the index to (a << 3) + b and 5.
112 /// Therefore, this class looks into the expression that computes a given GEP
113 /// index, and tries to find a constant integer that can be hoisted to the
114 /// outermost level of the expression as an addition. Not every constant in an
115 /// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a +
116 /// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case,
117 /// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15).
118 class ConstantOffsetExtractor {
120 /// Extracts a constant offset from the given GEP index. It outputs the
121 /// numeric value of the extracted constant offset (0 if failed), and a
122 /// new index representing the remainder (equal to the original index minus
123 /// the constant offset).
124 /// \p Idx The given GEP index
125 /// \p NewIdx The new index to replace (output)
126 /// \p DL The datalayout of the module
127 /// \p GEP The given GEP
128 static int64_t Extract(Value *Idx, Value *&NewIdx, const DataLayout *DL,
129 GetElementPtrInst *GEP);
130 /// Looks for a constant offset without extracting it. The meaning of the
131 /// arguments and the return value are the same as Extract.
132 static int64_t Find(Value *Idx, const DataLayout *DL, GetElementPtrInst *GEP);
135 ConstantOffsetExtractor(const DataLayout *Layout, Instruction *InsertionPt)
136 : DL(Layout), IP(InsertionPt) {}
137 /// Searches the expression that computes V for a non-zero constant C s.t.
138 /// V can be reassociated into the form V' + C. If the searching is
139 /// successful, returns C and update UserChain as a def-use chain from C to V;
140 /// otherwise, UserChain is empty.
142 /// \p V The given expression
143 /// \p SignExtended Whether V will be sign-extended in the computation of the
145 /// \p ZeroExtended Whether V will be zero-extended in the computation of the
147 /// \p NonNegative Whether V is guaranteed to be non-negative. For example,
148 /// an index of an inbounds GEP is guaranteed to be
149 /// non-negative. Levaraging this, we can better split
151 APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative);
152 /// A helper function to look into both operands of a binary operator.
153 APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended,
155 /// After finding the constant offset C from the GEP index I, we build a new
156 /// index I' s.t. I' + C = I. This function builds and returns the new
157 /// index I' according to UserChain produced by function "find".
159 /// The building conceptually takes two steps:
160 /// 1) iteratively distribute s/zext towards the leaves of the expression tree
162 /// 2) reassociate the expression tree to the form I' + C.
164 /// For example, to extract the 5 from sext(a + (b + 5)), we first distribute
165 /// sext to a, b and 5 so that we have
166 /// sext(a) + (sext(b) + 5).
167 /// Then, we reassociate it to
168 /// (sext(a) + sext(b)) + 5.
169 /// Given this form, we know I' is sext(a) + sext(b).
170 Value *rebuildWithoutConstOffset();
171 /// After the first step of rebuilding the GEP index without the constant
172 /// offset, distribute s/zext to the operands of all operators in UserChain.
173 /// e.g., zext(sext(a + (b + 5)) (assuming no overflow) =>
174 /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))).
176 /// The function also updates UserChain to point to new subexpressions after
177 /// distributing s/zext. e.g., the old UserChain of the above example is
178 /// 5 -> b + 5 -> a + (b + 5) -> sext(...) -> zext(sext(...)),
179 /// and the new UserChain is
180 /// zext(sext(5)) -> zext(sext(b)) + zext(sext(5)) ->
181 /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))
183 /// \p ChainIndex The index to UserChain. ChainIndex is initially
184 /// UserChain.size() - 1, and is decremented during
186 Value *distributeExtsAndCloneChain(unsigned ChainIndex);
187 /// Reassociates the GEP index to the form I' + C and returns I'.
188 Value *removeConstOffset(unsigned ChainIndex);
189 /// A helper function to apply ExtInsts, a list of s/zext, to value V.
190 /// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function
191 /// returns "sext i32 (zext i16 V to i32) to i64".
192 Value *applyExts(Value *V);
194 /// Returns true if LHS and RHS have no bits in common, i.e., LHS | RHS == 0.
195 bool NoCommonBits(Value *LHS, Value *RHS) const;
196 /// Computes which bits are known to be one or zero.
197 /// \p KnownOne Mask of all bits that are known to be one.
198 /// \p KnownZero Mask of all bits that are known to be zero.
199 void ComputeKnownBits(Value *V, APInt &KnownOne, APInt &KnownZero) const;
200 /// A helper function that returns whether we can trace into the operands
201 /// of binary operator BO for a constant offset.
203 /// \p SignExtended Whether BO is surrounded by sext
204 /// \p ZeroExtended Whether BO is surrounded by zext
205 /// \p NonNegative Whether BO is known to be non-negative, e.g., an in-bound
207 bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO,
210 /// The path from the constant offset to the old GEP index. e.g., if the GEP
211 /// index is "a * b + (c + 5)". After running function find, UserChain[0] will
212 /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and
213 /// UserChain[2] will be the entire expression "a * b + (c + 5)".
215 /// This path helps to rebuild the new GEP index.
216 SmallVector<User *, 8> UserChain;
217 /// A data structure used in rebuildWithoutConstOffset. Contains all
218 /// sext/zext instructions along UserChain.
219 SmallVector<CastInst *, 16> ExtInsts;
220 /// The data layout of the module. Used in ComputeKnownBits.
221 const DataLayout *DL;
222 Instruction *IP; /// Insertion position of cloned instructions.
225 /// \brief A pass that tries to split every GEP in the function into a variadic
226 /// base and a constant offset. It is a FunctionPass because searching for the
227 /// constant offset may inspect other basic blocks.
228 class SeparateConstOffsetFromGEP : public FunctionPass {
231 SeparateConstOffsetFromGEP() : FunctionPass(ID) {
232 initializeSeparateConstOffsetFromGEPPass(*PassRegistry::getPassRegistry());
235 void getAnalysisUsage(AnalysisUsage &AU) const override {
236 AU.addRequired<DataLayoutPass>();
237 AU.addRequired<TargetTransformInfo>();
239 bool runOnFunction(Function &F) override;
242 /// Tries to split the given GEP into a variadic base and a constant offset,
243 /// and returns true if the splitting succeeds.
244 bool splitGEP(GetElementPtrInst *GEP);
245 /// Finds the constant offset within each index, and accumulates them. This
246 /// function only inspects the GEP without changing it. The output
247 /// NeedsExtraction indicates whether we can extract a non-zero constant
248 /// offset from any index.
249 int64_t accumulateByteOffset(GetElementPtrInst *GEP, const DataLayout *DL,
250 bool &NeedsExtraction);
252 } // anonymous namespace
254 char SeparateConstOffsetFromGEP::ID = 0;
255 INITIALIZE_PASS_BEGIN(
256 SeparateConstOffsetFromGEP, "separate-const-offset-from-gep",
257 "Split GEPs to a variadic base and a constant offset for better CSE", false,
259 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
260 INITIALIZE_PASS_DEPENDENCY(DataLayoutPass)
262 SeparateConstOffsetFromGEP, "separate-const-offset-from-gep",
263 "Split GEPs to a variadic base and a constant offset for better CSE", false,
266 FunctionPass *llvm::createSeparateConstOffsetFromGEPPass() {
267 return new SeparateConstOffsetFromGEP();
270 bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,
274 // We only consider ADD, SUB and OR, because a non-zero constant found in
275 // expressions composed of these operations can be easily hoisted as a
276 // constant offset by reassociation.
277 if (BO->getOpcode() != Instruction::Add &&
278 BO->getOpcode() != Instruction::Sub &&
279 BO->getOpcode() != Instruction::Or) {
283 Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1);
284 // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS
285 // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS).
286 if (BO->getOpcode() == Instruction::Or && !NoCommonBits(LHS, RHS))
289 // In addition, tracing into BO requires that its surrounding s/zext (if
290 // any) is distributable to both operands.
292 // Suppose BO = A op B.
293 // SignExtended | ZeroExtended | Distributable?
294 // --------------+--------------+----------------------------------
295 // 0 | 0 | true because no s/zext exists
296 // 0 | 1 | zext(BO) == zext(A) op zext(B)
297 // 1 | 0 | sext(BO) == sext(A) op sext(B)
298 // 1 | 1 | zext(sext(BO)) ==
299 // | | zext(sext(A)) op zext(sext(B))
300 if (BO->getOpcode() == Instruction::Add && NonNegative) {
301 // If a + b >= 0 and (a >= 0 or b >= 0), then
302 // s/zext(a + b) = s/zext(a) + s/zext(b)
303 // even if the addition is not marked nsw.
305 // Leveraging this invarient, we can trace into an sext'ed inbound GEP
306 // index if the constant offset is non-negative.
308 // Verified in @sext_add in split-gep.ll.
309 if (ConstantInt *ConstLHS = dyn_cast<ConstantInt>(LHS)) {
310 if (!ConstLHS->isNegative())
313 if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(RHS)) {
314 if (!ConstRHS->isNegative())
319 // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B)
320 // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B)
321 if (BO->getOpcode() == Instruction::Add ||
322 BO->getOpcode() == Instruction::Sub) {
323 if (SignExtended && !BO->hasNoSignedWrap())
325 if (ZeroExtended && !BO->hasNoUnsignedWrap())
332 APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,
335 // BO being non-negative does not shed light on whether its operands are
336 // non-negative. Clear the NonNegative flag here.
337 APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended,
338 /* NonNegative */ false);
339 // If we found a constant offset in the left operand, stop and return that.
340 // This shortcut might cause us to miss opportunities of combining the
341 // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9.
342 // However, such cases are probably already handled by -instcombine,
343 // given this pass runs after the standard optimizations.
344 if (ConstantOffset != 0) return ConstantOffset;
345 ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended,
346 /* NonNegative */ false);
347 // If U is a sub operator, negate the constant offset found in the right
349 if (BO->getOpcode() == Instruction::Sub)
350 ConstantOffset = -ConstantOffset;
351 return ConstantOffset;
354 APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended,
355 bool ZeroExtended, bool NonNegative) {
356 // TODO(jingyue): We could trace into integer/pointer casts, such as
357 // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only
358 // integers because it gives good enough results for our benchmarks.
359 unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
361 // We cannot do much with Values that are not a User, such as an Argument.
362 User *U = dyn_cast<User>(V);
363 if (U == nullptr) return APInt(BitWidth, 0);
365 APInt ConstantOffset(BitWidth, 0);
366 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
367 // Hooray, we found it!
368 ConstantOffset = CI->getValue();
369 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) {
370 // Trace into subexpressions for more hoisting opportunities.
371 if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative)) {
372 ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended);
374 } else if (isa<SExtInst>(V)) {
375 ConstantOffset = find(U->getOperand(0), /* SignExtended */ true,
376 ZeroExtended, NonNegative).sext(BitWidth);
377 } else if (isa<ZExtInst>(V)) {
378 // As an optimization, we can clear the SignExtended flag because
379 // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll.
381 // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0.
382 // TODO: if zext(a) < 2 ^ (bitwidth(a) - 1), we can prove a >= 0.
384 find(U->getOperand(0), /* SignExtended */ false,
385 /* ZeroExtended */ true, /* NonNegative */ false).zext(BitWidth);
388 // If we found a non-zero constant offset, add it to the path for
389 // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't
390 // help this optimization.
391 if (ConstantOffset != 0)
392 UserChain.push_back(U);
393 return ConstantOffset;
396 Value *ConstantOffsetExtractor::applyExts(Value *V) {
398 // ExtInsts is built in the use-def order. Therefore, we apply them to V
399 // in the reversed order.
400 for (auto I = ExtInsts.rbegin(), E = ExtInsts.rend(); I != E; ++I) {
401 if (Constant *C = dyn_cast<Constant>(Current)) {
402 // If Current is a constant, apply s/zext using ConstantExpr::getCast.
403 // ConstantExpr::getCast emits a ConstantInt if C is a ConstantInt.
404 Current = ConstantExpr::getCast((*I)->getOpcode(), C, (*I)->getType());
406 Instruction *Ext = (*I)->clone();
407 Ext->setOperand(0, Current);
408 Ext->insertBefore(IP);
415 Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() {
416 distributeExtsAndCloneChain(UserChain.size() - 1);
417 // Remove all nullptrs (used to be s/zext) from UserChain.
418 unsigned NewSize = 0;
419 for (auto I = UserChain.begin(), E = UserChain.end(); I != E; ++I) {
421 UserChain[NewSize] = *I;
425 UserChain.resize(NewSize);
426 return removeConstOffset(UserChain.size() - 1);
430 ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) {
431 User *U = UserChain[ChainIndex];
432 if (ChainIndex == 0) {
433 assert(isa<ConstantInt>(U));
434 // If U is a ConstantInt, applyExts will return a ConstantInt as well.
435 return UserChain[ChainIndex] = cast<ConstantInt>(applyExts(U));
438 if (CastInst *Cast = dyn_cast<CastInst>(U)) {
439 assert((isa<SExtInst>(Cast) || isa<ZExtInst>(Cast)) &&
440 "We only traced into two types of CastInst: sext and zext");
441 ExtInsts.push_back(Cast);
442 UserChain[ChainIndex] = nullptr;
443 return distributeExtsAndCloneChain(ChainIndex - 1);
446 // Function find only trace into BinaryOperator and CastInst.
447 BinaryOperator *BO = cast<BinaryOperator>(U);
448 // OpNo = which operand of BO is UserChain[ChainIndex - 1]
449 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
450 Value *TheOther = applyExts(BO->getOperand(1 - OpNo));
451 Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1);
453 BinaryOperator *NewBO = nullptr;
455 NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther,
458 NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain,
461 return UserChain[ChainIndex] = NewBO;
464 Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) {
465 if (ChainIndex == 0) {
466 assert(isa<ConstantInt>(UserChain[ChainIndex]));
467 return ConstantInt::getNullValue(UserChain[ChainIndex]->getType());
470 BinaryOperator *BO = cast<BinaryOperator>(UserChain[ChainIndex]);
471 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
472 assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]);
473 Value *NextInChain = removeConstOffset(ChainIndex - 1);
474 Value *TheOther = BO->getOperand(1 - OpNo);
476 // If NextInChain is 0 and not the LHS of a sub, we can simplify the
477 // sub-expression to be just TheOther.
478 if (ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) {
479 if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0))
483 if (BO->getOpcode() == Instruction::Or) {
484 // Rebuild "or" as "add", because "or" may be invalid for the new
487 // For instance, given
488 // a | (b + 5) where a and b + 5 have no common bits,
489 // we can extract 5 as the constant offset.
491 // However, reusing the "or" in the new index would give us
493 // which does not equal a | (b + 5).
495 // Replacing the "or" with "add" is fine, because
496 // a | (b + 5) = a + (b + 5) = (a + b) + 5
497 return BinaryOperator::CreateAdd(BO->getOperand(0), BO->getOperand(1),
501 // We can reuse BO in this case, because the new expression shares the same
502 // instruction type and BO is used at most once.
503 assert(BO->getNumUses() <= 1 &&
504 "distributeExtsAndCloneChain clones each BinaryOperator in "
505 "UserChain, so no one should be used more than "
507 BO->setOperand(OpNo, NextInChain);
508 BO->setHasNoSignedWrap(false);
509 BO->setHasNoUnsignedWrap(false);
510 // Make sure it appears after all instructions we've inserted so far.
515 int64_t ConstantOffsetExtractor::Extract(Value *Idx, Value *&NewIdx,
516 const DataLayout *DL,
517 GetElementPtrInst *GEP) {
518 ConstantOffsetExtractor Extractor(DL, GEP);
519 // Find a non-zero constant offset first.
520 APInt ConstantOffset =
521 Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
523 if (ConstantOffset != 0) {
524 // Separates the constant offset from the GEP index.
525 NewIdx = Extractor.rebuildWithoutConstOffset();
527 return ConstantOffset.getSExtValue();
530 int64_t ConstantOffsetExtractor::Find(Value *Idx, const DataLayout *DL,
531 GetElementPtrInst *GEP) {
532 // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative.
533 return ConstantOffsetExtractor(DL, GEP)
534 .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
539 void ConstantOffsetExtractor::ComputeKnownBits(Value *V, APInt &KnownOne,
540 APInt &KnownZero) const {
541 IntegerType *IT = cast<IntegerType>(V->getType());
542 KnownOne = APInt(IT->getBitWidth(), 0);
543 KnownZero = APInt(IT->getBitWidth(), 0);
544 llvm::computeKnownBits(V, KnownZero, KnownOne, DL, 0);
547 bool ConstantOffsetExtractor::NoCommonBits(Value *LHS, Value *RHS) const {
548 assert(LHS->getType() == RHS->getType() &&
549 "LHS and RHS should have the same type");
550 APInt LHSKnownOne, LHSKnownZero, RHSKnownOne, RHSKnownZero;
551 ComputeKnownBits(LHS, LHSKnownOne, LHSKnownZero);
552 ComputeKnownBits(RHS, RHSKnownOne, RHSKnownZero);
553 return (LHSKnownZero | RHSKnownZero).isAllOnesValue();
556 int64_t SeparateConstOffsetFromGEP::accumulateByteOffset(
557 GetElementPtrInst *GEP, const DataLayout *DL, bool &NeedsExtraction) {
558 NeedsExtraction = false;
559 int64_t AccumulativeByteOffset = 0;
560 gep_type_iterator GTI = gep_type_begin(*GEP);
561 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
562 if (isa<SequentialType>(*GTI)) {
563 // Tries to extract a constant offset from this GEP index.
564 int64_t ConstantOffset =
565 ConstantOffsetExtractor::Find(GEP->getOperand(I), DL, GEP);
566 if (ConstantOffset != 0) {
567 NeedsExtraction = true;
568 // A GEP may have multiple indices. We accumulate the extracted
569 // constant offset to a byte offset, and later offset the remainder of
570 // the original GEP with this byte offset.
571 AccumulativeByteOffset +=
572 ConstantOffset * DL->getTypeAllocSize(GTI.getIndexedType());
576 return AccumulativeByteOffset;
579 bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) {
581 if (GEP->getType()->isVectorTy())
584 // The backend can already nicely handle the case where all indices are
586 if (GEP->hasAllConstantIndices())
589 bool Changed = false;
590 // Canonicalize array indices to pointer-size integers. This helps to simplify
591 // the logic of splitting a GEP. For example, if a + b is a pointer-size
593 // gep base, a + b = gep (gep base, a), b
594 // However, this equality may not hold if the size of a + b is smaller than
595 // the pointer size, because LLVM conceptually sign-extends GEP indices to
596 // pointer size before computing the address
597 // (http://llvm.org/docs/LangRef.html#id181).
599 // This canonicalization is very likely already done in clang and instcombine.
600 // Therefore, the program will probably remain the same.
602 // Verified in @i32_add in split-gep.ll
603 const DataLayout *DL = &getAnalysis<DataLayoutPass>().getDataLayout();
604 Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
605 gep_type_iterator GTI = gep_type_begin(*GEP);
606 for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end();
607 I != E; ++I, ++GTI) {
608 if (isa<SequentialType>(*GTI)) {
609 if ((*I)->getType() != IntPtrTy) {
610 *I = CastInst::CreateIntegerCast(*I, IntPtrTy, true, "idxprom", GEP);
616 bool NeedsExtraction;
617 int64_t AccumulativeByteOffset =
618 accumulateByteOffset(GEP, DL, NeedsExtraction);
620 if (!NeedsExtraction)
622 // Before really splitting the GEP, check whether the backend supports the
623 // addressing mode we are about to produce. If no, this splitting probably
624 // won't be beneficial.
625 TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
626 if (!TTI.isLegalAddressingMode(GEP->getType()->getElementType(),
627 /*BaseGV=*/nullptr, AccumulativeByteOffset,
628 /*HasBaseReg=*/true, /*Scale=*/0)) {
632 // Remove the constant offset in each GEP index. The resultant GEP computes
633 // the variadic base.
634 GTI = gep_type_begin(*GEP);
635 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
636 if (isa<SequentialType>(*GTI)) {
637 Value *NewIdx = nullptr;
638 // Tries to extract a constant offset from this GEP index.
639 int64_t ConstantOffset =
640 ConstantOffsetExtractor::Extract(GEP->getOperand(I), NewIdx, DL, GEP);
641 if (ConstantOffset != 0) {
642 assert(NewIdx != nullptr &&
643 "ConstantOffset != 0 implies NewIdx is set");
644 GEP->setOperand(I, NewIdx);
648 // Clear the inbounds attribute because the new index may be off-bound.
652 // addr = gep inbounds float* p, i64 b
654 // is transformed to:
656 // addr2 = gep float* p, i64 a
657 // addr = gep float* addr2, i64 5
659 // If a is -4, although the old index b is in bounds, the new index a is
660 // off-bound. http://llvm.org/docs/LangRef.html#id181 says "if the
661 // inbounds keyword is not present, the offsets are added to the base
662 // address with silently-wrapping two's complement arithmetic".
663 // Therefore, the final code will be a semantically equivalent.
665 // TODO(jingyue): do some range analysis to keep as many inbounds as
666 // possible. GEPs with inbounds are more friendly to alias analysis.
667 GEP->setIsInBounds(false);
669 // Offsets the base with the accumulative byte offset.
676 // %gep2 ; clone of %gep
677 // %new.gep = gep %gep2, <offset / sizeof(*%gep)>
678 // %gep ; will be removed
681 // => replace all uses of %gep with %new.gep and remove %gep
683 // %gep2 ; clone of %gep
684 // %new.gep = gep %gep2, <offset / sizeof(*%gep)>
687 // If AccumulativeByteOffset is not a multiple of sizeof(*%gep), we emit an
688 // uglygep (http://llvm.org/docs/GetElementPtr.html#what-s-an-uglygep):
689 // bitcast %gep2 to i8*, add the offset, and bitcast the result back to the
692 // %gep2 ; clone of %gep
693 // %0 = bitcast %gep2 to i8*
694 // %uglygep = gep %0, <offset>
695 // %new.gep = bitcast %uglygep to <type of %gep>
697 Instruction *NewGEP = GEP->clone();
698 NewGEP->insertBefore(GEP);
700 uint64_t ElementTypeSizeOfGEP =
701 DL->getTypeAllocSize(GEP->getType()->getElementType());
702 if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) {
703 // Very likely. As long as %gep is natually aligned, the byte offset we
704 // extracted should be a multiple of sizeof(*%gep).
705 // Per ANSI C standard, signed / unsigned = unsigned. Therefore, we
706 // cast ElementTypeSizeOfGEP to signed.
708 AccumulativeByteOffset / static_cast<int64_t>(ElementTypeSizeOfGEP);
709 NewGEP = GetElementPtrInst::Create(
710 NewGEP, ConstantInt::get(IntPtrTy, Index, true), GEP->getName(), GEP);
712 // Unlikely but possible. For example,
720 // Suppose the gep before extraction is &s[i + 1].b[j + 3]. After
721 // extraction, it becomes &s[i].b[j] and AccumulativeByteOffset is
722 // sizeof(S) + 3 * sizeof(int64) = 100, which is not a multiple of
725 // Emit an uglygep in this case.
726 Type *I8PtrTy = Type::getInt8PtrTy(GEP->getContext(),
727 GEP->getPointerAddressSpace());
728 NewGEP = new BitCastInst(NewGEP, I8PtrTy, "", GEP);
729 NewGEP = GetElementPtrInst::Create(
730 NewGEP, ConstantInt::get(IntPtrTy, AccumulativeByteOffset, true),
732 if (GEP->getType() != I8PtrTy)
733 NewGEP = new BitCastInst(NewGEP, GEP->getType(), GEP->getName(), GEP);
736 GEP->replaceAllUsesWith(NewGEP);
737 GEP->eraseFromParent();
742 bool SeparateConstOffsetFromGEP::runOnFunction(Function &F) {
743 if (DisableSeparateConstOffsetFromGEP)
746 bool Changed = false;
747 for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B) {
748 for (BasicBlock::iterator I = B->begin(), IE = B->end(); I != IE; ) {
749 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++)) {
750 Changed |= splitGEP(GEP);
752 // No need to split GEP ConstantExprs because all its indices are constant