// %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 <tuple>
using namespace llvm;
+#define DEBUG_TYPE "consthoist"
+
STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
STATISTIC(NumConstantsRebased, "Number of constants rebased");
struct RebasedConstantInfo {
ConstantUseListType Uses;
Constant *Offset;
- mutable BasicBlock *IDom;
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
- : Uses(Uses), Offset(Offset), IDom(nullptr) { }
+ : Uses(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());
}
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 *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);
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 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) && !isa<LandingPadInst>(Inst))
return 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();
/// 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;
/// \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 Inst : *BB)
- collectConstantCandidates(Inst);
+ collectConstantCandidates(ConstCandMap, Inst);
}
/// \brief Find the base constant within the given range and rebase all other
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');
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.
projects / oota-llvm.git / blobdiff