blob: 84589bf4db99f5f62db6f037685f3b517e23084d [file] [log] [blame]
//==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
//
// 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 expressions. For example:
// %0 = load i64* inttoptr (i64 big_constant to i64*)
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
#define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/PassManager.h"
#include <algorithm>
#include <vector>
namespace llvm {
class BasicBlock;
class BlockFrequencyInfo;
class Constant;
class ConstantInt;
class DominatorTree;
class Function;
class Instruction;
class TargetTransformInfo;
/// A private "module" namespace for types and utilities used by
/// ConstantHoisting. These are implementation details and should not be used by
/// clients.
namespace consthoist {
/// Keeps track of the user of a constant and the operand index where the
/// constant is used.
struct ConstantUser {
Instruction *Inst;
unsigned OpndIdx;
ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
};
using ConstantUseListType = SmallVector<ConstantUser, 8>;
/// Keeps track of a constant candidate and its uses.
struct ConstantCandidate {
ConstantUseListType Uses;
ConstantInt *ConstInt;
unsigned CumulativeCost = 0;
ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
/// Add the user to the use list and update the cost.
void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
CumulativeCost += Cost;
Uses.push_back(ConstantUser(Inst, Idx));
}
};
/// This represents a constant that has been rebased with respect to a
/// base constant. The difference to the base constant is recorded in Offset.
struct RebasedConstantInfo {
ConstantUseListType Uses;
Constant *Offset;
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
: Uses(std::move(Uses)), Offset(Offset) {}
};
using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
/// A base constant and all its rebased constants.
struct ConstantInfo {
ConstantInt *BaseConstant;
RebasedConstantListType RebasedConstants;
};
} // end namespace consthoist
class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
public:
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
// Glue for old PM.
bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
BlockFrequencyInfo *BFI, BasicBlock &Entry);
void releaseMemory() {
ConstantVec.clear();
ClonedCastMap.clear();
ConstCandVec.clear();
}
private:
using ConstCandMapType = DenseMap<ConstantInt *, unsigned>;
using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
const TargetTransformInfo *TTI;
DominatorTree *DT;
BlockFrequencyInfo *BFI;
BasicBlock *Entry;
/// Keeps track of constant candidates found in the function.
ConstCandVecType ConstCandVec;
/// Keep track of cast instructions we already cloned.
SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
/// These are the final constants we decided to hoist.
SmallVector<consthoist::ConstantInfo, 8> ConstantVec;
Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
SmallPtrSet<Instruction *, 8>
findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
void collectConstantCandidates(ConstCandMapType &ConstCandMap,
Instruction *Inst, unsigned Idx,
ConstantInt *ConstInt);
void collectConstantCandidates(ConstCandMapType &ConstCandMap,
Instruction *Inst, unsigned Idx);
void collectConstantCandidates(ConstCandMapType &ConstCandMap,
Instruction *Inst);
void collectConstantCandidates(Function &Fn);
void findAndMakeBaseConstant(ConstCandVecType::iterator S,
ConstCandVecType::iterator E);
unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
ConstCandVecType::iterator E,
ConstCandVecType::iterator &MaxCostItr);
void findBaseConstants();
void emitBaseConstants(Instruction *Base, Constant *Offset,
const consthoist::ConstantUser &ConstUser);
bool emitBaseConstants();
void deleteDeadCastInst() const;
bool optimizeConstants(Function &Fn);
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H