1 //===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SampleProfileLoader transformation. This pass
11 // reads a profile file generated by a sampling profiler (e.g. Linux Perf -
12 // http://perf.wiki.kernel.org/) and generates IR metadata to reflect the
13 // profile information in the given profile.
15 // This pass generates branch weight annotations on the IR:
17 // - prof: Represents branch weights. This annotation is added to branches
18 // to indicate the weights of each edge coming out of the branch.
19 // The weight of each edge is the weight of the target block for
20 // that edge. The weight of a block B is computed as the maximum
21 // number of samples found in B.
23 //===----------------------------------------------------------------------===//
25 #include "llvm/Transforms/Scalar.h"
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/StringRef.h"
30 #include "llvm/Analysis/LoopInfo.h"
31 #include "llvm/Analysis/PostDominators.h"
32 #include "llvm/IR/Constants.h"
33 #include "llvm/IR/DebugInfo.h"
34 #include "llvm/IR/DiagnosticInfo.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/InstIterator.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/LLVMContext.h"
40 #include "llvm/IR/MDBuilder.h"
41 #include "llvm/IR/Metadata.h"
42 #include "llvm/IR/Module.h"
43 #include "llvm/Pass.h"
44 #include "llvm/ProfileData/SampleProfReader.h"
45 #include "llvm/Support/CommandLine.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/raw_ostream.h"
51 using namespace sampleprof
;
53 #define DEBUG_TYPE "sample-profile"
55 // Command line option to specify the file to read samples from. This is
56 // mainly used for debugging.
57 static cl::opt
<std::string
> SampleProfileFile(
58 "sample-profile-file", cl::init(""), cl::value_desc("filename"),
59 cl::desc("Profile file loaded by -sample-profile"), cl::Hidden
);
60 static cl::opt
<unsigned> SampleProfileMaxPropagateIterations(
61 "sample-profile-max-propagate-iterations", cl::init(100),
62 cl::desc("Maximum number of iterations to go through when propagating "
63 "sample block/edge weights through the CFG."));
66 typedef DenseMap
<BasicBlock
*, unsigned> BlockWeightMap
;
67 typedef DenseMap
<BasicBlock
*, BasicBlock
*> EquivalenceClassMap
;
68 typedef std::pair
<BasicBlock
*, BasicBlock
*> Edge
;
69 typedef DenseMap
<Edge
, unsigned> EdgeWeightMap
;
70 typedef DenseMap
<BasicBlock
*, SmallVector
<BasicBlock
*, 8>> BlockEdgeMap
;
72 /// \brief Sample profile pass.
74 /// This pass reads profile data from the file specified by
75 /// -sample-profile-file and annotates every affected function with the
76 /// profile information found in that file.
77 class SampleProfileLoader
: public FunctionPass
{
79 // Class identification, replacement for typeinfo
82 SampleProfileLoader(StringRef Name
= SampleProfileFile
)
83 : FunctionPass(ID
), DT(nullptr), PDT(nullptr), LI(nullptr), Ctx(nullptr),
84 Reader(), Samples(nullptr), Filename(Name
), ProfileIsValid(false) {
85 initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
88 bool doInitialization(Module
&M
) override
;
90 void dump() { Reader
->dump(); }
92 const char *getPassName() const override
{ return "Sample profile pass"; }
94 bool runOnFunction(Function
&F
) override
;
96 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
98 AU
.addRequired
<LoopInfo
>();
99 AU
.addRequired
<DominatorTreeWrapperPass
>();
100 AU
.addRequired
<PostDominatorTree
>();
104 unsigned getFunctionLoc(Function
&F
);
105 bool emitAnnotations(Function
&F
);
106 unsigned getInstWeight(Instruction
&I
);
107 unsigned getBlockWeight(BasicBlock
*BB
);
108 void printEdgeWeight(raw_ostream
&OS
, Edge E
);
109 void printBlockWeight(raw_ostream
&OS
, BasicBlock
*BB
);
110 void printBlockEquivalence(raw_ostream
&OS
, BasicBlock
*BB
);
111 bool computeBlockWeights(Function
&F
);
112 void findEquivalenceClasses(Function
&F
);
113 void findEquivalencesFor(BasicBlock
*BB1
,
114 SmallVector
<BasicBlock
*, 8> Descendants
,
115 DominatorTreeBase
<BasicBlock
> *DomTree
);
116 void propagateWeights(Function
&F
);
117 unsigned visitEdge(Edge E
, unsigned *NumUnknownEdges
, Edge
*UnknownEdge
);
118 void buildEdges(Function
&F
);
119 bool propagateThroughEdges(Function
&F
);
121 /// \brief Line number for the function header. Used to compute absolute
122 /// line numbers from the relative line numbers found in the profile.
123 unsigned HeaderLineno
;
125 /// \brief Map basic blocks to their computed weights.
127 /// The weight of a basic block is defined to be the maximum
128 /// of all the instruction weights in that block.
129 BlockWeightMap BlockWeights
;
131 /// \brief Map edges to their computed weights.
133 /// Edge weights are computed by propagating basic block weights in
134 /// SampleProfile::propagateWeights.
135 EdgeWeightMap EdgeWeights
;
137 /// \brief Set of visited blocks during propagation.
138 SmallPtrSet
<BasicBlock
*, 128> VisitedBlocks
;
140 /// \brief Set of visited edges during propagation.
141 SmallSet
<Edge
, 128> VisitedEdges
;
143 /// \brief Equivalence classes for block weights.
145 /// Two blocks BB1 and BB2 are in the same equivalence class if they
146 /// dominate and post-dominate each other, and they are in the same loop
147 /// nest. When this happens, the two blocks are guaranteed to execute
148 /// the same number of times.
149 EquivalenceClassMap EquivalenceClass
;
151 /// \brief Dominance, post-dominance and loop information.
153 PostDominatorTree
*PDT
;
156 /// \brief Predecessors for each basic block in the CFG.
157 BlockEdgeMap Predecessors
;
159 /// \brief Successors for each basic block in the CFG.
160 BlockEdgeMap Successors
;
162 /// \brief LLVM context holding the debug data we need.
165 /// \brief Profile reader object.
166 std::unique_ptr
<SampleProfileReader
> Reader
;
168 /// \brief Samples collected for the body of this function.
169 FunctionSamples
*Samples
;
171 /// \brief Name of the profile file to load.
174 /// \brief Flag indicating whether the profile input loaded successfully.
179 /// \brief Print the weight of edge \p E on stream \p OS.
181 /// \param OS Stream to emit the output to.
182 /// \param E Edge to print.
183 void SampleProfileLoader::printEdgeWeight(raw_ostream
&OS
, Edge E
) {
184 OS
<< "weight[" << E
.first
->getName() << "->" << E
.second
->getName()
185 << "]: " << EdgeWeights
[E
] << "\n";
188 /// \brief Print the equivalence class of block \p BB on stream \p OS.
190 /// \param OS Stream to emit the output to.
191 /// \param BB Block to print.
192 void SampleProfileLoader::printBlockEquivalence(raw_ostream
&OS
,
194 BasicBlock
*Equiv
= EquivalenceClass
[BB
];
195 OS
<< "equivalence[" << BB
->getName()
196 << "]: " << ((Equiv
) ? EquivalenceClass
[BB
]->getName() : "NONE") << "\n";
199 /// \brief Print the weight of block \p BB on stream \p OS.
201 /// \param OS Stream to emit the output to.
202 /// \param BB Block to print.
203 void SampleProfileLoader::printBlockWeight(raw_ostream
&OS
, BasicBlock
*BB
) {
204 OS
<< "weight[" << BB
->getName() << "]: " << BlockWeights
[BB
] << "\n";
207 /// \brief Get the weight for an instruction.
209 /// The "weight" of an instruction \p Inst is the number of samples
210 /// collected on that instruction at runtime. To retrieve it, we
211 /// need to compute the line number of \p Inst relative to the start of its
212 /// function. We use HeaderLineno to compute the offset. We then
213 /// look up the samples collected for \p Inst using BodySamples.
215 /// \param Inst Instruction to query.
217 /// \returns The profiled weight of I.
218 unsigned SampleProfileLoader::getInstWeight(Instruction
&Inst
) {
219 DebugLoc DLoc
= Inst
.getDebugLoc();
220 unsigned Lineno
= DLoc
.getLine();
221 if (Lineno
< HeaderLineno
)
224 DILocation
DIL(DLoc
.getAsMDNode(*Ctx
));
225 int LOffset
= Lineno
- HeaderLineno
;
226 unsigned Discriminator
= DIL
.getDiscriminator();
227 unsigned Weight
= Samples
->samplesAt(LOffset
, Discriminator
);
228 DEBUG(dbgs() << " " << Lineno
<< "." << Discriminator
<< ":" << Inst
229 << " (line offset: " << LOffset
<< "." << Discriminator
230 << " - weight: " << Weight
<< ")\n");
234 /// \brief Compute the weight of a basic block.
236 /// The weight of basic block \p BB is the maximum weight of all the
237 /// instructions in BB. The weight of \p BB is computed and cached in
238 /// the BlockWeights map.
240 /// \param BB The basic block to query.
242 /// \returns The computed weight of BB.
243 unsigned SampleProfileLoader::getBlockWeight(BasicBlock
*BB
) {
244 // If we've computed BB's weight before, return it.
245 std::pair
<BlockWeightMap::iterator
, bool> Entry
=
246 BlockWeights
.insert(std::make_pair(BB
, 0));
248 return Entry
.first
->second
;
250 // Otherwise, compute and cache BB's weight.
252 for (auto &I
: BB
->getInstList()) {
253 unsigned InstWeight
= getInstWeight(I
);
254 if (InstWeight
> Weight
)
257 Entry
.first
->second
= Weight
;
261 /// \brief Compute and store the weights of every basic block.
263 /// This populates the BlockWeights map by computing
264 /// the weights of every basic block in the CFG.
266 /// \param F The function to query.
267 bool SampleProfileLoader::computeBlockWeights(Function
&F
) {
268 bool Changed
= false;
269 DEBUG(dbgs() << "Block weights\n");
271 unsigned Weight
= getBlockWeight(&BB
);
272 Changed
|= (Weight
> 0);
273 DEBUG(printBlockWeight(dbgs(), &BB
));
279 /// \brief Find equivalence classes for the given block.
281 /// This finds all the blocks that are guaranteed to execute the same
282 /// number of times as \p BB1. To do this, it traverses all the the
283 /// descendants of \p BB1 in the dominator or post-dominator tree.
285 /// A block BB2 will be in the same equivalence class as \p BB1 if
286 /// the following holds:
288 /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2
289 /// is a descendant of \p BB1 in the dominator tree, then BB2 should
290 /// dominate BB1 in the post-dominator tree.
292 /// 2- Both BB2 and \p BB1 must be in the same loop.
294 /// For every block BB2 that meets those two requirements, we set BB2's
295 /// equivalence class to \p BB1.
297 /// \param BB1 Block to check.
298 /// \param Descendants Descendants of \p BB1 in either the dom or pdom tree.
299 /// \param DomTree Opposite dominator tree. If \p Descendants is filled
300 /// with blocks from \p BB1's dominator tree, then
301 /// this is the post-dominator tree, and vice versa.
302 void SampleProfileLoader::findEquivalencesFor(
303 BasicBlock
*BB1
, SmallVector
<BasicBlock
*, 8> Descendants
,
304 DominatorTreeBase
<BasicBlock
> *DomTree
) {
305 for (auto *BB2
: Descendants
) {
306 bool IsDomParent
= DomTree
->dominates(BB2
, BB1
);
307 bool IsInSameLoop
= LI
->getLoopFor(BB1
) == LI
->getLoopFor(BB2
);
308 if (BB1
!= BB2
&& VisitedBlocks
.insert(BB2
).second
&& IsDomParent
&&
310 EquivalenceClass
[BB2
] = BB1
;
312 // If BB2 is heavier than BB1, make BB2 have the same weight
315 // Note that we don't worry about the opposite situation here
316 // (when BB2 is lighter than BB1). We will deal with this
317 // during the propagation phase. Right now, we just want to
318 // make sure that BB1 has the largest weight of all the
319 // members of its equivalence set.
320 unsigned &BB1Weight
= BlockWeights
[BB1
];
321 unsigned &BB2Weight
= BlockWeights
[BB2
];
322 BB1Weight
= std::max(BB1Weight
, BB2Weight
);
327 /// \brief Find equivalence classes.
329 /// Since samples may be missing from blocks, we can fill in the gaps by setting
330 /// the weights of all the blocks in the same equivalence class to the same
331 /// weight. To compute the concept of equivalence, we use dominance and loop
332 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
333 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
335 /// \param F The function to query.
336 void SampleProfileLoader::findEquivalenceClasses(Function
&F
) {
337 SmallVector
<BasicBlock
*, 8> DominatedBBs
;
338 DEBUG(dbgs() << "\nBlock equivalence classes\n");
339 // Find equivalence sets based on dominance and post-dominance information.
341 BasicBlock
*BB1
= &BB
;
343 // Compute BB1's equivalence class once.
344 if (EquivalenceClass
.count(BB1
)) {
345 DEBUG(printBlockEquivalence(dbgs(), BB1
));
349 // By default, blocks are in their own equivalence class.
350 EquivalenceClass
[BB1
] = BB1
;
352 // Traverse all the blocks dominated by BB1. We are looking for
353 // every basic block BB2 such that:
355 // 1- BB1 dominates BB2.
356 // 2- BB2 post-dominates BB1.
357 // 3- BB1 and BB2 are in the same loop nest.
359 // If all those conditions hold, it means that BB2 is executed
360 // as many times as BB1, so they are placed in the same equivalence
361 // class by making BB2's equivalence class be BB1.
362 DominatedBBs
.clear();
363 DT
->getDescendants(BB1
, DominatedBBs
);
364 findEquivalencesFor(BB1
, DominatedBBs
, PDT
->DT
);
366 // Repeat the same logic for all the blocks post-dominated by BB1.
367 // We are looking for every basic block BB2 such that:
369 // 1- BB1 post-dominates BB2.
370 // 2- BB2 dominates BB1.
371 // 3- BB1 and BB2 are in the same loop nest.
373 // If all those conditions hold, BB2's equivalence class is BB1.
374 DominatedBBs
.clear();
375 PDT
->getDescendants(BB1
, DominatedBBs
);
376 findEquivalencesFor(BB1
, DominatedBBs
, DT
);
378 DEBUG(printBlockEquivalence(dbgs(), BB1
));
381 // Assign weights to equivalence classes.
383 // All the basic blocks in the same equivalence class will execute
384 // the same number of times. Since we know that the head block in
385 // each equivalence class has the largest weight, assign that weight
386 // to all the blocks in that equivalence class.
387 DEBUG(dbgs() << "\nAssign the same weight to all blocks in the same class\n");
389 BasicBlock
*BB
= &BI
;
390 BasicBlock
*EquivBB
= EquivalenceClass
[BB
];
392 BlockWeights
[BB
] = BlockWeights
[EquivBB
];
393 DEBUG(printBlockWeight(dbgs(), BB
));
397 /// \brief Visit the given edge to decide if it has a valid weight.
399 /// If \p E has not been visited before, we copy to \p UnknownEdge
400 /// and increment the count of unknown edges.
402 /// \param E Edge to visit.
403 /// \param NumUnknownEdges Current number of unknown edges.
404 /// \param UnknownEdge Set if E has not been visited before.
406 /// \returns E's weight, if known. Otherwise, return 0.
407 unsigned SampleProfileLoader::visitEdge(Edge E
, unsigned *NumUnknownEdges
,
409 if (!VisitedEdges
.count(E
)) {
410 (*NumUnknownEdges
)++;
415 return EdgeWeights
[E
];
418 /// \brief Propagate weights through incoming/outgoing edges.
420 /// If the weight of a basic block is known, and there is only one edge
421 /// with an unknown weight, we can calculate the weight of that edge.
423 /// Similarly, if all the edges have a known count, we can calculate the
424 /// count of the basic block, if needed.
426 /// \param F Function to process.
428 /// \returns True if new weights were assigned to edges or blocks.
429 bool SampleProfileLoader::propagateThroughEdges(Function
&F
) {
430 bool Changed
= false;
431 DEBUG(dbgs() << "\nPropagation through edges\n");
433 BasicBlock
*BB
= &BI
;
435 // Visit all the predecessor and successor edges to determine
436 // which ones have a weight assigned already. Note that it doesn't
437 // matter that we only keep track of a single unknown edge. The
438 // only case we are interested in handling is when only a single
439 // edge is unknown (see setEdgeOrBlockWeight).
440 for (unsigned i
= 0; i
< 2; i
++) {
441 unsigned TotalWeight
= 0;
442 unsigned NumUnknownEdges
= 0;
443 Edge UnknownEdge
, SelfReferentialEdge
;
446 // First, visit all predecessor edges.
447 for (auto *Pred
: Predecessors
[BB
]) {
448 Edge E
= std::make_pair(Pred
, BB
);
449 TotalWeight
+= visitEdge(E
, &NumUnknownEdges
, &UnknownEdge
);
450 if (E
.first
== E
.second
)
451 SelfReferentialEdge
= E
;
454 // On the second round, visit all successor edges.
455 for (auto *Succ
: Successors
[BB
]) {
456 Edge E
= std::make_pair(BB
, Succ
);
457 TotalWeight
+= visitEdge(E
, &NumUnknownEdges
, &UnknownEdge
);
461 // After visiting all the edges, there are three cases that we
462 // can handle immediately:
464 // - All the edge weights are known (i.e., NumUnknownEdges == 0).
465 // In this case, we simply check that the sum of all the edges
466 // is the same as BB's weight. If not, we change BB's weight
467 // to match. Additionally, if BB had not been visited before,
468 // we mark it visited.
470 // - Only one edge is unknown and BB has already been visited.
471 // In this case, we can compute the weight of the edge by
472 // subtracting the total block weight from all the known
473 // edge weights. If the edges weight more than BB, then the
474 // edge of the last remaining edge is set to zero.
476 // - There exists a self-referential edge and the weight of BB is
477 // known. In this case, this edge can be based on BB's weight.
478 // We add up all the other known edges and set the weight on
479 // the self-referential edge as we did in the previous case.
481 // In any other case, we must continue iterating. Eventually,
482 // all edges will get a weight, or iteration will stop when
483 // it reaches SampleProfileMaxPropagateIterations.
484 if (NumUnknownEdges
<= 1) {
485 unsigned &BBWeight
= BlockWeights
[BB
];
486 if (NumUnknownEdges
== 0) {
487 // If we already know the weight of all edges, the weight of the
488 // basic block can be computed. It should be no larger than the sum
489 // of all edge weights.
490 if (TotalWeight
> BBWeight
) {
491 BBWeight
= TotalWeight
;
493 DEBUG(dbgs() << "All edge weights for " << BB
->getName()
494 << " known. Set weight for block: ";
495 printBlockWeight(dbgs(), BB
););
497 if (VisitedBlocks
.insert(BB
).second
)
499 } else if (NumUnknownEdges
== 1 && VisitedBlocks
.count(BB
)) {
500 // If there is a single unknown edge and the block has been
501 // visited, then we can compute E's weight.
502 if (BBWeight
>= TotalWeight
)
503 EdgeWeights
[UnknownEdge
] = BBWeight
- TotalWeight
;
505 EdgeWeights
[UnknownEdge
] = 0;
506 VisitedEdges
.insert(UnknownEdge
);
508 DEBUG(dbgs() << "Set weight for edge: ";
509 printEdgeWeight(dbgs(), UnknownEdge
));
511 } else if (SelfReferentialEdge
.first
&& VisitedBlocks
.count(BB
)) {
512 unsigned &BBWeight
= BlockWeights
[BB
];
513 // We have a self-referential edge and the weight of BB is known.
514 if (BBWeight
>= TotalWeight
)
515 EdgeWeights
[SelfReferentialEdge
] = BBWeight
- TotalWeight
;
517 EdgeWeights
[SelfReferentialEdge
] = 0;
518 VisitedEdges
.insert(SelfReferentialEdge
);
520 DEBUG(dbgs() << "Set self-referential edge weight to: ";
521 printEdgeWeight(dbgs(), SelfReferentialEdge
));
529 /// \brief Build in/out edge lists for each basic block in the CFG.
531 /// We are interested in unique edges. If a block B1 has multiple
532 /// edges to another block B2, we only add a single B1->B2 edge.
533 void SampleProfileLoader::buildEdges(Function
&F
) {
535 BasicBlock
*B1
= &BI
;
537 // Add predecessors for B1.
538 SmallPtrSet
<BasicBlock
*, 16> Visited
;
539 if (!Predecessors
[B1
].empty())
540 llvm_unreachable("Found a stale predecessors list in a basic block.");
541 for (pred_iterator PI
= pred_begin(B1
), PE
= pred_end(B1
); PI
!= PE
; ++PI
) {
542 BasicBlock
*B2
= *PI
;
543 if (Visited
.insert(B2
).second
)
544 Predecessors
[B1
].push_back(B2
);
547 // Add successors for B1.
549 if (!Successors
[B1
].empty())
550 llvm_unreachable("Found a stale successors list in a basic block.");
551 for (succ_iterator SI
= succ_begin(B1
), SE
= succ_end(B1
); SI
!= SE
; ++SI
) {
552 BasicBlock
*B2
= *SI
;
553 if (Visited
.insert(B2
).second
)
554 Successors
[B1
].push_back(B2
);
559 /// \brief Propagate weights into edges
561 /// The following rules are applied to every block BB in the CFG:
563 /// - If BB has a single predecessor/successor, then the weight
564 /// of that edge is the weight of the block.
566 /// - If all incoming or outgoing edges are known except one, and the
567 /// weight of the block is already known, the weight of the unknown
568 /// edge will be the weight of the block minus the sum of all the known
569 /// edges. If the sum of all the known edges is larger than BB's weight,
570 /// we set the unknown edge weight to zero.
572 /// - If there is a self-referential edge, and the weight of the block is
573 /// known, the weight for that edge is set to the weight of the block
574 /// minus the weight of the other incoming edges to that block (if
576 void SampleProfileLoader::propagateWeights(Function
&F
) {
580 // Before propagation starts, build, for each block, a list of
581 // unique predecessors and successors. This is necessary to handle
582 // identical edges in multiway branches. Since we visit all blocks and all
583 // edges of the CFG, it is cleaner to build these lists once at the start
587 // Propagate until we converge or we go past the iteration limit.
588 while (Changed
&& i
++ < SampleProfileMaxPropagateIterations
) {
589 Changed
= propagateThroughEdges(F
);
592 // Generate MD_prof metadata for every branch instruction using the
593 // edge weights computed during propagation.
594 DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
595 MDBuilder
MDB(F
.getContext());
597 BasicBlock
*BB
= &BI
;
598 TerminatorInst
*TI
= BB
->getTerminator();
599 if (TI
->getNumSuccessors() == 1)
601 if (!isa
<BranchInst
>(TI
) && !isa
<SwitchInst
>(TI
))
604 DEBUG(dbgs() << "\nGetting weights for branch at line "
605 << TI
->getDebugLoc().getLine() << ".\n");
606 SmallVector
<unsigned, 4> Weights
;
607 bool AllWeightsZero
= true;
608 for (unsigned I
= 0; I
< TI
->getNumSuccessors(); ++I
) {
609 BasicBlock
*Succ
= TI
->getSuccessor(I
);
610 Edge E
= std::make_pair(BB
, Succ
);
611 unsigned Weight
= EdgeWeights
[E
];
612 DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E
));
613 Weights
.push_back(Weight
);
615 AllWeightsZero
= false;
618 // Only set weights if there is at least one non-zero weight.
619 // In any other case, let the analyzer set weights.
620 if (!AllWeightsZero
) {
621 DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
622 TI
->setMetadata(llvm::LLVMContext::MD_prof
,
623 MDB
.createBranchWeights(Weights
));
625 DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
630 /// \brief Get the line number for the function header.
632 /// This looks up function \p F in the current compilation unit and
633 /// retrieves the line number where the function is defined. This is
634 /// line 0 for all the samples read from the profile file. Every line
635 /// number is relative to this line.
637 /// \param F Function object to query.
639 /// \returns the line number where \p F is defined. If it returns 0,
640 /// it means that there is no debug information available for \p F.
641 unsigned SampleProfileLoader::getFunctionLoc(Function
&F
) {
642 DISubprogram S
= getDISubprogram(&F
);
643 if (S
.isSubprogram())
644 return S
.getLineNumber();
646 // If could not find the start of \p F, emit a diagnostic to inform the user
647 // about the missed opportunity.
648 F
.getContext().diagnose(DiagnosticInfoSampleProfile(
649 "No debug information found in function " + F
.getName() +
650 ": Function profile not used",
655 /// \brief Generate branch weight metadata for all branches in \p F.
657 /// Branch weights are computed out of instruction samples using a
658 /// propagation heuristic. Propagation proceeds in 3 phases:
660 /// 1- Assignment of block weights. All the basic blocks in the function
661 /// are initial assigned the same weight as their most frequently
662 /// executed instruction.
664 /// 2- Creation of equivalence classes. Since samples may be missing from
665 /// blocks, we can fill in the gaps by setting the weights of all the
666 /// blocks in the same equivalence class to the same weight. To compute
667 /// the concept of equivalence, we use dominance and loop information.
668 /// Two blocks B1 and B2 are in the same equivalence class if B1
669 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
671 /// 3- Propagation of block weights into edges. This uses a simple
672 /// propagation heuristic. The following rules are applied to every
673 /// block BB in the CFG:
675 /// - If BB has a single predecessor/successor, then the weight
676 /// of that edge is the weight of the block.
678 /// - If all the edges are known except one, and the weight of the
679 /// block is already known, the weight of the unknown edge will
680 /// be the weight of the block minus the sum of all the known
681 /// edges. If the sum of all the known edges is larger than BB's weight,
682 /// we set the unknown edge weight to zero.
684 /// - If there is a self-referential edge, and the weight of the block is
685 /// known, the weight for that edge is set to the weight of the block
686 /// minus the weight of the other incoming edges to that block (if
689 /// Since this propagation is not guaranteed to finalize for every CFG, we
690 /// only allow it to proceed for a limited number of iterations (controlled
691 /// by -sample-profile-max-propagate-iterations).
693 /// FIXME: Try to replace this propagation heuristic with a scheme
694 /// that is guaranteed to finalize. A work-list approach similar to
695 /// the standard value propagation algorithm used by SSA-CCP might
698 /// Once all the branch weights are computed, we emit the MD_prof
699 /// metadata on BB using the computed values for each of its branches.
701 /// \param F The function to query.
703 /// \returns true if \p F was modified. Returns false, otherwise.
704 bool SampleProfileLoader::emitAnnotations(Function
&F
) {
705 bool Changed
= false;
707 // Initialize invariants used during computation and propagation.
708 HeaderLineno
= getFunctionLoc(F
);
709 if (HeaderLineno
== 0)
712 DEBUG(dbgs() << "Line number for the first instruction in " << F
.getName()
713 << ": " << HeaderLineno
<< "\n");
715 // Compute basic block weights.
716 Changed
|= computeBlockWeights(F
);
719 // Find equivalence classes.
720 findEquivalenceClasses(F
);
722 // Propagate weights to all edges.
729 char SampleProfileLoader::ID
= 0;
730 INITIALIZE_PASS_BEGIN(SampleProfileLoader
, "sample-profile",
731 "Sample Profile loader", false, false)
732 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
)
733 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree
)
734 INITIALIZE_PASS_DEPENDENCY(LoopInfo
)
735 INITIALIZE_PASS_DEPENDENCY(AddDiscriminators
)
736 INITIALIZE_PASS_END(SampleProfileLoader
, "sample-profile",
737 "Sample Profile loader", false, false)
739 bool SampleProfileLoader::doInitialization(Module
&M
) {
740 auto ReaderOrErr
= SampleProfileReader::create(Filename
, M
.getContext());
741 if (std::error_code EC
= ReaderOrErr
.getError()) {
742 std::string Msg
= "Could not open profile: " + EC
.message();
743 M
.getContext().diagnose(DiagnosticInfoSampleProfile(Filename
.data(), Msg
));
746 Reader
= std::move(ReaderOrErr
.get());
747 ProfileIsValid
= (Reader
->read() == sampleprof_error::success
);
751 FunctionPass
*llvm::createSampleProfileLoaderPass() {
752 return new SampleProfileLoader(SampleProfileFile
);
755 FunctionPass
*llvm::createSampleProfileLoaderPass(StringRef Name
) {
756 return new SampleProfileLoader(Name
);
759 bool SampleProfileLoader::runOnFunction(Function
&F
) {
763 DT
= &getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
764 PDT
= &getAnalysis
<PostDominatorTree
>();
765 LI
= &getAnalysis
<LoopInfo
>();
766 Ctx
= &F
.getParent()->getContext();
767 Samples
= Reader
->getSamplesFor(F
);
768 if (!Samples
->empty())
769 return emitAnnotations(F
);