Revert "Add Constant Hoisting Pass"
This reverts commit r200022 to unbreak the build bots.
llvm-svn: 200024
diff --git a/llvm/lib/Analysis/TargetTransformInfo.cpp b/llvm/lib/Analysis/TargetTransformInfo.cpp
index decb9ae..360c4f5 100644
--- a/llvm/lib/Analysis/TargetTransformInfo.cpp
+++ b/llvm/lib/Analysis/TargetTransformInfo.cpp
@@ -158,16 +158,6 @@
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);
}
@@ -551,17 +541,7 @@
}
unsigned getIntImmCost(const APInt &Imm, Type *Ty) const LLVM_OVERRIDE {
- 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;
+ return 1;
}
unsigned getNumberOfRegisters(bool Vector) const LLVM_OVERRIDE {
diff --git a/llvm/lib/CodeGen/Passes.cpp b/llvm/lib/CodeGen/Passes.cpp
index 7a7c42b..0e8e50e 100644
--- a/llvm/lib/CodeGen/Passes.cpp
+++ b/llvm/lib/CodeGen/Passes.cpp
@@ -70,8 +70,6 @@
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,
@@ -398,10 +396,6 @@
// 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
diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index afd8072..591b2c7 100644
--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -3212,14 +3212,11 @@
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) {
- SDValue COR = DAG.FoldConstantArithmetic(ISD::OR, VT, N1C, C1);
- if (!COR.getNode())
- return SDValue();
+ if ((C1->getAPIntValue() & N1C->getAPIntValue()) != 0)
return DAG.getNode(ISD::AND, SDLoc(N), VT,
DAG.getNode(ISD::OR, SDLoc(N0), VT,
- N0.getOperand(0), N1), COR);
- }
+ N0.getOperand(0), N1),
+ DAG.FoldConstantArithmetic(ISD::OR, VT, N1C, C1));
}
// fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 430736a..e003cae 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -384,12 +384,9 @@
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: {
- const ConstantSDNode *C = cast<ConstantSDNode>(N);
- ID.AddPointer(C->getConstantIntValue());
- ID.AddBoolean(C->isOpaque());
+ case ISD::Constant:
+ ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
break;
- }
case ISD::TargetConstantFP:
case ISD::ConstantFP: {
ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
@@ -974,21 +971,19 @@
return getNode(ISD::XOR, DL, VT, Val, NegOne);
}
-SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
+SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
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, isO);
+ return getConstant(APInt(EltVT.getSizeInBits(), 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 APInt &Val, EVT VT, bool isT) {
+ return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
}
-SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
- bool isO) {
+SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
assert(VT.isInteger() && "Cannot create FP integer constant!");
EVT EltVT = VT.getScalarType();
@@ -1030,7 +1025,7 @@
for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
.trunc(ViaEltSizeInBits),
- ViaEltVT, isT, isO));
+ ViaEltVT, isT));
}
// EltParts is currently in little endian order. If we actually want
@@ -1061,7 +1056,6 @@
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)))
@@ -1069,7 +1063,7 @@
return SDValue(N, 0);
if (!N) {
- N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
+ N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
CSEMap.InsertNode(N, IP);
AllNodes.push_back(N);
}
@@ -2795,13 +2789,10 @@
ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
- if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
- return SDValue();
-
- if (Scalar1 && Scalar2)
+ 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);
@@ -2817,9 +2808,6 @@
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)
@@ -3573,11 +3561,10 @@
Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
}
- // 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.
+ // If the "cost" of materializing the integer immediate is 1 or free, 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())) <
- TargetTransformInfo::TCC_Load)
+ if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) < 2)
return DAG.getConstant(Val, VT);
return SDValue(0, 0);
}
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index a561c51..6c8e2f8 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2945,9 +2945,6 @@
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.
}
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp
index 6f98088..79377f7 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp
@@ -81,10 +81,7 @@
case ISD::VALUETYPE: return "ValueType";
case ISD::Register: return "Register";
case ISD::RegisterMask: return "RegisterMask";
- case ISD::Constant:
- if (cast<ConstantSDNode>(this)->isOpaque())
- return "OpaqueConstant";
- return "Constant";
+ case ISD::Constant: return "Constant";
case ISD::ConstantFP: return "ConstantFP";
case ISD::GlobalAddress: return "GlobalAddress";
case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
@@ -114,10 +111,7 @@
}
case ISD::BUILD_VECTOR: return "BUILD_VECTOR";
- case ISD::TargetConstant:
- if (cast<ConstantSDNode>(this)->isOpaque())
- return "OpaqueTargetConstant";
- return "TargetConstant";
+ case ISD::TargetConstant: return "TargetConstant";
case ISD::TargetConstantFP: return "TargetConstantFP";
case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
diff --git a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index 6052a48..fa5f9b4 100644
--- a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -1470,23 +1470,17 @@
if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true
// X >= C0 --> X > (C0-1)
- 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);
+ return DAG.getSetCC(dl, VT, N0,
+ DAG.getConstant(C1-1, 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)
- 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);
+ return DAG.getSetCC(dl, VT, N0,
+ DAG.getConstant(C1+1, N1.getValueType()),
+ (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
}
if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
diff --git a/llvm/lib/Target/X86/X86TargetTransformInfo.cpp b/llvm/lib/Target/X86/X86TargetTransformInfo.cpp
index 781be2f..da2b021 100644
--- a/llvm/lib/Target/X86/X86TargetTransformInfo.cpp
+++ b/llvm/lib/Target/X86/X86TargetTransformInfo.cpp
@@ -18,7 +18,6 @@
#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"
@@ -108,14 +107,6 @@
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;
-
/// @}
};
@@ -703,89 +694,3 @@
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);
- }
-}
diff --git a/llvm/lib/Transforms/Scalar/CMakeLists.txt b/llvm/lib/Transforms/Scalar/CMakeLists.txt
index 8a29b0c..0b29286 100644
--- a/llvm/lib/Transforms/Scalar/CMakeLists.txt
+++ b/llvm/lib/Transforms/Scalar/CMakeLists.txt
@@ -1,7 +1,6 @@
add_llvm_library(LLVMScalarOpts
ADCE.cpp
CodeGenPrepare.cpp
- ConstantHoisting.cpp
ConstantProp.cpp
CorrelatedValuePropagation.cpp
DCE.cpp
diff --git a/llvm/lib/Transforms/Scalar/CodeGenPrepare.cpp b/llvm/lib/Transforms/Scalar/CodeGenPrepare.cpp
index 6acbd5e..38f587b 100644
--- a/llvm/lib/Transforms/Scalar/CodeGenPrepare.cpp
+++ b/llvm/lib/Transforms/Scalar/CodeGenPrepare.cpp
@@ -240,7 +240,7 @@
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 = llvm::next(F.begin()), E = F.end(); I != E; ) {
+ for (Function::iterator I = ++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.
@@ -276,7 +276,7 @@
bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
bool MadeChange = false;
// Note that this intentionally skips the entry block.
- for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
+ for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
BasicBlock *BB = I++;
// If this block doesn't end with an uncond branch, ignore it.
diff --git a/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp b/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp
deleted file mode 100644
index b6191bb..0000000
--- a/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp
+++ /dev/null
@@ -1,429 +0,0 @@
-//===- 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;
-}
diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp
index f774874..6983d06 100644
--- a/llvm/lib/Transforms/Scalar/Scalar.cpp
+++ b/llvm/lib/Transforms/Scalar/Scalar.cpp
@@ -30,7 +30,6 @@
initializeADCEPass(Registry);
initializeSampleProfileLoaderPass(Registry);
initializeCodeGenPreparePass(Registry);
- initializeConstantHoistingPass(Registry);
initializeConstantPropagationPass(Registry);
initializeCorrelatedValuePropagationPass(Registry);
initializeDCEPass(Registry);