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