1 //===- bolt/Passes/MCF.h ----------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef BOLT_PASSES_MCF_H
10 #define BOLT_PASSES_MCF_H
11 
12 namespace llvm {
13 namespace bolt {
14 
15 class BinaryFunction;
16 class DataflowInfoManager;
17 
18 enum MCFCostFunction : char {
19   MCF_DISABLE = 0,
20   MCF_LINEAR,
21   MCF_QUADRATIC,
22   MCF_LOG,
23   MCF_BLAMEFTS
24 };
25 
26 /// Implement the idea in "SamplePGO - The Power of Profile Guided Optimizations
27 /// without the Usability Burden" by Diego Novillo to make basic block counts
28 /// equal if we show that A dominates B, B post-dominates A and they are in the
29 /// same loop and same loop nesting level.
30 void equalizeBBCounts(DataflowInfoManager &Info, BinaryFunction &BF);
31 
32 /// Fill edge counts based on the basic block count. Used in nonLBR mode when
33 /// we only have bb count.
34 void estimateEdgeCounts(BinaryFunction &BF);
35 
36 /// Entry point for computing a min-cost flow for the CFG with the goal
37 /// of fixing the flow of the CFG edges, that is, making sure it obeys the
38 /// flow-conservation equation  SumInEdges = SumOutEdges.
39 ///
40 /// To do this, we create an instance of the min-cost flow problem in a
41 /// similar way as the one discussed in the work of Roy Levin "Completing
42 /// Incomplete Edge Profile by Applying Minimum Cost Circulation Algorithms".
43 /// We do a few things differently, though. We don't populate edge counts using
44 /// weights coming from a static branch prediction technique and we don't
45 /// use the same cost function.
46 ///
47 /// If cost function BlameFTs is used, assign all remaining flow to
48 /// fall-throughs. This is used when the sampling is based on taken branches
49 /// that do not account for them.
50 void solveMCF(BinaryFunction &BF, MCFCostFunction CostFunction);
51 
52 } // end namespace bolt
53 } // end namespace llvm
54 
55 #endif // BOLT_PASSES_MCF_H
56