1 : // Copyright 2012 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/reorder/transforms/basic_block_layout_transform.h"
16 :
17 : #include "base/strings/stringprintf.h"
18 :
19 : namespace reorder {
20 : namespace transforms {
21 :
22 : namespace {
23 :
24 : using block_graph::BlockGraph;
25 : using block_graph::BlockVector;
26 :
27 : typedef BasicBlockLayoutTransform::BlockInfo BlockInfo;
28 : typedef BasicBlockLayoutTransform::BlockInfos BlockInfos;
29 : typedef BasicBlockLayoutTransform::Order Order;
30 : typedef BasicBlockSubGraphLayoutTransform::BlockPositionPair BlockPositionPair;
31 : typedef BasicBlockSubGraphLayoutTransform::BasicBlockMap BasicBlockMap;
32 :
33 : // Build the basic-block map for the given collection of block specifications.
34 : // Returns true if the specifications are consistent, false otherwise.
35 : bool BuildBasicBlockMap(BlockInfos::const_iterator begin,
36 : BlockInfos::const_iterator end,
37 : BasicBlockMap* basic_block_map,
38 E : size_t* block_count) {
39 E : DCHECK(basic_block_map != NULL);
40 E : DCHECK(block_count != NULL);
41 :
42 E : basic_block_map->clear();
43 E : *block_count = 0;
44 E : bool empty_bloc_spec_seen = false;
45 :
46 : // Iterate over the block specifications.
47 E : BlockInfos::const_iterator it = begin;
48 E : for (; it != end; ++it, ++(*block_count)) {
49 E : if (it->block_spec->basic_block_offsets.empty())
50 E : empty_bloc_spec_seen = true;
51 :
52 : // For each one, iterate over the collection of basic blocks and update
53 : // the basic block map. While doing this we make sure that each basic
54 : // block is only specified once.
55 E : const Order::OffsetVector& offsets(it->block_spec->basic_block_offsets);
56 E : for (size_t i = 0; i < offsets.size(); ++i) {
57 E : BlockPositionPair block_position(*block_count, i);
58 : bool inserted = basic_block_map->insert(
59 E : std::make_pair(offsets[i], block_position)).second;
60 E : if (!inserted) {
61 i : LOG(ERROR) << "Basic block at offset " << offsets[i] << " of block \""
62 : << it->block_spec->block->name() << "\" with ID "
63 : << it->block_spec->block->id() << " is specified multiple "
64 : << "times.";
65 i : return false;
66 : }
67 E : }
68 E : }
69 :
70 : // This must have been called with non-empty input.
71 E : DCHECK_LT(0u, *block_count);
72 :
73 : // An empty block specification means that ALL of the basic-blocks belong
74 : // to that block. This is only valid if there is a single block specification.
75 E : if (*block_count != 1 && empty_bloc_spec_seen) {
76 i : LOG(ERROR) << "Have an empty block specification amongst multiple block "
77 : << "specifications.";
78 i : return false;
79 : }
80 :
81 E : return true;
82 E : }
83 :
84 : // Compares BlockInfos based on the original block pointer from the block_spec.
85 : // Allows comparing BlockInfos to each other, and Block pointers to BlockInfos.
86 : struct BlockInfoComparator {
87 : bool operator()(const BlockInfo& bi1,
88 E : const BlockInfo& bi2) const {
89 E : return bi1.original_block < bi2.original_block;
90 E : }
91 : bool operator()(const BlockGraph::Block* block,
92 E : const BlockInfo& bi) const {
93 E : return block < bi.original_block;
94 E : }
95 : bool operator()(const BlockInfo& bi,
96 E : const BlockGraph::Block* block) const {
97 E : return bi.original_block < block;
98 E : }
99 : };
100 :
101 : } // namespace
102 :
103 : const char BasicBlockLayoutTransform::kTransformName[] =
104 : "BasicBlockLayoutTransform";
105 :
106 : BasicBlockLayoutTransform::BasicBlockLayoutTransform(Order* order)
107 E : : order_(order) {
108 E : DCHECK(order != NULL);
109 E : }
110 :
111 E : BasicBlockLayoutTransform::~BasicBlockLayoutTransform() {
112 E : }
113 :
114 : bool BasicBlockLayoutTransform::PreBlockGraphIteration(
115 : const TransformPolicyInterface* policy,
116 : BlockGraph* block_graph,
117 E : BlockGraph::Block* header_block) {
118 E : DCHECK(policy != NULL);
119 E : DCHECK(block_graph != NULL);
120 E : DCHECK(header_block != NULL);
121 :
122 E : if (!FindOrCreateSections(block_graph))
123 E : return false;
124 :
125 E : BuildBlockInfos();
126 E : return true;
127 E : }
128 :
129 : bool BasicBlockLayoutTransform::OnBlock(
130 : const TransformPolicyInterface* policy,
131 : block_graph::BlockGraph* block_graph,
132 E : block_graph::BlockGraph::Block* block) {
133 E : DCHECK(policy != NULL);
134 E : DCHECK(block_graph != NULL);
135 E : DCHECK(block != NULL);
136 :
137 : // Get the range of block specifications that are to be applied to this
138 : // source block.
139 : BlockInfos::iterator it_begin = std::lower_bound(block_infos_.begin(),
140 : block_infos_.end(),
141 : block,
142 E : BlockInfoComparator());
143 : BlockInfos::iterator it_end = std::upper_bound(block_infos_.begin(),
144 : block_infos_.end(),
145 : block,
146 E : BlockInfoComparator());
147 :
148 : // This block is not specified in the ordering. It will be left to fall to
149 : // the tail of its original section by the orderer.
150 E : if (it_begin == it_end)
151 E : return true;
152 :
153 : // Build the basic block map. This maps from BB offsets to
154 : // (block index, bb index) pairs.
155 E : BasicBlockMap bb_map;
156 E : size_t block_count = 0;
157 E : if (!BuildBasicBlockMap(it_begin, it_end, &bb_map, &block_count))
158 i : return false;
159 :
160 E : BlockVector new_blocks;
161 :
162 : #ifndef NDEBUG
163 : // We expect the block_spec not to have been updated in place yet. If it
164 : // has it's because this block has already been seen by the BB transform,
165 : // which should never happen.
166 E : for (BlockInfos::iterator it = it_begin; it != it_end; ++it) {
167 E : DCHECK_EQ(it->original_block, it->block_spec->block);
168 E : }
169 : #endif // NDEBUG
170 :
171 : // Special case: a single block with no BB layout specification. Simply
172 : // ensure the block is in the appropriate section, add an entry to the
173 : // block specification map and move on.
174 E : if (block_count == 1 && bb_map.empty()) {
175 E : new_blocks.push_back(block);
176 E : } else {
177 : // If we get here it's because we have an explicitly specified BB layout.
178 E : DCHECK(!bb_map.empty());
179 :
180 : // Layout the basic-blocks using a basic block subgraph transform.
181 E : BasicBlockSubGraphLayoutTransform bb_layout_tx(bb_map);
182 : if (!ApplyBasicBlockSubGraphTransform(
183 : &bb_layout_tx,
184 : policy,
185 : block_graph,
186 : block,
187 E : &new_blocks)) {
188 i : return false;
189 : }
190 E : }
191 :
192 : // We expect there to be as many blocks created as there are block
193 : // specifications.
194 E : DCHECK_EQ(block_count, new_blocks.size());
195 :
196 : // The transform returns the newly created blocks in the same order as they
197 : // were specified by the BasicBlockMap, thus we can simply iterate through the
198 : // blocks to assign them to the appropriate sections and update the block
199 : // infos.
200 E : BlockInfos::iterator it = it_begin;
201 E : for (size_t i = 0; i < new_blocks.size(); ++i, ++it) {
202 E : new_blocks[i]->set_section(it->section_spec->id);
203 E : it->block_spec->block = new_blocks[i];
204 E : it->block_spec->basic_block_offsets.clear();
205 E : }
206 :
207 E : return true;
208 E : }
209 :
210 E : bool BasicBlockLayoutTransform::FindOrCreateSections(BlockGraph* block_graph) {
211 E : DCHECK(block_graph != NULL);
212 E : DCHECK(order_ != NULL);
213 :
214 E : Order::SectionSpecVector::iterator section_it = order_->sections.begin();
215 E : for (; section_it != order_->sections.end(); ++section_it) {
216 E : if (!FindOrCreateSection(block_graph, &(*section_it)))
217 E : return false;
218 E : }
219 E : return true;
220 E : }
221 :
222 : bool BasicBlockLayoutTransform::FindOrCreateSection(
223 : BlockGraph* block_graph,
224 E : Order::SectionSpec* section_spec) {
225 E : DCHECK(block_graph != NULL);
226 E : DCHECK(section_spec != NULL);
227 E : DCHECK(!section_spec->name.empty());
228 :
229 E : BlockGraph::Section* section = NULL;
230 :
231 : // Explicit section ID? Ensure it exists and validate it.
232 E : if (section_spec->id != Order::SectionSpec::kNewSectionId) {
233 E : section = block_graph->GetSectionById(section_spec->id);
234 E : if (section == NULL) {
235 E : LOG(ERROR) << "Order specifies an invalid section ID.";
236 E : return false;
237 : }
238 :
239 : // Rename the section if we've been asked to do so.
240 E : if (section_spec->name != section->name()) {
241 E : LOG(INFO) << "Renaming section \"" << section->name() << "\" to \""
242 : << section_spec->name << "\".";
243 E : section->set_name(section_spec->name);
244 : }
245 :
246 : // Set the section characteristics if need be.
247 E : if (section_spec->characteristics != section->characteristics()) {
248 E : LOG(INFO) << "Changing characteristics from "
249 : << base::StringPrintf("0x%08X", section->characteristics())
250 : << " to "
251 : << base::StringPrintf("0x%08X", section_spec->characteristics)
252 : << ".";
253 E : section->set_characteristics(section_spec->characteristics);
254 : }
255 E : } else {
256 : // If an ID wasn't provided then this section better contain at least one
257 : // block.
258 E : if (section_spec->blocks.empty()) {
259 E : LOG(ERROR) << "Invalid section specification.";
260 E : return false;
261 : }
262 :
263 : // Otherwise, create a new section.
264 : section = block_graph->AddSection(
265 E : section_spec->name, section_spec->characteristics);
266 E : if (section == NULL) {
267 i : LOG(ERROR) << "Failed to add section \"" << section_spec->name
268 : << "\".";
269 i : return false;
270 : }
271 :
272 : // Save the ID of this newly created section.
273 E : section_spec->id = section->id();
274 : }
275 :
276 E : return true;
277 E : }
278 :
279 E : void BasicBlockLayoutTransform::BuildBlockInfos() {
280 : Order::SectionSpecVector::iterator section_spec_it =
281 E : order_->sections.begin();
282 E : for (; section_spec_it != order_->sections.end(); ++section_spec_it) {
283 E : Order::SectionSpec* section_spec = &(*section_spec_it);
284 :
285 : Order::BlockSpecVector::iterator block_spec_it =
286 E : section_spec_it->blocks.begin();
287 E : for (; block_spec_it != section_spec_it->blocks.end(); ++block_spec_it) {
288 E : Order::BlockSpec* block_spec = &(*block_spec_it);
289 :
290 E : BlockInfo block_info = { block_spec->block, section_spec, block_spec };
291 E : block_infos_.push_back(block_info);
292 E : }
293 E : }
294 :
295 E : std::sort(block_infos_.begin(), block_infos_.end(), BlockInfoComparator());
296 E : }
297 :
298 : const char BasicBlockSubGraphLayoutTransform::kTransformName[] =
299 : "BasicBlockSubGraphLayoutTransform";
300 :
301 : bool BasicBlockSubGraphLayoutTransform::TransformBasicBlockSubGraph(
302 : const TransformPolicyInterface* policy,
303 : BlockGraph* bg,
304 E : BasicBlockSubGraph* bbsg) {
305 E : DCHECK(policy != NULL);
306 E : DCHECK(bg != NULL);
307 E : DCHECK(bbsg != NULL);
308 E : DCHECK_EQ(1u, bbsg->block_descriptions().size());
309 :
310 : typedef BasicBlockSubGraph::BasicBlock BasicBlock;
311 : typedef BasicBlockSubGraph::BBCollection::iterator BBIterator;
312 : typedef std::map<BlockPositionPair, BasicBlock*> ReverseMap;
313 :
314 : // Iterate through the basic blocks in the original block. While we're at it
315 : // we invert the basic block map so that iterating through it the blocks will
316 : // be in the necessary order.
317 E : size_t block_count = 0;
318 E : ReverseMap reverse_map;
319 E : BBIterator bb_it = bbsg->basic_blocks().begin();
320 E : for (; bb_it != bbsg->basic_blocks().end(); ++bb_it) {
321 : // Find the entry for this basic block in the basic block map. If there
322 : // isn't one the basic block is being deleted. If the BB is required for
323 : // layouting (is referenced by another BB) this will cause an error, but
324 : // we'll find that out when we build the block(s).
325 E : BasicBlock* bb = *bb_it;
326 E : BasicBlockMap::const_iterator bb_map_it = bb_map_.find(bb->offset());
327 E : if (bb_map_it == bb_map_.end())
328 E : continue;
329 :
330 E : block_count = std::max(block_count, bb_map_it->second.first);
331 E : CHECK(reverse_map.insert(std::make_pair(bb_map_it->second, bb)).second);
332 E : }
333 E : ++block_count;
334 :
335 : // Create the necessary new block descriptions.
336 E : BlockDescriptions block_descs;
337 E : if (!CreateBlockDescriptions(block_count, bbsg, &block_descs))
338 i : return false;
339 E : DCHECK_EQ(block_count, block_descs.size());
340 :
341 : // The reverse map will be conveniently in sorted order for us. So we simply
342 : // need to append blocks to the block descriptions in the appropriate order.
343 E : ReverseMap::iterator rev_map_it = reverse_map.begin();
344 E : size_t prev_block_index = SIZE_MAX;
345 E : size_t prev_bb_index = SIZE_MAX;
346 E : for (; rev_map_it != reverse_map.end(); ++rev_map_it) {
347 E : size_t block_index = rev_map_it->first.first;
348 E : size_t bb_index = rev_map_it->first.second;
349 E : BasicBlock* bb = rev_map_it->second;
350 :
351 : // We validate the basic block map by ensuring that it specifies each
352 : // block using values [0, block_count) and that the basic blocks are also
353 : // specified contiguously from 0.
354 E : if (block_index != prev_block_index) {
355 E : if (block_index != prev_block_index + 1 || block_index >= block_count) {
356 E : LOG(ERROR) << "Invalid block index in BasicBlockMap.";
357 E : return false;
358 : }
359 E : prev_bb_index = SIZE_MAX;
360 E : prev_block_index = block_index;
361 : }
362 :
363 E : if (bb_index != prev_bb_index + 1) {
364 E : LOG(ERROR) << "Invalid basic block index in BasicBlockMap.";
365 E : return false;
366 : }
367 E : prev_bb_index = bb_index;
368 :
369 : // Append this basic block to the appropriate block description.
370 E : block_descs[block_index]->basic_block_order.push_back(bb);
371 E : }
372 :
373 : // All blocks should have been written to.
374 E : if (prev_block_index + 1 != block_count) {
375 i : LOG(ERROR) << "Not all blocks were written to.";
376 i : return false;
377 : }
378 :
379 E : return true;
380 E : }
381 :
382 : bool BasicBlockSubGraphLayoutTransform::CreateBlockDescriptions(
383 : size_t block_count,
384 : BasicBlockSubGraph* bbsg,
385 E : BlockDescriptions* block_descs) {
386 E : DCHECK(bbsg != NULL);
387 E : DCHECK(block_descs != NULL);
388 E : DCHECK(block_descs->empty());
389 :
390 : // Get the original block description and empty its list of basic blocks.
391 : BasicBlockSubGraph::BlockDescriptionList::iterator orig_block_desc =
392 E : bbsg->block_descriptions().begin();
393 E : orig_block_desc->basic_block_order.clear();
394 :
395 E : block_descs->reserve(block_count);
396 E : block_descs->push_back(&(*orig_block_desc));
397 :
398 E : DCHECK_EQ(1u, bbsg->block_descriptions().size());
399 :
400 E : if (block_count == 1)
401 E : return true;
402 :
403 : // TODO(chrisha): We could be more specific in setting CODE or DATA block
404 : // type by analyzing basic-block types. If any CODE basic blocks exist,
405 : // the block type should be code. Otherwise, it should be data.
406 :
407 : // If we're outputting to multiple blocks, then create the appropriate
408 : // number of block descriptions. The block descriptions are identical to the
409 : // input block description.
410 E : for (size_t i = 1; i < block_count; ++i) {
411 : std::string name = base::StringPrintf(
412 E : "%s[%d]", orig_block_desc->name.c_str(), i);
413 :
414 : BasicBlockSubGraph::BlockDescription* block_desc =
415 : bbsg->AddBlockDescription(name,
416 : orig_block_desc->compiland_name,
417 : orig_block_desc->type,
418 : orig_block_desc->section,
419 : orig_block_desc->alignment,
420 E : orig_block_desc->attributes);
421 E : if (block_desc == NULL) {
422 i : LOG(ERROR) << "Failed to create new block description.";
423 i : return false;
424 : }
425 E : block_descs->push_back(block_desc);
426 E : }
427 :
428 E : DCHECK_EQ(block_count, block_descs->size());
429 :
430 E : return true;
431 E : }
432 :
433 : } // namespace transforms
434 : } // namespace reorder
|