0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 //===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This file implements basic block placement transformations using the CFG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 // structure and branch probability estimates.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 // The pass strives to preserve the structure of the CFG (that is, retain
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 // a topological ordering of basic blocks) in the absence of a *strong* signal
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 // to the contrary from probabilities. However, within the CFG structure, it
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 // attempts to choose an ordering which favors placing more likely sequences of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 // blocks adjacent to each other.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 // The algorithm works from the inner-most loop within a function outward, and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 // at each stage walks through the basic blocks, trying to coalesce them into
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 // sequential chains where allowed by the CFG (or demanded by heavy
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 // probabilities). Finally, it walks the blocks in topological order, and the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 // first time it reaches a chain of basic blocks, it schedules them in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 // function in-order.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 #include "llvm/CodeGen/Passes.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 #include "llvm/ADT/DenseMap.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 #include "llvm/ADT/SmallPtrSet.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 #include "llvm/ADT/SmallVector.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 #include "llvm/ADT/Statistic.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 #include "llvm/CodeGen/MachineBasicBlock.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
|
|
95
|
36 #include "llvm/CodeGen/MachineDominators.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 #include "llvm/CodeGen/MachineFunction.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 #include "llvm/CodeGen/MachineFunctionPass.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 #include "llvm/CodeGen/MachineLoopInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 #include "llvm/CodeGen/MachineModuleInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 #include "llvm/Support/Allocator.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 #include "llvm/Support/CommandLine.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 #include "llvm/Support/Debug.h"
|
|
95
|
44 #include "llvm/Support/raw_ostream.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 #include "llvm/Target/TargetInstrInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 #include "llvm/Target/TargetLowering.h"
|
|
77
|
47 #include "llvm/Target/TargetSubtargetInfo.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 #include <algorithm>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50
|
|
95
|
51 #define DEBUG_TYPE "block-placement"
|
|
77
|
52
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53 STATISTIC(NumCondBranches, "Number of conditional branches");
|
|
95
|
54 STATISTIC(NumUncondBranches, "Number of unconditional branches");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 STATISTIC(CondBranchTakenFreq,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 "Potential frequency of taking conditional branches");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 STATISTIC(UncondBranchTakenFreq,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 "Potential frequency of taking unconditional branches");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 static cl::opt<unsigned> AlignAllBlock("align-all-blocks",
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 cl::desc("Force the alignment of all "
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 "blocks in the function."),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 cl::init(0), cl::Hidden);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64
|
|
100
|
65 static cl::opt<unsigned> AlignAllNonFallThruBlocks(
|
|
|
66 "align-all-nofallthru-blocks",
|
|
|
67 cl::desc("Force the alignment of all "
|
|
|
68 "blocks that have no fall-through predecessors (i.e. don't add "
|
|
|
69 "nops that are executed)."),
|
|
|
70 cl::init(0), cl::Hidden);
|
|
|
71
|
|
95
|
72 // FIXME: Find a good default for this flag and remove the flag.
|
|
|
73 static cl::opt<unsigned> ExitBlockBias(
|
|
|
74 "block-placement-exit-block-bias",
|
|
|
75 cl::desc("Block frequency percentage a loop exit block needs "
|
|
|
76 "over the original exit to be considered the new exit."),
|
|
|
77 cl::init(0), cl::Hidden);
|
|
|
78
|
|
|
79 static cl::opt<bool> OutlineOptionalBranches(
|
|
|
80 "outline-optional-branches",
|
|
|
81 cl::desc("Put completely optional branches, i.e. branches with a common "
|
|
|
82 "post dominator, out of line."),
|
|
83
|
83 cl::init(false), cl::Hidden);
|
|
|
84
|
|
95
|
85 static cl::opt<unsigned> OutlineOptionalThreshold(
|
|
|
86 "outline-optional-threshold",
|
|
|
87 cl::desc("Don't outline optional branches that are a single block with an "
|
|
|
88 "instruction count below this threshold"),
|
|
|
89 cl::init(4), cl::Hidden);
|
|
33
|
90
|
|
100
|
91 static cl::opt<unsigned> LoopToColdBlockRatio(
|
|
|
92 "loop-to-cold-block-ratio",
|
|
|
93 cl::desc("Outline loop blocks from loop chain if (frequency of loop) / "
|
|
|
94 "(frequency of block) is greater than this ratio"),
|
|
|
95 cl::init(5), cl::Hidden);
|
|
|
96
|
|
|
97 static cl::opt<bool>
|
|
|
98 PreciseRotationCost("precise-rotation-cost",
|
|
|
99 cl::desc("Model the cost of loop rotation more "
|
|
|
100 "precisely by using profile data."),
|
|
|
101 cl::init(false), cl::Hidden);
|
|
|
102
|
|
|
103 static cl::opt<unsigned> MisfetchCost(
|
|
|
104 "misfetch-cost",
|
|
|
105 cl::desc("Cost that models the probablistic risk of an instruction "
|
|
|
106 "misfetch due to a jump comparing to falling through, whose cost "
|
|
|
107 "is zero."),
|
|
|
108 cl::init(1), cl::Hidden);
|
|
|
109
|
|
|
110 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
|
|
|
111 cl::desc("Cost of jump instructions."),
|
|
|
112 cl::init(1), cl::Hidden);
|
|
|
113
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 namespace {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 class BlockChain;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 /// \brief Type for our function-wide basic block -> block chain mapping.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 namespace {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 /// \brief A chain of blocks which will be laid out contiguously.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 /// This is the datastructure representing a chain of consecutive blocks that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 /// are profitable to layout together in order to maximize fallthrough
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125 /// probabilities and code locality. We also can use a block chain to represent
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 /// a sequence of basic blocks which have some external (correctness)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127 /// requirement for sequential layout.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 /// Chains can be built around a single basic block and can be merged to grow
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130 /// them. They participate in a block-to-chain mapping, which is updated
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131 /// automatically as chains are merged together.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 class BlockChain {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 /// \brief The sequence of blocks belonging to this chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 /// This is the sequence of blocks for a particular chain. These will be laid
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136 /// out in-order within the function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 SmallVector<MachineBasicBlock *, 4> Blocks;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 /// \brief A handle to the function-wide basic block to block chain mapping.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
141 /// This is retained in each block chain to simplify the computation of child
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
142 /// block chains for SCC-formation and iteration. We store the edges to child
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143 /// basic blocks, and map them back to their associated chains using this
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
144 /// structure.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145 BlockToChainMapType &BlockToChain;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 /// \brief Construct a new BlockChain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 /// This builds a new block chain representing a single basic block in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 /// function. It also registers itself as the chain that block participates
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 /// in with the BlockToChain mapping.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
|
|
95
|
154 : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 assert(BB && "Cannot create a chain with a null basic block");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156 BlockToChain[BB] = this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
158
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 /// \brief Iterator over blocks within the chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160 typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162 /// \brief Beginning of blocks within the chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 iterator begin() { return Blocks.begin(); }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 /// \brief End of blocks within the chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 iterator end() { return Blocks.end(); }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168 /// \brief Merge a block chain into this one.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 /// This routine merges a block chain into this one. It takes care of forming
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 /// a contiguous sequence of basic blocks, updating the edge list, and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 /// updating the block -> chain mapping. It does not free or tear down the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 /// old chain, but the old chain's block list is no longer valid.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 void merge(MachineBasicBlock *BB, BlockChain *Chain) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 assert(BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 assert(!Blocks.empty());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178 // Fast path in case we don't have a chain already.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 if (!Chain) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 assert(!BlockToChain[BB]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181 Blocks.push_back(BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 BlockToChain[BB] = this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 assert(BB == *Chain->begin());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187 assert(Chain->begin() != Chain->end());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
189 // Update the incoming blocks to point to this chain, and add them to the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 // chain structure.
|
|
95
|
191 for (MachineBasicBlock *ChainBB : *Chain) {
|
|
|
192 Blocks.push_back(ChainBB);
|
|
|
193 assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain");
|
|
|
194 BlockToChain[ChainBB] = this;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 #ifndef NDEBUG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199 /// \brief Dump the blocks in this chain.
|
|
77
|
200 LLVM_DUMP_METHOD void dump() {
|
|
95
|
201 for (MachineBasicBlock *MBB : *this)
|
|
|
202 MBB->dump();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
204 #endif // NDEBUG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206 /// \brief Count of predecessors within the loop currently being processed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
208 /// This count is updated at each loop we process to represent the number of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
209 /// in-loop predecessors of this chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210 unsigned LoopPredecessors;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
211 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
212 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
214 namespace {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 class MachineBlockPlacement : public MachineFunctionPass {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
216 /// \brief A typedef for a block filter set.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
217 typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
218
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
219 /// \brief A handle to the branch probability pass.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220 const MachineBranchProbabilityInfo *MBPI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
221
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
222 /// \brief A handle to the function-wide block frequency pass.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
223 const MachineBlockFrequencyInfo *MBFI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
224
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
225 /// \brief A handle to the loop info.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
226 const MachineLoopInfo *MLI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
227
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
228 /// \brief A handle to the target's instruction info.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
229 const TargetInstrInfo *TII;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
230
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
231 /// \brief A handle to the target's lowering info.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
232 const TargetLoweringBase *TLI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
233
|
|
95
|
234 /// \brief A handle to the post dominator tree.
|
|
|
235 MachineDominatorTree *MDT;
|
|
|
236
|
|
|
237 /// \brief A set of blocks that are unavoidably execute, i.e. they dominate
|
|
|
238 /// all terminators of the MachineFunction.
|
|
|
239 SmallPtrSet<MachineBasicBlock *, 4> UnavoidableBlocks;
|
|
|
240
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
241 /// \brief Allocator and owner of BlockChain structures.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
242 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
243 /// We build BlockChains lazily while processing the loop structure of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
244 /// a function. To reduce malloc traffic, we allocate them using this
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
245 /// slab-like allocator, and destroy them after the pass completes. An
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246 /// important guarantee is that this allocator produces stable pointers to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
247 /// the chains.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
248 SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
249
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
250 /// \brief Function wide BasicBlock to BlockChain mapping.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
251 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
252 /// This mapping allows efficiently moving from any given basic block to the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
253 /// BlockChain it participates in, if any. We use it to, among other things,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
254 /// allow implicitly defining edges between chains as the existing edges
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
255 /// between basic blocks.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
256 DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
257
|
|
95
|
258 void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
259 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
|
|
77
|
260 const BlockFilterSet *BlockFilter = nullptr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
261 MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
262 BlockChain &Chain,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
263 const BlockFilterSet *BlockFilter);
|
|
95
|
264 MachineBasicBlock *
|
|
|
265 selectBestCandidateBlock(BlockChain &Chain,
|
|
|
266 SmallVectorImpl<MachineBasicBlock *> &WorkList,
|
|
|
267 const BlockFilterSet *BlockFilter);
|
|
|
268 MachineBasicBlock *
|
|
|
269 getFirstUnplacedBlock(MachineFunction &F, const BlockChain &PlacedChain,
|
|
|
270 MachineFunction::iterator &PrevUnplacedBlockIt,
|
|
|
271 const BlockFilterSet *BlockFilter);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
272 void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
273 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
|
|
77
|
274 const BlockFilterSet *BlockFilter = nullptr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
275 MachineBasicBlock *findBestLoopTop(MachineLoop &L,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
276 const BlockFilterSet &LoopBlockSet);
|
|
95
|
277 MachineBasicBlock *findBestLoopExit(MachineFunction &F, MachineLoop &L,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
278 const BlockFilterSet &LoopBlockSet);
|
|
100
|
279 BlockFilterSet collectLoopBlockSet(MachineFunction &F, MachineLoop &L);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
280 void buildLoopChains(MachineFunction &F, MachineLoop &L);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
281 void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
282 const BlockFilterSet &LoopBlockSet);
|
|
100
|
283 void rotateLoopWithProfile(BlockChain &LoopChain, MachineLoop &L,
|
|
|
284 const BlockFilterSet &LoopBlockSet);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
285 void buildCFGChains(MachineFunction &F);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
286
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
287 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
288 static char ID; // Pass identification, replacement for typeid
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
289 MachineBlockPlacement() : MachineFunctionPass(ID) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
290 initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
291 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
292
|
|
77
|
293 bool runOnMachineFunction(MachineFunction &F) override;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
294
|
|
77
|
295 void getAnalysisUsage(AnalysisUsage &AU) const override {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
296 AU.addRequired<MachineBranchProbabilityInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
297 AU.addRequired<MachineBlockFrequencyInfo>();
|
|
95
|
298 AU.addRequired<MachineDominatorTree>();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
299 AU.addRequired<MachineLoopInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
300 MachineFunctionPass::getAnalysisUsage(AU);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
301 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
302 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
303 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
304
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
305 char MachineBlockPlacement::ID = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
306 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
|
|
95
|
307 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement",
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
308 "Branch Probability Basic Block Placement", false, false)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
309 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
310 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
|
|
95
|
311 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
312 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
|
|
95
|
313 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement",
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
314 "Branch Probability Basic Block Placement", false, false)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
315
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
316 #ifndef NDEBUG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
317 /// \brief Helper to print the name of a MBB.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
318 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
319 /// Only used by debug logging.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
320 static std::string getBlockName(MachineBasicBlock *BB) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
321 std::string Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
322 raw_string_ostream OS(Result);
|
|
95
|
323 OS << "BB#" << BB->getNumber();
|
|
|
324 OS << " (derived from LLVM BB '" << BB->getName() << "')";
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
325 OS.flush();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
326 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
327 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
328
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329 /// \brief Helper to print the number of a MBB.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
331 /// Only used by debug logging.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
332 static std::string getBlockNum(MachineBasicBlock *BB) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
333 std::string Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
334 raw_string_ostream OS(Result);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
335 OS << "BB#" << BB->getNumber();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336 OS.flush();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
337 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
338 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339 #endif
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
340
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
341 /// \brief Mark a chain's successors as having one fewer preds.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
342 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
343 /// When a chain is being merged into the "placed" chain, this routine will
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
344 /// quickly walk the successors of each block in the chain and mark them as
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345 /// having one fewer active predecessor. It also adds any successors of this
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
346 /// chain which reach the zero-predecessor state to the worklist passed in.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
347 void MachineBlockPlacement::markChainSuccessors(
|
|
95
|
348 BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
349 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
350 const BlockFilterSet *BlockFilter) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
351 // Walk all the blocks in this chain, marking their successors as having
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
352 // a predecessor placed.
|
|
95
|
353 for (MachineBasicBlock *MBB : Chain) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
354 // Add any successors for which this is the only un-placed in-loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
355 // predecessor to the worklist as a viable candidate for CFG-neutral
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
356 // placement. No subsequent placement of this block will violate the CFG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
357 // shape, so we get to use heuristics to choose a favorable placement.
|
|
95
|
358 for (MachineBasicBlock *Succ : MBB->successors()) {
|
|
|
359 if (BlockFilter && !BlockFilter->count(Succ))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
360 continue;
|
|
95
|
361 BlockChain &SuccChain = *BlockToChain[Succ];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
362 // Disregard edges within a fixed chain, or edges to the loop header.
|
|
95
|
363 if (&Chain == &SuccChain || Succ == LoopHeaderBB)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
364 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
365
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
366 // This is a cross-chain edge that is within the loop, so decrement the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
367 // loop predecessor count of the destination chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
368 if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
369 BlockWorkList.push_back(*SuccChain.begin());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
370 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
371 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
372 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
373
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
374 /// \brief Select the best successor for a block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
375 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
376 /// This looks across all successors of a particular block and attempts to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
377 /// select the "best" one to be the layout successor. It only considers direct
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
378 /// successors which also pass the block filter. It will attempt to avoid
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
379 /// breaking CFG structure, but cave and break such structures in the case of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
380 /// very hot successor edges.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
381 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
382 /// \returns The best successor block found, or null if none are viable.
|
|
95
|
383 MachineBasicBlock *
|
|
|
384 MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
|
|
|
385 BlockChain &Chain,
|
|
|
386 const BlockFilterSet *BlockFilter) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
387 const BranchProbability HotProb(4, 5); // 80%
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
388
|
|
77
|
389 MachineBasicBlock *BestSucc = nullptr;
|
|
100
|
390 auto BestProb = BranchProbability::getZero();
|
|
|
391
|
|
|
392 // Adjust edge probabilities by excluding edges pointing to blocks that is
|
|
|
393 // either not in BlockFilter or is already in the current chain. Consider the
|
|
|
394 // following CFG:
|
|
|
395 //
|
|
|
396 // --->A
|
|
|
397 // | / \
|
|
|
398 // | B C
|
|
|
399 // | \ / \
|
|
|
400 // ----D E
|
|
|
401 //
|
|
|
402 // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after
|
|
|
403 // A->C is chosen as a fall-through, D won't be selected as a successor of C
|
|
|
404 // due to CFG constraint (the probability of C->D is not greater than
|
|
|
405 // HotProb). If we exclude E that is not in BlockFilter when calculating the
|
|
|
406 // probability of C->D, D will be selected and we will get A C D B as the
|
|
|
407 // layout of this loop.
|
|
|
408 auto AdjustedSumProb = BranchProbability::getOne();
|
|
|
409 SmallVector<MachineBasicBlock *, 4> Successors;
|
|
95
|
410 for (MachineBasicBlock *Succ : BB->successors()) {
|
|
100
|
411 bool SkipSucc = false;
|
|
|
412 if (BlockFilter && !BlockFilter->count(Succ)) {
|
|
|
413 SkipSucc = true;
|
|
|
414 } else {
|
|
|
415 BlockChain *SuccChain = BlockToChain[Succ];
|
|
|
416 if (SuccChain == &Chain) {
|
|
|
417 DEBUG(dbgs() << " " << getBlockName(Succ)
|
|
|
418 << " -> Already merged!\n");
|
|
|
419 SkipSucc = true;
|
|
|
420 } else if (Succ != *SuccChain->begin()) {
|
|
|
421 DEBUG(dbgs() << " " << getBlockName(Succ) << " -> Mid chain!\n");
|
|
|
422 continue;
|
|
|
423 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
424 }
|
|
100
|
425 if (SkipSucc)
|
|
|
426 AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ);
|
|
|
427 else
|
|
|
428 Successors.push_back(Succ);
|
|
|
429 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
430
|
|
100
|
431 DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
|
|
|
432 for (MachineBasicBlock *Succ : Successors) {
|
|
|
433 BranchProbability SuccProb;
|
|
|
434 uint32_t SuccProbN = MBPI->getEdgeProbability(BB, Succ).getNumerator();
|
|
|
435 uint32_t SuccProbD = AdjustedSumProb.getNumerator();
|
|
|
436 if (SuccProbN >= SuccProbD)
|
|
|
437 SuccProb = BranchProbability::getOne();
|
|
|
438 else
|
|
|
439 SuccProb = BranchProbability(SuccProbN, SuccProbD);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
440
|
|
95
|
441 // If we outline optional branches, look whether Succ is unavoidable, i.e.
|
|
|
442 // dominates all terminators of the MachineFunction. If it does, other
|
|
|
443 // successors must be optional. Don't do this for cold branches.
|
|
|
444 if (OutlineOptionalBranches && SuccProb > HotProb.getCompl() &&
|
|
|
445 UnavoidableBlocks.count(Succ) > 0) {
|
|
|
446 auto HasShortOptionalBranch = [&]() {
|
|
|
447 for (MachineBasicBlock *Pred : Succ->predecessors()) {
|
|
|
448 // Check whether there is an unplaced optional branch.
|
|
|
449 if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
|
|
|
450 BlockToChain[Pred] == &Chain)
|
|
|
451 continue;
|
|
|
452 // Check whether the optional branch has exactly one BB.
|
|
|
453 if (Pred->pred_size() > 1 || *Pred->pred_begin() != BB)
|
|
|
454 continue;
|
|
|
455 // Check whether the optional branch is small.
|
|
|
456 if (Pred->size() < OutlineOptionalThreshold)
|
|
|
457 return true;
|
|
|
458 }
|
|
|
459 return false;
|
|
|
460 };
|
|
|
461 if (!HasShortOptionalBranch())
|
|
|
462 return Succ;
|
|
|
463 }
|
|
|
464
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
465 // Only consider successors which are either "hot", or wouldn't violate
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
466 // any CFG constraints.
|
|
100
|
467 BlockChain &SuccChain = *BlockToChain[Succ];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
468 if (SuccChain.LoopPredecessors != 0) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
469 if (SuccProb < HotProb) {
|
|
95
|
470 DEBUG(dbgs() << " " << getBlockName(Succ) << " -> " << SuccProb
|
|
33
|
471 << " (prob) (CFG conflict)\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
472 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
473 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
474
|
|
95
|
475 // Make sure that a hot successor doesn't have a globally more
|
|
|
476 // important predecessor.
|
|
100
|
477 auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
|
|
95
|
478 BlockFrequency CandidateEdgeFreq =
|
|
100
|
479 MBFI->getBlockFreq(BB) * RealSuccProb * HotProb.getCompl();
|
|
95
|
480 bool BadCFGConflict = false;
|
|
|
481 for (MachineBasicBlock *Pred : Succ->predecessors()) {
|
|
|
482 if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
|
|
|
483 BlockToChain[Pred] == &Chain)
|
|
|
484 continue;
|
|
|
485 BlockFrequency PredEdgeFreq =
|
|
|
486 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
|
|
|
487 if (PredEdgeFreq >= CandidateEdgeFreq) {
|
|
|
488 BadCFGConflict = true;
|
|
|
489 break;
|
|
83
|
490 }
|
|
95
|
491 }
|
|
|
492 if (BadCFGConflict) {
|
|
|
493 DEBUG(dbgs() << " " << getBlockName(Succ) << " -> " << SuccProb
|
|
|
494 << " (prob) (non-cold CFG conflict)\n");
|
|
|
495 continue;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
496 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
497 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
498
|
|
95
|
499 DEBUG(dbgs() << " " << getBlockName(Succ) << " -> " << SuccProb
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
500 << " (prob)"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
501 << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "")
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
502 << "\n");
|
|
100
|
503 if (BestSucc && BestProb >= SuccProb)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
504 continue;
|
|
95
|
505 BestSucc = Succ;
|
|
100
|
506 BestProb = SuccProb;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
507 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 return BestSucc;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
509 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
511 /// \brief Select the best block from a worklist.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
512 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
513 /// This looks through the provided worklist as a list of candidate basic
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
514 /// blocks and select the most profitable one to place. The definition of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
515 /// profitable only really makes sense in the context of a loop. This returns
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
516 /// the most frequently visited block in the worklist, which in the case of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
517 /// a loop, is the one most desirable to be physically close to the rest of the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
518 /// loop body in order to improve icache behavior.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
519 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
520 /// \returns The best block found, or null if none are viable.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
521 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
522 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
523 const BlockFilterSet *BlockFilter) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
524 // Once we need to walk the worklist looking for a candidate, cleanup the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
525 // worklist of already placed entries.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526 // FIXME: If this shows up on profiles, it could be folded (at the cost of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
527 // some code complexity) into the loop below.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
528 WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(),
|
|
77
|
529 [&](MachineBasicBlock *BB) {
|
|
95
|
530 return BlockToChain.lookup(BB) == &Chain;
|
|
|
531 }),
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
532 WorkList.end());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
533
|
|
77
|
534 MachineBasicBlock *BestBlock = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
535 BlockFrequency BestFreq;
|
|
95
|
536 for (MachineBasicBlock *MBB : WorkList) {
|
|
|
537 BlockChain &SuccChain = *BlockToChain[MBB];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
538 if (&SuccChain == &Chain) {
|
|
95
|
539 DEBUG(dbgs() << " " << getBlockName(MBB) << " -> Already merged!\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
540 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
541 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
542 assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
543
|
|
95
|
544 BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB);
|
|
|
545 DEBUG(dbgs() << " " << getBlockName(MBB) << " -> ";
|
|
|
546 MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
547 if (BestBlock && BestFreq >= CandidateFreq)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
548 continue;
|
|
95
|
549 BestBlock = MBB;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
550 BestFreq = CandidateFreq;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
551 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
552 return BestBlock;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
553 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
554
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
555 /// \brief Retrieve the first unplaced basic block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
556 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
557 /// This routine is called when we are unable to use the CFG to walk through
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
558 /// all of the basic blocks and form a chain due to unnatural loops in the CFG.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
559 /// We walk through the function's blocks in order, starting from the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
560 /// LastUnplacedBlockIt. We update this iterator on each call to avoid
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
561 /// re-scanning the entire sequence on repeated calls to this routine.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
562 MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock(
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
563 MachineFunction &F, const BlockChain &PlacedChain,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
564 MachineFunction::iterator &PrevUnplacedBlockIt,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
565 const BlockFilterSet *BlockFilter) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
566 for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
567 ++I) {
|
|
95
|
568 if (BlockFilter && !BlockFilter->count(&*I))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
569 continue;
|
|
95
|
570 if (BlockToChain[&*I] != &PlacedChain) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
571 PrevUnplacedBlockIt = I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
572 // Now select the head of the chain to which the unplaced block belongs
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
573 // as the block to place. This will force the entire chain to be placed,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
574 // and satisfies the requirements of merging chains.
|
|
95
|
575 return *BlockToChain[&*I]->begin();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
576 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
577 }
|
|
77
|
578 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
579 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
580
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
581 void MachineBlockPlacement::buildChain(
|
|
95
|
582 MachineBasicBlock *BB, BlockChain &Chain,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
583 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
584 const BlockFilterSet *BlockFilter) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
585 assert(BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
586 assert(BlockToChain[BB] == &Chain);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
587 MachineFunction &F = *BB->getParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
588 MachineFunction::iterator PrevUnplacedBlockIt = F.begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
589
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590 MachineBasicBlock *LoopHeaderBB = BB;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
591 markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter);
|
|
77
|
592 BB = *std::prev(Chain.end());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593 for (;;) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594 assert(BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
595 assert(BlockToChain[BB] == &Chain);
|
|
77
|
596 assert(*std::prev(Chain.end()) == BB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598 // Look for the best viable successor if there is one to place immediately
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599 // after this block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
600 MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
601
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
602 // If an immediate successor isn't available, look for the best viable
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
603 // block among those we've identified as not violating the loop's CFG at
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
604 // this point. This won't be a fallthrough, but it will increase locality.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
605 if (!BestSucc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
606 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
607
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
608 if (!BestSucc) {
|
|
95
|
609 BestSucc =
|
|
|
610 getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, BlockFilter);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
611 if (!BestSucc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
612 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
613
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
614 DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
615 "layout successor until the CFG reduces\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
616 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
617
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
618 // Place this block, updating the datastructures to reflect its placement.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
619 BlockChain &SuccChain = *BlockToChain[BestSucc];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
620 // Zero out LoopPredecessors for the successor we're about to merge in case
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
621 // we selected a successor that didn't fit naturally into the CFG.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
622 SuccChain.LoopPredecessors = 0;
|
|
95
|
623 DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to "
|
|
|
624 << getBlockNum(BestSucc) << "\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
625 markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
626 Chain.merge(BestSucc, &SuccChain);
|
|
77
|
627 BB = *std::prev(Chain.end());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
628 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
629
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
630 DEBUG(dbgs() << "Finished forming chain for header block "
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
631 << getBlockNum(*Chain.begin()) << "\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
632 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
633
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
634 /// \brief Find the best loop top block for layout.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
635 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
636 /// Look for a block which is strictly better than the loop header for laying
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
637 /// out at the top of the loop. This looks for one and only one pattern:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
638 /// a latch block with no conditional exit. This block will cause a conditional
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
639 /// jump around it or will be the bottom of the loop if we lay it out in place,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
640 /// but if it it doesn't end up at the bottom of the loop for any reason,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
641 /// rotation alone won't fix it. Because such a block will always result in an
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642 /// unconditional jump (for the backedge) rotating it in front of the loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
643 /// header is always profitable.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
644 MachineBasicBlock *
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
645 MachineBlockPlacement::findBestLoopTop(MachineLoop &L,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
646 const BlockFilterSet &LoopBlockSet) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
647 // Check that the header hasn't been fused with a preheader block due to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
648 // crazy branches. If it has, we need to start with the header at the top to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
649 // prevent pulling the preheader into the loop body.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
650 BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
651 if (!LoopBlockSet.count(*HeaderChain.begin()))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
652 return L.getHeader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
653
|
|
95
|
654 DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader())
|
|
|
655 << "\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
656
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
657 BlockFrequency BestPredFreq;
|
|
77
|
658 MachineBasicBlock *BestPred = nullptr;
|
|
95
|
659 for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
660 if (!LoopBlockSet.count(Pred))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
661 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
662 DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", "
|
|
77
|
663 << Pred->succ_size() << " successors, ";
|
|
95
|
664 MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
665 if (Pred->succ_size() > 1)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
666 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
667
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
668 BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
669 if (!BestPred || PredFreq > BestPredFreq ||
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
670 (!(PredFreq < BestPredFreq) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
671 Pred->isLayoutSuccessor(L.getHeader()))) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
672 BestPred = Pred;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
673 BestPredFreq = PredFreq;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
674 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
675 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
676
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
677 // If no direct predecessor is fine, just use the loop header.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
678 if (!BestPred)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
679 return L.getHeader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
680
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
681 // Walk backwards through any straight line of predecessors.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
682 while (BestPred->pred_size() == 1 &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
683 (*BestPred->pred_begin())->succ_size() == 1 &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
684 *BestPred->pred_begin() != L.getHeader())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
685 BestPred = *BestPred->pred_begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
686
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
687 DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
688 return BestPred;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
689 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
690
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
691 /// \brief Find the best loop exiting block for layout.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
692 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
693 /// This routine implements the logic to analyze the loop looking for the best
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
694 /// block to layout at the top of the loop. Typically this is done to maximize
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
695 /// fallthrough opportunities.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
696 MachineBasicBlock *
|
|
95
|
697 MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
698 const BlockFilterSet &LoopBlockSet) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
699 // We don't want to layout the loop linearly in all cases. If the loop header
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
700 // is just a normal basic block in the loop, we want to look for what block
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
701 // within the loop is the best one to layout at the top. However, if the loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
702 // header has be pre-merged into a chain due to predecessors not having
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
703 // analyzable branches, *and* the predecessor it is merged with is *not* part
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
704 // of the loop, rotating the header into the middle of the loop will create
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
705 // a non-contiguous range of blocks which is Very Bad. So start with the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
706 // header and only rotate if safe.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
707 BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
708 if (!LoopBlockSet.count(*HeaderChain.begin()))
|
|
77
|
709 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
710
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
711 BlockFrequency BestExitEdgeFreq;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
712 unsigned BestExitLoopDepth = 0;
|
|
77
|
713 MachineBasicBlock *ExitingBB = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
714 // If there are exits to outer loops, loop rotation can severely limit
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
715 // fallthrough opportunites unless it selects such an exit. Keep a set of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
716 // blocks where rotating to exit with that block will reach an outer loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
717 SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
718
|
|
95
|
719 DEBUG(dbgs() << "Finding best loop exit for: " << getBlockName(L.getHeader())
|
|
|
720 << "\n");
|
|
|
721 for (MachineBasicBlock *MBB : L.getBlocks()) {
|
|
|
722 BlockChain &Chain = *BlockToChain[MBB];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
723 // Ensure that this block is at the end of a chain; otherwise it could be
|
|
95
|
724 // mid-way through an inner loop or a successor of an unanalyzable branch.
|
|
|
725 if (MBB != *std::prev(Chain.end()))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
726 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
727
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
728 // Now walk the successors. We need to establish whether this has a viable
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
729 // exiting successor and whether it has a viable non-exiting successor.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
730 // We store the old exiting state and restore it if a viable looping
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
731 // successor isn't found.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
732 MachineBasicBlock *OldExitingBB = ExitingBB;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
733 BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
734 bool HasLoopingSucc = false;
|
|
95
|
735 for (MachineBasicBlock *Succ : MBB->successors()) {
|
|
|
736 if (Succ->isEHPad())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
737 continue;
|
|
95
|
738 if (Succ == MBB)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
739 continue;
|
|
95
|
740 BlockChain &SuccChain = *BlockToChain[Succ];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
741 // Don't split chains, either this chain or the successor's chain.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
742 if (&Chain == &SuccChain) {
|
|
95
|
743 DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> "
|
|
|
744 << getBlockName(Succ) << " (chain conflict)\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
745 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
746 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
747
|
|
100
|
748 auto SuccProb = MBPI->getEdgeProbability(MBB, Succ);
|
|
95
|
749 if (LoopBlockSet.count(Succ)) {
|
|
|
750 DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> "
|
|
100
|
751 << getBlockName(Succ) << " (" << SuccProb << ")\n");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
752 HasLoopingSucc = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
753 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
754 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
755
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
756 unsigned SuccLoopDepth = 0;
|
|
95
|
757 if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
758 SuccLoopDepth = ExitLoop->getLoopDepth();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
759 if (ExitLoop->contains(&L))
|
|
95
|
760 BlocksExitingToOuterLoop.insert(MBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
761 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
762
|
|
95
|
763 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
|
|
|
764 DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> "
|
|
|
765 << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] (";
|
|
|
766 MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n");
|
|
33
|
767 // Note that we bias this toward an existing layout successor to retain
|
|
|
768 // incoming order in the absence of better information. The exit must have
|
|
|
769 // a frequency higher than the current exit before we consider breaking
|
|
|
770 // the layout.
|
|
|
771 BranchProbability Bias(100 - ExitBlockBias, 100);
|
|
95
|
772 if (!ExitingBB || SuccLoopDepth > BestExitLoopDepth ||
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
773 ExitEdgeFreq > BestExitEdgeFreq ||
|
|
95
|
774 (MBB->isLayoutSuccessor(Succ) &&
|
|
33
|
775 !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
776 BestExitEdgeFreq = ExitEdgeFreq;
|
|
95
|
777 ExitingBB = MBB;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
778 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
779 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
780
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
781 if (!HasLoopingSucc) {
|
|
95
|
782 // Restore the old exiting state, no viable looping successor was found.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
783 ExitingBB = OldExitingBB;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
784 BestExitEdgeFreq = OldBestExitEdgeFreq;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
785 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
786 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
787 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
788 // Without a candidate exiting block or with only a single block in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
789 // loop, just use the loop header to layout the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
790 if (!ExitingBB || L.getNumBlocks() == 1)
|
|
77
|
791 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
792
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
793 // Also, if we have exit blocks which lead to outer loops but didn't select
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
794 // one of them as the exiting block we are rotating toward, disable loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
795 // rotation altogether.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
796 if (!BlocksExitingToOuterLoop.empty() &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
797 !BlocksExitingToOuterLoop.count(ExitingBB))
|
|
77
|
798 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
799
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
800 DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
801 return ExitingBB;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
802 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
803
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
804 /// \brief Attempt to rotate an exiting block to the bottom of the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
805 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
806 /// Once we have built a chain, try to rotate it to line up the hot exit block
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
807 /// with fallthrough out of the loop if doing so doesn't introduce unnecessary
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
808 /// branches. For example, if the loop has fallthrough into its header and out
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
809 /// of its bottom already, don't rotate it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
810 void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
811 MachineBasicBlock *ExitingBB,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
812 const BlockFilterSet &LoopBlockSet) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
813 if (!ExitingBB)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
814 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
815
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
816 MachineBasicBlock *Top = *LoopChain.begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
817 bool ViableTopFallthrough = false;
|
|
95
|
818 for (MachineBasicBlock *Pred : Top->predecessors()) {
|
|
|
819 BlockChain *PredChain = BlockToChain[Pred];
|
|
|
820 if (!LoopBlockSet.count(Pred) &&
|
|
|
821 (!PredChain || Pred == *std::prev(PredChain->end()))) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
822 ViableTopFallthrough = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
823 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
824 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
825 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
826
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
827 // If the header has viable fallthrough, check whether the current loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
828 // bottom is a viable exiting block. If so, bail out as rotating will
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
829 // introduce an unnecessary branch.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
830 if (ViableTopFallthrough) {
|
|
77
|
831 MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
|
|
95
|
832 for (MachineBasicBlock *Succ : Bottom->successors()) {
|
|
|
833 BlockChain *SuccChain = BlockToChain[Succ];
|
|
|
834 if (!LoopBlockSet.count(Succ) &&
|
|
|
835 (!SuccChain || Succ == *SuccChain->begin()))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
836 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
837 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
838 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
839
|
|
95
|
840 BlockChain::iterator ExitIt =
|
|
|
841 std::find(LoopChain.begin(), LoopChain.end(), ExitingBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
842 if (ExitIt == LoopChain.end())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
843 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
844
|
|
77
|
845 std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
846 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
847
|
|
100
|
848 /// \brief Attempt to rotate a loop based on profile data to reduce branch cost.
|
|
|
849 ///
|
|
|
850 /// With profile data, we can determine the cost in terms of missed fall through
|
|
|
851 /// opportunities when rotating a loop chain and select the best rotation.
|
|
|
852 /// Basically, there are three kinds of cost to consider for each rotation:
|
|
|
853 /// 1. The possibly missed fall through edge (if it exists) from BB out of
|
|
|
854 /// the loop to the loop header.
|
|
|
855 /// 2. The possibly missed fall through edges (if they exist) from the loop
|
|
|
856 /// exits to BB out of the loop.
|
|
|
857 /// 3. The missed fall through edge (if it exists) from the last BB to the
|
|
|
858 /// first BB in the loop chain.
|
|
|
859 /// Therefore, the cost for a given rotation is the sum of costs listed above.
|
|
|
860 /// We select the best rotation with the smallest cost.
|
|
|
861 void MachineBlockPlacement::rotateLoopWithProfile(
|
|
|
862 BlockChain &LoopChain, MachineLoop &L, const BlockFilterSet &LoopBlockSet) {
|
|
|
863 auto HeaderBB = L.getHeader();
|
|
|
864 auto HeaderIter = std::find(LoopChain.begin(), LoopChain.end(), HeaderBB);
|
|
|
865 auto RotationPos = LoopChain.end();
|
|
|
866
|
|
|
867 BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency();
|
|
|
868
|
|
|
869 // A utility lambda that scales up a block frequency by dividing it by a
|
|
|
870 // branch probability which is the reciprocal of the scale.
|
|
|
871 auto ScaleBlockFrequency = [](BlockFrequency Freq,
|
|
|
872 unsigned Scale) -> BlockFrequency {
|
|
|
873 if (Scale == 0)
|
|
|
874 return 0;
|
|
|
875 // Use operator / between BlockFrequency and BranchProbability to implement
|
|
|
876 // saturating multiplication.
|
|
|
877 return Freq / BranchProbability(1, Scale);
|
|
|
878 };
|
|
|
879
|
|
|
880 // Compute the cost of the missed fall-through edge to the loop header if the
|
|
|
881 // chain head is not the loop header. As we only consider natural loops with
|
|
|
882 // single header, this computation can be done only once.
|
|
|
883 BlockFrequency HeaderFallThroughCost(0);
|
|
|
884 for (auto *Pred : HeaderBB->predecessors()) {
|
|
|
885 BlockChain *PredChain = BlockToChain[Pred];
|
|
|
886 if (!LoopBlockSet.count(Pred) &&
|
|
|
887 (!PredChain || Pred == *std::prev(PredChain->end()))) {
|
|
|
888 auto EdgeFreq =
|
|
|
889 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, HeaderBB);
|
|
|
890 auto FallThruCost = ScaleBlockFrequency(EdgeFreq, MisfetchCost);
|
|
|
891 // If the predecessor has only an unconditional jump to the header, we
|
|
|
892 // need to consider the cost of this jump.
|
|
|
893 if (Pred->succ_size() == 1)
|
|
|
894 FallThruCost += ScaleBlockFrequency(EdgeFreq, JumpInstCost);
|
|
|
895 HeaderFallThroughCost = std::max(HeaderFallThroughCost, FallThruCost);
|
|
|
896 }
|
|
|
897 }
|
|
|
898
|
|
|
899 // Here we collect all exit blocks in the loop, and for each exit we find out
|
|
|
900 // its hottest exit edge. For each loop rotation, we define the loop exit cost
|
|
|
901 // as the sum of frequencies of exit edges we collect here, excluding the exit
|
|
|
902 // edge from the tail of the loop chain.
|
|
|
903 SmallVector<std::pair<MachineBasicBlock *, BlockFrequency>, 4> ExitsWithFreq;
|
|
|
904 for (auto BB : LoopChain) {
|
|
|
905 auto LargestExitEdgeProb = BranchProbability::getZero();
|
|
|
906 for (auto *Succ : BB->successors()) {
|
|
|
907 BlockChain *SuccChain = BlockToChain[Succ];
|
|
|
908 if (!LoopBlockSet.count(Succ) &&
|
|
|
909 (!SuccChain || Succ == *SuccChain->begin())) {
|
|
|
910 auto SuccProb = MBPI->getEdgeProbability(BB, Succ);
|
|
|
911 LargestExitEdgeProb = std::max(LargestExitEdgeProb, SuccProb);
|
|
|
912 }
|
|
|
913 }
|
|
|
914 if (LargestExitEdgeProb > BranchProbability::getZero()) {
|
|
|
915 auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb;
|
|
|
916 ExitsWithFreq.emplace_back(BB, ExitFreq);
|
|
|
917 }
|
|
|
918 }
|
|
|
919
|
|
|
920 // In this loop we iterate every block in the loop chain and calculate the
|
|
|
921 // cost assuming the block is the head of the loop chain. When the loop ends,
|
|
|
922 // we should have found the best candidate as the loop chain's head.
|
|
|
923 for (auto Iter = LoopChain.begin(), TailIter = std::prev(LoopChain.end()),
|
|
|
924 EndIter = LoopChain.end();
|
|
|
925 Iter != EndIter; Iter++, TailIter++) {
|
|
|
926 // TailIter is used to track the tail of the loop chain if the block we are
|
|
|
927 // checking (pointed by Iter) is the head of the chain.
|
|
|
928 if (TailIter == LoopChain.end())
|
|
|
929 TailIter = LoopChain.begin();
|
|
|
930
|
|
|
931 auto TailBB = *TailIter;
|
|
|
932
|
|
|
933 // Calculate the cost by putting this BB to the top.
|
|
|
934 BlockFrequency Cost = 0;
|
|
|
935
|
|
|
936 // If the current BB is the loop header, we need to take into account the
|
|
|
937 // cost of the missed fall through edge from outside of the loop to the
|
|
|
938 // header.
|
|
|
939 if (Iter != HeaderIter)
|
|
|
940 Cost += HeaderFallThroughCost;
|
|
|
941
|
|
|
942 // Collect the loop exit cost by summing up frequencies of all exit edges
|
|
|
943 // except the one from the chain tail.
|
|
|
944 for (auto &ExitWithFreq : ExitsWithFreq)
|
|
|
945 if (TailBB != ExitWithFreq.first)
|
|
|
946 Cost += ExitWithFreq.second;
|
|
|
947
|
|
|
948 // The cost of breaking the once fall-through edge from the tail to the top
|
|
|
949 // of the loop chain. Here we need to consider three cases:
|
|
|
950 // 1. If the tail node has only one successor, then we will get an
|
|
|
951 // additional jmp instruction. So the cost here is (MisfetchCost +
|
|
|
952 // JumpInstCost) * tail node frequency.
|
|
|
953 // 2. If the tail node has two successors, then we may still get an
|
|
|
954 // additional jmp instruction if the layout successor after the loop
|
|
|
955 // chain is not its CFG successor. Note that the more frequently executed
|
|
|
956 // jmp instruction will be put ahead of the other one. Assume the
|
|
|
957 // frequency of those two branches are x and y, where x is the frequency
|
|
|
958 // of the edge to the chain head, then the cost will be
|
|
|
959 // (x * MisfetechCost + min(x, y) * JumpInstCost) * tail node frequency.
|
|
|
960 // 3. If the tail node has more than two successors (this rarely happens),
|
|
|
961 // we won't consider any additional cost.
|
|
|
962 if (TailBB->isSuccessor(*Iter)) {
|
|
|
963 auto TailBBFreq = MBFI->getBlockFreq(TailBB);
|
|
|
964 if (TailBB->succ_size() == 1)
|
|
|
965 Cost += ScaleBlockFrequency(TailBBFreq.getFrequency(),
|
|
|
966 MisfetchCost + JumpInstCost);
|
|
|
967 else if (TailBB->succ_size() == 2) {
|
|
|
968 auto TailToHeadProb = MBPI->getEdgeProbability(TailBB, *Iter);
|
|
|
969 auto TailToHeadFreq = TailBBFreq * TailToHeadProb;
|
|
|
970 auto ColderEdgeFreq = TailToHeadProb > BranchProbability(1, 2)
|
|
|
971 ? TailBBFreq * TailToHeadProb.getCompl()
|
|
|
972 : TailToHeadFreq;
|
|
|
973 Cost += ScaleBlockFrequency(TailToHeadFreq, MisfetchCost) +
|
|
|
974 ScaleBlockFrequency(ColderEdgeFreq, JumpInstCost);
|
|
|
975 }
|
|
|
976 }
|
|
|
977
|
|
|
978 DEBUG(dbgs() << "The cost of loop rotation by making " << getBlockNum(*Iter)
|
|
|
979 << " to the top: " << Cost.getFrequency() << "\n");
|
|
|
980
|
|
|
981 if (Cost < SmallestRotationCost) {
|
|
|
982 SmallestRotationCost = Cost;
|
|
|
983 RotationPos = Iter;
|
|
|
984 }
|
|
|
985 }
|
|
|
986
|
|
|
987 if (RotationPos != LoopChain.end()) {
|
|
|
988 DEBUG(dbgs() << "Rotate loop by making " << getBlockNum(*RotationPos)
|
|
|
989 << " to the top\n");
|
|
|
990 std::rotate(LoopChain.begin(), RotationPos, LoopChain.end());
|
|
|
991 }
|
|
|
992 }
|
|
|
993
|
|
|
994 /// \brief Collect blocks in the given loop that are to be placed.
|
|
|
995 ///
|
|
|
996 /// When profile data is available, exclude cold blocks from the returned set;
|
|
|
997 /// otherwise, collect all blocks in the loop.
|
|
|
998 MachineBlockPlacement::BlockFilterSet
|
|
|
999 MachineBlockPlacement::collectLoopBlockSet(MachineFunction &F, MachineLoop &L) {
|
|
|
1000 BlockFilterSet LoopBlockSet;
|
|
|
1001
|
|
|
1002 // Filter cold blocks off from LoopBlockSet when profile data is available.
|
|
|
1003 // Collect the sum of frequencies of incoming edges to the loop header from
|
|
|
1004 // outside. If we treat the loop as a super block, this is the frequency of
|
|
|
1005 // the loop. Then for each block in the loop, we calculate the ratio between
|
|
|
1006 // its frequency and the frequency of the loop block. When it is too small,
|
|
|
1007 // don't add it to the loop chain. If there are outer loops, then this block
|
|
|
1008 // will be merged into the first outer loop chain for which this block is not
|
|
|
1009 // cold anymore. This needs precise profile data and we only do this when
|
|
|
1010 // profile data is available.
|
|
|
1011 if (F.getFunction()->getEntryCount()) {
|
|
|
1012 BlockFrequency LoopFreq(0);
|
|
|
1013 for (auto LoopPred : L.getHeader()->predecessors())
|
|
|
1014 if (!L.contains(LoopPred))
|
|
|
1015 LoopFreq += MBFI->getBlockFreq(LoopPred) *
|
|
|
1016 MBPI->getEdgeProbability(LoopPred, L.getHeader());
|
|
|
1017
|
|
|
1018 for (MachineBasicBlock *LoopBB : L.getBlocks()) {
|
|
|
1019 auto Freq = MBFI->getBlockFreq(LoopBB).getFrequency();
|
|
|
1020 if (Freq == 0 || LoopFreq.getFrequency() / Freq > LoopToColdBlockRatio)
|
|
|
1021 continue;
|
|
|
1022 LoopBlockSet.insert(LoopBB);
|
|
|
1023 }
|
|
|
1024 } else
|
|
|
1025 LoopBlockSet.insert(L.block_begin(), L.block_end());
|
|
|
1026
|
|
|
1027 return LoopBlockSet;
|
|
|
1028 }
|
|
|
1029
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1030 /// \brief Forms basic block chains from the natural loop structures.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1031 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1032 /// These chains are designed to preserve the existing *structure* of the code
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1033 /// as much as possible. We can then stitch the chains together in a way which
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1034 /// both preserves the topological structure and minimizes taken conditional
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1035 /// branches.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1036 void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1037 MachineLoop &L) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1038 // First recurse through any nested loops, building chains for those inner
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1039 // loops.
|
|
95
|
1040 for (MachineLoop *InnerLoop : L)
|
|
|
1041 buildLoopChains(F, *InnerLoop);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1042
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1043 SmallVector<MachineBasicBlock *, 16> BlockWorkList;
|
|
100
|
1044 BlockFilterSet LoopBlockSet = collectLoopBlockSet(F, L);
|
|
|
1045
|
|
|
1046 // Check if we have profile data for this function. If yes, we will rotate
|
|
|
1047 // this loop by modeling costs more precisely which requires the profile data
|
|
|
1048 // for better layout.
|
|
|
1049 bool RotateLoopWithProfile =
|
|
|
1050 PreciseRotationCost && F.getFunction()->getEntryCount();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1051
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1052 // First check to see if there is an obviously preferable top block for the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1053 // loop. This will default to the header, but may end up as one of the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1054 // predecessors to the header if there is one which will result in strictly
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1055 // fewer branches in the loop body.
|
|
100
|
1056 // When we use profile data to rotate the loop, this is unnecessary.
|
|
|
1057 MachineBasicBlock *LoopTop =
|
|
|
1058 RotateLoopWithProfile ? L.getHeader() : findBestLoopTop(L, LoopBlockSet);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1059
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1060 // If we selected just the header for the loop top, look for a potentially
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1061 // profitable exit block in the event that rotating the loop can eliminate
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1062 // branches by placing an exit edge at the bottom.
|
|
77
|
1063 MachineBasicBlock *ExitingBB = nullptr;
|
|
100
|
1064 if (!RotateLoopWithProfile && LoopTop == L.getHeader())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1065 ExitingBB = findBestLoopExit(F, L, LoopBlockSet);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1066
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1067 BlockChain &LoopChain = *BlockToChain[LoopTop];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1068
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1069 // FIXME: This is a really lame way of walking the chains in the loop: we
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1070 // walk the blocks, and use a set to prevent visiting a particular chain
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1071 // twice.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1072 SmallPtrSet<BlockChain *, 4> UpdatedPreds;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1073 assert(LoopChain.LoopPredecessors == 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1074 UpdatedPreds.insert(&LoopChain);
|
|
100
|
1075
|
|
|
1076 for (MachineBasicBlock *LoopBB : LoopBlockSet) {
|
|
95
|
1077 BlockChain &Chain = *BlockToChain[LoopBB];
|
|
83
|
1078 if (!UpdatedPreds.insert(&Chain).second)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1079 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1080
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1081 assert(Chain.LoopPredecessors == 0);
|
|
95
|
1082 for (MachineBasicBlock *ChainBB : Chain) {
|
|
|
1083 assert(BlockToChain[ChainBB] == &Chain);
|
|
|
1084 for (MachineBasicBlock *Pred : ChainBB->predecessors()) {
|
|
|
1085 if (BlockToChain[Pred] == &Chain || !LoopBlockSet.count(Pred))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1086 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1087 ++Chain.LoopPredecessors;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1088 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1089 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1090
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1091 if (Chain.LoopPredecessors == 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1092 BlockWorkList.push_back(*Chain.begin());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1093 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1094
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1095 buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet);
|
|
100
|
1096
|
|
|
1097 if (RotateLoopWithProfile)
|
|
|
1098 rotateLoopWithProfile(LoopChain, L, LoopBlockSet);
|
|
|
1099 else
|
|
|
1100 rotateLoop(LoopChain, ExitingBB, LoopBlockSet);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1101
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1102 DEBUG({
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1103 // Crash at the end so we get all of the debugging output first.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1104 bool BadLoop = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1105 if (LoopChain.LoopPredecessors) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1106 BadLoop = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1107 dbgs() << "Loop chain contains a block without its preds placed!\n"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1108 << " Loop header: " << getBlockName(*L.block_begin()) << "\n"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1109 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1110 }
|
|
95
|
1111 for (MachineBasicBlock *ChainBB : LoopChain) {
|
|
|
1112 dbgs() << " ... " << getBlockName(ChainBB) << "\n";
|
|
|
1113 if (!LoopBlockSet.erase(ChainBB)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1114 // We don't mark the loop as bad here because there are real situations
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1115 // where this can occur. For example, with an unanalyzable fallthrough
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1116 // from a loop block to a non-loop block or vice versa.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1117 dbgs() << "Loop chain contains a block not contained by the loop!\n"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1118 << " Loop header: " << getBlockName(*L.block_begin()) << "\n"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1119 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
|
|
95
|
1120 << " Bad block: " << getBlockName(ChainBB) << "\n";
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1121 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1122 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1123
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1124 if (!LoopBlockSet.empty()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1125 BadLoop = true;
|
|
95
|
1126 for (MachineBasicBlock *LoopBB : LoopBlockSet)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1127 dbgs() << "Loop contains blocks never placed into a chain!\n"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1128 << " Loop header: " << getBlockName(*L.block_begin()) << "\n"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1129 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
|
|
95
|
1130 << " Bad block: " << getBlockName(LoopBB) << "\n";
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1131 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1132 assert(!BadLoop && "Detected problems with the placement of this loop.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1133 });
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1134 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1135
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1136 void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1137 // Ensure that every BB in the function has an associated chain to simplify
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1138 // the assumptions of the remaining algorithm.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1139 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1140 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
|
|
95
|
1141 MachineBasicBlock *BB = &*FI;
|
|
|
1142 BlockChain *Chain =
|
|
|
1143 new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1144 // Also, merge any blocks which we cannot reason about and must preserve
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1145 // the exact fallthrough behavior for.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1146 for (;;) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1147 Cond.clear();
|
|
77
|
1148 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1149 if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1150 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1151
|
|
95
|
1152 MachineFunction::iterator NextFI = std::next(FI);
|
|
|
1153 MachineBasicBlock *NextBB = &*NextFI;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1154 // Ensure that the layout successor is a viable block, as we know that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1155 // fallthrough is a possibility.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1156 assert(NextFI != FE && "Can't fallthrough past the last block.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1157 DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: "
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1158 << getBlockName(BB) << " -> " << getBlockName(NextBB)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1159 << "\n");
|
|
77
|
1160 Chain->merge(NextBB, nullptr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1161 FI = NextFI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1162 BB = NextBB;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1163 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1164 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1165
|
|
95
|
1166 if (OutlineOptionalBranches) {
|
|
|
1167 // Find the nearest common dominator of all of F's terminators.
|
|
|
1168 MachineBasicBlock *Terminator = nullptr;
|
|
|
1169 for (MachineBasicBlock &MBB : F) {
|
|
|
1170 if (MBB.succ_size() == 0) {
|
|
|
1171 if (Terminator == nullptr)
|
|
|
1172 Terminator = &MBB;
|
|
|
1173 else
|
|
|
1174 Terminator = MDT->findNearestCommonDominator(Terminator, &MBB);
|
|
|
1175 }
|
|
|
1176 }
|
|
|
1177
|
|
|
1178 // MBBs dominating this common dominator are unavoidable.
|
|
|
1179 UnavoidableBlocks.clear();
|
|
|
1180 for (MachineBasicBlock &MBB : F) {
|
|
|
1181 if (MDT->dominates(&MBB, Terminator)) {
|
|
|
1182 UnavoidableBlocks.insert(&MBB);
|
|
|
1183 }
|
|
|
1184 }
|
|
|
1185 }
|
|
|
1186
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1187 // Build any loop-based chains.
|
|
95
|
1188 for (MachineLoop *L : *MLI)
|
|
|
1189 buildLoopChains(F, *L);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1190
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1191 SmallVector<MachineBasicBlock *, 16> BlockWorkList;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1192
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1193 SmallPtrSet<BlockChain *, 4> UpdatedPreds;
|
|
95
|
1194 for (MachineBasicBlock &MBB : F) {
|
|
|
1195 BlockChain &Chain = *BlockToChain[&MBB];
|
|
83
|
1196 if (!UpdatedPreds.insert(&Chain).second)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1197 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1198
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1199 assert(Chain.LoopPredecessors == 0);
|
|
95
|
1200 for (MachineBasicBlock *ChainBB : Chain) {
|
|
|
1201 assert(BlockToChain[ChainBB] == &Chain);
|
|
|
1202 for (MachineBasicBlock *Pred : ChainBB->predecessors()) {
|
|
|
1203 if (BlockToChain[Pred] == &Chain)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1204 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1205 ++Chain.LoopPredecessors;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1206 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1207 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1208
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1209 if (Chain.LoopPredecessors == 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1210 BlockWorkList.push_back(*Chain.begin());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1211 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1212
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1213 BlockChain &FunctionChain = *BlockToChain[&F.front()];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1214 buildChain(&F.front(), FunctionChain, BlockWorkList);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1215
|
|
33
|
1216 #ifndef NDEBUG
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1217 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType;
|
|
33
|
1218 #endif
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1219 DEBUG({
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1220 // Crash at the end so we get all of the debugging output first.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1221 bool BadFunc = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1222 FunctionBlockSetType FunctionBlockSet;
|
|
95
|
1223 for (MachineBasicBlock &MBB : F)
|
|
|
1224 FunctionBlockSet.insert(&MBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1225
|
|
95
|
1226 for (MachineBasicBlock *ChainBB : FunctionChain)
|
|
|
1227 if (!FunctionBlockSet.erase(ChainBB)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1228 BadFunc = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1229 dbgs() << "Function chain contains a block not in the function!\n"
|
|
95
|
1230 << " Bad block: " << getBlockName(ChainBB) << "\n";
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1231 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1232
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1233 if (!FunctionBlockSet.empty()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1234 BadFunc = true;
|
|
95
|
1235 for (MachineBasicBlock *RemainingBB : FunctionBlockSet)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1236 dbgs() << "Function contains blocks never placed into a chain!\n"
|
|
95
|
1237 << " Bad block: " << getBlockName(RemainingBB) << "\n";
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1238 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1239 assert(!BadFunc && "Detected problems with the block placement.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1240 });
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1241
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1242 // Splice the blocks into place.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1243 MachineFunction::iterator InsertPos = F.begin();
|
|
95
|
1244 for (MachineBasicBlock *ChainBB : FunctionChain) {
|
|
|
1245 DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain "
|
|
|
1246 : " ... ")
|
|
|
1247 << getBlockName(ChainBB) << "\n");
|
|
|
1248 if (InsertPos != MachineFunction::iterator(ChainBB))
|
|
|
1249 F.splice(InsertPos, ChainBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1250 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1251 ++InsertPos;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1252
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1253 // Update the terminator of the previous block.
|
|
95
|
1254 if (ChainBB == *FunctionChain.begin())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1255 continue;
|
|
95
|
1256 MachineBasicBlock *PrevBB = &*std::prev(MachineFunction::iterator(ChainBB));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1257
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1258 // FIXME: It would be awesome of updateTerminator would just return rather
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1259 // than assert when the branch cannot be analyzed in order to remove this
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1260 // boiler plate.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1261 Cond.clear();
|
|
77
|
1262 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1263 if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1264 // The "PrevBB" is not yet updated to reflect current code layout, so,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1265 // o. it may fall-through to a block without explict "goto" instruction
|
|
95
|
1266 // before layout, and no longer fall-through it after layout; or
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1267 // o. just opposite.
|
|
95
|
1268 //
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1269 // AnalyzeBranch() may return erroneous value for FBB when these two
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1270 // situations take place. For the first scenario FBB is mistakenly set
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1271 // NULL; for the 2nd scenario, the FBB, which is expected to be NULL,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1272 // is mistakenly pointing to "*BI".
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1273 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1274 bool needUpdateBr = true;
|
|
95
|
1275 if (!Cond.empty() && (!FBB || FBB == ChainBB)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1276 PrevBB->updateTerminator();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1277 needUpdateBr = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1278 Cond.clear();
|
|
77
|
1279 TBB = FBB = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1280 if (TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1281 // FIXME: This should never take place.
|
|
77
|
1282 TBB = FBB = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1283 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1284 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1285
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1286 // If PrevBB has a two-way branch, try to re-order the branches
|
|
100
|
1287 // such that we branch to the successor with higher probability first.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1288 if (TBB && !Cond.empty() && FBB &&
|
|
100
|
1289 MBPI->getEdgeProbability(PrevBB, FBB) >
|
|
|
1290 MBPI->getEdgeProbability(PrevBB, TBB) &&
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1291 !TII->ReverseBranchCondition(Cond)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1292 DEBUG(dbgs() << "Reverse order of the two branches: "
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1293 << getBlockName(PrevBB) << "\n");
|
|
100
|
1294 DEBUG(dbgs() << " Edge probability: "
|
|
|
1295 << MBPI->getEdgeProbability(PrevBB, FBB) << " vs "
|
|
|
1296 << MBPI->getEdgeProbability(PrevBB, TBB) << "\n");
|
|
95
|
1297 DebugLoc dl; // FIXME: this is nowhere
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1298 TII->RemoveBranch(*PrevBB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1299 TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1300 needUpdateBr = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1301 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1302 if (needUpdateBr)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1303 PrevBB->updateTerminator();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1304 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1305 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1306
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1307 // Fixup the last block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1308 Cond.clear();
|
|
77
|
1309 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1310 if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1311 F.back().updateTerminator();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1312
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1313 // Walk through the backedges of the function now that we have fully laid out
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1314 // the basic blocks and align the destination of each backedge. We don't rely
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1315 // exclusively on the loop info here so that we can align backedges in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1316 // unnatural CFGs and backedges that were introduced purely because of the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1317 // loop rotations done during this layout pass.
|
|
95
|
1318 // FIXME: Use Function::optForSize().
|
|
83
|
1319 if (F.getFunction()->hasFnAttribute(Attribute::OptimizeForSize))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1320 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1321 if (FunctionChain.begin() == FunctionChain.end())
|
|
95
|
1322 return; // Empty chain.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1323
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1324 const BranchProbability ColdProb(1, 5); // 20%
|
|
95
|
1325 BlockFrequency EntryFreq = MBFI->getBlockFreq(&F.front());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1326 BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb;
|
|
95
|
1327 for (MachineBasicBlock *ChainBB : FunctionChain) {
|
|
|
1328 if (ChainBB == *FunctionChain.begin())
|
|
|
1329 continue;
|
|
|
1330
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1331 // Don't align non-looping basic blocks. These are unlikely to execute
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1332 // enough times to matter in practice. Note that we'll still handle
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1333 // unnatural CFGs inside of a natural outer loop (the common case) and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1334 // rotated loops.
|
|
95
|
1335 MachineLoop *L = MLI->getLoopFor(ChainBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1336 if (!L)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1337 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1338
|
|
83
|
1339 unsigned Align = TLI->getPrefLoopAlignment(L);
|
|
|
1340 if (!Align)
|
|
95
|
1341 continue; // Don't care about loop alignment.
|
|
83
|
1342
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1343 // If the block is cold relative to the function entry don't waste space
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1344 // aligning it.
|
|
95
|
1345 BlockFrequency Freq = MBFI->getBlockFreq(ChainBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1346 if (Freq < WeightedEntryFreq)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1347 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1348
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1349 // If the block is cold relative to its loop header, don't align it
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1350 // regardless of what edges into the block exist.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1351 MachineBasicBlock *LoopHeader = L->getHeader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1352 BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1353 if (Freq < (LoopHeaderFreq * ColdProb))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1354 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1355
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1356 // Check for the existence of a non-layout predecessor which would benefit
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1357 // from aligning this block.
|
|
95
|
1358 MachineBasicBlock *LayoutPred =
|
|
|
1359 &*std::prev(MachineFunction::iterator(ChainBB));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1360
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1361 // Force alignment if all the predecessors are jumps. We already checked
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1362 // that the block isn't cold above.
|
|
95
|
1363 if (!LayoutPred->isSuccessor(ChainBB)) {
|
|
|
1364 ChainBB->setAlignment(Align);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1365 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1366 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1367
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1368 // Align this block if the layout predecessor's edge into this block is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1369 // cold relative to the block. When this is true, other predecessors make up
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1370 // all of the hot entries into the block and thus alignment is likely to be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1371 // important.
|
|
95
|
1372 BranchProbability LayoutProb =
|
|
|
1373 MBPI->getEdgeProbability(LayoutPred, ChainBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1374 BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1375 if (LayoutEdgeFreq <= (Freq * ColdProb))
|
|
95
|
1376 ChainBB->setAlignment(Align);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1377 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1378 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1379
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1380 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1381 // Check for single-block functions and skip them.
|
|
77
|
1382 if (std::next(F.begin()) == F.end())
|
|
|
1383 return false;
|
|
|
1384
|
|
|
1385 if (skipOptnoneFunction(*F.getFunction()))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1386 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1387
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1388 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1389 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1390 MLI = &getAnalysis<MachineLoopInfo>();
|
|
77
|
1391 TII = F.getSubtarget().getInstrInfo();
|
|
|
1392 TLI = F.getSubtarget().getTargetLowering();
|
|
95
|
1393 MDT = &getAnalysis<MachineDominatorTree>();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1394 assert(BlockToChain.empty());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1395
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1396 buildCFGChains(F);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1397
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1398 BlockToChain.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1399 ChainAllocator.DestroyAll();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1400
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1401 if (AlignAllBlock)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1402 // Align all of the blocks in the function to a specific alignment.
|
|
95
|
1403 for (MachineBasicBlock &MBB : F)
|
|
|
1404 MBB.setAlignment(AlignAllBlock);
|
|
100
|
1405 else if (AlignAllNonFallThruBlocks) {
|
|
|
1406 // Align all of the blocks that have no fall-through predecessors to a
|
|
|
1407 // specific alignment.
|
|
|
1408 for (auto MBI = std::next(F.begin()), MBE = F.end(); MBI != MBE; ++MBI) {
|
|
|
1409 auto LayoutPred = std::prev(MBI);
|
|
|
1410 if (!LayoutPred->isSuccessor(&*MBI))
|
|
|
1411 MBI->setAlignment(AlignAllNonFallThruBlocks);
|
|
|
1412 }
|
|
|
1413 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1414
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1415 // We always return true as we have no way to track whether the final order
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1416 // differs from the original order.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1417 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1418 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1419
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1420 namespace {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1421 /// \brief A pass to compute block placement statistics.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1422 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1423 /// A separate pass to compute interesting statistics for evaluating block
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1424 /// placement. This is separate from the actual placement pass so that they can
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1425 /// be computed in the absence of any placement transformations or when using
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1426 /// alternative placement strategies.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1427 class MachineBlockPlacementStats : public MachineFunctionPass {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1428 /// \brief A handle to the branch probability pass.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1429 const MachineBranchProbabilityInfo *MBPI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1430
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1431 /// \brief A handle to the function-wide block frequency pass.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1432 const MachineBlockFrequencyInfo *MBFI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1433
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1434 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1435 static char ID; // Pass identification, replacement for typeid
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1436 MachineBlockPlacementStats() : MachineFunctionPass(ID) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1437 initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1438 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1439
|
|
77
|
1440 bool runOnMachineFunction(MachineFunction &F) override;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1441
|
|
77
|
1442 void getAnalysisUsage(AnalysisUsage &AU) const override {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1443 AU.addRequired<MachineBranchProbabilityInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1444 AU.addRequired<MachineBlockFrequencyInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1445 AU.setPreservesAll();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1446 MachineFunctionPass::getAnalysisUsage(AU);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1447 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1448 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1449 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1450
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1451 char MachineBlockPlacementStats::ID = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1452 char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1453 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1454 "Basic Block Placement Stats", false, false)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1455 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1456 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1457 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats",
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1458 "Basic Block Placement Stats", false, false)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1459
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1460 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1461 // Check for single-block functions and skip them.
|
|
77
|
1462 if (std::next(F.begin()) == F.end())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1463 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1464
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1465 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1466 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1467
|
|
95
|
1468 for (MachineBasicBlock &MBB : F) {
|
|
|
1469 BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
|
|
|
1470 Statistic &NumBranches =
|
|
|
1471 (MBB.succ_size() > 1) ? NumCondBranches : NumUncondBranches;
|
|
|
1472 Statistic &BranchTakenFreq =
|
|
|
1473 (MBB.succ_size() > 1) ? CondBranchTakenFreq : UncondBranchTakenFreq;
|
|
|
1474 for (MachineBasicBlock *Succ : MBB.successors()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1475 // Skip if this successor is a fallthrough.
|
|
95
|
1476 if (MBB.isLayoutSuccessor(Succ))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1477 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1478
|
|
95
|
1479 BlockFrequency EdgeFreq =
|
|
|
1480 BlockFreq * MBPI->getEdgeProbability(&MBB, Succ);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1481 ++NumBranches;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1482 BranchTakenFreq += EdgeFreq.getFrequency();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1483 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1484 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1485
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1486 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1487 }
|
