// 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;
Constant *Offset;
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
- : Uses(Uses), Offset(Offset) { }
+ : 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;
Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const;
- void collectConstantCandidates(Instruction *Inst, unsigned Idx,
+ void collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst, unsigned Idx,
ConstantInt *ConstInt);
- void collectConstantCandidates(Instruction *Inst);
+ void collectConstantCandidates(ConstCandMapType &ConstCandMap,
+ Instruction *Inst);
void collectConstantCandidates(Function &Fn);
void findAndMakeBaseConstant(ConstCandVecType::iterator S,
ConstCandVecType::iterator E);
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');
/// \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))
SmallPtrSet<BasicBlock *, 8> BBs;
for (auto const &RCI : ConstInfo.RebasedConstants)
for (auto const &U : RCI.Uses)
- BBs.insert(U.Inst->getParent());
+ 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;
// Ask the target about the cost of materializing the constant for the given
- // instruction.
+ // instruction and operand index.
if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
- Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(),
+ Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx,
ConstInt->getValue(), ConstInt->getType());
else
- Cost = TTI->getIntImmCost(Inst->getOpcode(), ConstInt->getValue(),
+ Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(),
ConstInt->getType());
// Ignore cheap integer constants.
/// \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) {
- for (Function::iterator BB : Fn)
- for (BasicBlock::iterator Inst : *BB)
- collectConstantCandidates(Inst);
+ 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
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
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,
// Visit constant integer.
if (isa<ConstantInt>(Opnd)) {
DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
- ConstUser.Inst->setOperand(ConstUser.OpndIdx, Mat);
+ 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: " << *ConstUser.Inst << '\n');
- ConstUser.Inst->setOperand(ConstUser.OpndIdx, ClonedCastInst);
+ updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
return;
}
DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
<< "From : " << *ConstExpr << '\n');
DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
- ConstUser.Inst->setOperand(ConstUser.OpndIdx, ConstExprInst);
+ 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();
projects / oota-llvm.git / blobdiff