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 E : EntryCountType bb_count = bb_profile->count();
152 :
153 : // Accumulate the count for jumps which do not target the next basic block.
154 E : const BasicCodeBlock::Successors& successors = bb->successors();
155 E : BasicCodeBlock::Successors::const_iterator succ = successors.begin();
156 E : for (; succ != successors.end(); ++succ) {
157 E : const BasicCodeBlock* succ_bb = GetSuccessorBB(*succ);
158 E : if (succ_bb == NULL)
159 i : continue;
160 : // Assume the branch is taken when the basic block is the last one or when
161 : // the next successor doesn't jump to the next basic block.
162 E : if (next == order.end() || succ_bb != *next)
163 E : accumulate += bb_profile->GetSuccessorCount(succ_bb);
164 E : }
165 E : }
166 :
167 E : return accumulate;
168 E : }
169 :
170 : void BasicBlockReorderingTransform::CommitOrdering(
171 : const BasicBlockOrdering& order,
172 : BasicEndBlock* basic_end_block,
173 E : BasicBlockSubGraph::BasicBlockOrdering* target) {
174 : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph::BasicBlockOrdering*>(NULL),
175 E : target);
176 :
177 E : size_t previous_size = target->size();
178 E : target->clear();
179 :
180 E : std::set<BasicCodeBlock*> placed;
181 :
182 E : BasicBlockOrdering::const_iterator it = order.begin();
183 E : for (; it != order.end(); ++it) {
184 E : BasicCodeBlock* bb = const_cast<BasicCodeBlock*>(*it);
185 E : CHECK(placed.insert(bb).second);
186 E : target->push_back(bb);
187 E : }
188 :
189 E : if (basic_end_block != NULL)
190 E : target->push_back(basic_end_block);
191 :
192 E : CHECK_EQ(previous_size, target->size());
193 E : }
194 :
195 : bool BasicBlockReorderingTransform::TransformBasicBlockSubGraph(
196 : const TransformPolicyInterface* policy,
197 : BlockGraph* block_graph,
198 : BasicBlockSubGraph* subgraph,
199 : ApplicationProfile* profile,
200 E : SubGraphProfile* subgraph_profile) {
201 E : DCHECK_NE(reinterpret_cast<TransformPolicyInterface*>(NULL), policy);
202 E : DCHECK_NE(reinterpret_cast<BlockGraph*>(NULL), block_graph);
203 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
204 E : DCHECK_NE(reinterpret_cast<ApplicationProfile*>(NULL), profile);
205 E : DCHECK_NE(reinterpret_cast<SubGraphProfile*>(NULL), subgraph_profile);
206 :
207 : // Do not reorder cold code.
208 E : const BlockGraph::Block* block = subgraph->original_block();
209 E : DCHECK_NE(reinterpret_cast<const BlockGraph::Block*>(NULL), block);
210 : const ApplicationProfile::BlockProfile* block_profile =
211 E : profile->GetBlockProfile(block);
212 E : if (block_profile->count() == 0)
213 E : return true;
214 :
215 : // Avoid reordering a block with a jump table or data block.
216 : // TODO(etienneb): Add support for jump table reordering.
217 : BasicBlockSubGraph::BBCollection::iterator bb_iter =
218 E : subgraph->basic_blocks().begin();
219 E : for (; bb_iter != subgraph->basic_blocks().end(); ++bb_iter) {
220 E : BasicBlock* bb = *bb_iter;
221 E : if (bb->type() == BlockGraph::DATA_BLOCK)
222 i : return true;
223 E : }
224 :
225 : // Retrieve the block description.
226 : BasicBlockSubGraph::BlockDescriptionList& descriptions =
227 E : subgraph->block_descriptions();
228 E : if (descriptions.size() != 1)
229 i : return true;
230 :
231 : // Retrieve the original ordering of this subgraph.
232 E : BasicBlockOrdering original_order;
233 E : BasicBlockSubGraph::BasicBlockOrdering end_blocks;
234 : BasicBlockSubGraph::BasicBlockOrdering& original_order_list =
235 E : descriptions.begin()->basic_block_order;
236 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator order_it =
237 E : original_order_list.begin();
238 E : BasicEndBlock* end_block = NULL;
239 E : for (; order_it != original_order_list.end(); ++order_it) {
240 : // Keep track of the end block, if there is one.
241 E : if ((*order_it)->type() == BasicBlock::BASIC_END_BLOCK) {
242 E : BasicEndBlock* ebb = BasicEndBlock::Cast(*order_it);
243 E : DCHECK_NE(reinterpret_cast<BasicEndBlock*>(NULL), ebb);
244 :
245 : // We currently only support a single 'end' block per BlockDescription,
246 : // and it must be the last basic block. However, there is no reason for
247 : // this to be the case. We may need support for the more general case when
248 : // handling more complicated function inlining scenarios.
249 : // TODO(chrisha): Add support for multiple arbitrarily placed end blocks.
250 E : if (end_block != NULL) {
251 i : LOG(ERROR) << "Encountered multiple end blocks.";
252 i : return false;
253 : }
254 E : end_block = ebb;
255 E : continue;
256 : }
257 :
258 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(*order_it);
259 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), bb);
260 E : original_order.push_back(bb);
261 E : }
262 :
263 : // Compute the number of jumps taken for the original ordering.
264 E : uint64 original_cost = EvaluateCost(original_order, *subgraph_profile);
265 E : if (original_cost == 0)
266 E : return true;
267 :
268 E : BasicBlockOrdering flatten_order;
269 : bool reducible = FlattenStructuralTreeToAnOrder(subgraph,
270 : subgraph_profile,
271 E : &flatten_order);
272 E : if (reducible) {
273 : // Compute the number of jumps taken for the optimized ordering.
274 E : uint64 flatten_cost = EvaluateCost(flatten_order, *subgraph_profile);
275 :
276 : // If the new basic block layout is better than the previous one, commit it.
277 E : if (flatten_cost < original_cost)
278 E : CommitOrdering(flatten_order, end_block, &original_order_list);
279 : }
280 :
281 E : return true;
282 E : }
283 :
284 : } // namespace transforms
285 : } // namespace optimize
|