1 : // Copyright 2013 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : #include "syzygy/optimize/transforms/basic_block_reordering_transform.h"
16 :
17 : #include "syzygy/block_graph/block_graph.h"
18 : #include "syzygy/optimize/application_profile.h"
19 :
20 : namespace optimize {
21 : namespace transforms {
22 :
23 : namespace {
24 :
25 : using block_graph::BasicBlock;
26 : using block_graph::BasicCodeBlock;
27 : using block_graph::BasicEndBlock;
28 : using block_graph::BasicBlockSubGraph;
29 : using block_graph::Successor;
30 : using block_graph::analysis::ControlFlowAnalysis;
31 : typedef ControlFlowAnalysis::BasicBlockOrdering BasicBlockOrdering;
32 : typedef ControlFlowAnalysis::StructuralTree StructuralTree;
33 : typedef ControlFlowAnalysis::StructuralNode StructuralNode;
34 : typedef SubGraphProfile::BasicBlockProfile BasicBlockProfile;
35 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
36 :
37 : // A helper to "cast" the given successor as a BasicCodeBlock.
38 E : const BasicCodeBlock* GetSuccessorBB(const Successor& successor) {
39 E : const BasicBlock* bb = successor.reference().basic_block();
40 :
41 : // This might be an inter block reference (i.e., refers to a block not
42 : // a basic-block).
43 E : if (bb == NULL)
44 i : return NULL;
45 :
46 : // If it's a basic-block then it must be a code basic-block.
47 E : const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(bb);
48 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), code_bb);
49 E : return code_bb;
50 E : }
51 :
52 : void FlattenStructuralTreeRecursive(const StructuralNode* tree,
53 : const SubGraphProfile* profile,
54 : BasicBlockOrdering* order,
55 E : BasicBlockOrdering* cold) {
56 E : DCHECK_NE(reinterpret_cast<StructuralNode*>(NULL), tree);
57 E : DCHECK_NE(reinterpret_cast<SubGraphProfile*>(NULL), profile);
58 E : DCHECK_NE(reinterpret_cast<BasicBlockOrdering*>(NULL), order);
59 E : DCHECK_NE(reinterpret_cast<BasicBlockOrdering*>(NULL), cold);
60 :
61 : // TODO(etienneb): Implement rules based on profile.
62 E : switch (tree->kind()) {
63 : case StructuralNode::kBaseNode: {
64 E : order->push_back(tree->root());
65 E : break;
66 : }
67 : case StructuralNode::kSequenceNode: {
68 E : FlattenStructuralTreeRecursive(tree->entry_node(), profile, order, cold);
69 : FlattenStructuralTreeRecursive(tree->sequence_node(),
70 : profile,
71 : order,
72 E : cold);
73 E : break;
74 : }
75 : case StructuralNode::kIfThenNode: {
76 E : FlattenStructuralTreeRecursive(tree->entry_node(), profile, order, cold);
77 E : FlattenStructuralTreeRecursive(tree->then_node(), profile, order, cold);
78 E : break;
79 : }
80 : case StructuralNode::kIfThenElseNode: {
81 E : FlattenStructuralTreeRecursive(tree->entry_node(), profile, order, cold);
82 E : FlattenStructuralTreeRecursive(tree->then_node(), profile, order, cold);
83 E : FlattenStructuralTreeRecursive(tree->else_node(), profile, order, cold);
84 E : break;
85 : }
86 : case StructuralNode::kRepeatNode: {
87 E : FlattenStructuralTreeRecursive(tree->entry_node(), profile, order, cold);
88 E : break;
89 : }
90 : case StructuralNode::kWhileNode: {
91 i : FlattenStructuralTreeRecursive(tree->entry_node(), profile, order, cold);
92 i : FlattenStructuralTreeRecursive(tree->body_node(), profile, order, cold);
93 i : break;
94 : }
95 : case StructuralNode::kLoopNode: {
96 i : FlattenStructuralTreeRecursive(tree->entry_node(), profile, order, cold);
97 i : break;
98 : }
99 : default: {
100 i : NOTREACHED() << "Invalid structural-tree node.";
101 : }
102 : }
103 E : }
104 :
105 : } // namespace
106 :
107 : bool BasicBlockReorderingTransform::FlattenStructuralTreeToAnOrder(
108 : const BasicBlockSubGraph* subgraph,
109 : const SubGraphProfile* subgraph_profile,
110 E : BasicBlockOrdering* order) {
111 E : DCHECK_NE(reinterpret_cast<const BasicBlockSubGraph*>(NULL), subgraph);
112 E : DCHECK_NE(reinterpret_cast<BasicBlockOrdering*>(NULL), order);
113 :
114 : // Build a structural tree.
115 E : ControlFlowAnalysis::StructuralTree tree;
116 E : bool reducible = ControlFlowAnalysis::BuildStructuralTree(subgraph, &tree);
117 E : if (!reducible)
118 i : return false;
119 :
120 : // Flatten the structural tree.
121 E : BasicBlockOrdering cold;
122 : FlattenStructuralTreeRecursive(tree.get(),
123 : subgraph_profile,
124 : order,
125 E : &cold);
126 :
127 : // Cold basic blocks are appended after the hot ones.
128 E : order->insert(order->end(), cold.begin(), cold.end());
129 :
130 E : return reducible;
131 E : }
132 :
133 : uint64 BasicBlockReorderingTransform::EvaluateCost(
134 : const BasicBlockOrdering& order,
135 E : const SubGraphProfile& profile) {
136 E : uint64 accumulate = 0;
137 :
138 : // For each basic block, accumulate the number of taken jumps.
139 E : BasicBlockOrdering::const_iterator it = order.begin();
140 E : for (; it != order.end(); ++it) {
141 E : const BasicCodeBlock* bb = BasicCodeBlock::Cast(*it);
142 E : if (bb == NULL)
143 i : continue;
144 :
145 : // Get the successor of this basic block in the ordering.
146 E : BasicBlockOrdering::const_iterator next = it;
147 E : next++;
148 :
149 : // Retrieve the basic block profile information.
150 E : const BasicBlockProfile* bb_profile = profile.GetBasicBlockProfile(bb);
151 :
152 : // Accumulate the count for jumps which do not target the next basic block.
153 E : const BasicCodeBlock::Successors& successors = bb->successors();
154 E : BasicCodeBlock::Successors::const_iterator succ = successors.begin();
155 E : for (; succ != successors.end(); ++succ) {
156 E : const BasicCodeBlock* succ_bb = GetSuccessorBB(*succ);
157 E : if (succ_bb == NULL)
158 i : continue;
159 : // Assume the branch is taken when the basic block is the last one or when
160 : // the next successor doesn't jump to the next basic block.
161 E : if (next == order.end() || succ_bb != *next)
162 E : accumulate += bb_profile->GetSuccessorCount(succ_bb);
163 E : }
164 E : }
165 :
166 E : return accumulate;
167 E : }
168 :
169 : void BasicBlockReorderingTransform::CommitOrdering(
170 : const BasicBlockOrdering& order,
171 : BasicEndBlock* basic_end_block,
172 E : BasicBlockSubGraph::BasicBlockOrdering* target) {
173 : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph::BasicBlockOrdering*>(NULL),
174 E : target);
175 :
176 E : size_t previous_size = target->size();
177 E : target->clear();
178 :
179 E : std::set<BasicCodeBlock*> placed;
180 :
181 E : BasicBlockOrdering::const_iterator it = order.begin();
182 E : for (; it != order.end(); ++it) {
183 E : BasicCodeBlock* bb = const_cast<BasicCodeBlock*>(*it);
184 E : CHECK(placed.insert(bb).second);
185 E : target->push_back(bb);
186 E : }
187 :
188 E : if (basic_end_block != NULL)
189 E : target->push_back(basic_end_block);
190 :
191 E : CHECK_EQ(previous_size, target->size());
192 E : }
193 :
194 : bool BasicBlockReorderingTransform::TransformBasicBlockSubGraph(
195 : const TransformPolicyInterface* policy,
196 : BlockGraph* block_graph,
197 : BasicBlockSubGraph* subgraph,
198 : ApplicationProfile* profile,
199 E : SubGraphProfile* subgraph_profile) {
200 E : DCHECK_NE(reinterpret_cast<TransformPolicyInterface*>(NULL), policy);
201 E : DCHECK_NE(reinterpret_cast<BlockGraph*>(NULL), block_graph);
202 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
203 E : DCHECK_NE(reinterpret_cast<ApplicationProfile*>(NULL), profile);
204 E : DCHECK_NE(reinterpret_cast<SubGraphProfile*>(NULL), subgraph_profile);
205 :
206 : // Do not reorder cold code.
207 E : const BlockGraph::Block* block = subgraph->original_block();
208 E : DCHECK_NE(reinterpret_cast<const BlockGraph::Block*>(NULL), block);
209 : const ApplicationProfile::BlockProfile* block_profile =
210 E : profile->GetBlockProfile(block);
211 E : if (block_profile->count() == 0)
212 E : return true;
213 :
214 : // Avoid reordering a block with a jump table or data block.
215 : // TODO(etienneb): Add support for jump table reordering.
216 : BasicBlockSubGraph::BBCollection::iterator bb_iter =
217 E : subgraph->basic_blocks().begin();
218 E : for (; bb_iter != subgraph->basic_blocks().end(); ++bb_iter) {
219 E : BasicBlock* bb = *bb_iter;
220 E : if (bb->type() == BlockGraph::DATA_BLOCK)
221 i : return true;
222 E : }
223 :
224 : // Retrieve the block description.
225 : BasicBlockSubGraph::BlockDescriptionList& descriptions =
226 E : subgraph->block_descriptions();
227 E : if (descriptions.size() != 1)
228 i : return true;
229 :
230 : // Retrieve the original ordering of this subgraph.
231 E : BasicBlockOrdering original_order;
232 E : BasicBlockSubGraph::BasicBlockOrdering end_blocks;
233 : BasicBlockSubGraph::BasicBlockOrdering& original_order_list =
234 E : descriptions.begin()->basic_block_order;
235 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator order_it =
236 E : original_order_list.begin();
237 E : BasicEndBlock* end_block = NULL;
238 E : for (; order_it != original_order_list.end(); ++order_it) {
239 : // Keep track of the end block, if there is one.
240 E : if ((*order_it)->type() == BasicBlock::BASIC_END_BLOCK) {
241 E : BasicEndBlock* ebb = BasicEndBlock::Cast(*order_it);
242 E : DCHECK_NE(reinterpret_cast<BasicEndBlock*>(NULL), ebb);
243 :
244 : // We currently only support a single 'end' block per BlockDescription,
245 : // and it must be the last basic block. However, there is no reason for
246 : // this to be the case. We may need support for the more general case when
247 : // handling more complicated function inlining scenarios.
248 : // TODO(chrisha): Add support for multiple arbitrarily placed end blocks.
249 E : if (end_block != NULL) {
250 i : LOG(ERROR) << "Encountered multiple end blocks.";
251 i : return false;
252 : }
253 E : end_block = ebb;
254 E : continue;
255 : }
256 :
257 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(*order_it);
258 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), bb);
259 E : original_order.push_back(bb);
260 E : }
261 :
262 : // Compute the number of jumps taken for the original ordering.
263 E : uint64 original_cost = EvaluateCost(original_order, *subgraph_profile);
264 E : if (original_cost == 0)
265 E : return true;
266 :
267 E : BasicBlockOrdering flatten_order;
268 : bool reducible = FlattenStructuralTreeToAnOrder(subgraph,
269 : subgraph_profile,
270 E : &flatten_order);
271 E : if (reducible) {
272 : // Compute the number of jumps taken for the optimized ordering.
273 E : uint64 flatten_cost = EvaluateCost(flatten_order, *subgraph_profile);
274 :
275 : // If the new basic block layout is better than the previous one, commit it.
276 E : if (flatten_cost < original_cost)
277 E : CommitOrdering(flatten_order, end_block, &original_order_list);
278 : }
279 :
280 E : return true;
281 E : }
282 :
283 : } // namespace transforms
284 : } // namespace optimize
|