"sample-profile-max-propagate-iterations", cl::init(100),
cl::desc("Maximum number of iterations to go through when propagating "
"sample block/edge weights through the CFG."));
+static cl::opt<unsigned> SampleProfileCoverage(
+ "sample-profile-check-coverage", cl::init(0), cl::value_desc("N"),
+ cl::desc("Emit a warning if less than N% of samples in the input profile "
+ "are matched to the IR."));
namespace {
-typedef DenseMap<const BasicBlock *, unsigned> BlockWeightMap;
+typedef DenseMap<const BasicBlock *, uint64_t> BlockWeightMap;
typedef DenseMap<const BasicBlock *, const BasicBlock *> EquivalenceClassMap;
typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
-typedef DenseMap<Edge, unsigned> EdgeWeightMap;
+typedef DenseMap<Edge, uint64_t> EdgeWeightMap;
typedef DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>
BlockEdgeMap;
bool runOnFunction(Function &F);
unsigned getFunctionLoc(Function &F);
bool emitAnnotations(Function &F);
- ErrorOr<unsigned> getInstWeight(const Instruction &I) const;
- ErrorOr<unsigned> getBlockWeight(const BasicBlock *BB) const;
+ ErrorOr<uint64_t> getInstWeight(const Instruction &I) const;
+ ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB) const;
const FunctionSamples *findCalleeFunctionSamples(const CallInst &I) const;
const FunctionSamples *findFunctionSamples(const Instruction &I) const;
bool inlineHotFunctions(Function &F);
SmallVector<BasicBlock *, 8> Descendants,
DominatorTreeBase<BasicBlock> *DomTree);
void propagateWeights(Function &F);
- unsigned visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
+ uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
void buildEdges(Function &F);
bool propagateThroughEdges(Function &F);
void computeDominanceAndLoopInfo(Function &F);
-
- /// \brief Line number for the function header. Used to compute absolute
- /// line numbers from the relative line numbers found in the profile.
- unsigned HeaderLineno;
+ unsigned getOffset(unsigned L, unsigned H) const;
+ void clearFunctionData();
/// \brief Map basic blocks to their computed weights.
///
/// \brief Flag indicating whether the profile input loaded successfully.
bool ProfileIsValid;
};
+
+class SampleCoverageTracker {
+public:
+ SampleCoverageTracker() : SampleCoverage() {}
+
+ void markSamplesUsed(const FunctionSamples *Samples, uint32_t LineOffset,
+ uint32_t Discriminator);
+ unsigned computeCoverage(const FunctionSamples *Samples) const;
+ unsigned getNumUsedSamples(const FunctionSamples *Samples) const;
+
+private:
+ typedef DenseMap<LineLocation, unsigned> BodySampleCoverageMap;
+ typedef DenseMap<const FunctionSamples *, BodySampleCoverageMap>
+ FunctionSamplesCoverageMap;
+
+ /// Coverage map for sampling records.
+ ///
+ /// This map keeps a record of sampling records that have been matched to
+ /// an IR instruction. This is used to detect some form of staleness in
+ /// profiles (see flag -sample-profile-check-coverage).
+ ///
+ /// Each entry in the map corresponds to a FunctionSamples instance. This is
+ /// another map that counts how many times the sample record at the
+ /// given location has been used.
+ FunctionSamplesCoverageMap SampleCoverage;
+};
+
+SampleCoverageTracker CoverageTracker;
+}
+
+/// Mark as used the sample record for the given function samples at
+/// (LineOffset, Discriminator).
+void SampleCoverageTracker::markSamplesUsed(const FunctionSamples *Samples,
+ uint32_t LineOffset,
+ uint32_t Discriminator) {
+ BodySampleCoverageMap &Coverage = SampleCoverage[Samples];
+ Coverage[LineLocation(LineOffset, Discriminator)]++;
+}
+
+/// Return the number of sample records that were applied from this profile.
+unsigned
+SampleCoverageTracker::getNumUsedSamples(const FunctionSamples *Samples) const {
+ auto I = SampleCoverage.find(Samples);
+ return (I != SampleCoverage.end()) ? I->second.size() : 0;
+}
+
+/// Return the fraction of sample records used in this profile.
+///
+/// The returned value is an unsigned integer in the range 0-100 indicating
+/// the percentage of sample records that were used while applying this
+/// profile to the associated function.
+unsigned
+SampleCoverageTracker::computeCoverage(const FunctionSamples *Samples) const {
+ uint32_t NumTotalRecords = Samples->getBodySamples().size();
+ uint32_t NumUsedRecords = getNumUsedSamples(Samples);
+ assert(NumUsedRecords <= NumTotalRecords &&
+ "number of used records cannot exceed the total number of records");
+ return NumTotalRecords > 0 ? NumUsedRecords * 100 / NumTotalRecords : 100;
+}
+
+/// Clear all the per-function data used to load samples and propagate weights.
+void SampleProfileLoader::clearFunctionData() {
+ BlockWeights.clear();
+ EdgeWeights.clear();
+ VisitedBlocks.clear();
+ VisitedEdges.clear();
+ EquivalenceClass.clear();
+ DT = nullptr;
+ PDT = nullptr;
+ LI = nullptr;
+ Predecessors.clear();
+ Successors.clear();
+}
+
+/// \brief Returns the offset of lineno \p L to head_lineno \p H
+///
+/// \param L Lineno
+/// \param H Header lineno of the function
+///
+/// \returns offset to the header lineno. 16 bits are used to represent offset.
+/// We assume that a single function will not exceed 65535 LOC.
+unsigned SampleProfileLoader::getOffset(unsigned L, unsigned H) const {
+ return (L - H) & 0xffff;
}
/// \brief Print the weight of edge \p E on stream \p OS.
void SampleProfileLoader::printBlockWeight(raw_ostream &OS,
const BasicBlock *BB) const {
const auto &I = BlockWeights.find(BB);
- unsigned W = (I == BlockWeights.end() ? 0 : I->second);
+ uint64_t W = (I == BlockWeights.end() ? 0 : I->second);
OS << "weight[" << BB->getName() << "]: " << W << "\n";
}
/// \param Inst Instruction to query.
///
/// \returns the weight of \p Inst.
-ErrorOr<unsigned>
+ErrorOr<uint64_t>
SampleProfileLoader::getInstWeight(const Instruction &Inst) const {
DebugLoc DLoc = Inst.getDebugLoc();
if (!DLoc)
return std::error_code();
- unsigned Lineno = DLoc.getLine();
- if (Lineno < HeaderLineno)
- return std::error_code();
-
- const DILocation *DIL = DLoc;
const FunctionSamples *FS = findFunctionSamples(Inst);
if (!FS)
return std::error_code();
- ErrorOr<unsigned> R =
- FS->findSamplesAt(Lineno - HeaderLineno, DIL->getDiscriminator());
- if (R)
+
+ const DILocation *DIL = DLoc;
+ unsigned Lineno = DLoc.getLine();
+ unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();
+
+ uint32_t LineOffset = getOffset(Lineno, HeaderLineno);
+ uint32_t Discriminator = DIL->getDiscriminator();
+ ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);
+ if (R) {
+ if (SampleProfileCoverage)
+ CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator);
DEBUG(dbgs() << " " << Lineno << "." << DIL->getDiscriminator() << ":"
<< Inst << " (line offset: " << Lineno - HeaderLineno << "."
<< DIL->getDiscriminator() << " - weight: " << R.get()
<< ")\n");
+ }
return R;
}
/// \param BB The basic block to query.
///
/// \returns the weight for \p BB.
-ErrorOr<unsigned>
+ErrorOr<uint64_t>
SampleProfileLoader::getBlockWeight(const BasicBlock *BB) const {
bool Found = false;
- unsigned Weight = 0;
+ uint64_t Weight = 0;
for (auto &I : BB->getInstList()) {
- const ErrorOr<unsigned> &R = getInstWeight(I);
+ const ErrorOr<uint64_t> &R = getInstWeight(I);
if (R && R.get() >= Weight) {
Weight = R.get();
Found = true;
bool Changed = false;
DEBUG(dbgs() << "Block weights\n");
for (const auto &BB : F) {
- ErrorOr<unsigned> Weight = getBlockWeight(&BB);
+ ErrorOr<uint64_t> Weight = getBlockWeight(&BB);
if (Weight) {
BlockWeights[&BB] = Weight.get();
+ VisitedBlocks.insert(&BB);
Changed = true;
}
DEBUG(printBlockWeight(dbgs(), &BB));
}
+ if (SampleProfileCoverage) {
+ unsigned Coverage = CoverageTracker.computeCoverage(Samples);
+ if (Coverage < SampleProfileCoverage) {
+ const char *Filename = getDISubprogram(&F)->getFilename().str().c_str();
+ F.getContext().diagnose(DiagnosticInfoSampleProfile(
+ Filename, getFunctionLoc(F),
+ Twine(CoverageTracker.getNumUsedSamples(Samples)) + " of " +
+ Twine(Samples->getBodySamples().size()) +
+ " available profile records (" + Twine(Coverage) +
+ "%) were applied",
+ DS_Warning));
+ }
+ }
+
return Changed;
}
return nullptr;
}
DISubprogram *SP = DIL->getScope()->getSubprogram();
- if (!SP || DIL->getLine() < SP->getLine())
+ if (!SP)
return nullptr;
Function *CalleeFunc = Inst.getCalledFunction();
if (FS == nullptr)
return nullptr;
- return FS->findFunctionSamplesAt(CallsiteLocation(
- DIL->getLine() - SP->getLine(), DIL->getDiscriminator(), CalleeName));
+ return FS->findFunctionSamplesAt(
+ CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
+ DIL->getDiscriminator(), CalleeName));
}
/// \brief Get the FunctionSamples for an instruction.
for (const DILocation *DIL = Inst.getDebugLoc(); DIL;
DIL = DIL->getInlinedAt()) {
DISubprogram *SP = DIL->getScope()->getSubprogram();
- if (!SP || DIL->getLine() < SP->getLine())
+ if (!SP)
return nullptr;
if (!CalleeName.empty()) {
- S.push_back(CallsiteLocation(DIL->getLine() - SP->getLine(),
+ S.push_back(CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
DIL->getDiscriminator(), CalleeName));
}
CalleeName = SP->getLinkageName();
/// \returns True if there is any inline happened.
bool SampleProfileLoader::inlineHotFunctions(Function &F) {
bool Changed = false;
+ LLVMContext &Ctx = F.getContext();
while (true) {
bool LocalChanged = false;
SmallVector<CallInst *, 10> CIS;
}
for (auto CI : CIS) {
InlineFunctionInfo IFI;
- if (InlineFunction(CI, IFI))
+ Function *CalledFunction = CI->getCalledFunction();
+ DebugLoc DLoc = CI->getDebugLoc();
+ uint64_t NumSamples = findCalleeFunctionSamples(*CI)->getTotalSamples();
+ if (InlineFunction(CI, IFI)) {
LocalChanged = true;
+ emitOptimizationRemark(Ctx, DEBUG_TYPE, F, DLoc,
+ Twine("inlined hot callee '") +
+ CalledFunction->getName() + "' with " +
+ Twine(NumSamples) + " samples into '" +
+ F.getName() + "'");
+ }
}
if (LocalChanged) {
Changed = true;
void SampleProfileLoader::findEquivalencesFor(
BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
DominatorTreeBase<BasicBlock> *DomTree) {
+ const BasicBlock *EC = EquivalenceClass[BB1];
+ uint64_t Weight = BlockWeights[EC];
for (const auto *BB2 : Descendants) {
bool IsDomParent = DomTree->dominates(BB2, BB1);
bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
- if (BB1 != BB2 && VisitedBlocks.insert(BB2).second && IsDomParent &&
- IsInSameLoop) {
- EquivalenceClass[BB2] = BB1;
+ if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
+ EquivalenceClass[BB2] = EC;
// If BB2 is heavier than BB1, make BB2 have the same weight
// as BB1.
// 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.
- unsigned &BB1Weight = BlockWeights[BB1];
- unsigned &BB2Weight = BlockWeights[BB2];
- BB1Weight = std::max(BB1Weight, BB2Weight);
+ Weight = std::max(Weight, BlockWeights[BB2]);
}
}
+ BlockWeights[EC] = Weight;
}
/// \brief Find equivalence classes.
DT->getDescendants(BB1, DominatedBBs);
findEquivalencesFor(BB1, DominatedBBs, PDT.get());
- // Repeat the same logic for all the blocks post-dominated by BB1.
- // We are looking for every basic block BB2 such that:
- //
- // 1- BB1 post-dominates BB2.
- // 2- BB2 dominates BB1.
- // 3- BB1 and BB2 are in the same loop nest.
- //
- // If all those conditions hold, BB2's equivalence class is BB1.
- DominatedBBs.clear();
- PDT->getDescendants(BB1, DominatedBBs);
- findEquivalencesFor(BB1, DominatedBBs, DT.get());
-
DEBUG(printBlockEquivalence(dbgs(), BB1));
}
/// \param UnknownEdge Set if E has not been visited before.
///
/// \returns E's weight, if known. Otherwise, return 0.
-unsigned SampleProfileLoader::visitEdge(Edge E, unsigned *NumUnknownEdges,
+uint64_t SampleProfileLoader::visitEdge(Edge E, unsigned *NumUnknownEdges,
Edge *UnknownEdge) {
if (!VisitedEdges.count(E)) {
(*NumUnknownEdges)++;
bool SampleProfileLoader::propagateThroughEdges(Function &F) {
bool Changed = false;
DEBUG(dbgs() << "\nPropagation through edges\n");
- for (auto &BI : F) {
- BasicBlock *BB = &BI;
+ for (const auto &BI : F) {
+ const BasicBlock *BB = &BI;
+ const BasicBlock *EC = EquivalenceClass[BB];
// Visit all the predecessor and successor edges to determine
// which ones have a weight assigned already. Note that it doesn't
// only case we are interested in handling is when only a single
// edge is unknown (see setEdgeOrBlockWeight).
for (unsigned i = 0; i < 2; i++) {
- unsigned TotalWeight = 0;
+ uint64_t TotalWeight = 0;
unsigned NumUnknownEdges = 0;
Edge UnknownEdge, SelfReferentialEdge;
// all edges will get a weight, or iteration will stop when
// it reaches SampleProfileMaxPropagateIterations.
if (NumUnknownEdges <= 1) {
- unsigned &BBWeight = BlockWeights[BB];
+ uint64_t &BBWeight = BlockWeights[EC];
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
<< " known. Set weight for block: ";
printBlockWeight(dbgs(), BB););
}
- if (VisitedBlocks.insert(BB).second)
+ if (VisitedBlocks.insert(EC).second)
Changed = true;
- } else if (NumUnknownEdges == 1 && VisitedBlocks.count(BB)) {
+ } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
// If there is a single unknown edge and the block has been
// visited, then we can compute E's weight.
if (BBWeight >= TotalWeight)
DEBUG(dbgs() << "Set weight for edge: ";
printEdgeWeight(dbgs(), UnknownEdge));
}
- } else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) {
- unsigned &BBWeight = BlockWeights[BB];
+ } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
+ uint64_t &BBWeight = BlockWeights[BB];
// We have a self-referential edge and the weight of BB is known.
if (BBWeight >= TotalWeight)
EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
/// known).
void SampleProfileLoader::propagateWeights(Function &F) {
bool Changed = true;
- unsigned i = 0;
+ unsigned I = 0;
// Add an entry count to the function using the samples gathered
// at the function entry.
buildEdges(F);
// Propagate until we converge or we go past the iteration limit.
- while (Changed && i++ < SampleProfileMaxPropagateIterations) {
+ while (Changed && I++ < SampleProfileMaxPropagateIterations) {
Changed = propagateThroughEdges(F);
}
// Generate MD_prof metadata for every branch instruction using the
// edge weights computed during propagation.
DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
- MDBuilder MDB(F.getContext());
+ LLVMContext &Ctx = F.getContext();
+ MDBuilder MDB(Ctx);
for (auto &BI : F) {
BasicBlock *BB = &BI;
TerminatorInst *TI = BB->getTerminator();
DEBUG(dbgs() << "\nGetting weights for branch at line "
<< TI->getDebugLoc().getLine() << ".\n");
- SmallVector<unsigned, 4> Weights;
- bool AllWeightsZero = true;
+ SmallVector<uint32_t, 4> Weights;
+ uint32_t MaxWeight = 0;
+ DebugLoc MaxDestLoc;
for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
BasicBlock *Succ = TI->getSuccessor(I);
Edge E = std::make_pair(BB, Succ);
- unsigned Weight = EdgeWeights[E];
+ uint64_t Weight = EdgeWeights[E];
DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
- Weights.push_back(Weight);
- if (Weight != 0)
- AllWeightsZero = false;
+ // Use uint32_t saturated arithmetic to adjust the incoming weights,
+ // if needed. Sample counts in profiles are 64-bit unsigned values,
+ // but internally branch weights are expressed as 32-bit values.
+ if (Weight > std::numeric_limits<uint32_t>::max()) {
+ DEBUG(dbgs() << " (saturated due to uint32_t overflow)");
+ Weight = std::numeric_limits<uint32_t>::max();
+ }
+ Weights.push_back(static_cast<uint32_t>(Weight));
+ if (Weight != 0) {
+ if (Weight > MaxWeight) {
+ MaxWeight = Weight;
+ MaxDestLoc = Succ->getFirstNonPHIOrDbgOrLifetime()->getDebugLoc();
+ }
+ }
}
// Only set weights if there is at least one non-zero weight.
// In any other case, let the analyzer set weights.
- if (!AllWeightsZero) {
+ if (MaxWeight > 0) {
DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
TI->setMetadata(llvm::LLVMContext::MD_prof,
MDB.createBranchWeights(Weights));
+ DebugLoc BranchLoc = TI->getDebugLoc();
+ emitOptimizationRemark(
+ Ctx, DEBUG_TYPE, F, MaxDestLoc,
+ Twine("most popular destination for conditional branches at ") +
+ ((BranchLoc) ? Twine(BranchLoc->getFilename() + ":" +
+ Twine(BranchLoc.getLine()) + ":" +
+ Twine(BranchLoc.getCol()))
+ : Twine("<UNKNOWN LOCATION>")));
} else {
DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
}
if (DISubprogram *S = getDISubprogram(&F))
return S->getLine();
- // If could not find the start of \p F, emit a diagnostic to inform the user
+ // If the start of \p F is missing, emit a diagnostic to inform the user
// about the missed opportunity.
F.getContext().diagnose(DiagnosticInfoSampleProfile(
"No debug information found in function " + F.getName() +
bool SampleProfileLoader::emitAnnotations(Function &F) {
bool Changed = false;
- // Initialize invariants used during computation and propagation.
- HeaderLineno = getFunctionLoc(F);
- if (HeaderLineno == 0)
+ if (getFunctionLoc(F) == 0)
return false;
DEBUG(dbgs() << "Line number for the first instruction in " << F.getName()
- << ": " << HeaderLineno << "\n");
+ << ": " << getFunctionLoc(F) << "\n");
Changed |= inlineHotFunctions(F);
}
bool SampleProfileLoader::runOnModule(Module &M) {
+ if (!ProfileIsValid)
+ return false;
+
bool retval = false;
for (auto &F : M)
- if (!F.isDeclaration())
+ if (!F.isDeclaration()) {
+ clearFunctionData();
retval |= runOnFunction(F);
+ }
return retval;
}
bool SampleProfileLoader::runOnFunction(Function &F) {
- if (!ProfileIsValid)
- return false;
-
Samples = Reader->getSamplesFor(F);
if (!Samples->empty())
return emitAnnotations(F);
projects / oota-llvm.git / blobdiff