enum TargetCostConstants {
TCC_Free = 0, ///< Expected to fold away in lowering.
TCC_Basic = 1, ///< The cost of a typical 'add' instruction.
+ TCC_Load = 3,
TCC_Expensive = 4 ///< The cost of a 'div' instruction on x86.
};
/// immediate of the specified type.
virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) const;
+ /// \brief Return the expected cost of materialization for the given integer
+ /// immediate of the specified type for a given instruction. The cost can be
+ /// zero if the immediate can be folded into the specified instruction.
+ virtual unsigned getIntImmCost(unsigned Opcode, const APInt &Imm,
+ Type *Ty) const;
+ virtual unsigned getIntImmCost(Intrinsic::ID IID, const APInt &Imm,
+ Type *Ty) const;
/// @}
/// \name Vector Target Information
//===--------------------------------------------------------------------===//
// Node creation methods.
//
- SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
- SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
- SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
+ SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false,
+ bool isOpaque = false);
+ SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false,
+ bool isOpaque = false);
+ SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false,
+ bool isOpaque = false);
SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
- SDValue getTargetConstant(uint64_t Val, EVT VT) {
- return getConstant(Val, VT, true);
+ SDValue getTargetConstant(uint64_t Val, EVT VT, bool isOpaque = false) {
+ return getConstant(Val, VT, true, isOpaque);
}
- SDValue getTargetConstant(const APInt &Val, EVT VT) {
- return getConstant(Val, VT, true);
+ SDValue getTargetConstant(const APInt &Val, EVT VT, bool isOpaque = false) {
+ return getConstant(Val, VT, true, isOpaque);
}
- SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
- return getConstant(Val, VT, true);
+ SDValue getTargetConstant(const ConstantInt &Val, EVT VT,
+ bool isOpaque = false) {
+ return getConstant(Val, VT, true, isOpaque);
}
// The forms below that take a double should only be used for simple
// constants that can be exactly represented in VT. No checks are made.
class ConstantSDNode : public SDNode {
const ConstantInt *Value;
friend class SelectionDAG;
- ConstantSDNode(bool isTarget, const ConstantInt *val, EVT VT)
+ ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val, EVT VT)
: SDNode(isTarget ? ISD::TargetConstant : ISD::Constant,
0, DebugLoc(), getSDVTList(VT)), Value(val) {
+ SubclassData |= isOpaque;
}
public:
bool isNullValue() const { return Value->isNullValue(); }
bool isAllOnesValue() const { return Value->isAllOnesValue(); }
+ bool isOpaque() const { return SubclassData & 1; }
+
static bool classof(const SDNode *N) {
return N->getOpcode() == ISD::Constant ||
N->getOpcode() == ISD::TargetConstant;
void initializeFlattenCFGPassPass(PassRegistry&);
void initializeStructurizeCFGPass(PassRegistry&);
void initializeCFGViewerPass(PassRegistry&);
+void initializeConstantHoistingPass(PassRegistry&);
void initializeCodeGenPreparePass(PassRegistry&);
void initializeConstantMergePass(PassRegistry&);
void initializeConstantPropagationPass(PassRegistry&);
(void) llvm::createJumpThreadingPass();
(void) llvm::createUnifyFunctionExitNodesPass();
(void) llvm::createInstCountPass();
+ (void) llvm::createConstantHoistingPass();
(void) llvm::createCodeGenPreparePass();
(void) llvm::createEarlyCSEPass();
(void) llvm::createGVNPass();
//
Pass *createLoopDeletionPass();
+//===----------------------------------------------------------------------===//
+//
+// ConstantHoisting - This pass prepares a function for expensive constants.
+//
+FunctionPass *createConstantHoistingPass();
+
//===----------------------------------------------------------------------===//
//
// CodeGenPrepare - This pass prepares a function for instruction selection.
return PrevTTI->getIntImmCost(Imm, Ty);
}
+unsigned TargetTransformInfo::getIntImmCost(unsigned Opcode, const APInt &Imm,
+ Type *Ty) const {
+ return PrevTTI->getIntImmCost(Opcode, Imm, Ty);
+}
+
+unsigned TargetTransformInfo::getIntImmCost(Intrinsic::ID IID, const APInt &Imm,
+ Type *Ty) const {
+ return PrevTTI->getIntImmCost(IID, Imm, Ty);
+}
+
unsigned TargetTransformInfo::getNumberOfRegisters(bool Vector) const {
return PrevTTI->getNumberOfRegisters(Vector);
}
}
unsigned getIntImmCost(const APInt &Imm, Type *Ty) const LLVM_OVERRIDE {
- return 1;
+ return TCC_Basic;
+ }
+
+ unsigned getIntImmCost(unsigned Opcode, const APInt &Imm,
+ Type *Ty) const LLVM_OVERRIDE {
+ return TCC_Free;
+ }
+
+ unsigned getIntImmCost(Intrinsic::ID IID, const APInt &Imm,
+ Type *Ty) const LLVM_OVERRIDE {
+ return TCC_Free;
}
unsigned getNumberOfRegisters(bool Vector) const LLVM_OVERRIDE {
cl::desc("Disable Machine Sinking"));
static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
cl::desc("Disable Loop Strength Reduction Pass"));
+static cl::opt<bool> DisableConstantHoisting("disable-constant-hoisting",
+ cl::Hidden, cl::desc("Disable ConstantHoisting"));
static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
cl::desc("Disable Codegen Prepare"));
static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
// Make sure that no unreachable blocks are instruction selected.
addPass(createUnreachableBlockEliminationPass());
+
+ // Prepare expensive constants for SelectionDAG.
+ if (getOptLevel() != CodeGenOpt::None && !DisableConstantHoisting)
+ addPass(createConstantHoistingPass());
}
/// Turn exception handling constructs into something the code generators can
if (N1C && N0.getOpcode() == ISD::AND && N0.getNode()->hasOneUse() &&
isa<ConstantSDNode>(N0.getOperand(1))) {
ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1));
- if ((C1->getAPIntValue() & N1C->getAPIntValue()) != 0)
+ if ((C1->getAPIntValue() & N1C->getAPIntValue()) != 0) {
+ SDValue COR = DAG.FoldConstantArithmetic(ISD::OR, VT, N1C, C1);
+ if (!COR.getNode())
+ return SDValue();
return DAG.getNode(ISD::AND, SDLoc(N), VT,
DAG.getNode(ISD::OR, SDLoc(N0), VT,
- N0.getOperand(0), N1),
- DAG.FoldConstantArithmetic(ISD::OR, VT, N1C, C1));
+ N0.getOperand(0), N1), COR);
+ }
}
// fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
llvm_unreachable("Should only be used on nodes with operands");
default: break; // Normal nodes don't need extra info.
case ISD::TargetConstant:
- case ISD::Constant:
- ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
+ case ISD::Constant: {
+ const ConstantSDNode *C = cast<ConstantSDNode>(N);
+ ID.AddPointer(C->getConstantIntValue());
+ ID.AddBoolean(C->isOpaque());
break;
+ }
case ISD::TargetConstantFP:
case ISD::ConstantFP: {
ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
return getNode(ISD::XOR, DL, VT, Val, NegOne);
}
-SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
+SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
EVT EltVT = VT.getScalarType();
assert((EltVT.getSizeInBits() >= 64 ||
(uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
"getConstant with a uint64_t value that doesn't fit in the type!");
- return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
+ return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
}
-SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
- return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
+SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
+{
+ return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
}
-SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
+SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
+ bool isO) {
assert(VT.isInteger() && "Cannot create FP integer constant!");
EVT EltVT = VT.getScalarType();
for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
.trunc(ViaEltSizeInBits),
- ViaEltVT, isT));
+ ViaEltVT, isT, isO));
}
// EltParts is currently in little endian order. If we actually want
FoldingSetNodeID ID;
AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
ID.AddPointer(Elt);
+ ID.AddBoolean(isO);
void *IP = 0;
SDNode *N = NULL;
if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
return SDValue(N, 0);
if (!N) {
- N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
+ N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
CSEMap.InsertNode(N, IP);
AllNodes.push_back(N);
}
ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
- if (Scalar1 && Scalar2) {
+ if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
+ return SDValue();
+
+ if (Scalar1 && Scalar2)
// Scalar instruction.
Inputs.push_back(std::make_pair(Scalar1, Scalar2));
- } else {
+ else {
// For vectors extract each constant element into Inputs so we can constant
// fold them individually.
BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
if (!V1 || !V2) // Not a constant, bail.
return SDValue();
+ if (V1->isOpaque() || V2->isOpaque())
+ return SDValue();
+
// Avoid BUILD_VECTOR nodes that perform implicit truncation.
// FIXME: This is valid and could be handled by truncating the APInts.
if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
}
- // If the "cost" of materializing the integer immediate is 1 or free, then
- // it is cost effective to turn the load into the immediate.
+ // If the "cost" of materializing the integer immediate is less than the cost
+ // of a load, then it is cost effective to turn the load into the immediate.
const TargetTransformInfo *TTI = DAG.getTargetTransformInfo();
- if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) < 2)
+ if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) <
+ TargetTransformInfo::TCC_Load)
return DAG.getConstant(Val, VT);
return SDValue(0, 0);
}
if (DestVT != N.getValueType())
setValue(&I, DAG.getNode(ISD::BITCAST, getCurSDLoc(),
DestVT, N)); // convert types.
+ else if(ConstantSDNode *C = dyn_cast<ConstantSDNode>(N))
+ setValue(&I, DAG.getConstant(C->getAPIntValue(), C->getValueType(0),
+ /*isTarget=*/false, /*isOpaque*/true));
else
setValue(&I, N); // noop cast.
}
case ISD::VALUETYPE: return "ValueType";
case ISD::Register: return "Register";
case ISD::RegisterMask: return "RegisterMask";
- case ISD::Constant: return "Constant";
+ case ISD::Constant:
+ if (cast<ConstantSDNode>(this)->isOpaque())
+ return "OpaqueConstant";
+ return "Constant";
case ISD::ConstantFP: return "ConstantFP";
case ISD::GlobalAddress: return "GlobalAddress";
case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
}
case ISD::BUILD_VECTOR: return "BUILD_VECTOR";
- case ISD::TargetConstant: return "TargetConstant";
+ case ISD::TargetConstant:
+ if (cast<ConstantSDNode>(this)->isOpaque())
+ return "OpaqueTargetConstant";
+ return "TargetConstant";
case ISD::TargetConstantFP: return "TargetConstantFP";
case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true
// X >= C0 --> X > (C0-1)
- return DAG.getSetCC(dl, VT, N0,
- DAG.getConstant(C1-1, N1.getValueType()),
- (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
+ APInt C = C1-1;
+ if (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
+ isLegalICmpImmediate(C.getSExtValue())))
+ return DAG.getSetCC(dl, VT, N0,
+ DAG.getConstant(C, N1.getValueType()),
+ (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
}
if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true
// X <= C0 --> X < (C0+1)
- return DAG.getSetCC(dl, VT, N0,
- DAG.getConstant(C1+1, N1.getValueType()),
- (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
+ APInt C = C1+1;
+ if (!N1C->isOpaque() || (N1C->isOpaque() && C.getBitWidth() <= 64 &&
+ isLegalICmpImmediate(C.getSExtValue())))
+ return DAG.getSetCC(dl, VT, N0,
+ DAG.getConstant(C, N1.getValueType()),
+ (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
}
if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
#include "X86.h"
#include "X86TargetMachine.h"
#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/CostTable.h"
#include "llvm/Target/TargetLowering.h"
virtual unsigned getReductionCost(unsigned Opcode, Type *Ty,
bool IsPairwiseForm) const LLVM_OVERRIDE;
+ virtual unsigned getIntImmCost(const APInt &Imm,
+ Type *Ty) const LLVM_OVERRIDE;
+
+ virtual unsigned getIntImmCost(unsigned Opcode, const APInt &Imm,
+ Type *Ty) const LLVM_OVERRIDE;
+ virtual unsigned getIntImmCost(Intrinsic::ID IID, const APInt &Imm,
+ Type *Ty) const LLVM_OVERRIDE;
+
/// @}
};
return TargetTransformInfo::getReductionCost(Opcode, ValTy, IsPairwise);
}
+unsigned X86TTI::getIntImmCost(const APInt &Imm, Type *Ty) const {
+ assert(Ty->isIntegerTy());
+
+ unsigned BitSize = Ty->getPrimitiveSizeInBits();
+ if (BitSize == 0)
+ return ~0U;
+
+ if (Imm.getBitWidth() <= 64 &&
+ (isInt<32>(Imm.getSExtValue()) || isUInt<32>(Imm.getZExtValue())))
+ return TCC_Basic;
+ else
+ return 2 * TCC_Basic;
+}
+
+unsigned X86TTI::getIntImmCost(unsigned Opcode, const APInt &Imm,
+ Type *Ty) const {
+ assert(Ty->isIntegerTy());
+
+ unsigned BitSize = Ty->getPrimitiveSizeInBits();
+ if (BitSize == 0)
+ return ~0U;
+
+ switch (Opcode) {
+ case Instruction::Add:
+ case Instruction::Sub:
+ case Instruction::Mul:
+ case Instruction::UDiv:
+ case Instruction::SDiv:
+ case Instruction::URem:
+ case Instruction::SRem:
+ case Instruction::Shl:
+ case Instruction::LShr:
+ case Instruction::AShr:
+ case Instruction::And:
+ case Instruction::Or:
+ case Instruction::Xor:
+ case Instruction::ICmp:
+ if (Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue()))
+ return TCC_Free;
+ else
+ return X86TTI::getIntImmCost(Imm, Ty);
+ case Instruction::Trunc:
+ case Instruction::ZExt:
+ case Instruction::SExt:
+ case Instruction::IntToPtr:
+ case Instruction::PtrToInt:
+ case Instruction::BitCast:
+ case Instruction::Call:
+ case Instruction::Select:
+ case Instruction::Ret:
+ case Instruction::Load:
+ case Instruction::Store:
+ return X86TTI::getIntImmCost(Imm, Ty);
+ }
+ return TargetTransformInfo::getIntImmCost(Opcode, Imm, Ty);
+}
+
+unsigned X86TTI::getIntImmCost(Intrinsic::ID IID, const APInt &Imm,
+ Type *Ty) const {
+ assert(Ty->isIntegerTy());
+
+ unsigned BitSize = Ty->getPrimitiveSizeInBits();
+ if (BitSize == 0)
+ return ~0U;
+
+ switch (IID) {
+ default: return TargetTransformInfo::getIntImmCost(IID, Imm, Ty);
+ case Intrinsic::sadd_with_overflow:
+ case Intrinsic::uadd_with_overflow:
+ case Intrinsic::ssub_with_overflow:
+ case Intrinsic::usub_with_overflow:
+ case Intrinsic::smul_with_overflow:
+ case Intrinsic::umul_with_overflow:
+ if (Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue()))
+ return TCC_Free;
+ else
+ return X86TTI::getIntImmCost(Imm, Ty);
+ case Intrinsic::experimental_stackmap:
+ case Intrinsic::experimental_patchpoint_void:
+ case Intrinsic::experimental_patchpoint_i64:
+ if (Imm.getBitWidth() <= 64 && isInt<64>(Imm.getSExtValue()))
+ return TCC_Free;
+ else
+ return X86TTI::getIntImmCost(Imm, Ty);
+ }
+}
add_llvm_library(LLVMScalarOpts
ADCE.cpp
CodeGenPrepare.cpp
+ ConstantHoisting.cpp
ConstantProp.cpp
CorrelatedValuePropagation.cpp
DCE.cpp
bool CodeGenPrepare::EliminateFallThrough(Function &F) {
bool Changed = false;
// Scan all of the blocks in the function, except for the entry block.
- for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
+ for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
BasicBlock *BB = I++;
// If the destination block has a single pred, then this is a trivial
// edge, just collapse it.
bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
bool MadeChange = false;
// Note that this intentionally skips the entry block.
- for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
+ for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
BasicBlock *BB = I++;
// If this block doesn't end with an uncond branch, ignore it.
--- /dev/null
+//===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass identifies expensive constants to hoist and coalesces them to
+// better prepare it for SelectionDAG-based code generation. This works around
+// the limitations of the basic-block-at-a-time approach.
+//
+// First it scans all instructions for integer constants and calculates its
+// cost. If the constant can be folded into the instruction (the cost is
+// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
+// consider it expensive and leave it alone. This is the default behavior and
+// the default implementation of getIntImmCost will always return TCC_Free.
+//
+// If the cost is more than TCC_BASIC, then the integer constant can't be folded
+// into the instruction and it might be beneficial to hoist the constant.
+// Similar constants are coalesced to reduce register pressure and
+// materialization code.
+//
+// When a constant is hoisted, it is also hidden behind a bitcast to force it to
+// be live-out of the basic block. Otherwise the constant would be just
+// duplicated and each basic block would have its own copy in the SelectionDAG.
+// The SelectionDAG recognizes such constants as opaque and doesn't perform
+// 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:
+// %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/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"
+
+using namespace llvm;
+
+STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
+STATISTIC(NumConstantsRebased, "Number of constants rebased");
+
+
+namespace {
+typedef SmallVector<User *, 4> ConstantUseListType;
+struct ConstantCandidate {
+ unsigned CumulativeCost;
+ ConstantUseListType Uses;
+};
+
+struct ConstantInfo {
+ ConstantInt *BaseConstant;
+ struct RebasedConstantInfo {
+ ConstantInt *OriginalConstant;
+ Constant *Offset;
+ ConstantUseListType Uses;
+ };
+ typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
+ RebasedConstantListType RebasedConstants;
+};
+
+class ConstantHoisting : public FunctionPass {
+ const TargetTransformInfo *TTI;
+ DominatorTree *DT;
+
+ /// Keeps track of expensive constants found in the function.
+ typedef MapVector<ConstantInt *, ConstantCandidate> ConstantMapType;
+ ConstantMapType ConstantMap;
+
+ /// These are the final constants we decided to hoist.
+ SmallVector<ConstantInfo, 4> Constants;
+public:
+ static char ID; // Pass identification, replacement for typeid
+ ConstantHoisting() : FunctionPass(ID), TTI(0) {
+ initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
+ }
+
+ bool runOnFunction(Function &F);
+
+ const char *getPassName() const { return "Constant Hoisting"; }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
+ AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<TargetTransformInfo>();
+ }
+
+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);
+};
+}
+
+char ConstantHoisting::ID = 0;
+INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
+ false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
+INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
+ false, false)
+
+FunctionPass *llvm::createConstantHoistingPass() {
+ return new ConstantHoisting();
+}
+
+/// \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');
+
+ DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ TTI = &getAnalysis<TargetTransformInfo>();
+
+ return OptimizeConstants(F);
+}
+
+void ConstantHoisting::CollectConstant(User * U, unsigned Opcode,
+ Intrinsic::ID IID, ConstantInt *C) {
+ unsigned Cost;
+ if (Opcode)
+ Cost = TTI->getIntImmCost(Opcode, C->getValue(), C->getType());
+ else
+ Cost = TTI->getIntImmCost(IID, C->getValue(), C->getType());
+
+ if (Cost > TargetTransformInfo::TCC_Basic) {
+ ConstantCandidate &CC = ConstantMap[C];
+ CC.CumulativeCost += Cost;
+ CC.Uses.push_back(U);
+ }
+}
+
+/// \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();
+
+ // 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);
+ continue;
+ }
+ if (ConstantExpr *CE = dyn_cast<ConstantExpr>(O)) {
+ // We only handle constant cast expressions.
+ if (!CE->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);
+ continue;
+ }
+ }
+ }
+}
+
+/// \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();
+}
+
+/// \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;
+ 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;
+ }
+
+ // Don't hoist constants that have only one use.
+ if (NumUses <= 1)
+ return;
+
+ ConstantInfo CI;
+ CI.BaseConstant = MaxCostItr->first;
+ Type *Ty = CI.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);
+ }
+ Constants.push_back(CI);
+}
+
+/// \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()) {
+ // Check if the constant is in range of an add with immediate.
+ APInt Diff = I->first->getValue() - MinValItr->first->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);
+ // Start a new base constant search.
+ MinValItr = I;
+ }
+ // 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, 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.
+ if (Instruction *I = dyn_cast<Instruction>(*UU))
+ BBs.insert(I->getParent());
+}
+
+/// \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, *U);
+
+ if (BBs.count(Entry))
+ return Entry->getFirstInsertionPt();
+
+ 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 Entry->getFirstInsertionPt();
+ BBs.erase(BB1);
+ BBs.erase(BB2);
+ BBs.insert(BB);
+ }
+ assert((BBs.size() == 1) && "Expected only one element.");
+ return (*BBs.begin())->getFirstInsertionPt();
+}
+
+/// \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", I);
+
+ // 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');
+ return;
+ }
+ assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
+ ConstantExpr *CE = cast<ConstantExpr>(U);
+ for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
+ UU != E; ++UU) {
+ // 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)) {
+ Instruction *Mat = Base;
+ if (!Offset->isNullValue()) {
+ Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
+ "const_mat", I);
+
+ // 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(I);
+
+ // Use the same debug location as the instruction we are about to update.
+ ICE->setDebugLoc(I->getDebugLoc());
+
+ DEBUG(dbgs() << "Create instruction: " << *ICE << '\n');
+ DEBUG(dbgs() << "Update: " << *I << '\n');
+ I->replaceUsesOfWith(CE, ICE);
+ DEBUG(dbgs() << "To: " << *I << '\n');
+ }
+ }
+}
+
+/// \brief Hoist and hide the base constant behind a bitcast and emit
+/// materialization code for derived constants.
+bool ConstantHoisting::EmitBaseConstants(Function &F) {
+ bool MadeChange = false;
+ SmallVectorImpl<ConstantInfo>::iterator CI, CE;
+ for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
+ // 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');
+ 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) {
+ NumConstantsRebased++;
+ for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
+ E = RCI->Uses.end(); U != E; ++U)
+ EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
+ }
+
+ // 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()) &&
+ "All uses should be instructions.");
+ Base->setDebugLoc(cast<Instruction>(Base->use_back())->getDebugLoc());
+
+ // Correct for base constant, which we counted above too.
+ NumConstantsRebased--;
+ MadeChange = true;
+ }
+ return MadeChange;
+}
+
+/// \brief Optimize expensive integer constants in the given function.
+bool ConstantHoisting::OptimizeConstants(Function &F) {
+ bool MadeChange = false;
+
+ // Collect all constant candidates.
+ CollectConstants(F);
+
+ // There are no constants to worry about.
+ if (ConstantMap.empty())
+ return MadeChange;
+
+ // Combine constants that can be easily materialized with an add from a common
+ // base constant.
+ FindBaseConstants();
+
+ // Finaly hoist the base constant and emit materializating code for dependent
+ // constants.
+ MadeChange |= EmitBaseConstants(F);
+
+ ConstantMap.clear();
+ Constants.clear();
+
+ return MadeChange;
+}
initializeADCEPass(Registry);
initializeSampleProfileLoaderPass(Registry);
initializeCodeGenPreparePass(Registry);
+ initializeConstantHoistingPass(Registry);
initializeConstantPropagationPass(Registry);
initializeCorrelatedValuePropagationPass(Registry);
initializeDCEPass(Registry);
define void @t2(i8* nocapture %C) nounwind {
entry:
; CHECK-LABEL: t2:
-; CHECK: ldr [[REG2:r[0-9]+]], [r1, #32]
+; CHECK: movw [[REG2:r[0-9]+]], #16716
+; CHECK: movt [[REG2:r[0-9]+]], #72
; CHECK: str [[REG2]], [r0, #32]
; CHECK: vld1.8 {d{{[0-9]+}}, d{{[0-9]+}}}, [r1]
; CHECK: vst1.8 {d{{[0-9]+}}, d{{[0-9]+}}}, [r0]
; CHECK: strb [[REG5]], [r0, #6]
; CHECK: movw [[REG6:r[0-9]+]], #21587
; CHECK: strh [[REG6]], [r0, #4]
-; CHECK: ldr [[REG7:r[0-9]+]],
+; CHECK: movw [[REG7:r[0-9]+]], #18500
+; CHECK: movt [[REG7:r[0-9]+]], #22866
; CHECK: str [[REG7]]
tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %C, i8* getelementptr inbounds ([7 x i8]* @.str5, i64 0, i64 0), i64 7, i32 1, i1 false)
ret void
--- /dev/null
+; RUN: llc < %s -mtriple=x86_64-darwin -mcpu=corei7 | grep movabsq | count 2
+
+define i64 @constant_hoisting(i64 %o0, i64 %o1, i64 %o2, i64 %o3, i64 %o4, i64 %o5) {
+entry:
+ %l0 = and i64 %o0, -281474976710654
+ %c0 = icmp ne i64 %l0, 0
+ br i1 %c0, label %fail, label %bb1
+
+bb1:
+ %l1 = and i64 %o1, -281474976710654
+ %c1 = icmp ne i64 %l1, 0
+ br i1 %c1, label %fail, label %bb2
+
+bb2:
+ %l2 = and i64 %o2, -281474976710654
+ %c2 = icmp ne i64 %l2, 0
+ br i1 %c2, label %fail, label %bb3
+
+bb3:
+ %l3 = and i64 %o3, -281474976710654
+ %c3 = icmp ne i64 %l3, 0
+ br i1 %c3, label %fail, label %bb4
+
+bb4:
+ %l4 = and i64 %o4, -281474976710653
+ %c4 = icmp ne i64 %l4, 0
+ br i1 %c4, label %fail, label %bb5
+
+bb5:
+ %l5 = and i64 %o5, -281474976710652
+ %c5 = icmp ne i64 %l5, 0
+ br i1 %c5, label %fail, label %bb6
+
+bb6:
+ ret i64 %l5
+
+fail:
+ ret i64 -1
+}
+
+define void @constant_expressions() {
+entry:
+ %0 = load i64* inttoptr (i64 add (i64 51250129900, i64 0) to i64*)
+ %1 = load i64* inttoptr (i64 add (i64 51250129900, i64 8) to i64*)
+ %2 = load i64* inttoptr (i64 add (i64 51250129900, i64 16) to i64*)
+ %3 = load i64* inttoptr (i64 add (i64 51250129900, i64 24) to i64*)
+ %4 = add i64 %0, %1
+ %5 = add i64 %2, %3
+ %6 = add i64 %4, %5
+ store i64 %6, i64* inttoptr (i64 add (i64 51250129900, i64 0) to i64*)
+ ret void
+}
+
projects / oota-llvm.git / commitdiff