[Constant Hoisting] Hoisting Constant GEP Expressions

[zzheng]

Summary

Leverage existing logic in constant hoisting pass so that constant gep expressions
sharing the same base global variable are transformed into the form of
[Base + Offset], where Base is a constant gep and Offset is an integer.

This transformation can effectively reduce constant pool entries in the backend.

[efriedma]

include/llvm/Transforms/Scalar/ConstantHoisting.h

84

Could use a comment explaining what ConstExpr and ConstInt represent.

113

Could use a comment explaining what BaseExpr and BaseInt represent.

114

I'm sort of confused by the usage of BaseTy; why does the type of the base matter? It just gets bitcast away later, anyway.

lib/Transforms/Scalar/ConstantHoisting.cpp

412

getIntImmCodeSizeCost returns either zero or one on ARM... so it's always less than SizeCost?

736

Please use bitcast+GEP+bitcast, instead of ptrtoint/inttoptr.

[zzheng]

Unfortunately bitcast + gep + bitcast will only change the constant GEP expr from multi-dimension to single dimension, and it's still a constant pool entry after lowering.

[efriedma]

lib/Transforms/Scalar/ConstantHoisting.cpp

407

This still seems weird; we only hoist if the cost is less than 3?

[zzheng]

lib/Transforms/Scalar/ConstantHoisting.cpp

407

We want to hoist when cost of hoisting is smaller than cost of not-hoisting.

Currently a constant GEP whose base pointer is a GV, is lowered to a CP entry. The initial value of Cost reflects cost of loading this CP entry.

If loading from CP is always more expensive than computing it by <base + offset>, perhaps we can get rid of this if condition?

[efriedma]

lib/Transforms/Scalar/ConstantHoisting.cpp

407

Making it unconditional is probably okay.

Well, we might not want to hoist if the offset is so small we aren't actually getting any benefit. (e.g. loading from [r0] and [r0, #4] isn't really better than loading from [r0, #8] and [r0, #12]).

[zzheng]

Updated version reflects discussion with Eli.

Added AArch64 llc test.

Turns out one of our internal changes is bloating code size on thumbv6m. Will upstream a follow up patch address that.

[zzheng]

lib/Transforms/Scalar/ConstantHoisting.cpp

407

This patch tries to change from loading a group of CP entries to loading one CP entry and loading the reset by <Base + Offset>.

However, that's the case on our internal tree. We have a patch that lowers constant GEPs to CP entries

[efriedma]

A few more comments with minor tweaks. Otherwise looks good.

include/llvm/Transforms/Scalar/ConstantHoisting.h

182

Dead declaration.

192

Don't use default arguments for functions like this... it's more confusing than helpful.

lib/Transforms/Scalar/ConstantHoisting.cpp

731

You probably should specify the address-space here, to the same address-space as Ty.

788

Could you add an assertion here assert(ConstExpr->isCast()), so it's clear this matches the code in collectConstantCandidates?

[zzheng]

Addressed Eli's comments.

[efriedma]

LGTM

lib/Transforms/Scalar/ConstantHoisting.cpp

732

cast<PointerType>(Ty)

include/llvm/Transforms/Scalar/ConstantHoisting.h

 // %0 = load i64* inttoptr (i64 big_constant to i64*)
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include <algorithm>
 #include <vector>
 
 namespace llvm {
 
 class BasicBlock;
 class BlockFrequencyInfo;
 class Constant;
 class ConstantInt;
+class ConstantExpr;
 class DominatorTree;
 class Function;
+class GlobalVariable;
 class Instruction;
 class TargetTransformInfo;
 
 /// A private "module" namespace for types and utilities used by
 /// ConstantHoisting. These are implementation details and should not be used by
 /// clients.
 namespace consthoist {
 
 /// Keeps track of the user of a constant and the operand index where the
 /// constant is used.
 struct ConstantUser {
   Instruction *Inst;
   unsigned OpndIdx;
 
   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
 };
 
 using ConstantUseListType = SmallVector<ConstantUser, 8>;
 
 /// Keeps track of a constant candidate and its uses.
 struct ConstantCandidate {
   ConstantUseListType Uses;
+  // If the candidate is a ConstantExpr (currely only constant GEP expressions
+  // whose base pointers are GlobalVariables are supported), ConstInt records
+  // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
   ConstantInt *ConstInt;
+  ConstantExpr *ConstExpr;
   unsigned CumulativeCost = 0;
 
-  ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
+  ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
+      ConstInt(ConstInt), ConstExpr(ConstExpr) {}
 
   /// Add the user to the use list and update the cost.
   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
     CumulativeCost += Cost;
     Uses.push_back(ConstantUser(Inst, Idx));
   }
 };
 
 /// This represents a constant that has been rebased with respect to a
 /// base constant. The difference to the base constant is recorded in Offset.
 struct RebasedConstantInfo {
   ConstantUseListType Uses;
   Constant *Offset;
+  Type *Ty;
 
-  RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
-    : Uses(std::move(Uses)), Offset(Offset) {}
+  RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
+      Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
 };
 
 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
 
 /// A base constant and all its rebased constants.
 struct ConstantInfo {
-  ConstantInt *BaseConstant;
+  // If the candidate is a ConstantExpr (currely only constant GEP expressions
+  // whose base pointers are GlobalVariables are supported), ConstInt records
+  // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
+  ConstantInt *BaseInt;
+  ConstantExpr *BaseExpr;
   RebasedConstantListType RebasedConstants;
 };
 
 } // end namespace consthoist
 
 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for old PM.
   bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
                BlockFrequencyInfo *BFI, BasicBlock &Entry);
 
   void releaseMemory() {
-    ConstantVec.clear();
     ClonedCastMap.clear();
-    ConstCandVec.clear();
+    ConstIntCandVec.clear();
+    for (auto MapEntry : ConstGEPCandMap)
+      MapEntry.second.clear();
+    ConstGEPCandMap.clear();
+    ConstIntInfoVec.clear();
+    for (auto MapEntry : ConstGEPInfoMap)
+      MapEntry.second.clear();
+    ConstGEPInfoMap.clear();
   }
 
 private:
-  using ConstCandMapType = DenseMap<ConstantInt *, unsigned>;
-  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
+  using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
+  using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
 
   const TargetTransformInfo *TTI;
   DominatorTree *DT;
   BlockFrequencyInfo *BFI;
+  LLVMContext *Ctx;
+  const DataLayout *DL;
   BasicBlock *Entry;
 
   /// Keeps track of constant candidates found in the function.
-  ConstCandVecType ConstCandVec;
+  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
+  using GVCandVecMapType = DenseMap<GlobalVariable *, ConstCandVecType>;
+  ConstCandVecType ConstIntCandVec;
+  GVCandVecMapType ConstGEPCandMap;
+
+  /// These are the final constants we decided to hoist.
+  using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
+  using GVInfoVecMapType = DenseMap<GlobalVariable *, ConstInfoVecType>;
+  ConstInfoVecType ConstIntInfoVec;
+  GVInfoVecMapType ConstGEPInfoMap;
 
   /// Keep track of cast instructions we already cloned.
   SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
 
-  /// These are the final constants we decided to hoist.
-  SmallVector<consthoist::ConstantInfo, 8> ConstantVec;
-
   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
   SmallPtrSet<Instruction *, 8>
   findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst, unsigned Idx,
                                  ConstantInt *ConstInt);
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
+                                 Instruction *Inst, unsigned Idx,
+                                 ConstantExpr *ConstExpr);
+  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst, unsigned Idx);
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst);
   void collectConstantCandidates(Function &Fn);
+  void computeGEPOffset(ConstantExpr *ConstExpr, Type *Ty, APInt &Offset);
   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
-                               ConstCandVecType::iterator E);
+                               ConstCandVecType::iterator E,
+      SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
   unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
                                     ConstCandVecType::iterator E,
                                     ConstCandVecType::iterator &MaxCostItr);
-  void findBaseConstants();
-  void emitBaseConstants(Instruction *Base, Constant *Offset,
+  void findBaseConstants(GlobalVariable *BaseGV = nullptr);
+  void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty,
                          const consthoist::ConstantUser &ConstUser);
-  bool emitBaseConstants();
+  bool emitBaseConstants(GlobalVariable *BaseGV = nullptr);
   void deleteDeadCastInst() const;
   bool optimizeConstants(Function &Fn);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H

lib/Transforms/Scalar/ConstantHoisting.cpp

 STATISTIC(NumConstantsRebased, "Number of constants rebased");
 
 static cl::opt<bool> ConstHoistWithBlockFrequency(
     "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
     cl::desc("Enable the use of the block frequency analysis to reduce the "
              "chance to execute const materialization more frequently than "
              "without hoisting."));
 
+static cl::opt<bool> ConstHoistGEP(
+    "consthoist-gep", cl::init(false), cl::Hidden,
+    cl::desc("Try hoisting constant gep expressions"));
+
 namespace {
 
 /// The constant hoisting pass.
 class ConstantHoistingLegacyPass : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
 
   ConstantHoistingLegacyPass() : FunctionPass(ID) {
SmallPtrSet<Instruction *, 8> ConstantHoistingPass::findConstantInsertionPoint(
   return InsertPts;
 }
 
 /// Record constant integer ConstInt for instruction Inst at operand
 /// index Idx.
 ///
 /// The operand at index Idx is not necessarily the constant integer itself. It
 /// could also be a cast instruction or a constant expression that uses the
-// constant integer.
+/// constant integer.
 void ConstantHoistingPass::collectConstantCandidates(
     ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
     ConstantInt *ConstInt) {
   unsigned Cost;
   // Ask the target about the cost of materializing the constant for the given
   // instruction and operand index.
   if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
     Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx,
                               ConstInt->getValue(), ConstInt->getType());
   else
     Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(),
                               ConstInt->getType());
 
   // Ignore cheap integer constants.
   if (Cost > TargetTransformInfo::TCC_Basic) {
     ConstCandMapType::iterator Itr;
     bool Inserted;
-    std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(ConstInt, 0));
+    ConstPtrUnionType Cand = ConstInt;
+    std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
     if (Inserted) {
-      ConstCandVec.push_back(ConstantCandidate(ConstInt));
-      Itr->second = ConstCandVec.size() - 1;
+      ConstIntCandVec.push_back(ConstantCandidate(ConstInt));
+      Itr->second = ConstIntCandVec.size() - 1;
     }
-    ConstCandVec[Itr->second].addUser(Inst, Idx, Cost);
+    ConstIntCandVec[Itr->second].addUser(Inst, Idx, Cost);
     LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs()
                    << "Collect constant " << *ConstInt << " from " << *Inst
                    << " with cost " << Cost << '\n';
                else dbgs() << "Collect constant " << *ConstInt
                            << " indirectly from " << *Inst << " via "
                            << *Inst->getOperand(Idx) << " with cost " << Cost
                            << '\n';);
   }
 }
 
+/// Record constant GEP expression for instruction Inst at operand index Idx.
+void ConstantHoistingPass::collectConstantCandidates(
+    ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
+    ConstantExpr *ConstExpr) {
+  // TODO: Handle vector GEPs
+  if (ConstExpr->getType()->isVectorTy())
+    return;
+
+  GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(ConstExpr->getOperand(0));
+  if (!BaseGV)
+    return;
+
+  // Get offset from the base GV.
+  PointerType *GVPtrTy = dyn_cast<PointerType>(BaseGV->getType());
+  IntegerType *PtrIntTy = DL->getIntPtrType(*Ctx, GVPtrTy->getAddressSpace());
+  APInt Offset(DL->getTypeSizeInBits(PtrIntTy), /*val*/0, /*isSigned*/true);
+  auto *GEPO = cast<GEPOperator>(ConstExpr);
+  if (!GEPO->accumulateConstantOffset(*DL, Offset))
+    return;
+
+  if (!Offset.isIntN(32))
+    return;
+
+  // Initial cost is 3, load from constant pool.
+  int Cost = 3;;
+  if (Cost > TTI->getIntImmCost(Instruction::Add, 1, Offset, PtrIntTy)) {
+    ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
+    ConstCandMapType::iterator Itr;
+    bool Inserted;
+    ConstPtrUnionType Cand = ConstExpr;
+    std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
+    if (Inserted) {
+      ExprCandVec.push_back(ConstantCandidate(
+          ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
+          ConstExpr));
+      Itr->second = ExprCandVec.size() - 1;
+    }
+    ExprCandVec[Itr->second].addUser(Inst, Idx, Cost);
+  }
+}
+
 /// Check the operand for instruction Inst at index Idx.
 void ConstantHoistingPass::collectConstantCandidates(
     ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
   Value *Opnd = Inst->getOperand(Idx);
 
   // Visit constant integers.
   if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
     collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
       // the cast instruction.
       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
       return;
     }
   }
 
   // Visit constant expressions that have constant integers.
   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
+    // Handle constant gep expressions.
+    if (ConstHoistGEP && ConstExpr->isGEPWithNoNotionalOverIndexing())
+      collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
+
     // Only visit constant cast expressions.
     if (!ConstExpr->isCast())
       return;
 
     if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
       // Pretend the constant is directly used by the instruction and ignore
       // the constant expression.
       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
     }
   }
   return NumUses;
 }
 
 /// Find the base constant within the given range and rebase all other
 /// constants with respect to the base constant.
 void ConstantHoistingPass::findAndMakeBaseConstant(
-    ConstCandVecType::iterator S, ConstCandVecType::iterator E) {
+    ConstCandVecType::iterator S, ConstCandVecType::iterator E,
+    SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec) {
   auto MaxCostItr = S;
   unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
 
   // Don't hoist constants that have only one use.
   if (NumUses <= 1)
     return;
 
+  ConstantInt *ConstInt = MaxCostItr->ConstInt;
+  ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
   ConstantInfo ConstInfo;
-  ConstInfo.BaseConstant = MaxCostItr->ConstInt;
-  Type *Ty = ConstInfo.BaseConstant->getType();
+  ConstInfo.BaseInt = ConstInt;
+  ConstInfo.BaseExpr = ConstExpr;
+  Type *Ty = ConstInt->getType();
 
   // Rebase the constants with respect to the base constant.
   for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
-    APInt Diff = ConstCand->ConstInt->getValue() -
-                 ConstInfo.BaseConstant->getValue();
+    APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
     Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
+    Type *ConstTy =
+        ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
     ConstInfo.RebasedConstants.push_back(
-      RebasedConstantInfo(std::move(ConstCand->Uses), Offset));
+      RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
   }
-  ConstantVec.push_back(std::move(ConstInfo));
+  ConstInfoVec.push_back(std::move(ConstInfo));
 }
 
 /// Finds and combines constant candidates that can be easily
 /// rematerialized with an add from a common base constant.
-void ConstantHoistingPass::findBaseConstants() {
+void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
+  // If BaseGV is nullptr, find base among candidate constant integers;
+  // Otherwise find base among constant GEPs that share the same BaseGV.
+  ConstCandVecType &ConstCandVec = BaseGV ?
+      ConstGEPCandMap[BaseGV] : ConstIntCandVec;
+  ConstInfoVecType &ConstInfoVec = BaseGV ?
+      ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
+
   // Sort the constants by value and type. This invalidates the mapping!
   llvm::sort(ConstCandVec.begin(), ConstCandVec.end(),
              [](const ConstantCandidate &LHS, const ConstantCandidate &RHS) {
     if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
       return LHS.ConstInt->getType()->getBitWidth() <
              RHS.ConstInt->getType()->getBitWidth();
     return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
   });
if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
           // memory instruction.
           (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
            /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
            /*HasBaseReg*/true, /*Scale*/0)))
         continue;
     }
     // We either have now a different constant type or the constant is not in
     // range of an add with immediate anymore.
-    findAndMakeBaseConstant(MinValItr, CC);
+    findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
     // Start a new base constant search.
     MinValItr = CC;
   }
   // Finalize the last base constant search.
-  findAndMakeBaseConstant(MinValItr, ConstCandVec.end());
+  findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
 }
 
 /// Updates the operand at Idx in instruction Inst with the result of
 ///        instruction Mat. If the instruction is a PHI node then special
 ///        handling for duplicate values form the same incoming basic block is
 ///        required.
 /// \return The update will always succeed, but the return value indicated if
 ///         Mat was used for the update or not.
static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
   Inst->setOperand(Idx, Mat);
   return true;
 }
 
 /// Emit materialization code for all rebased constants and update their
 /// users.
 void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
                                              Constant *Offset,
+                                             Type *Ty,
                                              const ConstantUser &ConstUser) {
   Instruction *Mat = Base;
+
+  // The same offset can be dereferenced to different types in nested struct.
+  if (!Offset && Ty && Ty != Base->getType())
+    Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);
+
   if (Offset) {
     Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
                                                ConstUser.OpndIdx);
+    if (Ty) {
+      // Constant being rebased is a ConstantExpr.
+      Type *Int64Ty = Type::getInt64Ty(*Ctx);
+      Base = new PtrToIntInst(Base, Int64Ty, "base_ptrtoint", InsertionPt);
+      Mat = new SExtInst(Offset, Int64Ty, "offset_sext", InsertionPt);
+      Mat = BinaryOperator::Create(Instruction::Add, Base, Mat,
+                                 "const_mat", InsertionPt);
+      Mat = new IntToPtrInst(Mat, Ty, "mat_inttoptr", InsertionPt);
+    } else
+      // Constant being rebased is a ConstantInt.
       Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
                                  "const_mat", InsertionPt);
 
     LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
                       << " + " << *Offset << ") in BB "
                       << Mat->getParent()->getName() << '\n'
                       << *Mat << '\n');
     Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
   }
if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
     LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
     updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
     LLVM_DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
     return;
   }
 
   // Visit constant expression.
   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
+    if (ConstExpr->isGEPWithNoNotionalOverIndexing()) {
+      // Operand is a ConstantGEP, replace it.
+      updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat);
+      return;
+    }
     Instruction *ConstExprInst = ConstExpr->getAsInstruction();
     ConstExprInst->setOperand(0, Mat);
     ConstExprInst->insertBefore(findMatInsertPt(ConstUser.Inst,
                                                 ConstUser.OpndIdx));
 
     // Use the same debug location as the instruction we are about to update.
     ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
 
     LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
                       << "From              : " << *ConstExpr << '\n');
     LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
     if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
       ConstExprInst->eraseFromParent();
       if (Offset)
         Mat->eraseFromParent();
     }
     LLVM_DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
     return;
   }
 }
 
 /// Hoist and hide the base constant behind a bitcast and emit
 /// materialization code for derived constants.
-bool ConstantHoistingPass::emitBaseConstants() {
+bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
   bool MadeChange = false;
-  for (auto const &ConstInfo : ConstantVec) {
-    // Hoist and hide the base constant behind a bitcast.
+  SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec =
+      BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
+  for (auto const &ConstInfo : ConstInfoVec) {
     SmallPtrSet<Instruction *, 8> IPSet = findConstantInsertionPoint(ConstInfo);
     assert(!IPSet.empty() && "IPSet is empty");
 
     unsigned UsesNum = 0;
     unsigned ReBasesNum = 0;
     for (Instruction *IP : IPSet) {
-      IntegerType *Ty = ConstInfo.BaseConstant->getType();
-      Instruction *Base =
-          new BitCastInst(ConstInfo.BaseConstant, Ty, "const", IP);
+      Instruction *Base = nullptr;
+      // Hoist and hide the base constant behind a bitcast.
+      if (ConstInfo.BaseExpr) {
+        assert(BaseGV && "A base constant expression must have an base GV");
+        Type *Ty = ConstInfo.BaseExpr->getType();
+        Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
+      } else {
+        IntegerType *Ty = ConstInfo.BaseInt->getType();
+        Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
+      }
 
       Base->setDebugLoc(IP->getDebugLoc());
 
-      LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant
+      LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
                         << ") to BB " << IP->getParent()->getName() << '\n'
                         << *Base << '\n');
 
       // Emit materialization code for all rebased constants.
       unsigned Uses = 0;
       for (auto const &RCI : ConstInfo.RebasedConstants) {
         for (auto const &U : RCI.Uses) {
           Uses++;
           BasicBlock *OrigMatInsertBB =
               findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
           // If Base constant is to be inserted in multiple places,
           // generate rebase for U using the Base dominating U.
           if (IPSet.size() == 1 ||
               DT->dominates(Base->getParent(), OrigMatInsertBB)) {
-            emitBaseConstants(Base, RCI.Offset, U);
+            emitBaseConstants(Base, RCI.Offset, RCI.Ty, U);
             ReBasesNum++;
           }
 
-          Base->setDebugLoc(DILocation::getMergedLocation(Base->getDebugLoc(), U.Inst->getDebugLoc()));
+          Base->setDebugLoc(DILocation::getMergedLocation(
+              Base->getDebugLoc(), U.Inst->getDebugLoc()));
         }
       }
       UsesNum = Uses;
 
       // Use the same debug location as the last user of the constant.
       assert(!Base->use_empty() && "The use list is empty!?");
       assert(isa<Instruction>(Base->user_back()) &&
              "All uses should be instructions.");
     }
     (void)UsesNum;
     (void)ReBasesNum;
     // Expect all uses are rebased after rebase is done.
     assert(UsesNum == ReBasesNum && "Not all uses are rebased");
 
     NumConstantsHoisted++;
 
     // Base constant is also included in ConstInfo.RebasedConstants, so
     // deduct 1 from ConstInfo.RebasedConstants.size().
-    NumConstantsRebased = ConstInfo.RebasedConstants.size() - 1;
+    NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
 
     MadeChange = true;
   }
   return MadeChange;
 }
 
 /// Check all cast instructions we made a copy of and remove them if they
 /// have no more users.
 void ConstantHoistingPass::deleteDeadCastInst() const {
   for (auto const &I : ClonedCastMap)
     if (I.first->use_empty())
       I.first->eraseFromParent();
 }
 
 /// Optimize expensive integer constants in the given function.
 bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI,
                                    DominatorTree &DT, BlockFrequencyInfo *BFI,
                                    BasicBlock &Entry) {
   this->TTI = &TTI;
   this->DT = &DT;
   this->BFI = BFI;
+  this->DL = &Fn.getParent()->getDataLayout();
+  this->Ctx = &Fn.getContext();
   this->Entry = &Entry;
   // Collect all constant candidates.
   collectConstantCandidates(Fn);
 
-  // There are no constant candidates to worry about.
-  if (ConstCandVec.empty())
-    return false;
-
   // Combine constants that can be easily materialized with an add from a common
   // base constant.
+  if (!ConstIntCandVec.empty())
     findBaseConstants();
-
-  // There are no constants to emit.
-  if (ConstantVec.empty())
-    return false;
+  for (auto &MapEntry : ConstGEPCandMap)
+    if (!MapEntry.second.empty())
+      findBaseConstants(MapEntry.first);
 
   // Finally hoist the base constant and emit materialization code for dependent
   // constants.
-  bool MadeChange = emitBaseConstants();
+  bool MadeChange = false;
+  if (!ConstIntInfoVec.empty())
+    MadeChange = emitBaseConstants();
+  for (auto MapEntry : ConstGEPInfoMap)
+    if (!MapEntry.second.empty())
+      MadeChange |= emitBaseConstants(MapEntry.first);
+
 
   // Cleanup dead instructions.
   deleteDeadCastInst();
 
   return MadeChange;
 }
 
 PreservedAnalyses ConstantHoistingPass::run(Function &F,

test/Transforms/ConstantHoisting/AArch64/const-hoist-gep.ll

+; RUN: opt -consthoist -consthoist-gep -S -o - %s | FileCheck %s
+
+target triple = "aarch64-none--musleabi"
+
+; Check that constant gep expressions are materialized in the form of
+; (Base + Offset), where Base is a constant gep, Offset is an integer.
+; CHECK:  %const = bitcast i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 0, i32 0) to i32*
+; CHECK-NEXT:  store i32 undef, i32* %const, align 4
+; CHECK-NEXT:  %base_ptrtoint = ptrtoint i32* %const to i64
+; CHECK-NEXT:  %offset_sext = sext i32 4 to i64
+; CHECK-NEXT:  %const_mat = add i64 %base_ptrtoint, %offset_sext
+; CHECK-NEXT:  %mat_inttoptr = inttoptr i64 %const_mat to i32*
+; CHECK-NEXT:  store i32 undef, i32* %mat_inttoptr, align 4
+; CHECK-NEXT:  %base_ptrtoint1 = ptrtoint i32* %const to i64
+; CHECK-NEXT:  %offset_sext2 = sext i32 160 to i64
+; CHECK-NEXT:  %const_mat3 = add i64 %base_ptrtoint1, %offset_sext2
+; CHECK-NEXT:  %mat_inttoptr4 = inttoptr i64 %const_mat3 to i32*
+; CHECK-NEXT:  store i32 undef, i32* %mat_inttoptr4, align 4
+; CHECK-NEXT:  %base_ptrtoint5 = ptrtoint i32* %const to i64
+; CHECK-NEXT:  %offset_sext6 = sext i32 164 to i64
+; CHECK-NEXT:  %const_mat7 = add i64 %base_ptrtoint5, %offset_sext6
+; CHECK-NEXT:  %mat_inttoptr8 = inttoptr i64 %const_mat7 to i32*
+; CHECK-NEXT:  store i32 undef, i32* %mat_inttoptr8, align 4
+
+%0 = type { %1, %2, [9 x i16], %6, %7 }
+%1 = type { i32, i32, i32, i32, i32, i32, i16, i16, i8, i8, i16, i32, i32, i16, i8, i8 }
+%2 = type { i32, %3, i8, i8, i8, i8, i32, %4, %5, [16 x i8], i16, i16, i8, i8, i8, i8, i32, i32, i32 }
+%3 = type { i16, i8, i8 }
+%4 = type { i16, i8, i8 }
+%5 = type { i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8 }
+%6 = type { i8, i8 }
+%7 = type { [5 x i32], [3 x i32], [6 x i32], [3 x i32], [2 x i32], [4 x i32], [3 x i32], [2 x i32], [4 x i32], [5 x i32], [3 x i32], [6 x i32], [1 x i32], i32, i32, i32, i32, i32, i32 }
+
+@global = external dso_local local_unnamed_addr global %0, align 4
+
+define dso_local void @zot() {
+bb:
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 0, i32 0), align 4
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 0, i32 1), align 4
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 11, i32 0), align 4
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 11, i32 1), align 4
+  ret void
+}
+

test/Transforms/ConstantHoisting/ARM/const-hoist-gep.ll

+; RUN: opt -consthoist -consthoist-gep -S -o - %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv6m-none--musleabi"
+
+; Check that constant gep expressions are materialized in the form of
+; (Base + Offset), where Base is a constant gep, Offset is an integer.
+; CHECK-DAG:  %const[[C1:[0-9]?]] = bitcast i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 11, i32 0) to i32*
+; CHECK-DAG:  %const[[C2:[0-9]?]] = bitcast i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 0, i32 0) to i32*
+; CHECK:  store i32 undef, i32* %const[[C2]], align 4
+; CHECK-NEXT:  %[[INT1:[a-z0-9_]+]] = ptrtoint i32* %const[[C2]] to i64
+; CHECK-NEXT:  %[[OFF1:[a-z0-9_]+]] = sext i32 4 to i64
+; CHECK-NEXT:  %[[MAT1:[a-z0-9_]+]] = add i64 %[[INT1]], %[[OFF1]]
+; CHECK-NEXT:  %[[PTR1:[a-z0-9_]+]] = inttoptr i64 %[[MAT1]] to i32*
+; CHECK-NEXT:  store i32 undef, i32* %[[PTR1]], align 4
+; CHECK:  store i32 undef, i32* %const[[C1]], align 4
+; CHECK-NEXT:  %[[INT2:[a-z0-9_]+]] = ptrtoint i32* %const[[C1]] to i64
+; CHECK-NEXT:  %[[OFF2:[a-z0-9_]+]] = sext i32 4 to i64
+; CHECK-NEXT:  %[[MAT2:[a-z0-9_]+]] = add i64 %[[INT2]], %[[OFF2]]
+; CHECK-NEXT:  %[[PTR2:[a-z0-9_]+]] = inttoptr i64 %[[MAT2]] to i32*
+; CHECK-NEXT:  store i32 undef, i32* %[[PTR2]], align 4
+
+%0 = type { %1, %2, [9 x i16], %6, %7 }
+%1 = type { i32, i32, i32, i32, i32, i32, i16, i16, i8, i8, i16, i32, i32, i16, i8, i8 }
+%2 = type { i32, %3, i8, i8, i8, i8, i32, %4, %5, [16 x i8], i16, i16, i8, i8, i8, i8, i32, i32, i32 }
+%3 = type { i16, i8, i8 }
+%4 = type { i16, i8, i8 }
+%5 = type { i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8 }
+%6 = type { i8, i8 }
+%7 = type { [5 x i32], [3 x i32], [6 x i32], [3 x i32], [2 x i32], [4 x i32], [3 x i32], [2 x i32], [4 x i32], [5 x i32], [3 x i32], [6 x i32], [1 x i32], i32, i32, i32, i32, i32, i32 }
+
+@global = external dso_local local_unnamed_addr global %0, align 4
+
+define dso_local void @zot() {
+bb:
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 0, i32 0), align 4
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 0, i32 1), align 4
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 11, i32 0), align 4
+  store i32 undef, i32* getelementptr inbounds (%0, %0* @global, i32 0, i32 4, i32 11, i32 1), align 4
+  ret void
+}
+

test/Transforms/ConstantHoisting/ARM/same-offset-multi-types.ll

+; RUN: opt -consthoist -consthoist-gep -S -o - %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv6m-none--musleabi"
+
+; Check that for the same offset from the base constant, different types are materialized separately.
+; CHECK: %const = bitcast %5** getelementptr inbounds (%0, %0* @global, i32 0, i32 2, i32 0) to %5**
+; CHECK: %tmp = load %5*, %5** %const, align 4
+; CHECK: %base_ptrtoint = ptrtoint %5** %const to i64
+; CHECK: %offset_sext = sext i32 0 to i64
+; CHECK: %const_mat = add i64 %base_ptrtoint, %offset_sext
+; CHECK: %mat_inttoptr = inttoptr i64 %const_mat to %4*
+; CHECK: tail call void undef(%5* nonnull %tmp, %4* %mat_inttoptr)
+
+
+%0 = type { [16 x %1], %2, %4, [16 x %5], %6, %7, i32, [4 x i32], [8 x %3], i8, i8, i8, i8, i8, i8, i8, %8, %11, %11*, i32, i16, i8, i8, i8, i8, i8, i8, [15 x i16], i8, i8, [23 x %12], i8, i8*, i8, %13, i8, i8 }
+%1 = type { i32, i32, i8, i8, i8, i8, i8, i8, i8, i8 }
+%2 = type { %3*, i16, i16, i16 }
+%3 = type { [4 x i32] }
+%4 = type { %5*, %5*, i8 }
+%5 = type { [4 x i32], i8*, i8, i8 }
+%6 = type { i8, [4 x i32] }
+%7 = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
+%8 = type { [16 x %9], %9*, %9*, %9*, %9*, %11, %11, %11, i8, i8, i8, i8 }
+%9 = type { %1, %11, %11, %9*, %9*, %10, i8, i8, i8, i8 }
+%10 = type { i32, i16 }
+%11 = type { %11*, %11* }
+%12 = type { i8, i16, i32 }
+%13 = type { i32, i32, i8 }
+
+@global = external dso_local global %0, align 4
+
+; Function Attrs: nounwind optsize ssp
+define dso_local void @zot() {
+bb:
+  br i1 undef, label %bb2, label %bb1
+
+bb1:                                              ; preds = %bb
+  %tmp = load %5*, %5** getelementptr inbounds (%0, %0* @global, i32 0, i32 2, i32 0), align 4
+  tail call void undef(%5* nonnull %tmp, %4* getelementptr inbounds (%0, %0* @global, i32 0, i32 2))
+  unreachable
+
+bb2:                                              ; preds = %bb
+  ret void
+}
+