text: //===- SeparateConstOffsetFromGEP.cpp -------------------------------------===//
  //
  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  // See https://llvm.org/LICENSE.txt for license information.
  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  //
  //===----------------------------------------------------------------------===//
  //
  // Loop unrolling may create many similar GEPs for array accesses.
  // e.g., a 2-level loop
  //
  // float a[32][32]; // global variable
  //
  // for (int i = 0; i < 2; ++i) {
  //   for (int j = 0; j < 2; ++j) {
  //     ...
  //     ... = a[x + i][y + j];
  //     ...
  //   }
  // }
  //
  // will probably be unrolled to:
  //
  // gep %a, 0, %x, %y; load
  // gep %a, 0, %x, %y + 1; load
  // gep %a, 0, %x + 1, %y; load
  // gep %a, 0, %x + 1, %y + 1; load
  //
  // LLVM's GVN does not use partial redundancy elimination yet, and is thus
  // unable to reuse (gep %a, 0, %x, %y). As a result, this misoptimization incurs
  // significant slowdown in targets with limited addressing modes. For instance,
  // because the PTX target does not support the reg+reg addressing mode, the
  // NVPTX backend emits PTX code that literally computes the pointer address of
  // each GEP, wasting tons of registers. It emits the following PTX for the
  // first load and similar PTX for other loads.
  //
  // mov.u32         %r1, %x;
  // mov.u32         %r2, %y;
  // mul.wide.u32    %rl2, %r1, 128;
  // mov.u64         %rl3, a;
  // add.s64         %rl4, %rl3, %rl2;
  // mul.wide.u32    %rl5, %r2, 4;
  // add.s64         %rl6, %rl4, %rl5;
  // ld.global.f32   %f1, [%rl6];
  //
  // To reduce the register pressure, the optimization implemented in this file
  // merges the common part of a group of GEPs, so we can compute each pointer
  // address by adding a simple offset to the common part, saving many registers.
  //
  // It works by splitting each GEP into a variadic base and a constant offset.
  // The variadic base can be computed once and reused by multiple GEPs, and the
  // constant offsets can be nicely folded into the reg+immediate addressing mode
  // (supported by most targets) without using any extra register.
  //
  // For instance, we transform the four GEPs and four loads in the above example
  // into:
  //
  // base = gep a, 0, x, y
  // load base
  // laod base + 1  * sizeof(float)
  // load base + 32 * sizeof(float)
  // load base + 33 * sizeof(float)
  //
  // Given the transformed IR, a backend that supports the reg+immediate
  // addressing mode can easily fold the pointer arithmetics into the loads. For
  // example, the NVPTX backend can easily fold the pointer arithmetics into the
  // ld.global.f32 instructions, and the resultant PTX uses much fewer registers.
  //
  // mov.u32         %r1, %tid.x;
  // mov.u32         %r2, %tid.y;
  // mul.wide.u32    %rl2, %r1, 128;
  // mov.u64         %rl3, a;
  // add.s64         %rl4, %rl3, %rl2;
  // mul.wide.u32    %rl5, %r2, 4;
  // add.s64         %rl6, %rl4, %rl5;
  // ld.global.f32   %f1, [%rl6]; // so far the same as unoptimized PTX
  // ld.global.f32   %f2, [%rl6+4]; // much better
  // ld.global.f32   %f3, [%rl6+128]; // much better
  // ld.global.f32   %f4, [%rl6+132]; // much better
  //
  // Another improvement enabled by the LowerGEP flag is to lower a GEP with
  // multiple indices to either multiple GEPs with a single index or arithmetic
  // operations (depending on whether the target uses alias analysis in codegen).
  // Such transformation can have following benefits:
  // (1) It can always extract constants in the indices of structure type.
  // (2) After such Lowering, there are more optimization opportunities such as
  //     CSE, LICM and CGP.
  //
  // E.g. The following GEPs have multiple indices:
  //  BB1:
  //    %p = getelementptr [10 x %struct]* %ptr, i64 %i, i64 %j1, i32 3
  //    load %p
  //    ...
  //  BB2:
  //    %p2 = getelementptr [10 x %struct]* %ptr, i64 %i, i64 %j1, i32 2
  //    load %p2
  //    ...
  //
  // We can not do CSE to the common part related to index "i64 %i". Lowering
  // GEPs can achieve such goals.
  // If the target does not use alias analysis in codegen, this pass will
  // lower a GEP with multiple indices into arithmetic operations:
  //  BB1:
  //    %1 = ptrtoint [10 x %struct]* %ptr to i64    ; CSE opportunity
  //    %2 = mul i64 %i, length_of_10xstruct         ; CSE opportunity
  //    %3 = add i64 %1, %2                          ; CSE opportunity
  //    %4 = mul i64 %j1, length_of_struct
  //    %5 = add i64 %3, %4
  //    %6 = add i64 %3, struct_field_3              ; Constant offset
  //    %p = inttoptr i64 %6 to i32*
  //    load %p
  //    ...
  //  BB2:
  //    %7 = ptrtoint [10 x %struct]* %ptr to i64    ; CSE opportunity
  //    %8 = mul i64 %i, length_of_10xstruct         ; CSE opportunity
  //    %9 = add i64 %7, %8                          ; CSE opportunity
  //    %10 = mul i64 %j2, length_of_struct
  //    %11 = add i64 %9, %10
  //    %12 = add i64 %11, struct_field_2            ; Constant offset
  //    %p = inttoptr i64 %12 to i32*
  //    load %p2
  //    ...
  //
  // If the target uses alias analysis in codegen, this pass will lower a GEP
  // with multiple indices into multiple GEPs with a single index:
  //  BB1:
  //    %1 = bitcast [10 x %struct]* %ptr to i8*     ; CSE opportunity
  //    %2 = mul i64 %i, length_of_10xstruct         ; CSE opportunity
  //    %3 = getelementptr i8* %1, i64 %2            ; CSE opportunity
  //    %4 = mul i64 %j1, length_of_struct
  //    %5 = getelementptr i8* %3, i64 %4
  //    %6 = getelementptr i8* %5, struct_field_3    ; Constant offset
  //    %p = bitcast i8* %6 to i32*
  //    load %p
  //    ...
  //  BB2:
  //    %7 = bitcast [10 x %struct]* %ptr to i8*     ; CSE opportunity
  //    %8 = mul i64 %i, length_of_10xstruct         ; CSE opportunity
  //    %9 = getelementptr i8* %7, i64 %8            ; CSE opportunity
  //    %10 = mul i64 %j2, length_of_struct
  //    %11 = getelementptr i8* %9, i64 %10
  //    %12 = getelementptr i8* %11, struct_field_2  ; Constant offset
  //    %p2 = bitcast i8* %12 to i32*
  //    load %p2
  //    ...
  //
  // Lowering GEPs can also benefit other passes such as LICM and CGP.
  // LICM (Loop Invariant Code Motion) can not hoist/sink a GEP of multiple
  // indices if one of the index is variant. If we lower such GEP into invariant
  // parts and variant parts, LICM can hoist/sink those invariant parts.
  // CGP (CodeGen Prepare) tries to sink address calculations that match the
  // target's addressing modes. A GEP with multiple indices may not match and will
  // not be sunk. If we lower such GEP into smaller parts, CGP may sink some of
  // them. So we end up with a better addressing mode.
  //
  //===----------------------------------------------------------------------===//
  
  #include "llvm/Transforms/Scalar/SeparateConstOffsetFromGEP.h"
  #include "llvm/ADT/APInt.h"
  #include "llvm/ADT/DenseMap.h"
  #include "llvm/ADT/DepthFirstIterator.h"
  #include "llvm/ADT/SmallVector.h"
  #include "llvm/Analysis/LoopInfo.h"
  #include "llvm/Analysis/MemoryBuiltins.h"
  #include "llvm/Analysis/ScalarEvolution.h"
  #include "llvm/Analysis/TargetLibraryInfo.h"
  #include "llvm/Analysis/TargetTransformInfo.h"
  #include "llvm/Analysis/ValueTracking.h"
  #include "llvm/IR/BasicBlock.h"
  #include "llvm/IR/Constant.h"
  #include "llvm/IR/Constants.h"
  #include "llvm/IR/DataLayout.h"
  #include "llvm/IR/DerivedTypes.h"
  #include "llvm/IR/Dominators.h"
  #include "llvm/IR/Function.h"
  #include "llvm/IR/GetElementPtrTypeIterator.h"
  #include "llvm/IR/IRBuilder.h"
  #include "llvm/IR/Instruction.h"
  #include "llvm/IR/Instructions.h"
  #include "llvm/IR/Module.h"
  #include "llvm/IR/PassManager.h"
  #include "llvm/IR/PatternMatch.h"
  #include "llvm/IR/Type.h"
  #include "llvm/IR/User.h"
  #include "llvm/IR/Value.h"
  #include "llvm/InitializePasses.h"
  #include "llvm/Pass.h"
  #include "llvm/Support/Casting.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/ErrorHandling.h"
  #include "llvm/Support/raw_ostream.h"
  #include "llvm/Target/TargetMachine.h"
  #include "llvm/Transforms/Scalar.h"
  #include "llvm/Transforms/Utils/Local.h"
  #include <cassert>
  #include <cstdint>
  #include <string>
  
  using namespace llvm;
  using namespace llvm::PatternMatch;
  
  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
  // free of dead code.
  static cl::opt<bool>
      VerifyNoDeadCode("reassociate-geps-verify-no-dead-code", cl::init(false),
                       cl::desc("Verify this pass produces no dead code"),
                       cl::Hidden);
  
  namespace {
  
  /// A helper class for separating a constant offset from a GEP index.
  ///
  /// In real programs, a GEP index may be more complicated than a simple addition
  /// of something and a constant integer which can be trivially splitted. For
  /// example, to split ((a << 3) | 5) + b, we need to search deeper for the
  /// constant offset, so that we can separate the index to (a << 3) + b and 5.
  ///
  /// Therefore, this class looks into the expression that computes a given GEP
  /// index, and tries to find a constant integer that can be hoisted to the
  /// outermost level of the expression as an addition. Not every constant in an
  /// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a +
  /// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case,
  /// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15).
  class ConstantOffsetExtractor {
  public:
    /// Extracts a constant offset from the given GEP index. It returns the
    /// new index representing the remainder (equal to the original index minus
    /// the constant offset), or nullptr if we cannot extract a constant offset.
    /// \p Idx The given GEP index
    /// \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);
  
  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.
    APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative);
  
    /// A helper function to look into both operands of a binary operator.
    APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended,
                              bool ZeroExtended);
  
    /// 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
    /// 2) reassociate the expression tree to the form I' + C.
    ///
    /// For example, to extract the 5 from sext(a + (b + 5)), we first distribute
    /// sext to a, b and 5 so that we have
    ///   sext(a) + (sext(b) + 5).
    /// Then, we reassociate it to
    ///   (sext(a) + sext(b)) + 5.
    /// Given this form, we know I' is sext(a) + sext(b).
    Value *rebuildWithoutConstOffset();
  
    /// After the first step of rebuilding the GEP index without the constant
    /// offset, distribute s/zext to the operands of all operators in UserChain.
    /// e.g., zext(sext(a + (b + 5)) (assuming no overflow) =>
    /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))).
    ///
    /// The function also updates UserChain to point to new subexpressions after
    /// distributing s/zext. e.g., the old UserChain of the above example is
    /// 5 -> b + 5 -> a + (b + 5) -> sext(...) -> zext(sext(...)),
    /// and the new UserChain is
    /// zext(sext(5)) -> zext(sext(b)) + zext(sext(5)) ->
    ///   zext(sext(a)) + (zext(sext(b)) + zext(sext(5))
    ///
    /// \p ChainIndex The index to UserChain. ChainIndex is initially
    ///               UserChain.size() - 1, and is decremented during
    ///               the recursion.
    Value *distributeExtsAndCloneChain(unsigned ChainIndex);
  
    /// Reassociates the GEP index to the form I' + C and returns I'.
    Value *removeConstOffset(unsigned ChainIndex);
  
    /// A helper function to apply ExtInsts, a list of s/zext, to value V.
    /// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function
    /// returns "sext i32 (zext i16 V to i32) to i64".
    Value *applyExts(Value *V);
  
    /// A helper function that returns whether we can trace into the operands
    /// of binary operator BO for a constant offset.
    ///
    /// \p SignExtended Whether BO is surrounded by sext
    /// \p ZeroExtended Whether BO is surrounded by zext
    /// \p NonNegative Whether BO is known to be non-negative, e.g., an in-bound
    ///                array index.
    bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO,
                      bool NonNegative);
  
    /// The path from the constant offset to the old GEP index. e.g., if the GEP
    /// index is "a * b + (c + 5)". After running function find, UserChain[0] will
    /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and
    /// UserChain[2] will be the entire expression "a * b + (c + 5)".
    ///
    /// This path helps to rebuild the new GEP index.
    SmallVector<User *, 8> UserChain;
  
    /// A data structure used in rebuildWithoutConstOffset. Contains all
    /// sext/zext instructions along UserChain.
    SmallVector<CastInst *, 16> ExtInsts;
  
    /// Insertion position of cloned instructions.
    Instruction *IP;
  
    const DataLayout &DL;
    const DominatorTree *DT;
  };
  
  /// 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)
        : FunctionPass(ID), LowerGEP(LowerGEP) {
      initializeSeparateConstOffsetFromGEPLegacyPassPass(
          *PassRegistry::getPassRegistry());
    }
  
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.addRequired<DominatorTreeWrapperPass>();
      AU.addRequired<ScalarEvolutionWrapperPass>();
      AU.addRequired<TargetTransformInfoWrapperPass>();
      AU.addRequired<LoopInfoWrapperPass>();
      AU.setPreservesCFG();
      AU.addRequired<TargetLibraryInfoWrapperPass>();
    }
  
    bool runOnFunction(Function &F) override;
  
  private:
    bool LowerGEP;
  };
  
  /// 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 SeparateConstOffsetFromGEP {
  public:
    SeparateConstOffsetFromGEP(
        DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI,
        TargetLibraryInfo *TLI,
        function_ref<TargetTransformInfo &(Function &)> GetTTI, bool LowerGEP)
        : DT(DT), SE(SE), LI(LI), TLI(TLI), GetTTI(GetTTI), LowerGEP(LowerGEP) {}
  
    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);
  
    /// 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.
    /// \p AccumulativeByteOffset    The constant offset.
    void lowerToSingleIndexGEPs(GetElementPtrInst *Variadic,
                                int64_t AccumulativeByteOffset);
  
    /// Lower a GEP with multiple indices into ptrtoint+arithmetics+inttoptr form.
    /// 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 arithmetic operations and applies
    /// AccumulativeByteOffset to it.
    /// \p Variadic                  The variadic part of the original GEP.
    /// \p AccumulativeByteOffset    The constant offset.
    void lowerToArithmetics(GetElementPtrInst *Variadic,
                            int64_t AccumulativeByteOffset);
  
    /// Finds the constant offset within each index and accumulates them. If
    /// LowerGEP is true, it finds in indices of both sequential and structure
    /// types, otherwise it only finds in sequential indices. The output
    /// NeedsExtraction indicates whether we successfully find a non-zero constant
    /// offset.
    int64_t accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction);
  
    /// Canonicalize array indices to pointer-size integers. This helps to
    /// simplify the logic of splitting a GEP. For example, if a + b is a
    /// pointer-size integer, we have
    ///   gep base, a + b = gep (gep base, a), b
    /// However, this equality may not hold if the size of a + b is smaller than
    /// the pointer size, because LLVM conceptually sign-extends GEP indices to
    /// pointer size before computing the address
    /// (http://llvm.org/docs/LangRef.html#id181).
    ///
    /// This canonicalization is very likely already done in clang and
    /// instcombine. Therefore, the program will probably remain the same.
    ///
    /// Returns true if the module changes.
    ///
    /// Verified in @i32_add in split-gep.ll
    bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP);
  
    /// Optimize sext(a)+sext(b) to sext(a+b) when a+b can't sign overflow.
    /// SeparateConstOffsetFromGEP distributes a sext to leaves before extracting
    /// the constant offset. After extraction, it becomes desirable to reunion the
    /// distributed sexts. For example,
    ///
    ///                              &a[sext(i +nsw (j +nsw 5)]
    ///   => distribute              &a[sext(i) +nsw (sext(j) +nsw 5)]
    ///   => constant extraction     &a[sext(i) + sext(j)] + 5
    ///   => reunion                 &a[sext(i +nsw j)] + 5
    bool reuniteExts(Function &F);
  
    /// A helper that reunites sexts in an instruction.
    bool reuniteExts(Instruction *I);
  
    /// Find the closest dominator of <Dominatee> that is equivalent to <Key>.
    Instruction *findClosestMatchingDominator(
        const SCEV *Key, Instruction *Dominatee,
        DenseMap<const SCEV *, SmallVector<Instruction *, 2>> &DominatingExprs);
  
    /// Verify F is free of dead code.
    void verifyNoDeadCode(Function &F);
  
    bool hasMoreThanOneUseInLoop(Value *v, Loop *L);
  
    // Swap the index operand of two GEP.
    void swapGEPOperand(GetElementPtrInst *First, GetElementPtrInst *Second);
  
    // Check if it is safe to swap operand of two GEP.
    bool isLegalToSwapOperand(GetElementPtrInst *First, GetElementPtrInst *Second,
                              Loop *CurLoop);
  
    const DataLayout *DL = nullptr;
    DominatorTree *DT = nullptr;
    ScalarEvolution *SE;
    LoopInfo *LI;
    TargetLibraryInfo *TLI;
    // Retrieved lazily since not always used.
    function_ref<TargetTransformInfo &(Function &)> GetTTI;
  
    /// Whether to lower a GEP with multiple indices into arithmetic operations or
    /// multiple GEPs with a single index.
    bool LowerGEP;
  
    DenseMap<const SCEV *, SmallVector<Instruction *, 2>> DominatingAdds;
    DenseMap<const SCEV *, SmallVector<Instruction *, 2>> DominatingSubs;
  };
  
  } // end anonymous namespace
  
  char SeparateConstOffsetFromGEPLegacyPass::ID = 0;
  
  INITIALIZE_PASS_BEGIN(
      SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep",
      "Split GEPs to a variadic base and a constant offset for better CSE", false,
      false)
  INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
  INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
  INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
  INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
  INITIALIZE_PASS_END(
      SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep",
      "Split GEPs to a variadic base and a constant offset for better CSE", false,
      false)
  
  FunctionPass *llvm::createSeparateConstOffsetFromGEPPass(bool LowerGEP) {
    return new SeparateConstOffsetFromGEPLegacyPass(LowerGEP);
  }
  
  bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,
                                              bool ZeroExtended,
                                              BinaryOperator *BO,
                                              bool NonNegative) {
    // We only consider ADD, SUB and OR, because a non-zero constant found in
    // expressions composed of these operations can be easily hoisted as a
    // constant offset by reassociation.
    if (BO->getOpcode() != Instruction::Add &&
        BO->getOpcode() != Instruction::Sub &&
        BO->getOpcode() != Instruction::Or) {
      return false;
    }
  
    Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1);
    // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS
    // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS).
    // FIXME: this does not appear to be covered by any tests
    //        (with x86/aarch64 backends at least)
    if (BO->getOpcode() == Instruction::Or &&
        !haveNoCommonBitsSet(LHS, RHS, DL, nullptr, BO, DT))
      return false;
  
    // In addition, tracing into BO requires that its surrounding s/zext (if
    // any) is distributable to both operands.
    //
    // Suppose BO = A op B.
    //  SignExtended | ZeroExtended | Distributable?
    // --------------+--------------+----------------------------------
    //       0       |      0       | true because no s/zext exists
    //       0       |      1       | zext(BO) == zext(A) op zext(B)
    //       1       |      0       | sext(BO) == sext(A) op sext(B)
    //       1       |      1       | zext(sext(BO)) ==
    //               |              |     zext(sext(A)) op zext(sext(B))
    if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) {
      // If a + b >= 0 and (a >= 0 or b >= 0), then
      //   sext(a + b) = sext(a) + sext(b)
      // even if the addition is not marked nsw.
      //
      // Leveraging this invariant, we can trace into an sext'ed inbound GEP
      // index if the constant offset is non-negative.
      //
      // Verified in @sext_add in split-gep.ll.
      if (ConstantInt *ConstLHS = dyn_cast<ConstantInt>(LHS)) {
        if (!ConstLHS->isNegative())
          return true;
      }
      if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(RHS)) {
        if (!ConstRHS->isNegative())
          return true;
      }
    }
  
    // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B)
    // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B)
    if (BO->getOpcode() == Instruction::Add ||
        BO->getOpcode() == Instruction::Sub) {
      if (SignExtended && !BO->hasNoSignedWrap())
        return false;
      if (ZeroExtended && !BO->hasNoUnsignedWrap())
        return false;
    }
  
    return true;
  }
  
  APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,
                                                     bool SignExtended,
                                                     bool ZeroExtended) {
    // 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);
    // 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) 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);
    // 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);
  
    return ConstantOffset;
  }
  
  APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended,
                                      bool ZeroExtended, bool NonNegative) {
    // 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);
    } else if (isa<TruncInst>(V)) {
      ConstantOffset =
          find(U->getOperand(0), SignExtended, ZeroExtended, NonNegative)
              .trunc(BitWidth);
    } else if (isa<SExtInst>(V)) {
      ConstantOffset = find(U->getOperand(0), /* SignExtended */ true,
                            ZeroExtended, NonNegative).sext(BitWidth);
    } 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).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);
    return ConstantOffset;
  }
  
  Value *ConstantOffsetExtractor::applyExts(Value *V) {
    Value *Current = V;
    // ExtInsts is built in the use-def order. Therefore, we apply them to V
    // in the reversed order.
    for (CastInst *I : llvm::reverse(ExtInsts)) {
      if (Constant *C = dyn_cast<Constant>(Current)) {
        // If Current is a constant, apply s/zext using ConstantExpr::getCast.
        // ConstantExpr::getCast emits a ConstantInt if C is a ConstantInt.
        Current = ConstantExpr::getCast(I->getOpcode(), C, I->getType());
      } else {
        Instruction *Ext = I->clone();
        Ext->setOperand(0, Current);
        Ext->insertBefore(IP);
        Current = Ext;
      }
    }
    return Current;
  }
  
  Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() {
    distributeExtsAndCloneChain(UserChain.size() - 1);
    // Remove all nullptrs (used to be s/zext) from UserChain.
    unsigned NewSize = 0;
    for (User *I : UserChain) {
      if (I != nullptr) {
        UserChain[NewSize] = I;
        NewSize++;
      }
    }
    UserChain.resize(NewSize);
    return removeConstOffset(UserChain.size() - 1);
  }
  
  Value *
  ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) {
    User *U = UserChain[ChainIndex];
    if (ChainIndex == 0) {
      assert(isa<ConstantInt>(U));
      // If U is a ConstantInt, applyExts will return a ConstantInt as well.
      return UserChain[ChainIndex] = cast<ConstantInt>(applyExts(U));
    }
  
    if (CastInst *Cast = dyn_cast<CastInst>(U)) {
      assert(
          (isa<SExtInst>(Cast) || isa<ZExtInst>(Cast) || isa<TruncInst>(Cast)) &&
          "Only following instructions can be traced: sext, zext & trunc");
      ExtInsts.push_back(Cast);
      UserChain[ChainIndex] = nullptr;
      return distributeExtsAndCloneChain(ChainIndex - 1);
    }
  
    // Function find only trace into BinaryOperator and CastInst.
    BinaryOperator *BO = cast<BinaryOperator>(U);
    // OpNo = which operand of BO is UserChain[ChainIndex - 1]
    unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
    Value *TheOther = applyExts(BO->getOperand(1 - OpNo));
    Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1);
  
    BinaryOperator *NewBO = nullptr;
    if (OpNo == 0) {
      NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther,
                                     BO->getName(), IP);
    } else {
      NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain,
                                     BO->getName(), IP);
    }
    return UserChain[ChainIndex] = NewBO;
  }
  
  Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) {
    if (ChainIndex == 0) {
      assert(isa<ConstantInt>(UserChain[ChainIndex]));
      return ConstantInt::getNullValue(UserChain[ChainIndex]->getType());
    }
  
    BinaryOperator *BO = cast<BinaryOperator>(UserChain[ChainIndex]);
    assert((BO->use_empty() || BO->hasOneUse()) &&
           "distributeExtsAndCloneChain clones each BinaryOperator in "
           "UserChain, so no one should be used more than "
           "once");
  
    unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
    assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]);
    Value *NextInChain = removeConstOffset(ChainIndex - 1);
    Value *TheOther = BO->getOperand(1 - OpNo);
  
    // If NextInChain is 0 and not the LHS of a sub, we can simplify the
    // sub-expression to be just TheOther.
    if (ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) {
      if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0))
        return TheOther;
    }
  
    BinaryOperator::BinaryOps NewOp = BO->getOpcode();
    if (BO->getOpcode() == Instruction::Or) {
      // Rebuild "or" as "add", because "or" may be invalid for the new
      // expression.
      //
      // For instance, given
      //   a | (b + 5) where a and b + 5 have no common bits,
      // we can extract 5 as the constant offset.
      //
      // However, reusing the "or" in the new index would give us
      //   (a | b) + 5
      // which does not equal a | (b + 5).
      //
      // Replacing the "or" with "add" is fine, because
      //   a | (b + 5) = a + (b + 5) = (a + b) + 5
      NewOp = Instruction::Add;
    }
  
    BinaryOperator *NewBO;
    if (OpNo == 0) {
      NewBO = BinaryOperator::Create(NewOp, NextInChain, TheOther, "", IP);
    } else {
      NewBO = BinaryOperator::Create(NewOp, TheOther, NextInChain, "", IP);
    }
    NewBO->takeName(BO);
    return NewBO;
  }
  
  Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP,
                                          User *&UserChainTail,
                                          const DominatorTree *DT) {
    ConstantOffsetExtractor Extractor(GEP, DT);
    // Find a non-zero constant offset first.
    APInt ConstantOffset =
        Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
                       GEP->isInBounds());
    if (ConstantOffset == 0) {
      UserChainTail = nullptr;
      return nullptr;
    }
    // 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) {
    // 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())
        .getSExtValue();
  }
  
  bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToPointerSize(
      GetElementPtrInst *GEP) {
    bool Changed = false;
    Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
    gep_type_iterator GTI = gep_type_begin(*GEP);
    for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end();
         I != E; ++I, ++GTI) {
      // Skip struct member indices which must be i32.
      if (GTI.isSequential()) {
        if ((*I)->getType() != IntPtrTy) {
          *I = CastInst::CreateIntegerCast(*I, IntPtrTy, true, "idxprom", GEP);
          Changed = true;
        }
      }
    }
    return Changed;
  }
  
  int64_t
  SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP,
                                                   bool &NeedsExtraction) {
    NeedsExtraction = false;
    int64_t AccumulativeByteOffset = 0;
    gep_type_iterator GTI = gep_type_begin(*GEP);
    for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
      if (GTI.isSequential()) {
        // Tries to extract a constant offset from this GEP index.
        int64_t ConstantOffset =
            ConstantOffsetExtractor::Find(GEP->getOperand(I), GEP, DT);
        if (ConstantOffset != 0) {
          NeedsExtraction = true;
          // 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());
        }
      } 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) {
          NeedsExtraction = true;
          AccumulativeByteOffset +=
              DL->getStructLayout(StTy)->getElementOffset(Field);
        }
      }
    }
    return AccumulativeByteOffset;
  }
  
  void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs(
      GetElementPtrInst *Variadic, int64_t AccumulativeByteOffset) {
    IRBuilder<> Builder(Variadic);
    Type *IntPtrTy = DL->getIntPtrType(Variadic->getType());
  
    Type *I8PtrTy =
        Builder.getInt8PtrTy(Variadic->getType()->getPointerAddressSpace());
    Value *ResultPtr = Variadic->getOperand(0);
    Loop *L = LI->getLoopFor(Variadic->getParent());
    // Check if the base is not loop invariant or used more than once.
    bool isSwapCandidate =
        L && L->isLoopInvariant(ResultPtr) &&
        !hasMoreThanOneUseInLoop(ResultPtr, L);
    Value *FirstResult = nullptr;
  
    if (ResultPtr->getType() != I8PtrTy)
      ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
  
    gep_type_iterator GTI = gep_type_begin(*Variadic);
    // Create an ugly GEP for each sequential index. We don't create GEPs for
    // structure indices, as they are accumulated in the constant offset index.
    for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) {
      if (GTI.isSequential()) {
        Value *Idx = Variadic->getOperand(I);
        // Skip zero indices.
        if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx))
          if (CI->isZero())
            continue;
  
        APInt ElementSize = APInt(IntPtrTy->getIntegerBitWidth(),
                                  DL->getTypeAllocSize(GTI.getIndexedType()));
        // Scale the index by element size.
        if (ElementSize != 1) {
          if (ElementSize.isPowerOf2()) {
            Idx = Builder.CreateShl(
                Idx, ConstantInt::get(IntPtrTy, ElementSize.logBase2()));
          } else {
            Idx = Builder.CreateMul(Idx, ConstantInt::get(IntPtrTy, ElementSize));
          }
        }
        // Create an ugly GEP with a single index for each index.
        ResultPtr =
            Builder.CreateGEP(Builder.getInt8Ty(), ResultPtr, Idx, "uglygep");
        if (FirstResult == nullptr)
          FirstResult = ResultPtr;
      }
    }
  
    // Create a GEP with the constant offset index.
    if (AccumulativeByteOffset != 0) {
      Value *Offset = ConstantInt::get(IntPtrTy, AccumulativeByteOffset);
      ResultPtr =
          Builder.CreateGEP(Builder.getInt8Ty(), ResultPtr, Offset, "uglygep");
    } else
      isSwapCandidate = false;
  
    // If we created a GEP with constant index, and the base is loop invariant,
    // then we swap the first one with it, so LICM can move constant GEP out
    // later.
    auto *FirstGEP = dyn_cast_or_null<GetElementPtrInst>(FirstResult);
    auto *SecondGEP = dyn_cast<GetElementPtrInst>(ResultPtr);
    if (isSwapCandidate && isLegalToSwapOperand(FirstGEP, SecondGEP, L))
      swapGEPOperand(FirstGEP, SecondGEP);
  
    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.
    for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) {
      if (GTI.isSequential()) {
        Value *Idx = Variadic->getOperand(I);
        // Skip zero indices.
        if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx))
          if (CI->isZero())
            continue;
  
        APInt ElementSize = APInt(IntPtrTy->getIntegerBitWidth(),
                                  DL->getTypeAllocSize(GTI.getIndexedType()));
        // Scale the index by element size.
        if (ElementSize != 1) {
          if (ElementSize.isPowerOf2()) {
            Idx = Builder.CreateShl(
                Idx, ConstantInt::get(IntPtrTy, ElementSize.logBase2()));
          } else {
            Idx = Builder.CreateMul(Idx, ConstantInt::get(IntPtrTy, ElementSize));
          }
        }
        // Create an ADD for each index.
        ResultPtr = Builder.CreateAdd(ResultPtr, Idx);
      }
    }
  
    // Create an ADD for the constant offset index.
    if (AccumulativeByteOffset != 0) {
      ResultPtr = Builder.CreateAdd(
          ResultPtr, ConstantInt::get(IntPtrTy, AccumulativeByteOffset));
    }
  
    ResultPtr = Builder.CreateIntToPtr(ResultPtr, Variadic->getType());
    Variadic->replaceAllUsesWith(ResultPtr);
    Variadic->eraseFromParent();
  }
  
  bool SeparateConstOffsetFromGEP::splitGEP(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;
  
    bool Changed = canonicalizeArrayIndicesToPointerSize(GEP);
  
    bool NeedsExtraction;
    int64_t AccumulativeByteOffset = accumulateByteOffset(GEP, NeedsExtraction);
  
    if (!NeedsExtraction)
      return Changed;
  
    TargetTransformInfo &TTI = GetTTI(*GEP->getFunction());
  
    // If LowerGEP is disabled, before really splitting the GEP, check whether the
    // backend supports the addressing mode we are about to produce. If no, this
    // splitting probably won't be beneficial.
    // If LowerGEP is enabled, even the extracted constant offset can not match
    // the addressing mode, we can still do optimizations to other lowered parts
    // of variable indices. Therefore, we don't check for addressing modes in that
    // case.
    if (!LowerGEP) {
      unsigned AddrSpace = GEP->getPointerAddressSpace();
      if (!TTI.isLegalAddressingMode(GEP->getResultElementType(),
                                     /*BaseGV=*/nullptr, AccumulativeByteOffset,
                                     /*HasBaseReg=*/true, /*Scale=*/0,
                                     AddrSpace)) {
        return Changed;
      }
    }
  
    // Remove the constant offset in each sequential index. The resultant GEP
    // computes the variadic base.
    // Notice that we don't remove struct field indices here. If LowerGEP is
    // disabled, a structure index is not accumulated and we still use the old
    // one. If LowerGEP is enabled, a structure index is accumulated in the
    // constant offset. LowerToSingleIndexGEPs or lowerToArithmetics will later
    // handle the constant offset and won't need a new structure index.
    gep_type_iterator GTI = gep_type_begin(*GEP);
    for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
      if (GTI.isSequential()) {
        // Splits this GEP index into a variadic part and a constant offset, and
        // uses the variadic part as the new index.
        Value *OldIdx = GEP->getOperand(I);
        User *UserChainTail;
        Value *NewIdx =
            ConstantOffsetExtractor::Extract(OldIdx, GEP, UserChainTail, DT);
        if (NewIdx != nullptr) {
          // Switches to the index with the constant offset removed.
          GEP->setOperand(I, NewIdx);
          // After switching to the new index, we can garbage-collect UserChain
          // and the old index if they are not used.
          RecursivelyDeleteTriviallyDeadInstructions(UserChainTail);
          RecursivelyDeleteTriviallyDeadInstructions(OldIdx);
        }
      }
    }
  
    // Clear the inbounds attribute because the new index may be off-bound.
    // e.g.,
    //
    //   b     = add i64 a, 5
    //   addr  = gep inbounds float, float* p, i64 b
    //
    // is transformed to:
    //
    //   addr2 = gep float, float* p, i64 a ; inbounds removed
    //   addr  = gep inbounds float, float* addr2, i64 5
    //
    // If a is -4, although the old index b is in bounds, the new index a is
    // off-bound. http://llvm.org/docs/LangRef.html#id181 says "if the
    // inbounds keyword is not present, the offsets are added to the base
    // address with silently-wrapping two's complement arithmetic".
    // Therefore, the final code will be a semantically equivalent.
    //
    // TODO(jingyue): do some range analysis to keep as many inbounds as
    // possible. GEPs with inbounds are more friendly to alias analysis.
    bool GEPWasInBounds = GEP->isInBounds();
    GEP->setIsInBounds(false);
  
    // Lowers a GEP to either GEPs with a single index or arithmetic operations.
    if (LowerGEP) {
      // As currently BasicAA does not analyze ptrtoint/inttoptr, do not lower to
      // arithmetic operations if the target uses alias analysis in codegen.
      if (TTI.useAA())
        lowerToSingleIndexGEPs(GEP, AccumulativeByteOffset);
      else
        lowerToArithmetics(GEP, AccumulativeByteOffset);
      return true;
    }
  
    // No need to create another GEP if the accumulative byte offset is 0.
    if (AccumulativeByteOffset == 0)
      return true;
  
    // Offsets the base with the accumulative byte offset.
    //
    //   %gep                        ; the base
    //   ... %gep ...
    //
    // => add the offset
    //
    //   %gep2                       ; clone of %gep
    //   %new.gep = gep %gep2, <offset / sizeof(*%gep)>
    //   %gep                        ; will be removed
    //   ... %gep ...
    //
    // => replace all uses of %gep with %new.gep and remove %gep
    //
    //   %gep2                       ; clone of %gep
    //   %new.gep = gep %gep2, <offset / sizeof(*%gep)>
    //   ... %new.gep ...
    //
    // If AccumulativeByteOffset is not a multiple of sizeof(*%gep), we emit an
    // uglygep (http://llvm.org/docs/GetElementPtr.html#what-s-an-uglygep):
    // bitcast %gep2 to i8*, add the offset, and bitcast the result back to the
    // type of %gep.
    //
    //   %gep2                       ; clone of %gep
    //   %0       = bitcast %gep2 to i8*
    //   %uglygep = gep %0, <offset>
    //   %new.gep = bitcast %uglygep to <type of %gep>
    //   ... %new.gep ...
    Instruction *NewGEP = GEP->clone();
    NewGEP->insertBefore(GEP);
  
    // Per ANSI C standard, signed / unsigned = unsigned and signed % unsigned =
    // unsigned.. Therefore, we cast ElementTypeSizeOfGEP to signed because it is
    // used with unsigned integers later.
    int64_t ElementTypeSizeOfGEP = static_cast<int64_t>(
        DL->getTypeAllocSize(GEP->getResultElementType()));
    Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
    if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) {
      // Very likely. As long as %gep is naturally aligned, the byte offset we
      // extracted should be a multiple of sizeof(*%gep).
      int64_t Index = AccumulativeByteOffset / ElementTypeSizeOfGEP;
      NewGEP = GetElementPtrInst::Create(GEP->getResultElementType(), NewGEP,
                                         ConstantInt::get(IntPtrTy, Index, true),
                                         GEP->getName(), GEP);
      NewGEP->copyMetadata(*GEP);
      // Inherit the inbounds attribute of the original GEP.
      cast<GetElementPtrInst>(NewGEP)->setIsInBounds(GEPWasInBounds);
    } else {
      // Unlikely but possible. For example,
      // #pragma pack(1)
      // struct S {
      //   int a[3];
      //   int64 b[8];
      // };
      // #pragma pack()
      //
      // Suppose the gep before extraction is &s[i + 1].b[j + 3]. After
      // extraction, it becomes &s[i].b[j] and AccumulativeByteOffset is
      // sizeof(S) + 3 * sizeof(int64) = 100, which is not a multiple of
      // sizeof(int64).
      //
      // Emit an uglygep in this case.
      Type *I8PtrTy = Type::getInt8PtrTy(GEP->getContext(),
                                         GEP->getPointerAddressSpace());
      NewGEP = new BitCastInst(NewGEP, I8PtrTy, "", GEP);
      NewGEP = GetElementPtrInst::Create(
          Type::getInt8Ty(GEP->getContext()), NewGEP,
          ConstantInt::get(IntPtrTy, AccumulativeByteOffset, true), "uglygep",
          GEP);
      NewGEP->copyMetadata(*GEP);
      // Inherit the inbounds attribute of the original GEP.
      cast<GetElementPtrInst>(NewGEP)->setIsInBounds(GEPWasInBounds);
      if (GEP->getType() != I8PtrTy)
        NewGEP = new BitCastInst(NewGEP, GEP->getType(), GEP->getName(), GEP);
    }
  
    GEP->replaceAllUsesWith(NewGEP);
    GEP->eraseFromParent();
  
    return true;
  }
  
  bool SeparateConstOffsetFromGEPLegacyPass::runOnFunction(Function &F) {
    if (skipFunction(F))
      return false;
    auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
    auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
    auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
    auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
      return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
    };
    SeparateConstOffsetFromGEP Impl(DT, SE, LI, TLI, GetTTI, LowerGEP);
    return Impl.run(F);
  }
  
  bool SeparateConstOffsetFromGEP::run(Function &F) {
    if (DisableSeparateConstOffsetFromGEP)
      return false;
  
    DL = &F.getParent()->getDataLayout();
    bool Changed = false;
    for (BasicBlock &B : F) {
      if (!DT->isReachableFromEntry(&B))
        continue;
  
      for (Instruction &I : llvm::make_early_inc_range(B))
        if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I))
          Changed |= splitGEP(GEP);
      // No need to split GEP ConstantExprs because all its indices are constant
      // already.
    }
  
    Changed |= reuniteExts(F);
  
    if (VerifyNoDeadCode)
      verifyNoDeadCode(F);
  
    return Changed;
  }
  
  Instruction *SeparateConstOffsetFromGEP::findClosestMatchingDominator(
      const SCEV *Key, Instruction *Dominatee,
      DenseMap<const SCEV *, SmallVector<Instruction *, 2>> &DominatingExprs) {
    auto Pos = DominatingExprs.find(Key);
    if (Pos == DominatingExprs.end())
      return nullptr;
  
    auto &Candidates = Pos->second;
    // Because we process the basic blocks in pre-order of the dominator tree, a
    // candidate that doesn't dominate the current instruction won't dominate any
    // future instruction either. Therefore, we pop it out of the stack. This
    // optimization makes the algorithm O(n).
    while (!Candidates.empty()) {
      Instruction *Candidate = Candidates.back();
      if (DT->dominates(Candidate, Dominatee))
        return Candidate;
      Candidates.pop_back();
    }
    return nullptr;
  }
  
  bool SeparateConstOffsetFromGEP::reuniteExts(Instruction *I) {
    if (!SE->isSCEVable(I->getType()))
      return false;
  
    //   Dom: LHS+RHS
    //   I: sext(LHS)+sext(RHS)
    // If Dom can't sign overflow and Dom dominates I, optimize I to sext(Dom).
    // TODO: handle zext
    Value *LHS = nullptr, *RHS = nullptr;
    if (match(I, m_Add(m_SExt(m_Value(LHS)), m_SExt(m_Value(RHS))))) {
      if (LHS->getType() == RHS->getType()) {
        const SCEV *Key =
            SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
        if (auto *Dom = findClosestMatchingDominator(Key, I, DominatingAdds)) {
          Instruction *NewSExt = new SExtInst(Dom, I->getType(), "", I);
          NewSExt->takeName(I);
          I->replaceAllUsesWith(NewSExt);
          RecursivelyDeleteTriviallyDeadInstructions(I);
          return true;
        }
      }
    } else if (match(I, m_Sub(m_SExt(m_Value(LHS)), m_SExt(m_Value(RHS))))) {
      if (LHS->getType() == RHS->getType()) {
        const SCEV *Key =
            SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
        if (auto *Dom = findClosestMatchingDominator(Key, I, DominatingSubs)) {
          Instruction *NewSExt = new SExtInst(Dom, I->getType(), "", I);
          NewSExt->takeName(I);
          I->replaceAllUsesWith(NewSExt);
          RecursivelyDeleteTriviallyDeadInstructions(I);
          return true;
        }
      }
    }
  
    // Add I to DominatingExprs if it's an add/sub that can't sign overflow.
    if (match(I, m_NSWAdd(m_Value(LHS), m_Value(RHS)))) {
      if (programUndefinedIfPoison(I)) {
        const SCEV *Key =
            SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
        DominatingAdds[Key].push_back(I);
      }
    } else if (match(I, m_NSWSub(m_Value(LHS), m_Value(RHS)))) {
      if (programUndefinedIfPoison(I)) {
        const SCEV *Key =
            SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
        DominatingSubs[Key].push_back(I);
      }
    }
    return false;
  }
  
  bool SeparateConstOffsetFromGEP::reuniteExts(Function &F) {
    bool Changed = false;
    DominatingAdds.clear();
    DominatingSubs.clear();
    for (const auto Node : depth_first(DT)) {
      BasicBlock *BB = Node->getBlock();
      for (Instruction &I : llvm::make_early_inc_range(*BB))
        Changed |= reuniteExts(&I);
    }
    return Changed;
  }
  
  void SeparateConstOffsetFromGEP::verifyNoDeadCode(Function &F) {
    for (BasicBlock &B : F) {
      for (Instruction &I : B) {
        if (isInstructionTriviallyDead(&I)) {
          std::string ErrMessage;
          raw_string_ostream RSO(ErrMessage);
          RSO << "Dead instruction detected!\n" << I << "\n";
          llvm_unreachable(RSO.str().c_str());
        }
      }
    }
  }
  
  bool SeparateConstOffsetFromGEP::isLegalToSwapOperand(
      GetElementPtrInst *FirstGEP, GetElementPtrInst *SecondGEP, Loop *CurLoop) {
    if (!FirstGEP || !FirstGEP->hasOneUse())
      return false;
  
    if (!SecondGEP || FirstGEP->getParent() != SecondGEP->getParent())
      return false;
  
    if (FirstGEP == SecondGEP)
      return false;
  
    unsigned FirstNum = FirstGEP->getNumOperands();
    unsigned SecondNum = SecondGEP->getNumOperands();
    // Give up if the number of operands are not 2.
    if (FirstNum != SecondNum || FirstNum != 2)
      return false;
  
    Value *FirstBase = FirstGEP->getOperand(0);
    Value *SecondBase = SecondGEP->getOperand(0);
    Value *FirstOffset = FirstGEP->getOperand(1);
    // Give up if the index of the first GEP is loop invariant.
    if (CurLoop->isLoopInvariant(FirstOffset))
      return false;
  
    // Give up if base doesn't have same type.
    if (FirstBase->getType() != SecondBase->getType())
      return false;
  
    Instruction *FirstOffsetDef = dyn_cast<Instruction>(FirstOffset);
  
    // Check if the second operand of first GEP has constant coefficient.
    // For an example, for the following code,  we won't gain anything by
    // hoisting the second GEP out because the second GEP can be folded away.
    //   %scevgep.sum.ur159 = add i64 %idxprom48.ur, 256
    //   %67 = shl i64 %scevgep.sum.ur159, 2
    //   %uglygep160 = getelementptr i8* %65, i64 %67
    //   %uglygep161 = getelementptr i8* %uglygep160, i64 -1024
  
    // Skip constant shift instruction which may be generated by Splitting GEPs.
    if (FirstOffsetDef && FirstOffsetDef->isShift() &&
        isa<ConstantInt>(FirstOffsetDef->getOperand(1)))
      FirstOffsetDef = dyn_cast<Instruction>(FirstOffsetDef->getOperand(0));
  
    // Give up if FirstOffsetDef is an Add or Sub with constant.
    // Because it may not profitable at all due to constant folding.
    if (FirstOffsetDef)
      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FirstOffsetDef)) {
        unsigned opc = BO->getOpcode();
        if ((opc == Instruction::Add || opc == Instruction::Sub) &&
            (isa<ConstantInt>(BO->getOperand(0)) ||
             isa<ConstantInt>(BO->getOperand(1))))
          return false;
      }
    return true;
  }
  
  bool SeparateConstOffsetFromGEP::hasMoreThanOneUseInLoop(Value *V, Loop *L) {
    int UsesInLoop = 0;
    for (User *U : V->users()) {
      if (Instruction *User = dyn_cast<Instruction>(U))
        if (L->contains(User))
          if (++UsesInLoop > 1)
            return true;
    }
    return false;
  }
  
  void SeparateConstOffsetFromGEP::swapGEPOperand(GetElementPtrInst *First,
                                                  GetElementPtrInst *Second) {
    Value *Offset1 = First->getOperand(1);
    Value *Offset2 = Second->getOperand(1);
    First->setOperand(1, Offset2);
    Second->setOperand(1, Offset1);
  
    // We changed p+o+c to p+c+o, p+c may not be inbound anymore.
    const DataLayout &DAL = First->getModule()->getDataLayout();
    APInt Offset(DAL.getIndexSizeInBits(
                     cast<PointerType>(First->getType())->getAddressSpace()),
                 0);
    Value *NewBase =
        First->stripAndAccumulateInBoundsConstantOffsets(DAL, Offset);
    uint64_t ObjectSize;
    if (!getObjectSize(NewBase, ObjectSize, DAL, TLI) ||
       Offset.ugt(ObjectSize)) {
      First->setIsInBounds(false);
      Second->setIsInBounds(false);
    } else
      First->setIsInBounds(true);
  }
  
  PreservedAnalyses
  SeparateConstOffsetFromGEPPass::run(Function &F, FunctionAnalysisManager &AM) {
    auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
    auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
    auto *LI = &AM.getResult<LoopAnalysis>(F);
    auto *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
    auto GetTTI = [&AM](Function &F) -> TargetTransformInfo & {
      return AM.getResult<TargetIRAnalysis>(F);
    };
    SeparateConstOffsetFromGEP Impl(DT, SE, LI, TLI, GetTTI, LowerGEP);
    if (!Impl.run(F))
      return PreservedAnalyses::all();
    PreservedAnalyses PA;
    PA.preserveSet<CFGAnalyses>();
    return PA;
  }
  