[ConstantHoisting] stop rematerializing InsertionPt

[nickdesaulniers]

Summary

Reading this code, I noticed that we call findMatInsertPt a lot, for the
same inputs. Calculate it once and save the result.

[MaskRay]

LGTM, it seems that findMatInsertPt is somewhat complex and avoiding the recomputation is nice.

[nickdesaulniers]

• rebase

[nickdesaulniers]

• rebase

llvm/include/llvm/Transforms/Scalar/ConstantHoisting.h

 // simple (this means not nested) constant cast expressions. For example:
 // %0 = load i64* inttoptr (i64 big_constant to i64*)
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include <algorithm>
 #include <vector>
private:
   using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
   using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>;
   ConstInfoVecType ConstIntInfoVec;
   GVInfoVecMapType ConstGEPInfoMap;
 
   /// Keep track of cast instructions we already cloned.
   MapVector<Instruction *, Instruction *> ClonedCastMap;
 
+  void collectMatInsertPts(
+      const consthoist::RebasedConstantListType &RebasedConstants,
+      SmallVectorImpl<Instruction *> &MatInsertPts) const;
   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
   SetVector<Instruction *>
-  findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
+  findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo,
+                             const ArrayRef<Instruction *> MatInsertPts) 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);

llvm/lib/Transforms/Scalar/ConstantHoisting.cpp

bool MadeChange =
                    Fn.getEntryBlock(),
                    &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
 
   LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
 
   return MadeChange;
 }
 
+void ConstantHoistingPass::collectMatInsertPts(
+    const RebasedConstantListType &RebasedConstants,
+    SmallVectorImpl<Instruction *> &MatInsertPts) const {
+  for (const RebasedConstantInfo &RCI : RebasedConstants)
+    for (const ConstantUser &U : RCI.Uses)
+      MatInsertPts.emplace_back(findMatInsertPt(U.Inst, U.OpndIdx));
+}
+
 /// Find the constant materialization insertion point.
 Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
                                                    unsigned Idx) const {
   // If the operand is a cast instruction, then we have to materialize the
   // constant before the cast instruction.
   if (Idx != ~0U) {
     Value *Opnd = Inst->getOperand(Idx);
     if (auto CastInst = dyn_cast<Instruction>(Opnd))
if (NodeInBBs ||
       ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
       ParentPtsFreq += InsertPtsFreq;
     }
   }
 }
 
 /// Find an insertion point that dominates all uses.
 SetVector<Instruction *> ConstantHoistingPass::findConstantInsertionPoint(
-    const ConstantInfo &ConstInfo) const {
+    const ConstantInfo &ConstInfo,
+    const ArrayRef<Instruction *> MatInsertPts) const {
   assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
   // Collect all basic blocks.
   SetVector<BasicBlock *> BBs;
   SetVector<Instruction *> InsertPts;
-  for (auto const &RCI : ConstInfo.RebasedConstants)
-    for (auto const &U : RCI.Uses)
-      BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
+
+  for (Instruction *MatInsertPt : MatInsertPts)
+    BBs.insert(MatInsertPt->getParent());
 
   if (BBs.count(Entry)) {
     InsertPts.insert(&Entry->front());
     return InsertPts;
   }
 
   if (BFI) {
     findBestInsertionSet(*DT, *BFI, Entry, BBs);
void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
                                              UserAdjustment *Adj) {
   Instruction *Mat = Base;
 
   // The same offset can be dereferenced to different types in nested struct.
   if (!Adj->Offset && Adj->Ty && Adj->Ty != Base->getType())
     Adj->Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);
 
   if (Adj->Offset) {
-    Instruction *InsertionPt =
-        findMatInsertPt(Adj->User.Inst, Adj->User.OpndIdx);
     if (Adj->Ty) {
       // Constant being rebased is a ConstantExpr.
       PointerType *Int8PtrTy = Type::getInt8PtrTy(
           *Ctx, cast<PointerType>(Adj->Ty)->getAddressSpace());
-      Base = new BitCastInst(Base, Int8PtrTy, "base_bitcast", InsertionPt);
+      Base = new BitCastInst(Base, Int8PtrTy, "base_bitcast", Adj->MatInsertPt);
       Mat = GetElementPtrInst::Create(Type::getInt8Ty(*Ctx), Base, Adj->Offset,
-                                      "mat_gep", InsertionPt);
-      Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast", InsertionPt);
+                                      "mat_gep", Adj->MatInsertPt);
+      Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast", Adj->MatInsertPt);
     } else
       // Constant being rebased is a ConstantInt.
       Mat = BinaryOperator::Create(Instruction::Add, Base, Adj->Offset,
-                                   "const_mat", InsertionPt);
+                                   "const_mat", Adj->MatInsertPt);
 
     LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
                       << " + " << *Adj->Offset << ") in BB "
                       << Mat->getParent()->getName() << '\n'
                       << *Mat << '\n');
     Mat->setDebugLoc(Adj->User.Inst->getDebugLoc());
   }
   Value *Opnd = Adj->User.Inst->getOperand(Adj->User.OpndIdx);
if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
     if (isa<GEPOperator>(ConstExpr)) {
       // Operand is a ConstantGEP, replace it.
       updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat);
       return;
     }
 
     // Aside from constant GEPs, only constant cast expressions are collected.
     assert(ConstExpr->isCast() && "ConstExpr should be a cast");
-    Instruction *ConstExprInst = ConstExpr->getAsInstruction(
-        findMatInsertPt(Adj->User.Inst, Adj->User.OpndIdx));
+    Instruction *ConstExprInst = ConstExpr->getAsInstruction(Adj->MatInsertPt);
     ConstExprInst->setOperand(0, Mat);
 
     // Use the same debug location as the instruction we are about to update.
     ConstExprInst->setDebugLoc(Adj->User.Inst->getDebugLoc());
 
     LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
                       << "From              : " << *ConstExpr << '\n');
     LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
     if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ConstExprInst)) {
       ConstExprInst->eraseFromParent();
       if (Adj->Offset)
         Mat->eraseFromParent();
     }
     LLVM_DEBUG(dbgs() << "To    : " << *Adj->User.Inst << '\n');
     return;
   }
 }
 
 /// Hoist and hide the base constant behind a bitcast and emit
 /// materialization code for derived constants.
 bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
   bool MadeChange = false;
   SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec =
       BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
-  for (auto const &ConstInfo : ConstInfoVec) {
-    SetVector<Instruction *> IPSet = findConstantInsertionPoint(ConstInfo);
+  for (const consthoist::ConstantInfo &ConstInfo : ConstInfoVec) {
+    SmallVector<Instruction *, 4> MatInsertPts;
+    collectMatInsertPts(ConstInfo.RebasedConstants, MatInsertPts);
+    SetVector<Instruction *> IPSet =
+        findConstantInsertionPoint(ConstInfo, MatInsertPts);
     // We can have an empty set if the function contains unreachable blocks.
     if (IPSet.empty())
       continue;
 
     unsigned UsesNum = 0;
     unsigned ReBasesNum = 0;
     unsigned NotRebasedNum = 0;
     for (Instruction *IP : IPSet) {
       // First, collect constants depending on this IP of the base.
       UsesNum = 0;
       SmallVector<UserAdjustment, 4> ToBeRebased;
+      unsigned MatCtr = 0;
       for (auto const &RCI : ConstInfo.RebasedConstants) {
         UsesNum += RCI.Uses.size();
         for (auto const &U : RCI.Uses) {
-          BasicBlock *OrigMatInsertBB =
-              findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
+          Instruction *MatInsertPt = MatInsertPts[MatCtr++];
+          BasicBlock *OrigMatInsertBB = MatInsertPt->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(IP->getParent(), OrigMatInsertBB))
-            ToBeRebased.emplace_back(RCI.Offset, RCI.Ty, U);
+            ToBeRebased.emplace_back(RCI.Offset, RCI.Ty, MatInsertPt, U);
         }
       }
 
       // If only few constants depend on this IP of base, skip rebasing,
       // assuming the base and the rebased have the same materialization cost.
       if (ToBeRebased.size() < MinNumOfDependentToRebase) {
         NotRebasedNum += ToBeRebased.size();
         continue;