// certain transformations on them, which would create a new expensive constant.
//
// This optimization is only applied to integer constants in instructions and
-// simple (this means not nested) constant cast experessions. For example:
+// simple (this means not nested) constant cast expressions. For example:
// %0 = load i64* inttoptr (i64 big_constant to i64*)
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "consthoist"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Pass.h"
-#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <tuple>
using namespace llvm;
+#define DEBUG_TYPE "consthoist"
+
STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
STATISTIC(NumConstantsRebased, "Number of constants rebased");
-
namespace {
-typedef SmallVector<User *, 4> ConstantUseListType;
+struct ConstantUser;
+struct RebasedConstantInfo;
+
+typedef SmallVector<ConstantUser, 8> ConstantUseListType;
+typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
+
+/// \brief 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) { }
+};
+
+/// \brief Keeps track of a constant candidate and its uses.
struct ConstantCandidate {
+ ConstantUseListType Uses;
+ ConstantInt *ConstInt;
unsigned CumulativeCost;
+
+ ConstantCandidate(ConstantInt *ConstInt)
+ : ConstInt(ConstInt), CumulativeCost(0) { }
+
+ /// \brief 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));
+ }
+};
+
+/// \brief 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;
+
+ RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
+ : Uses(std::move(Uses)), Offset(Offset) { }
};
+/// \brief A base constant and all its rebased constants.
struct ConstantInfo {
ConstantInt *BaseConstant;
- struct RebasedConstantInfo {
- ConstantInt *OriginalConstant;
- Constant *Offset;
- ConstantUseListType Uses;
- };
- typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
RebasedConstantListType RebasedConstants;
};
+/// \brief The constant hoisting pass.
class ConstantHoisting : public FunctionPass {
+ typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType;
+ typedef std::vector<ConstantCandidate> ConstCandVecType;
+
const TargetTransformInfo *TTI;
DominatorTree *DT;
+ BasicBlock *Entry;
- /// Keeps track of expensive constants found in the function.
- typedef MapVector<ConstantInt *, ConstantCandidate> ConstantMapType;
- ConstantMapType ConstantMap;
+ /// Keeps track of constant candidates found in the function.
+ ConstCandVecType ConstCandVec;
+
+ /// Keep track of cast instructions we already cloned.
+ SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
/// These are the final constants we decided to hoist.
- SmallVector<ConstantInfo, 4> Constants;
+ SmallVector<ConstantInfo, 8> ConstantVec;
public:
static char ID; // Pass identification, replacement for typeid
- ConstantHoisting() : FunctionPass(ID), TTI(0) {
+ ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr),
+ Entry(nullptr) {
initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
}
- bool runOnFunction(Function &F);
+ bool runOnFunction(Function &Fn) override;
- const char *getPassName() const { return "Constant Hoisting"; }
+ const char *getPassName() const override { return "Constant Hoisting"; }
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
- AU.addRequired<TargetTransformInfo>();
+ AU.addRequired<TargetTransformInfoWrapperPass>();
}
private:
- void CollectConstant(User *U, unsigned Opcode, Intrinsic::ID IID,
- ConstantInt *C);
- void CollectConstants(Instruction *I);
- void CollectConstants(Function &F);
- void FindAndMakeBaseConstant(ConstantMapType::iterator S,
- ConstantMapType::iterator E);
- void FindBaseConstants();
- Instruction *FindConstantInsertionPoint(Function &F,
- const ConstantInfo &CI) const;
- void EmitBaseConstants(Function &F, User *U, Instruction *Base,
- Constant *Offset, ConstantInt *OriginalConstant);
- bool EmitBaseConstants(Function &F);
- bool OptimizeConstants(Function &F);
+ /// \brief Initialize the pass.
+ void setup(Function &Fn) {
+ DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn);
+ Entry = &Fn.getEntryBlock();
+ }
+
+ /// \brief Cleanup.
+ void cleanup() {
+ ConstantVec.clear();
+ ClonedCastMap.clear();
+ ConstCandVec.clear();
+
+ TTI = nullptr;
+ DT = nullptr;
+ Entry = nullptr;
+ }
+
+ Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
+ Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const;
+ void collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst, unsigned Idx,
+ ConstantInt *ConstInt);
+ void collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst);
+ void collectConstantCandidates(Function &Fn);
+ void findAndMakeBaseConstant(ConstCandVecType::iterator S,
+ ConstCandVecType::iterator E);
+ void findBaseConstants();
+ void emitBaseConstants(Instruction *Base, Constant *Offset,
+ const ConstantUser &ConstUser);
+ bool emitBaseConstants();
+ void deleteDeadCastInst() const;
+ bool optimizeConstants(Function &Fn);
};
}
INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
false, false)
}
/// \brief Perform the constant hoisting optimization for the given function.
-bool ConstantHoisting::runOnFunction(Function &F) {
- DEBUG(dbgs() << "********** Constant Hoisting **********\n");
- DEBUG(dbgs() << "********** Function: " << F.getName() << '\n');
+bool ConstantHoisting::runOnFunction(Function &Fn) {
+ if (skipOptnoneFunction(Fn))
+ return false;
+
+ DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
+ DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
+
+ setup(Fn);
+
+ bool MadeChange = optimizeConstants(Fn);
+
+ if (MadeChange) {
+ DEBUG(dbgs() << "********** Function after Constant Hoisting: "
+ << Fn.getName() << '\n');
+ DEBUG(dbgs() << Fn);
+ }
+ DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
+
+ cleanup();
- DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- TTI = &getAnalysis<TargetTransformInfo>();
+ return MadeChange;
+}
+
+
+/// \brief Find the constant materialization insertion point.
+Instruction *ConstantHoisting::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 (CastInst->isCast())
+ return CastInst;
+ }
+
+ // The simple and common case. This also includes constant expressions.
+ if (!isa<PHINode>(Inst) && !Inst->isEHPad())
+ return Inst;
- return OptimizeConstants(F);
+ // We can't insert directly before a phi node or an eh pad. Insert before
+ // the terminator of the incoming or dominating block.
+ assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
+ if (Idx != ~0U && isa<PHINode>(Inst))
+ return cast<PHINode>(Inst)->getIncomingBlock(Idx)->getTerminator();
+
+ BasicBlock *IDom = DT->getNode(Inst->getParent())->getIDom()->getBlock();
+ return IDom->getTerminator();
}
-void ConstantHoisting::CollectConstant(User * U, unsigned Opcode,
- Intrinsic::ID IID, ConstantInt *C) {
+/// \brief Find an insertion point that dominates all uses.
+Instruction *ConstantHoisting::
+findConstantInsertionPoint(const ConstantInfo &ConstInfo) const {
+ assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
+ // Collect all basic blocks.
+ SmallPtrSet<BasicBlock *, 8> BBs;
+ for (auto const &RCI : ConstInfo.RebasedConstants)
+ for (auto const &U : RCI.Uses)
+ BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
+
+ if (BBs.count(Entry))
+ return &Entry->front();
+
+ while (BBs.size() >= 2) {
+ BasicBlock *BB, *BB1, *BB2;
+ BB1 = *BBs.begin();
+ BB2 = *std::next(BBs.begin());
+ BB = DT->findNearestCommonDominator(BB1, BB2);
+ if (BB == Entry)
+ return &Entry->front();
+ BBs.erase(BB1);
+ BBs.erase(BB2);
+ BBs.insert(BB);
+ }
+ assert((BBs.size() == 1) && "Expected only one element.");
+ Instruction &FirstInst = (*BBs.begin())->front();
+ return findMatInsertPt(&FirstInst);
+}
+
+
+/// \brief 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.
+void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst,
+ unsigned Idx,
+ ConstantInt *ConstInt) {
unsigned Cost;
- if (Opcode)
- Cost = TTI->getIntImmCost(Opcode, C->getValue(), C->getType());
+ // 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(IID, C->getValue(), C->getType());
+ Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(),
+ ConstInt->getType());
+ // Ignore cheap integer constants.
if (Cost > TargetTransformInfo::TCC_Basic) {
- ConstantCandidate &CC = ConstantMap[C];
- CC.CumulativeCost += Cost;
- CC.Uses.push_back(U);
- DEBUG(dbgs() << "Collect constant " << *C << " with cost " << Cost
- << " from " << *U << '\n');
+ ConstCandMapType::iterator Itr;
+ bool Inserted;
+ std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(ConstInt, 0));
+ if (Inserted) {
+ ConstCandVec.push_back(ConstantCandidate(ConstInt));
+ Itr->second = ConstCandVec.size() - 1;
+ }
+ ConstCandVec[Itr->second].addUser(Inst, Idx, Cost);
+ 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';
+ );
}
}
-/// \brief Scan the instruction or constant expression for expensive integer
-/// constants and record them in the constant map.
-void ConstantHoisting::CollectConstants(Instruction *I) {
- unsigned Opcode = 0;
- Intrinsic::ID IID = Intrinsic::not_intrinsic;
- if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
- IID = II->getIntrinsicID();
- else
- Opcode = I->getOpcode();
+/// \brief Scan the instruction for expensive integer constants and record them
+/// in the constant candidate vector.
+void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst) {
+ // Skip all cast instructions. They are visited indirectly later on.
+ if (Inst->isCast())
+ return;
+
+ // Can't handle inline asm. Skip it.
+ if (auto Call = dyn_cast<CallInst>(Inst))
+ if (isa<InlineAsm>(Call->getCalledValue()))
+ return;
// Scan all operands.
- for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) {
- if (ConstantInt *C = dyn_cast<ConstantInt>(O)) {
- CollectConstant(I, Opcode, IID, C);
+ for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
+ Value *Opnd = Inst->getOperand(Idx);
+
+ // Visit constant integers.
+ if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
+ collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
continue;
}
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(O)) {
- // We only handle constant cast expressions.
- if (!CE->isCast())
+
+ // Visit cast instructions that have constant integers.
+ if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
+ // Only visit cast instructions, which have been skipped. All other
+ // instructions should have already been visited.
+ if (!CastInst->isCast())
continue;
- if (ConstantInt *C = dyn_cast<ConstantInt>(CE->getOperand(0))) {
- // Ignore the cast expression and use the opcode of the instruction.
- CollectConstant(CE, Opcode, IID, C);
+ if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
+ // Pretend the constant is directly used by the instruction and ignore
+ // the cast instruction.
+ collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
continue;
}
}
- }
+
+ // Visit constant expressions that have constant integers.
+ if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
+ // Only visit constant cast expressions.
+ if (!ConstExpr->isCast())
+ continue;
+
+ 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);
+ continue;
+ }
+ }
+ } // end of for all operands
}
/// \brief Collect all integer constants in the function that cannot be folded
/// into an instruction itself.
-void ConstantHoisting::CollectConstants(Function &F) {
- for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
- for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
- CollectConstants(I);
-}
-
-/// \brief Compare function for sorting integer constants by type and by value
-/// within a type in ConstantMaps.
-static bool
-ConstantMapLessThan(const std::pair<ConstantInt *, ConstantCandidate> &LHS,
- const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
- if (LHS.first->getType() == RHS.first->getType())
- return LHS.first->getValue().ult(RHS.first->getValue());
- else
- return LHS.first->getType()->getBitWidth() <
- RHS.first->getType()->getBitWidth();
+void ConstantHoisting::collectConstantCandidates(Function &Fn) {
+ ConstCandMapType ConstCandMap;
+ for (BasicBlock &BB : Fn)
+ for (Instruction &Inst : BB)
+ collectConstantCandidates(ConstCandMap, &Inst);
}
/// \brief Find the base constant within the given range and rebase all other
/// constants with respect to the base constant.
-void ConstantHoisting::FindAndMakeBaseConstant(ConstantMapType::iterator S,
- ConstantMapType::iterator E) {
- ConstantMapType::iterator MaxCostItr = S;
+void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S,
+ ConstCandVecType::iterator E) {
+ auto MaxCostItr = S;
unsigned NumUses = 0;
// Use the constant that has the maximum cost as base constant.
- for (ConstantMapType::iterator I = S; I != E; ++I) {
- NumUses += I->second.Uses.size();
- if (I->second.CumulativeCost > MaxCostItr->second.CumulativeCost)
- MaxCostItr = I;
+ for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
+ NumUses += ConstCand->Uses.size();
+ if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
+ MaxCostItr = ConstCand;
}
// Don't hoist constants that have only one use.
if (NumUses <= 1)
return;
- ConstantInfo CI;
- CI.BaseConstant = MaxCostItr->first;
- Type *Ty = CI.BaseConstant->getType();
+ ConstantInfo ConstInfo;
+ ConstInfo.BaseConstant = MaxCostItr->ConstInt;
+ Type *Ty = ConstInfo.BaseConstant->getType();
+
// Rebase the constants with respect to the base constant.
- for (ConstantMapType::iterator I = S; I != E; ++I) {
- APInt Diff = I->first->getValue() - CI.BaseConstant->getValue();
- ConstantInfo::RebasedConstantInfo RCI;
- RCI.OriginalConstant = I->first;
- RCI.Offset = ConstantInt::get(Ty, Diff);
- RCI.Uses = llvm_move(I->second.Uses);
- CI.RebasedConstants.push_back(RCI);
+ for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
+ APInt Diff = ConstCand->ConstInt->getValue() -
+ ConstInfo.BaseConstant->getValue();
+ Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
+ ConstInfo.RebasedConstants.push_back(
+ RebasedConstantInfo(std::move(ConstCand->Uses), Offset));
}
- Constants.push_back(CI);
+ ConstantVec.push_back(std::move(ConstInfo));
}
-/// \brief Finds and combines constants that can be easily rematerialized with
-/// an add from a common base constant.
-void ConstantHoisting::FindBaseConstants() {
- // Sort the constants by value and type. This invalidates the mapping.
- std::sort(ConstantMap.begin(), ConstantMap.end(), ConstantMapLessThan);
-
- // Simple linear scan through the sorted constant map for viable merge
- // candidates.
- ConstantMapType::iterator MinValItr = ConstantMap.begin();
- for (ConstantMapType::iterator I = llvm::next(ConstantMap.begin()),
- E = ConstantMap.end(); I != E; ++I) {
- if (MinValItr->first->getType() == I->first->getType()) {
+/// \brief Finds and combines constant candidates that can be easily
+/// rematerialized with an add from a common base constant.
+void ConstantHoisting::findBaseConstants() {
+ // Sort the constants by value and type. This invalidates the mapping!
+ std::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());
+ });
+
+ // Simple linear scan through the sorted constant candidate vector for viable
+ // merge candidates.
+ auto MinValItr = ConstCandVec.begin();
+ for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
+ CC != E; ++CC) {
+ if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
// Check if the constant is in range of an add with immediate.
- APInt Diff = I->first->getValue() - MinValItr->first->getValue();
+ APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
if ((Diff.getBitWidth() <= 64) &&
TTI->isLegalAddImmediate(Diff.getSExtValue()))
continue;
}
// We either have now a different constant type or the constant is not in
// range of an add with immediate anymore.
- FindAndMakeBaseConstant(MinValItr, I);
+ findAndMakeBaseConstant(MinValItr, CC);
// Start a new base constant search.
- MinValItr = I;
+ MinValItr = CC;
}
// Finalize the last base constant search.
- FindAndMakeBaseConstant(MinValItr, ConstantMap.end());
-}
-
-/// \brief Records the basic block of the instruction or all basic blocks of the
-/// users of the constant expression.
-static void CollectBasicBlocks(SmallPtrSet<BasicBlock *, 4> &BBs, Function &F,
- User *U) {
- if (Instruction *I = dyn_cast<Instruction>(U))
- BBs.insert(I->getParent());
- else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U))
- // Find all users of this constant expression.
- for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
- UU != E; ++UU)
- // Only record users that are instructions. We don't want to go down a
- // nested constant expression chain. Also check if the instruction is even
- // in the current function.
- if (Instruction *I = dyn_cast<Instruction>(*UU))
- if(I->getParent()->getParent() == &F)
- BBs.insert(I->getParent());
+ findAndMakeBaseConstant(MinValItr, ConstCandVec.end());
}
-/// \brief Find the instruction we should insert the constant materialization
-/// before.
-static Instruction *getMatInsertPt(Instruction *I, const DominatorTree *DT) {
- if (!isa<PHINode>(I) && !isa<LandingPadInst>(I)) // Simple case.
- return I;
-
- // We can't insert directly before a phi node or landing pad. Insert before
- // the terminator of the dominating block.
- assert(&I->getParent()->getParent()->getEntryBlock() != I->getParent() &&
- "PHI or landing pad in entry block!");
- BasicBlock *IDom = DT->getNode(I->getParent())->getIDom()->getBlock();
- return IDom->getTerminator();
-}
-
-/// \brief Find an insertion point that dominates all uses.
-Instruction *ConstantHoisting::
-FindConstantInsertionPoint(Function &F, const ConstantInfo &CI) const {
- BasicBlock *Entry = &F.getEntryBlock();
-
- // Collect all basic blocks.
- SmallPtrSet<BasicBlock *, 4> BBs;
- ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE;
- for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end();
- RCI != RCE; ++RCI)
- for (SmallVectorImpl<User *>::const_iterator U = RCI->Uses.begin(),
- E = RCI->Uses.end(); U != E; ++U)
- CollectBasicBlocks(BBs, F, *U);
-
- if (BBs.count(Entry))
- return getMatInsertPt(&Entry->front(), DT);
-
- while (BBs.size() >= 2) {
- BasicBlock *BB, *BB1, *BB2;
- BB1 = *BBs.begin();
- BB2 = *llvm::next(BBs.begin());
- BB = DT->findNearestCommonDominator(BB1, BB2);
- if (BB == Entry)
- return getMatInsertPt(&Entry->front(), DT);
- BBs.erase(BB1);
- BBs.erase(BB2);
- BBs.insert(BB);
+/// \brief 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 incomming 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) {
+ if (auto PHI = dyn_cast<PHINode>(Inst)) {
+ // Check if any previous operand of the PHI node has the same incoming basic
+ // block. This is a very odd case that happens when the incoming basic block
+ // has a switch statement. In this case use the same value as the previous
+ // operand(s), otherwise we will fail verification due to different values.
+ // The values are actually the same, but the variable names are different
+ // and the verifier doesn't like that.
+ BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
+ for (unsigned i = 0; i < Idx; ++i) {
+ if (PHI->getIncomingBlock(i) == IncomingBB) {
+ Value *IncomingVal = PHI->getIncomingValue(i);
+ Inst->setOperand(Idx, IncomingVal);
+ return false;
+ }
+ }
}
- assert((BBs.size() == 1) && "Expected only one element.");
- Instruction &FirstInst = (*BBs.begin())->front();
- return getMatInsertPt(&FirstInst, DT);
+
+ Inst->setOperand(Idx, Mat);
+ return true;
}
/// \brief Emit materialization code for all rebased constants and update their
/// users.
-void ConstantHoisting::EmitBaseConstants(Function &F, User *U,
- Instruction *Base, Constant *Offset,
- ConstantInt *OriginalConstant) {
- if (Instruction *I = dyn_cast<Instruction>(U)) {
- Instruction *Mat = Base;
- if (!Offset->isNullValue()) {
- Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
- "const_mat", getMatInsertPt(I, DT));
-
- // Use the same debug location as the instruction we are about to update.
- Mat->setDebugLoc(I->getDebugLoc());
-
- DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
- << " + " << *Offset << ") in BB "
- << I->getParent()->getName() << '\n' << *Mat << '\n');
- }
- DEBUG(dbgs() << "Update: " << *I << '\n');
- I->replaceUsesOfWith(OriginalConstant, Mat);
- DEBUG(dbgs() << "To: " << *I << '\n');
+void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset,
+ const ConstantUser &ConstUser) {
+ Instruction *Mat = Base;
+ if (Offset) {
+ Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
+ ConstUser.OpndIdx);
+ Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
+ "const_mat", InsertionPt);
+
+ DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
+ << " + " << *Offset << ") in BB "
+ << Mat->getParent()->getName() << '\n' << *Mat << '\n');
+ Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
+ }
+ Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
+
+ // Visit constant integer.
+ if (isa<ConstantInt>(Opnd)) {
+ DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
+ if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
+ Mat->eraseFromParent();
+ DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
return;
}
- assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
- ConstantExpr *CE = cast<ConstantExpr>(U);
- SmallVector<std::pair<Instruction *, Instruction *>, 8> WorkList;
- DEBUG(dbgs() << "Visit ConstantExpr " << *CE << '\n');
- for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
- UU != E; ++UU) {
- DEBUG(dbgs() << "Check user "; UU->print(dbgs()); dbgs() << '\n');
- // We only handel instructions here and won't walk down a ConstantExpr chain
- // to replace all ConstExpr with instructions.
- if (Instruction *I = dyn_cast<Instruction>(*UU)) {
- // Only update constant expressions in the current function.
- if (I->getParent()->getParent() != &F) {
- DEBUG(dbgs() << "Not in the same function - skip.\n");
- continue;
- }
-
- Instruction *Mat = Base;
- Instruction *InsertBefore = getMatInsertPt(I, DT);
- if (!Offset->isNullValue()) {
- Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
- "const_mat", InsertBefore);
- // Use the same debug location as the instruction we are about to
- // update.
- Mat->setDebugLoc(I->getDebugLoc());
-
- DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
- << " + " << *Offset << ") in BB "
- << I->getParent()->getName() << '\n' << *Mat << '\n');
- }
- Instruction *ICE = CE->getAsInstruction();
- ICE->replaceUsesOfWith(OriginalConstant, Mat);
- ICE->insertBefore(InsertBefore);
+ // Visit cast instruction.
+ if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
+ assert(CastInst->isCast() && "Expected an cast instruction!");
+ // Check if we already have visited this cast instruction before to avoid
+ // unnecessary cloning.
+ Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
+ if (!ClonedCastInst) {
+ ClonedCastInst = CastInst->clone();
+ ClonedCastInst->setOperand(0, Mat);
+ ClonedCastInst->insertAfter(CastInst);
+ // Use the same debug location as the original cast instruction.
+ ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
+ DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
+ << "To : " << *ClonedCastInst << '\n');
+ }
- // Use the same debug location as the instruction we are about to update.
- ICE->setDebugLoc(I->getDebugLoc());
+ DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
+ updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
+ DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
+ return;
+ }
- WorkList.push_back(std::make_pair(I, ICE));
- } else {
- DEBUG(dbgs() << "Not an instruction - skip.\n");
+ // Visit constant expression.
+ if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
+ 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());
+
+ DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
+ << "From : " << *ConstExpr << '\n');
+ DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
+ if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
+ ConstExprInst->eraseFromParent();
+ if (Offset)
+ Mat->eraseFromParent();
}
- }
- SmallVectorImpl<std::pair<Instruction *, Instruction *> >::iterator I, E;
- for (I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
- DEBUG(dbgs() << "Create instruction: " << *I->second << '\n');
- DEBUG(dbgs() << "Update: " << *I->first << '\n');
- I->first->replaceUsesOfWith(CE, I->second);
- DEBUG(dbgs() << "To: " << *I->first << '\n');
+ DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
+ return;
}
}
/// \brief Hoist and hide the base constant behind a bitcast and emit
/// materialization code for derived constants.
-bool ConstantHoisting::EmitBaseConstants(Function &F) {
+bool ConstantHoisting::emitBaseConstants() {
bool MadeChange = false;
- SmallVectorImpl<ConstantInfo>::iterator CI, CE;
- for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
+ for (auto const &ConstInfo : ConstantVec) {
// Hoist and hide the base constant behind a bitcast.
- Instruction *IP = FindConstantInsertionPoint(F, *CI);
- IntegerType *Ty = CI->BaseConstant->getType();
- Instruction *Base = new BitCastInst(CI->BaseConstant, Ty, "const", IP);
- DEBUG(dbgs() << "Hoist constant (" << *CI->BaseConstant << ") to BB "
- << IP->getParent()->getName() << '\n');
+ Instruction *IP = findConstantInsertionPoint(ConstInfo);
+ IntegerType *Ty = ConstInfo.BaseConstant->getType();
+ Instruction *Base =
+ new BitCastInst(ConstInfo.BaseConstant, Ty, "const", IP);
+ DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant << ") to BB "
+ << IP->getParent()->getName() << '\n' << *Base << '\n');
NumConstantsHoisted++;
// Emit materialization code for all rebased constants.
- ConstantInfo::RebasedConstantListType::iterator RCI, RCE;
- for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end();
- RCI != RCE; ++RCI) {
+ for (auto const &RCI : ConstInfo.RebasedConstants) {
NumConstantsRebased++;
- for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
- E = RCI->Uses.end(); U != E; ++U)
- EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
+ for (auto const &U : RCI.Uses)
+ emitBaseConstants(Base, RCI.Offset, U);
}
// 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->use_back()) &&
+ assert(isa<Instruction>(Base->user_back()) &&
"All uses should be instructions.");
- Base->setDebugLoc(cast<Instruction>(Base->use_back())->getDebugLoc());
+ Base->setDebugLoc(cast<Instruction>(Base->user_back())->getDebugLoc());
// Correct for base constant, which we counted above too.
NumConstantsRebased--;
return MadeChange;
}
-/// \brief Optimize expensive integer constants in the given function.
-bool ConstantHoisting::OptimizeConstants(Function &F) {
- bool MadeChange = false;
+/// \brief Check all cast instructions we made a copy of and remove them if they
+/// have no more users.
+void ConstantHoisting::deleteDeadCastInst() const {
+ for (auto const &I : ClonedCastMap)
+ if (I.first->use_empty())
+ I.first->eraseFromParent();
+}
+/// \brief Optimize expensive integer constants in the given function.
+bool ConstantHoisting::optimizeConstants(Function &Fn) {
// Collect all constant candidates.
- CollectConstants(F);
+ collectConstantCandidates(Fn);
- // There are no constants to worry about.
- if (ConstantMap.empty())
- return MadeChange;
+ // 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.
- FindBaseConstants();
+ findBaseConstants();
+
+ // There are no constants to emit.
+ if (ConstantVec.empty())
+ return false;
- // Finally hoist the base constant and emit materializating code for dependent
+ // Finally hoist the base constant and emit materialization code for dependent
// constants.
- MadeChange |= EmitBaseConstants(F);
+ bool MadeChange = emitBaseConstants();
- ConstantMap.clear();
- Constants.clear();
+ // Cleanup dead instructions.
+ deleteDeadCastInst();
return MadeChange;
}
projects / oota-llvm.git / blobdiff