summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/SampleProfile.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar/SampleProfile.cpp')
-rw-r--r--llvm/lib/Transforms/Scalar/SampleProfile.cpp125
1 files changed, 85 insertions, 40 deletions
diff --git a/llvm/lib/Transforms/Scalar/SampleProfile.cpp b/llvm/lib/Transforms/Scalar/SampleProfile.cpp
index d48e43d47c5..ab26fa5b23e 100644
--- a/llvm/lib/Transforms/Scalar/SampleProfile.cpp
+++ b/llvm/lib/Transforms/Scalar/SampleProfile.cpp
@@ -64,12 +64,51 @@ static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
"sample block/edge weights through the CFG."));
namespace {
+/// \brief Represents the relative location of an instruction.
+///
+/// Instruction locations are specified by the line offset from the
+/// beginning of the function (marked by the line where the function
+/// header is) and the discriminator value within that line.
+///
+/// The discriminator value is useful to distinguish instructions
+/// that are on the same line but belong to different basic blocks
+/// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
+struct InstructionLocation {
+ InstructionLocation(int L, unsigned D) : LineOffset(L), Discriminator(D) {}
+ int LineOffset;
+ unsigned Discriminator;
+};
+}
-typedef DenseMap<uint32_t, uint32_t> BodySampleMap;
-typedef DenseMap<BasicBlock *, uint32_t> BlockWeightMap;
+namespace llvm {
+template <> struct DenseMapInfo<InstructionLocation> {
+ typedef DenseMapInfo<int> OffsetInfo;
+ typedef DenseMapInfo<unsigned> DiscriminatorInfo;
+ static inline InstructionLocation getEmptyKey() {
+ return InstructionLocation(OffsetInfo::getEmptyKey(),
+ DiscriminatorInfo::getEmptyKey());
+ }
+ static inline InstructionLocation getTombstoneKey() {
+ return InstructionLocation(OffsetInfo::getTombstoneKey(),
+ DiscriminatorInfo::getTombstoneKey());
+ }
+ static inline unsigned getHashValue(InstructionLocation Val) {
+ return DenseMapInfo<std::pair<int, unsigned> >::getHashValue(
+ std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator));
+ }
+ static inline bool isEqual(InstructionLocation LHS, InstructionLocation RHS) {
+ return LHS.LineOffset == RHS.LineOffset &&
+ LHS.Discriminator == RHS.Discriminator;
+ }
+};
+}
+
+namespace {
+typedef DenseMap<InstructionLocation, unsigned> BodySampleMap;
+typedef DenseMap<BasicBlock *, unsigned> BlockWeightMap;
typedef DenseMap<BasicBlock *, BasicBlock *> EquivalenceClassMap;
typedef std::pair<BasicBlock *, BasicBlock *> Edge;
-typedef DenseMap<Edge, uint32_t> EdgeWeightMap;
+typedef DenseMap<Edge, unsigned> EdgeWeightMap;
typedef DenseMap<BasicBlock *, SmallVector<BasicBlock *, 8> > BlockEdgeMap;
/// \brief Representation of the runtime profile for a function.
@@ -81,17 +120,18 @@ class SampleFunctionProfile {
public:
SampleFunctionProfile()
: TotalSamples(0), TotalHeadSamples(0), HeaderLineno(0), DT(0), PDT(0),
- LI(0) {}
+ LI(0), Ctx(0) {}
unsigned getFunctionLoc(Function &F);
bool emitAnnotations(Function &F, DominatorTree *DomTree,
PostDominatorTree *PostDomTree, LoopInfo *Loops);
- uint32_t getInstWeight(Instruction &I);
- uint32_t getBlockWeight(BasicBlock *B);
+ unsigned getInstWeight(Instruction &I);
+ unsigned getBlockWeight(BasicBlock *B);
void addTotalSamples(unsigned Num) { TotalSamples += Num; }
void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; }
- void addBodySamples(unsigned LineOffset, unsigned Num) {
- BodySamples[LineOffset] += Num;
+ void addBodySamples(int LineOffset, unsigned Discriminator, unsigned Num) {
+ assert(LineOffset >= 0);
+ BodySamples[InstructionLocation(LineOffset, Discriminator)] += Num;
}
void print(raw_ostream &OS);
void printEdgeWeight(raw_ostream &OS, Edge E);
@@ -103,7 +143,7 @@ public:
SmallVector<BasicBlock *, 8> Descendants,
DominatorTreeBase<BasicBlock> *DomTree);
void propagateWeights(Function &F);
- uint32_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
+ unsigned visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
void buildEdges(Function &F);
bool propagateThroughEdges(Function &F);
bool empty() { return BodySamples.empty(); }
@@ -168,6 +208,9 @@ protected:
/// \brief Successors for each basic block in the CFG.
BlockEdgeMap Successors;
+
+ /// \brief LLVM context holding the debug data we need.
+ LLVMContext *Ctx;
};
/// \brief Sample-based profile reader.
@@ -276,7 +319,8 @@ void SampleFunctionProfile::print(raw_ostream &OS) {
for (BodySampleMap::const_iterator SI = BodySamples.begin(),
SE = BodySamples.end();
SI != SE; ++SI)
- OS << "\tline offset: " << SI->first
+ OS << "\tline offset: " << SI->first.LineOffset
+ << ", discriminator: " << SI->first.Discriminator
<< ", number of samples: " << SI->second << "\n";
OS << "\n";
}
@@ -364,10 +408,6 @@ void SampleModuleProfile::dump() {
/// b- [OPTIONAL] Discriminator. This is used if the sampled program
/// was compiled with DWARF discriminator support
/// (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators)
-/// This is currently only emitted by GCC and we just ignore it.
-///
-/// FIXME: Handle discriminators, since they are needed to distinguish
-/// multiple control flow within a single source LOC.
///
/// c- Number of samples. This is the number of samples collected by
/// the profiler at this source location.
@@ -408,7 +448,7 @@ void SampleModuleProfile::loadText() {
// mentioned more than once, and we are collecting flat profiles,
// accumulate samples as we parse them.
Regex HeadRE("^([^:]+):([0-9]+):([0-9]+)$");
- Regex LineSample("^([0-9]+)(\\.[0-9]+)?: ([0-9]+)(.*)$");
+ Regex LineSample("^([0-9]+)\\.?([0-9]+)?: ([0-9]+)(.*)$");
while (!LineIt.is_at_eof()) {
// Read the header of each function. The function header should
// have this format:
@@ -439,11 +479,10 @@ void SampleModuleProfile::loadText() {
LineIt.line_number(),
"Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " + *LineIt);
assert(Matches.size() == 5);
- unsigned LineOffset, NumSamples;
+ unsigned LineOffset, NumSamples, Discriminator = 0;
Matches[1].getAsInteger(10, LineOffset);
-
- // FIXME: Handle discriminator information (in Matches[2]).
-
+ if (Matches[2] != "")
+ Matches[2].getAsInteger(10, Discriminator);
Matches[3].getAsInteger(10, NumSamples);
// FIXME: Handle called targets (in Matches[4]).
@@ -454,7 +493,7 @@ void SampleModuleProfile::loadText() {
// avoid the confusion later on.
if (NumSamples == 0)
NumSamples = 1;
- FProfile.addBodySamples(LineOffset, NumSamples);
+ FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
++LineIt;
}
}
@@ -471,14 +510,19 @@ void SampleModuleProfile::loadText() {
/// \param Inst Instruction to query.
///
/// \returns The profiled weight of I.
-uint32_t SampleFunctionProfile::getInstWeight(Instruction &Inst) {
- unsigned Lineno = Inst.getDebugLoc().getLine();
+unsigned SampleFunctionProfile::getInstWeight(Instruction &Inst) {
+ DebugLoc DLoc = Inst.getDebugLoc();
+ unsigned Lineno = DLoc.getLine();
if (Lineno < HeaderLineno)
return 0;
- unsigned LOffset = Lineno - HeaderLineno;
- uint32_t Weight = BodySamples.lookup(LOffset);
- DEBUG(dbgs() << " " << Lineno << ":" << Inst.getDebugLoc().getCol() << ":"
- << Inst << " (line offset: " << LOffset
+
+ DILocation DIL(DLoc.getAsMDNode(*Ctx));
+ int LOffset = Lineno - HeaderLineno;
+ unsigned Discriminator = DIL.getDiscriminator();
+ unsigned Weight =
+ BodySamples.lookup(InstructionLocation(LOffset, Discriminator));
+ DEBUG(dbgs() << " " << Lineno << "." << Discriminator << ":" << Inst
+ << " (line offset: " << LOffset << "." << Discriminator
<< " - weight: " << Weight << ")\n");
return Weight;
}
@@ -492,7 +536,7 @@ uint32_t SampleFunctionProfile::getInstWeight(Instruction &Inst) {
/// \param B The basic block to query.
///
/// \returns The computed weight of B.
-uint32_t SampleFunctionProfile::getBlockWeight(BasicBlock *B) {
+unsigned SampleFunctionProfile::getBlockWeight(BasicBlock *B) {
// If we've computed B's weight before, return it.
std::pair<BlockWeightMap::iterator, bool> Entry =
BlockWeights.insert(std::make_pair(B, 0));
@@ -500,9 +544,9 @@ uint32_t SampleFunctionProfile::getBlockWeight(BasicBlock *B) {
return Entry.first->second;
// Otherwise, compute and cache B's weight.
- uint32_t Weight = 0;
+ unsigned Weight = 0;
for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
- uint32_t InstWeight = getInstWeight(*I);
+ unsigned InstWeight = getInstWeight(*I);
if (InstWeight > Weight)
Weight = InstWeight;
}
@@ -520,7 +564,7 @@ bool SampleFunctionProfile::computeBlockWeights(Function &F) {
bool Changed = false;
DEBUG(dbgs() << "Block weights\n");
for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) {
- uint32_t Weight = getBlockWeight(B);
+ unsigned Weight = getBlockWeight(B);
Changed |= (Weight > 0);
DEBUG(printBlockWeight(dbgs(), B));
}
@@ -572,8 +616,8 @@ void SampleFunctionProfile::findEquivalencesFor(
// during the propagation phase. Right now, we just want to
// make sure that BB1 has the largest weight of all the
// members of its equivalence set.
- uint32_t &BB1Weight = BlockWeights[BB1];
- uint32_t &BB2Weight = BlockWeights[BB2];
+ unsigned &BB1Weight = BlockWeights[BB1];
+ unsigned &BB2Weight = BlockWeights[BB2];
BB1Weight = std::max(BB1Weight, BB2Weight);
}
}
@@ -659,7 +703,7 @@ void SampleFunctionProfile::findEquivalenceClasses(Function &F) {
/// \param UnknownEdge Set if E has not been visited before.
///
/// \returns E's weight, if known. Otherwise, return 0.
-uint32_t SampleFunctionProfile::visitEdge(Edge E, unsigned *NumUnknownEdges,
+unsigned SampleFunctionProfile::visitEdge(Edge E, unsigned *NumUnknownEdges,
Edge *UnknownEdge) {
if (!VisitedEdges.count(E)) {
(*NumUnknownEdges)++;
@@ -693,7 +737,7 @@ bool SampleFunctionProfile::propagateThroughEdges(Function &F) {
// only case we are interested in handling is when only a single
// edge is unknown (see setEdgeOrBlockWeight).
for (unsigned i = 0; i < 2; i++) {
- uint32_t TotalWeight = 0;
+ unsigned TotalWeight = 0;
unsigned NumUnknownEdges = 0;
Edge UnknownEdge, SelfReferentialEdge;
@@ -737,7 +781,7 @@ bool SampleFunctionProfile::propagateThroughEdges(Function &F) {
// all edges will get a weight, or iteration will stop when
// it reaches SampleProfileMaxPropagateIterations.
if (NumUnknownEdges <= 1) {
- uint32_t &BBWeight = BlockWeights[BB];
+ unsigned &BBWeight = BlockWeights[BB];
if (NumUnknownEdges == 0) {
// If we already know the weight of all edges, the weight of the
// basic block can be computed. It should be no larger than the sum
@@ -764,7 +808,7 @@ bool SampleFunctionProfile::propagateThroughEdges(Function &F) {
printEdgeWeight(dbgs(), UnknownEdge));
}
} else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) {
- uint32_t &BBWeight = BlockWeights[BB];
+ unsigned &BBWeight = BlockWeights[BB];
// We have a self-referential edge and the weight of BB is known.
if (BBWeight >= TotalWeight)
EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
@@ -857,14 +901,13 @@ void SampleFunctionProfile::propagateWeights(Function &F) {
continue;
DEBUG(dbgs() << "\nGetting weights for branch at line "
- << TI->getDebugLoc().getLine() << ":"
- << TI->getDebugLoc().getCol() << ".\n");
- SmallVector<uint32_t, 4> Weights;
+ << TI->getDebugLoc().getLine() << ".\n");
+ SmallVector<unsigned, 4> Weights;
bool AllWeightsZero = true;
for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
BasicBlock *Succ = TI->getSuccessor(I);
Edge E = std::make_pair(B, Succ);
- uint32_t Weight = EdgeWeights[E];
+ unsigned Weight = EdgeWeights[E];
DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
Weights.push_back(Weight);
if (Weight != 0)
@@ -970,6 +1013,7 @@ bool SampleFunctionProfile::emitAnnotations(Function &F, DominatorTree *DomTree,
DT = DomTree;
PDT = PostDomTree;
LI = Loops;
+ Ctx = &F.getParent()->getContext();
// Compute basic block weights.
Changed |= computeBlockWeights(F);
@@ -991,6 +1035,7 @@ INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
+INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
"Sample Profile loader", false, false)
OpenPOWER on IntegriCloud