[SeparateConstOffsetFromGEPPass] Added optional modification strategy

[eklepilkina]

Summary

This modification strategy tries to understand which GEP instrucions is profitable to modify for register pressure decreasing.

[anton-afanasyev]

Please rebase against precommited tests.

[eklepilkina]

Rebased against precommited tests

[reames]

At least for me, I need some context to be able to review this. What is the case which this improves in terms of codegen? And how common are such patterns? Keep in mind, I'm not terribly familiar with the pass here, so this may be pretty basic explanation. Do you have a bug with examples or analyze that lead to this change?

[eklepilkina]

Sorry, I had to provide the context at the beginning.

Now clang for RISC-V doesn't use offset addressing in generated assembly. Example from Dhrystone

 addiw   a0, s1, 5
 slli    a1, a0, 0x2
 add     a2, s4, a1
 sw      s2, 0(a2)
 addiw   a3, s1, 6
 slli    a3, a3, 0x2
 add     a3, a3, s4
 sw      s2, 0(a3)
 addiw   a3, s1, 35
 slli    a3, a3, 0x2
add     a3, a3, s4
sw      a0, 0(a3)

It's inefficient because we can use offsets.
Adding this pass allows to generate the next code

    addiw   a4, a2, 5
    slli    a5, a2, 2
    add a0, a0, a5
    sw  a3, 20(a0)
    sw  a3, 24(a0)
    sw  a4, 140(a0)
...

SeparateConstOffsetFromGEPPass is used to solve this problem in targets with limited addressing modes.
The changes inside pass was made because modification of all GEPs isn't profitable, seems that we need at least 2 GEPs and one value that was used for index that can be removed after modification. Otherwise we don't decrease register pressure.

[craig.topper]

This should be two patches, one changing the pass and one enabling for RISC-V.

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

171 ↗

(On Diff #436758)

Can we add a command line option to control this like AArch64 and PowerPC have?

llvm/test/Transforms/SeparateConstOffsetFromGEP/RISCV/split-gep.ll

1 ↗

(On Diff #436758)

This test doesn't exist in the repo. Where is the patch that adds it?

[eklepilkina]

llvm/test/Transforms/SeparateConstOffsetFromGEP/RISCV/split-gep.ll

1 ↗

(On Diff #436758)

I was told in the first comment to rebase on precommited tests. These tests are added as precommited in separate commit. Should I commit them?

[craig.topper]

llvm/test/Transforms/SeparateConstOffsetFromGEP/RISCV/split-gep.ll

1 ↗

(On Diff #436758)

Why is the script NOTE: Assertions have been autogenerated by utils/update_test_checks.py not in the pre-committed version?

[eklepilkina]

This should be two patches, one changing the pass and one enabling for RISC-V.

As far as I want to turn pass with enabled strategy, should I wait approve and merge of the accepting strategy and only after this create the second review? Or create series of patches as mentionedin documentation https://llvm.org/docs/Phabricator.html#creating-a-patch-series?

[craig.topper]

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

365

I think there you should be a std::move on PreviousIndices

368

rhs -> RHS

955–959

PossibleBase.size() == 0 -> PossibleBases.empty()

[craig.topper]

In D127727#3582087, @eklepilkina wrote:

This should be two patches, one changing the pass and one enabling for RISC-V.

As far as I want to turn pass with enabled strategy, should I wait approve and merge of the accepting strategy and only after this create the second review? Or create series of patches as mentionedin documentation https://llvm.org/docs/Phabricator.html#creating-a-patch-series?

You should create a series of patches.

[eklepilkina]

Separate part with pass modification

[eklepilkina]

• [SeparateConstOffsetFromGEP] Fix comparator for map with GEP bases

[eklepilkina]

Refactoring

[eklepilkina]

Fix review

[eklepilkina]

Ping

[eklepilkina]

• [SeparateConstOffsetFromGEP] Fix ignoring condition

[eklepilkina]

Gentle ping

[mkazantsev]

Some nits from me. If I may, some advice if you want to make progress here.

First, it seems that some pieces of this patch can be split out as seprate NFC refactorings. If so, please do. It should greatly reduce the code to look at, and smaller patches are generally easier to comprehend and review.

Second, the motivation of this patch is obscure. The structures and algorithms that you are using are not obvious. This either needs a detailed explanation in comments, or maybe incremental approach, when each step is understandable.

Third, the benefit isn't obvious either. In your tests, new IR is bigger than the old IR. This is not necessarily bad, but it requires explanation. If you have some particular scenario where the resulting assembly is better with this change, then it makes sense to provide an LLC test which shows it.

Fourth, this patch claims to improve register pressure. At the same time, it is done in a middle-end pass, which means its impact on register pressure on different platforms might be different. Was it actually tested on other platforms than RICSV? Or you think that the algorithm should be profitable regardless of the platform? Can I see any benefit from this patch in X86 for example?

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

203

Can this go as a separate NFC?

262–274

Please commit this reformatting separately.

271

\p CheckProfitability ?..

357

This requires more explanation. I could not figure what are indices, which of them is being optimized, and what is precedence in this context. Maybe write a detailed comment on what's going on here and what does this structure represent?

434

Canonize -> Canonicalize

435

I guess it should be "Returns true if a change was made, false otherwise".

531

Maybe rename InstructionsToTransform -> GEPsToTransform?

1066–1067

Pls commit separately if it is needed.

1111

Rename as separate NFC?

1357

To me, this code structure looks counter-intuitive. Why do we print "Try to split GEP "... only when we check profitability, and do it silently when we don't? If possible, please restructure it like

if (CheckProfitability) {
  // Do all required profitability checks
}
// Do common transform logic uniformly

I'm not sure if it's possible here because of this post-processing. If not, then the transform part should be unified somehow else.

1364

More natural way would be

if (!CurrentChanged)
  continue;
for ...

1365

The complexity of this is SortedInstructionsList.size() * SortedInstructionsList.size() * sum(SortedInstructionsList[J]) if I'm reading this correctly. Looks very expensive. Is there a cheaper way of doing this? Imagine you have 10k instructions on your list. It will just be stuck forever.

llvm/test/Transforms/SeparateConstOffsetFromGEP/RISCV/split-gep.ll

86 ↗

(On Diff #445498)

Why is it a better code tha the old one?

286 ↗

(On Diff #445498)

This code is bigger than it used to be. Can you explain why is it better?

[eklepilkina]

Can I see any benefit from this patch in X86 for example?

This pass was written for targets with limited addressing mode, so it isn't added to X86 pipeline. It's used under the flag on Aarch64 and on RISCV we also suggest to turn off it by default, but this patch helps to make these optimization be useful more often, and remove some regressions that was found if turn these pass on on all test-suite. I'll provide test-suite results on Aarch64 platform with turned this pass with and without this patch. But yes, the main measurements were made for RISCV.

And if you mean that these changes should be done later in pipeline, there is the problem with the current instruction selection that can work only with one BB, so CodeGenPrepare pass need to sunk such GEPs with const to generate adddressing by offset, so I believe this pass was created as middle-end part.

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

1111

I don't really like the idea to rename in separate NFC patch, because renaming is connected with changes that were made and the old name wasn't suitable any more

1357

I understand your concerns, but I don't see a good solution here, because I don't want to make the unneeded actions for original version without checking profitability.

1365

Imagine you have 10k instructions on your list

I amn't sure we should optimize this case, because it's mostly impossible, because this list is always quite small. I'll think some more, but I amn't sure that the optimization here is more important than readability.

llvm/test/Transforms/SeparateConstOffsetFromGEP/RISCV/split-gep.ll

86 ↗

(On Diff #445498)

In assembly we use one more register to save the result of new generated GEP instruction, bt we have no profit because registers that are used by adds are also needed as far as these values are used in other instructions.

286 ↗

(On Diff #445498)

This code is bigger on IR, and it's so becuase of repeating sext opertaions, but sext isn't so critical in assembly, at the same time pass generates 2 new GEP instructions that are used as base and we need registers for them

[eklepilkina]

• [NFC][SeparateConstOffsetFromGEP] Small refactoring and reformatting
• [SeparateConstOffsetFromGEPPass] Added optional modification strategy
• Review fixes (part 1)

[eklepilkina]

• [SeparateConstOffsetFromGEPPass] Added optional modification strategy
• Review fixes (part 1)

[mkazantsev]

Found some bugs, some style proposals as well. The general point still holds. If the patch is purposed to reduce register pressure on some platform, please provide a test which shows that this actually happens. This can only be shown on a llc test.

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

247

This comment is obsolete now, Extract does not have these new parameters.

272

And if V is not binop, should it change?

359

This is usually called BasePointer in other parts of optimizer.

360

Shouldn't %b also be a part of it? Or where does it go?
Maybe more elaborate example on how there can be more than one previous index?

385

APInt? Just to make sure this doesn't overflow.

386

Naturaly I'd expect this to be SmallVector<const ConstantInt *>, but the code below suggests there might not be constants. Misleading name?

541

Use DenseMapInfo<Value *>::getTombstoneKey() and same above

545

Why PreviousIndices size but not contents?

694

No { }

695

undef and poison are constants but not ConstantInt. Are you OK with them?

1365

"Mostly impossible" means "possible". We generally bail out on non-linear algorithms with some thresholds. This could also be the case here.

llvm/test/Transforms/SeparateConstOffsetFromGEP/RISCV/split-gep.ll

286 ↗

(On Diff #445498)

Then please provide a llc test that demonstrates a positive change.

The fact that "sext isn't so critical" is a way not obvious to me. Filling the upper part of the registry may sometimes be an extra operation.

[eklepilkina]

Sorry for delay. Looked more on different benchmarks from test-suite during searching a good test case. There are such cases. But a deep exploration shows that SeparateConstOffsetFromGEP pass isn't the main reason, it produces better IR, but in some cases later passes can make it worse and cause worse asssembly code. So hacks I have made in the current pass as workarounds for these particular cases don't seem to be the proper decision. As far as this pass isn't the main reason of regressions we got, I decided to abandon this review.

Thank you very much for review and sorry to bother you.

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

 #include <cassert>
 #include <cstdint>
 #include <map>
 #include <string>
 
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "separate-const-offset-from-gep"
 
 static cl::opt<bool> DisableSeparateConstOffsetFromGEP(
     "disable-separate-const-offset-from-gep", cl::init(false),
     cl::desc("Do not separate the constant offset from a GEP instruction"),
     cl::Hidden);
 
 // Setting this flag may emit false positives when the input module already
 // contains dead instructions. Therefore, we set it only in unit tests that are
public:
   /// \p GEP The given GEP
   /// \p UserChainTail Outputs the tail of UserChain so that we can
   ///                  garbage-collect unused instructions in UserChain.
   static Value *Extract(Value *Idx, GetElementPtrInst *GEP,
                         User *&UserChainTail, const DominatorTree *DT);
 
   /// Looks for a constant offset from the given GEP index without extracting
   /// it. It returns the numeric value of the extracted constant offset (0 if
   /// failed). The meaning of the arguments are the same as Extract.
   static int64_t Find(Value *Idx, GetElementPtrInst *GEP,
-                      const DominatorTree *DT, Value *&NonConstantBaseValue);
+                      const DominatorTree *DT, Value *&NonConstantBaseValue,
+                      bool CheckProfitability = false);
 
 private:
   ConstantOffsetExtractor(Instruction *InsertionPt, const DominatorTree *DT)
       : IP(InsertionPt), DL(InsertionPt->getModule()->getDataLayout()), DT(DT) {
   }
 
   /// Searches the expression that computes V for a non-zero constant C s.t.
   /// V can be reassociated into the form V' + C. If the searching is
   /// successful, returns C and update UserChain as a def-use chain from C to V;
   /// otherwise, UserChain is empty.
   ///
   /// \p V                    The given expression
   /// \p SignExtended         Whether V will be sign-extended in the computation
   ///                         of the GEP index
   /// \p ZeroExtended         Whether V will be zero-extended in the computation
   ///                         of the GEP index
   /// \p NonNegative          Whether V is guaranteed to be non-negative. For
   ///                         example, an index of an inbounds GEP is guaranteed
   ///                         to be non-negative. Levaraging this, we can better
   ///                         split inbounds GEPs.
   /// \p NonConstantBaseValue The second non-constant operand if V is binary
   ///                         operator.
   APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative,
-             Value *&NonConstantBaseValue);
+             Value *&NonConstantBaseValue, bool CheckProfitability = false);
 
   /// A helper function to look into both operands of a binary operator.
   APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended,
-                            bool ZeroExtended, Value *&NonConstantBaseValue);
+                            bool ZeroExtended, Value *&NonConstantBaseValue,
+                            bool CheckProfitability = false);
 
   /// After finding the constant offset C from the GEP index I, we build a new
   /// index I' s.t. I' + C = I. This function builds and returns the new
   /// index I' according to UserChain produced by function "find".
   ///
   /// The building conceptually takes two steps:
   /// 1) iteratively distribute s/zext towards the leaves of the expression tree
   /// that computes I
private:
   const DominatorTree *DT;
 };
 
 /// GEPBaseInfo - structure contains information about possible common base for
 /// GEP instructions.
 struct GEPBaseInfo {
   /// Pointer used in GEP instruction.
   const Value *GEPPointer;
   /// Indexes that precede index that can be optimized.
   SmallVector<const Value *> PreviousIndices;
   /// Non constant value that will be used in new base GEP.
   const Value *NonConstantBaseValue;
 
   GEPBaseInfo(const Value *GEPPointer,
               SmallVector<const Value *> PreviousIndices,
               const Value *NonConstantBaseValue)
       : GEPPointer(GEPPointer), PreviousIndices(PreviousIndices),
         NonConstantBaseValue(NonConstantBaseValue) {}
 };
 
 /// GEPInfo - structure contains basic information about GEP instruction
 /// needed for their modification.
 struct GEPInfo {
   GetElementPtrInst *GEPInstruction;
   int64_t AccumulativeByteOffset;
   SmallVector<const Value *> ConstantIndices;
 
   GEPInfo(GetElementPtrInst *GEPInstruction, int64_t AccumulativeByteOffset,
           SmallVector<const Value *> &&Indices)
       : GEPInstruction(GEPInstruction),
         AccumulativeByteOffset(AccumulativeByteOffset),
         ConstantIndices(Indices) {}
 };
 
 /// A pass that tries to split every GEP in the function into a variadic
 /// base and a constant offset. It is a FunctionPass because searching for the
 /// constant offset may inspect other basic blocks.
 class SeparateConstOffsetFromGEPLegacyPass : public FunctionPass {
 public:
   static char ID;
 
   SeparateConstOffsetFromGEPLegacyPass(bool LowerGEP = false,
                                        bool CheckProfitability = false)
       : FunctionPass(ID), LowerGEP(LowerGEP),
         CheckProfitability(CheckProfitability) {
     initializeSeparateConstOffsetFromGEPLegacyPassPass(
public:
 
   bool run(Function &F);
 
 private:
   /// Tries to split the given GEP into a variadic base and a constant offset,
   /// and returns true if the splitting succeeds.
   bool splitGEP(GetElementPtrInst *GEP, int64_t AccumulativeByteOffset);
 
   /// Canonize GEP if needed and collect information to decide if GEP
   /// modification is useful
   bool preprocessGEP(GetElementPtrInst *GEP);
 
   /// Lower a GEP with multiple indices into multiple GEPs with a single index.
   /// Function splitGEP already split the original GEP into a variadic part and
   /// a constant offset (i.e., AccumulativeByteOffset). This function lowers the
   /// variadic part into a set of GEPs with a single index and applies
   /// AccumulativeByteOffset to it.
   /// \p Variadic                  The variadic part of the original GEP.
private:
   /// Check the possible profit of optimization to reduce register pressure
   /// or modify all possible GEPs.
   bool CheckProfitability;
 
   DenseMap<const SCEV *, SmallVector<Instruction *, 2>> DominatingAdds;
   DenseMap<const SCEV *, SmallVector<Instruction *, 2>> DominatingSubs;
 
   /// GEP instructions chosen for transformation
   DenseMap<GEPBaseInfo, SmallVector<GEPInfo>> InstructionsToTransform;
 };
 
 } // end anonymous namespace
 
 template <> struct llvm::DenseMapInfo<GEPBaseInfo> {
   static inline GEPBaseInfo getEmptyKey() {
     return GEPBaseInfo(nullptr, SmallVector<const Value *>(), nullptr);
   }
   static inline GEPBaseInfo getTombstoneKey() {
     return GEPBaseInfo((Value *)(-1), SmallVector<const Value *>(),
                        (Value *)(-1));
   }
   static unsigned getHashValue(const GEPBaseInfo &Val) {
     return llvm::hash_combine(Val.GEPPointer, Val.PreviousIndices.size(),
                               Val.NonConstantBaseValue);
   }
   static bool isEqual(const GEPBaseInfo &LHS, const GEPBaseInfo &RHS) {
     return LHS.GEPPointer == RHS.GEPPointer &&
            LHS.NonConstantBaseValue == RHS.NonConstantBaseValue &&
            LHS.PreviousIndices == RHS.PreviousIndices;
   }
 };
if (SignExtended && !BO->hasNoSignedWrap())
       return false;
     if (ZeroExtended && !BO->hasNoUnsignedWrap())
       return false;
   }
 
   return true;
 }
 
-APInt ConstantOffsetExtractor::findInEitherOperand(
-    BinaryOperator *BO, bool SignExtended, bool ZeroExtended,
-    Value *&NonConstantBaseValue) {
+APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,
+                                                   bool SignExtended,
+                                                   bool ZeroExtended,
+                                                   Value *&NonConstantBaseValue,
+                                                   bool CheckProfitability) {
   // Save off the current height of the chain, in case we need to restore it.
   size_t ChainLength = UserChain.size();
 
   // BO being non-negative does not shed light on whether its operands are
   // non-negative. Clear the NonNegative flag here.
-  APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended,
-                              /* NonNegative */ false, NonConstantBaseValue);
+  APInt ConstantOffset =
+      find(BO->getOperand(0), SignExtended, ZeroExtended,
+           /* NonNegative */ false, NonConstantBaseValue, CheckProfitability);
+
+  // Only sub and add instructions don't need adding extra instructions.
+  if (CheckProfitability && (BO->getOpcode() != Instruction::Sub ||
+                             BO->getOpcode() != Instruction::Add)) {
+    LLVM_DEBUG(dbgs() << "Reset ConstantOffset\n");
+    NonConstantBaseValue = nullptr;
+    ConstantOffset = 0;
+    UserChain.resize(ChainLength);
+    return ConstantOffset;
+  }
+
   // If we found a constant offset in the left operand, stop and return that.
   // This shortcut might cause us to miss opportunities of combining the
   // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9.
   // However, such cases are probably already handled by -instcombine,
   // given this pass runs after the standard optimizations.
   if (ConstantOffset != 0) {
     if (!isa<ConstantInt>(BO->getOperand(1))) {
       NonConstantBaseValue = BO->getOperand(1);
     }
     return ConstantOffset;
   }
 
   // Reset the chain back to where it was when we started exploring this node,
   // since visiting the LHS didn't pan out.
   UserChain.resize(ChainLength);
 
-  ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended,
-                        /* NonNegative */ false, NonConstantBaseValue);
+  ConstantOffset =
+      find(BO->getOperand(1), SignExtended, ZeroExtended,
+           /* NonNegative */ false, NonConstantBaseValue, CheckProfitability);
   // If U is a sub operator, negate the constant offset found in the right
   // operand.
   if (BO->getOpcode() == Instruction::Sub)
     ConstantOffset = -ConstantOffset;
 
   // If RHS wasn't a suitable candidate either, reset the chain again.
   if (ConstantOffset == 0)
     UserChain.resize(ChainLength);
 
   if (!isa<ConstantInt>(BO->getOperand(0))) {
     NonConstantBaseValue = BO->getOperand(0);
   }
 
   return ConstantOffset;
 }
 
 APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended,
                                     bool ZeroExtended, bool NonNegative,
-                                    Value *&NonConstantBaseValue) {
+                                    Value *&NonConstantBaseValue,
+                                    bool CheckProfitability) {
   // TODO(jingyue): We could trace into integer/pointer casts, such as
   // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only
   // integers because it gives good enough results for our benchmarks.
   unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
 
   // We cannot do much with Values that are not a User, such as an Argument.
   User *U = dyn_cast<User>(V);
   if (U == nullptr) return APInt(BitWidth, 0);
 
   APInt ConstantOffset(BitWidth, 0);
   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     // Hooray, we found it!
     ConstantOffset = CI->getValue();
   } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) {
     // Trace into subexpressions for more hoisting opportunities.
     if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative))
-      ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended,
-                                           NonConstantBaseValue);
+      ConstantOffset =
+          findInEitherOperand(BO, SignExtended, ZeroExtended,
+                              NonConstantBaseValue, CheckProfitability);
   } else if (isa<TruncInst>(V)) {
     ConstantOffset = find(U->getOperand(0), SignExtended, ZeroExtended,
-                          NonNegative, NonConstantBaseValue)
+                          NonNegative, NonConstantBaseValue, CheckProfitability)
                          .trunc(BitWidth);
   } else if (isa<SExtInst>(V)) {
-    ConstantOffset = find(U->getOperand(0), /* SignExtended */ true,
-                          ZeroExtended, NonNegative, NonConstantBaseValue)
-                         .sext(BitWidth);
+    ConstantOffset =
+        find(U->getOperand(0), /* SignExtended */ true, ZeroExtended,
+             NonNegative, NonConstantBaseValue, CheckProfitability)
   } else if (isa<ZExtInst>(V)) {
     // As an optimization, we can clear the SignExtended flag because
     // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll.
     //
     // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0.
     ConstantOffset = find(U->getOperand(0), /* SignExtended */ false,
                           /* ZeroExtended */ true, /* NonNegative */ false,
-                          NonConstantBaseValue)
+                          NonConstantBaseValue, CheckProfitability)
                          .zext(BitWidth);
   }
 
   // If we found a non-zero constant offset, add it to the path for
   // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't
   // help this optimization.
   if (ConstantOffset != 0)
     UserChain.push_back(U);
Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP,
   // Separates the constant offset from the GEP index.
   Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset();
   UserChainTail = Extractor.UserChain.back();
   return IdxWithoutConstOffset;
 }
 
 int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP,
                                       const DominatorTree *DT,
-                                      Value *&NonConstantBaseValue) {
+                                      Value *&NonConstantBaseValue,
+                                      bool CheckProfitability) {
   // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative.
   return ConstantOffsetExtractor(GEP, DT)
       .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
-            GEP->isInBounds(), NonConstantBaseValue)
+            GEP->isInBounds(), NonConstantBaseValue, CheckProfitability)
       .getSExtValue();
 }
 
 bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToPointerSize(
     GetElementPtrInst *GEP) {
   bool Changed = false;
   Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
   gep_type_iterator GTI = gep_type_begin(*GEP);
void SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP) {
   SmallVector<const Value *> ConstantIndices;
   SmallVector<GEPBaseInfo, 2> PossibleBases;
 
   for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
     Value *NonConstantBaseValue = nullptr;
     if (GTI.isSequential()) {
       // Tries to extract a constant offset from this GEP index.
       int64_t ConstantOffset = ConstantOffsetExtractor::Find(
-          GEP->getOperand(I), GEP, DT, NonConstantBaseValue);
+          GEP->getOperand(I), GEP, DT, NonConstantBaseValue,
+          CheckProfitability);
       if (ConstantOffset != 0) {
         if (CheckProfitability || PossibleBases.empty()) {
           PossibleBases.emplace_back(
               GEP->getPointerOperand(),
               SmallVector<const Value *, 4>(GEP->idx_begin(),
                                             GEP->idx_begin() + I - 1),
               NonConstantBaseValue);
         }
 
         // A GEP may have multiple indices.  We accumulate the extracted
         // constant offset to a byte offset, and later offset the remainder of
         // the original GEP with this byte offset.
         AccumulativeByteOffset +=
             ConstantOffset * DL->getTypeAllocSize(GTI.getIndexedType());
         ConstantIndices.push_back(GEP->getOperand(I));
       }
     } else if (LowerGEP) {
       StructType *StTy = GTI.getStructType();
       uint64_t Field = cast<ConstantInt>(GEP->getOperand(I))->getZExtValue();
       // Skip field 0 as the offset is always 0.
       if (Field != 0) {
         if (CheckProfitability || PossibleBases.empty()) {
           PossibleBases.emplace_back(GEP->getPointerOperand(),
                                      SmallVector<const Value *>(),
                                      NonConstantBaseValue);
         }
         AccumulativeByteOffset +=
             DL->getStructLayout(StTy)->getElementOffset(Field);
       }
     }
   }
   TargetTransformInfo &TTI = GetTTI(*GEP->getFunction());
 
   // If LowerGEP is disabled, before really splitting the GEP, check whether the
void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs(
 
   if (ResultPtr->getType() != Variadic->getType())
     ResultPtr = Builder.CreateBitCast(ResultPtr, Variadic->getType());
 
   Variadic->replaceAllUsesWith(ResultPtr);
   Variadic->eraseFromParent();
 }
 
 void SeparateConstOffsetFromGEP::lowerToArithmetics(
     GetElementPtrInst *Variadic, int64_t AccumulativeByteOffset) {
   IRBuilder<> Builder(Variadic);
   Type *IntPtrTy = DL->getIntPtrType(Variadic->getType());
 
   Value *ResultPtr = Builder.CreatePtrToInt(Variadic->getOperand(0), IntPtrTy);
   gep_type_iterator GTI = gep_type_begin(*Variadic);
   // Create ADD/SHL/MUL arithmetic operations for each sequential indices. We
   // don't create arithmetics for structure indices, as they are accumulated
   // in the constant offset index.
ResultPtr = Builder.CreateAdd(
         ResultPtr, ConstantInt::get(IntPtrTy, AccumulativeByteOffset));
   }
 
   ResultPtr = Builder.CreateIntToPtr(ResultPtr, Variadic->getType());
   Variadic->replaceAllUsesWith(ResultPtr);
   Variadic->eraseFromParent();
 }
 
 bool SeparateConstOffsetFromGEP::preprocessGEP(GetElementPtrInst *GEP) {
   // Skip vector GEPs.
   if (GEP->getType()->isVectorTy())
     return false;
 
   // The backend can already nicely handle the case where all indices are
   // constant.
   if (GEP->hasAllConstantIndices())
     return false;
if (!CheckProfitability) {
       });
 
       // Optimize all chosen GEPs
       for (unsigned I = 0; I < SortedInstructionsList.size(); I++) {
         auto DetailedInfoList = SortedInstructionsList[I].first;
         if (DetailedInfoList.size() > 1 &&
             any_of(DetailedInfoList, OnlyUsedInGEP)) {
           for (const auto &GEPInfo : DetailedInfoList) {
             LLVM_DEBUG(dbgs() << "Try to split GEP " << *GEPInfo.GEPInstruction
                               << "\n");
             bool CurrentChanged = splitGEP(GEPInfo.GEPInstruction,
                                            GEPInfo.AccumulativeByteOffset);
             Changed |= CurrentChanged;
             // If GEP is already optimized remove it from lists connected with
             // other bases.
             for (unsigned J = I + 1;
                  J < SortedInstructionsList.size() && CurrentChanged; J++) {
               auto RemoveIt = remove_if(SortedInstructionsList[J].first,
                                         [&GEPInfo](const struct GEPInfo &Info) {
                                           return Info.GEPInstruction ==
                                                  GEPInfo.GEPInstruction;
                                         });
               SortedInstructionsList[J].first.erase(
                   RemoveIt, SortedInstructionsList[J].first.end());
             }