// 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/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Pass.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");
ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { }
};
-/// \brief Keeps track of a constant candidate and its usees.
+/// \brief Keeps track of a constant candidate and its uses.
struct ConstantCandidate {
ConstantUseListType Uses;
ConstantInt *ConstInt;
struct RebasedConstantInfo {
ConstantUseListType Uses;
Constant *Offset;
- mutable BasicBlock *IDom;
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
- : Uses(Uses), Offset(Offset), IDom(nullptr) { }
+ : Uses(std::move(Uses)), Offset(Offset) { }
};
/// \brief A base constant and all its rebased constants.
BasicBlock *Entry;
/// Keeps track of constant candidates found in the function.
- ConstCandMapType ConstCandMap;
ConstCandVecType ConstCandVec;
/// Keep track of cast instructions we already cloned.
SmallVector<ConstantInfo, 8> ConstantVec;
public:
static char ID; // Pass identification, replacement for typeid
- ConstantHoisting() : FunctionPass(ID), TTI(0), DT(0), Entry(0) {
+ ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr),
+ Entry(nullptr) {
initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
- AU.addRequired<TargetTransformInfo>();
+ AU.addRequired<TargetTransformInfoWrapperPass>();
}
private:
/// \brief Initialize the pass.
void setup(Function &Fn) {
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- TTI = &getAnalysis<TargetTransformInfo>();
+ TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn);
Entry = &Fn.getEntryBlock();
}
ConstantVec.clear();
ClonedCastMap.clear();
ConstCandVec.clear();
- ConstCandMap.clear();
TTI = nullptr;
DT = nullptr;
Entry = nullptr;
}
- /// \brief Find the common dominator of all uses and cache the result for
- /// future lookup.
- BasicBlock *getIDom(const RebasedConstantInfo &RCI) const {
- if (RCI.IDom)
- return RCI.IDom;
- RCI.IDom = findIDomOfAllUses(RCI.Uses);
- assert(RCI.IDom && "Invalid IDom.");
- return RCI.IDom;
- }
-
- BasicBlock *findIDomOfAllUses(const ConstantUseListType &Uses) const;
- Instruction *findMatInsertPt(Instruction *I, unsigned Idx = ~0U) const;
- Instruction *findConstantInsertionPoint(const ConstantInfo &CI) const;
- void collectConstantCandidates(Instruction *I, unsigned Idx, ConstantInt *C);
- void collectConstantCandidates(Instruction *I);
+ 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 &CU);
+ const ConstantUser &ConstUser);
bool emitBaseConstants();
void deleteDeadCastInst() const;
- bool optimizeConstants(Function &F);
+ 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 &Fn) {
+ if (skipOptnoneFunction(Fn))
+ return false;
+
DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
return MadeChange;
}
-/// \brief Find nearest common dominator of all uses.
-/// FIXME: Replace this with NearestCommonDominator once it is in common code.
-BasicBlock *
-ConstantHoisting::findIDomOfAllUses(const ConstantUseListType &Uses) const {
- // Collect all basic blocks.
- SmallPtrSet<BasicBlock *, 8> BBs;
- for (auto const &U : Uses)
- BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
-
- if (BBs.count(Entry))
- return Entry;
-
- 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;
- BBs.erase(BB1);
- BBs.erase(BB2);
- BBs.insert(BB);
- }
- assert((BBs.size() == 1) && "Expected only one element.");
- return *BBs.begin();
-}
/// \brief Find the constant materialization insertion point.
Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst,
unsigned Idx) const {
- // The simple and common case.
- if (!isa<PHINode>(Inst) && !isa<LandingPadInst>(Inst))
+ // 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;
- // We can't insert directly before a phi node or landing pad. Insert before
+ // 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))
Instruction *ConstantHoisting::
findConstantInsertionPoint(const ConstantInfo &ConstInfo) const {
assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
- // Collect all IDoms.
+ // Collect all basic blocks.
SmallPtrSet<BasicBlock *, 8> BBs;
for (auto const &RCI : ConstInfo.RebasedConstants)
- BBs.insert(getIDom(RCI));
-
- assert(!BBs.empty() && "No dominators!?");
+ for (auto const &U : RCI.Uses)
+ BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
if (BBs.count(Entry))
return &Entry->front();
/// \brief Record constant integer ConstInt for instruction Inst at operand
/// index Idx.
///
-/// The operand at index Idx is not necessarily the constant inetger itself. It
+/// 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(Instruction *Inst,
+void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst,
unsigned Idx,
ConstantInt *ConstInt) {
unsigned Cost;
Itr->second = ConstCandVec.size() - 1;
}
ConstCandVec[Itr->second].addUser(Inst, Idx, Cost);
- DEBUG(if (auto ConstInt = dyn_cast<ConstantInt>(Inst->getOperand(Idx)))
+ DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx)))
dbgs() << "Collect constant " << *ConstInt << " from " << *Inst
<< " with cost " << Cost << '\n';
else
/// \brief Scan the instruction for expensive integer constants and record them
/// in the constant candidate vector.
-void ConstantHoisting::collectConstantCandidates(Instruction *Inst) {
+void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst) {
// Skip all cast instructions. They are visited indirectly later on.
if (Inst->isCast())
return;
for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
Value *Opnd = Inst->getOperand(Idx);
- // Vist constant integers.
+ // Visit constant integers.
if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
- collectConstantCandidates(Inst, Idx, ConstInt);
+ collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
continue;
}
if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
// Pretend the constant is directly used by the instruction and ignore
// the cast instruction.
- collectConstantCandidates(Inst, Idx, ConstInt);
+ collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
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(Inst, Idx, ConstInt);
+ collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
continue;
}
}
/// \brief Collect all integer constants in the function that cannot be folded
/// into an instruction itself.
void ConstantHoisting::collectConstantCandidates(Function &Fn) {
+ ConstCandMapType ConstCandMap;
for (Function::iterator BB : Fn)
- for (BasicBlock::iterator I : *BB)
- collectConstantCandidates(I);
+ for (BasicBlock::iterator Inst : *BB)
+ collectConstantCandidates(ConstCandMap, Inst);
}
/// \brief Find the base constant within the given range and rebase all other
ConstInfo.RebasedConstants.push_back(
RebasedConstantInfo(std::move(ConstCand->Uses), Offset));
}
- ConstantVec.push_back(ConstInfo);
+ ConstantVec.push_back(std::move(ConstInfo));
}
/// \brief Finds and combines constant candidates that can be easily
// 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());
- });
+ 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.
findAndMakeBaseConstant(MinValItr, ConstCandVec.end());
}
+/// \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;
+ }
+ }
+ }
+
+ Inst->setOperand(Idx, Mat);
+ return true;
+}
+
/// \brief Emit materialization code for all rebased constants and update their
/// users.
void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset,
- const ConstantUser &CU) {
+ const ConstantUser &ConstUser) {
Instruction *Mat = Base;
if (Offset) {
- Instruction *InsertionPt = findMatInsertPt(CU.Inst, CU.OpndIdx);
+ 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(CU.Inst->getDebugLoc());
+ Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
}
- Value *Opnd = CU.Inst->getOperand(CU.OpndIdx);
+ Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
// Visit constant integer.
if (isa<ConstantInt>(Opnd)) {
- DEBUG(dbgs() << "Update: " << *CU.Inst << '\n');
- CU.Inst->setOperand(CU.OpndIdx, Mat);
- DEBUG(dbgs() << "To : " << *CU.Inst << '\n');
+ DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
+ if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
+ Mat->eraseFromParent();
+ DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
return;
}
ClonedCastInst->insertAfter(CastInst);
// Use the same debug location as the original cast instruction.
ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
- DEBUG(dbgs() << "Clone instruction: " << *ClonedCastInst << '\n'
- << "To : " << *CastInst << '\n');
+ DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
+ << "To : " << *ClonedCastInst << '\n');
}
- DEBUG(dbgs() << "Update: " << *CU.Inst << '\n');
- CU.Inst->setOperand(CU.OpndIdx, ClonedCastInst);
- DEBUG(dbgs() << "To : " << *CU.Inst << '\n');
+ DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
+ updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
+ DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
return;
}
if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
Instruction *ConstExprInst = ConstExpr->getAsInstruction();
ConstExprInst->setOperand(0, Mat);
- ConstExprInst->insertBefore(findMatInsertPt(CU.Inst, CU.OpndIdx));
+ ConstExprInst->insertBefore(findMatInsertPt(ConstUser.Inst,
+ ConstUser.OpndIdx));
// Use the same debug location as the instruction we are about to update.
- ConstExprInst->setDebugLoc(CU.Inst->getDebugLoc());
+ ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
<< "From : " << *ConstExpr << '\n');
- DEBUG(dbgs() << "Update: " << *CU.Inst << '\n');
- CU.Inst->setOperand(CU.OpndIdx, ConstExprInst);
- DEBUG(dbgs() << "To : " << *CU.Inst << '\n');
+ DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
+ if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
+ ConstExprInst->eraseFromParent();
+ if (Offset)
+ Mat->eraseFromParent();
+ }
+ DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
return;
}
}
void ConstantHoisting::deleteDeadCastInst() const {
for (auto const &I : ClonedCastMap)
if (I.first->use_empty())
- I.first->removeFromParent();
+ I.first->eraseFromParent();
}
/// \brief Optimize expensive integer constants in the given function.
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.
bool MadeChange = emitBaseConstants();