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 : // Implementation of BasicBlockSubGraph class.
16 :
17 : #include "syzygy/block_graph/basic_block_subgraph.h"
18 :
19 : #include <algorithm>
20 :
21 : #include "base/memory/scoped_ptr.h"
22 :
23 : namespace block_graph {
24 :
25 : namespace {
26 :
27 : // Returns true if any of the instructions in the range [@p start, @p end) is
28 : // a, for the purposes of basic-block decomposition, control flow instruction.
29 : bool HasControlFlow(BasicBlock::Instructions::const_iterator start,
30 E : BasicBlock::Instructions::const_iterator end) {
31 E : for (; start != end; ++start) {
32 E : if (start->IsControlFlow())
33 i : return true;
34 E : }
35 E : return false;
36 E : }
37 :
38 : } // namespace
39 :
40 : BasicBlockSubGraph::BasicBlockSubGraph()
41 E : : original_block_(NULL), next_block_id_(0U) {
42 E : }
43 :
44 E : BasicBlockSubGraph::~BasicBlockSubGraph() {
45 : // Delete all the BB's we've been entrusted with.
46 E : BBCollection::iterator it = basic_blocks_.begin();
47 E : for (; it != basic_blocks_.end(); ++it)
48 E : delete *it;
49 :
50 : // And wipe the collection.
51 E : basic_blocks_.clear();
52 E : }
53 :
54 : BasicBlockSubGraph::BlockDescription* BasicBlockSubGraph::AddBlockDescription(
55 : const base::StringPiece& name,
56 : const base::StringPiece& compiland,
57 : BlockType type,
58 : SectionId section,
59 : Size alignment,
60 E : BlockAttributes attributes) {
61 E : block_descriptions_.push_back(BlockDescription());
62 E : BlockDescription* desc = &block_descriptions_.back();
63 E : desc->name.assign(name.begin(), name.end());
64 E : desc->compiland_name.assign(compiland.begin(), compiland.end());
65 E : desc->type = type;
66 E : desc->section = section;
67 E : desc->alignment = alignment;
68 E : desc->padding_before = 0U;
69 E : desc->attributes = attributes;
70 E : return desc;
71 E : }
72 :
73 : block_graph::BasicCodeBlock* BasicBlockSubGraph::AddBasicCodeBlock(
74 E : const base::StringPiece& name) {
75 E : DCHECK(!name.empty());
76 :
77 E : BlockId id = next_block_id_++;
78 E : scoped_ptr<BasicCodeBlock> new_code_block(new BasicCodeBlock(this, name, id));
79 E : bool inserted = basic_blocks_.insert(new_code_block.get()).second;
80 E : DCHECK(inserted);
81 :
82 E : return new_code_block.release();
83 E : }
84 :
85 : block_graph::BasicDataBlock* BasicBlockSubGraph::AddBasicDataBlock(
86 : const base::StringPiece& name,
87 : Size size,
88 E : const uint8* data) {
89 E : DCHECK(!name.empty());
90 :
91 E : BlockId id = next_block_id_++;
92 : scoped_ptr<BasicDataBlock> new_data_block(
93 E : new BasicDataBlock(this, name, id, data, size));
94 E : bool inserted = basic_blocks_.insert(new_data_block.get()).second;
95 E : DCHECK(inserted);
96 :
97 E : return new_data_block.release();
98 E : }
99 :
100 E : block_graph::BasicEndBlock* BasicBlockSubGraph::AddBasicEndBlock() {
101 E : BlockId id = next_block_id_++;
102 : scoped_ptr<BasicEndBlock> new_end_block(
103 E : new BasicEndBlock(this, id));
104 E : bool inserted = basic_blocks_.insert(new_end_block.get()).second;
105 E : DCHECK(inserted);
106 :
107 E : return new_end_block.release();
108 E : }
109 :
110 : void BasicBlockSubGraph::Remove(BasicBlock* bb) {
111 : DCHECK(basic_blocks_.find(bb) != basic_blocks_.end());
112 :
113 : basic_blocks_.erase(bb);
114 : }
115 :
116 E : bool BasicBlockSubGraph::IsValid() const {
117 E : if (!MapsBasicBlocksToAtMostOneDescription())
118 i : return false;
119 :
120 E : if (!HasValidSuccessors())
121 i : return false;
122 :
123 E : if (!HasValidReferrers())
124 i : return false;
125 :
126 E : return true;
127 E : }
128 :
129 E : bool BasicBlockSubGraph::MapsBasicBlocksToAtMostOneDescription() const {
130 E : std::set<BasicBlock*> bb_set;
131 E : BlockDescriptionList::const_iterator desc_iter = block_descriptions_.begin();
132 E : for (; desc_iter != block_descriptions_.end(); ++desc_iter) {
133 : BasicBlockOrdering::const_iterator bb_iter =
134 E : desc_iter->basic_block_order.begin();
135 E : for (; bb_iter != desc_iter->basic_block_order.end(); ++bb_iter) {
136 E : if (!bb_set.insert(*bb_iter).second) {
137 E : LOG(ERROR) << "Basic-block '" << (*bb_iter)->name() << "' appears "
138 : << " in more than one block description.";
139 E : return false;
140 : }
141 E : }
142 E : }
143 E : return true;
144 E : }
145 :
146 E : bool BasicBlockSubGraph::HasValidSuccessors() const {
147 E : ReachabilityMap rm;
148 E : GetReachabilityMap(&rm);
149 :
150 E : BlockDescriptionList::const_iterator desc_iter = block_descriptions_.begin();
151 E : for (; desc_iter != block_descriptions_.end(); ++desc_iter) {
152 : BasicBlockOrdering::const_iterator bb_iter =
153 E : desc_iter->basic_block_order.begin();
154 E : for (; bb_iter != desc_iter->basic_block_order.end(); ++bb_iter) {
155 E : const BasicCodeBlock* bb = BasicCodeBlock::Cast(*bb_iter);
156 E : if (bb == NULL)
157 E : continue;
158 :
159 E : const BasicBlock::Instructions& instructions = bb->instructions();
160 E : const BasicBlock::Successors& successors = bb->successors();
161 :
162 : // There may be at most 2 successors.
163 E : size_t num_successors = successors.size();
164 E : switch (num_successors) {
165 : case 0: {
166 : // If there are no successors, then there must be some instructions
167 : // in the basic block.
168 E : if (instructions.empty())
169 E : return false;
170 :
171 : // There should be no control flow instructions except the last one.
172 E : if (HasControlFlow(instructions.begin(), --instructions.end()))
173 i : return false;
174 :
175 : // If this basic block is reachable then either there is an implicit
176 : // control flow instruction at the end or this basic block calls a
177 : // non-returning function. Otherwise, it should have been flagged by
178 : // the decomposer as unsafe to basic-block decompose.
179 : if (IsReachable(rm, bb) &&
180 : !instructions.back().IsImplicitControlFlow() &&
181 E : !instructions.back().CallsNonReturningFunction()) {
182 i : return false;
183 : }
184 E : break;
185 : }
186 :
187 : case 1: {
188 : // There should be no control flow instructions.
189 E : if (HasControlFlow(instructions.begin(), instructions.end()))
190 i : return false;
191 :
192 : // The successor must be unconditional.
193 E : if (successors.back().condition() != Successor::kConditionTrue)
194 E : return false;
195 :
196 E : break;
197 : }
198 :
199 : case 2: {
200 : // There should be no control flow instructions.
201 E : if (HasControlFlow(instructions.begin(), instructions.end()))
202 i : return false;
203 :
204 : // The conditions on the successors should be inverses of one another.
205 : if (successors.front().condition() !=
206 E : Successor::InvertCondition(successors.back().condition())) {
207 E : return false;
208 : }
209 :
210 E : break;
211 : }
212 :
213 : default:
214 i : NOTREACHED();
215 i : return false;
216 : }
217 E : }
218 E : }
219 :
220 : // If we get here then everything was OK.
221 E : return true;
222 E : }
223 :
224 E : bool BasicBlockSubGraph::HasValidReferrers() const {
225 E : if (original_block_ == NULL)
226 i : return true;
227 :
228 : using block_graph::BasicBlockReferrer;
229 : typedef std::map<BasicBlockReferrer,
230 : size_t,
231 : BasicBlockReferrer::CompareAsLess> ReferrerCountMap;
232 E : ReferrerCountMap external_referrers;
233 :
234 : // Copy the external referrers into the count map, initializing their
235 : // counter to zero. These must all be incremented to 1 as we visit each
236 : // referrer in the basic-block graph.
237 : Block::ReferrerSet::const_iterator orig_iter =
238 E : original_block_->referrers().begin();
239 E : for (; orig_iter != original_block_->referrers().end(); ++orig_iter) {
240 E : if (orig_iter->first != original_block_) {
241 E : BasicBlockReferrer temp_referrer(orig_iter->first, orig_iter->second);
242 E : external_referrers.insert(std::make_pair(temp_referrer, 0));
243 : }
244 E : }
245 :
246 : // For each referrer to each basic block, add or increment the count for the
247 : // number of times it will be set to point to something. This will increment
248 : // the values initialized above (accounting for all the external referrers)
249 : // and will create a record for each internal referrer.
250 E : BBCollection::const_iterator bb_iter = basic_blocks_.begin();
251 E : for (; bb_iter != basic_blocks_.end(); ++bb_iter) {
252 : typedef BasicBlock::BasicBlockReferrerSet BasicBlockReferrerSet;
253 : const BasicBlockReferrerSet& bb_referrers =
254 E : (*bb_iter)->referrers();
255 E : BasicBlockReferrerSet::const_iterator ref_iter = bb_referrers.begin();
256 E : for (; ref_iter != bb_referrers.end(); ++ref_iter) {
257 E : size_t count = ++external_referrers[*ref_iter];
258 E : if (count != 1) {
259 i : LOG(ERROR) << "Basic-block composition updates a referrer with "
260 : << "multiple destinations.";
261 i : return false;
262 : }
263 E : }
264 E : }
265 :
266 : // Make sure all of the referrers were incremented to 1. If we missed any
267 : // they will still be 0.
268 E : ReferrerCountMap::const_iterator count_iter = external_referrers.begin();
269 E : for (; count_iter != external_referrers.end(); ++count_iter) {
270 E : if (count_iter->second != 1) {
271 E : LOG(ERROR) << "Basic-block composition does not properly update a "
272 : << "referrer.";
273 E : return false;
274 : }
275 E : }
276 :
277 E : return true;
278 E : }
279 :
280 E : void BasicBlockSubGraph::GetReachabilityMap(ReachabilityMap* rm) const {
281 E : DCHECK(rm != NULL);
282 E : DCHECK(rm->empty());
283 E : std::set<const BasicBlock*> reachability_queue;
284 :
285 : // Mark all basic-blocks as unreachable and put all externally referenced
286 : // basic-blocks into the reachability queue.
287 E : BBCollection::const_iterator bb_iter = basic_blocks_.begin();
288 E : for (; bb_iter != basic_blocks_.end(); ++bb_iter) {
289 E : const BasicBlock* bb = *bb_iter;
290 E : rm->insert(std::make_pair(bb, false));
291 : BasicBlock::BasicBlockReferrerSet::const_iterator ref_iter =
292 E : bb->referrers().begin();
293 E : for (; ref_iter != bb->referrers().end(); ++ref_iter)
294 E : reachability_queue.insert(bb);
295 E : }
296 :
297 : // Traverse the reachability queue marking basic blocks as reachable.
298 E : while (!reachability_queue.empty()) {
299 E : const BasicBlock* bb = *reachability_queue.begin();
300 E : reachability_queue.erase(reachability_queue.begin());
301 E : (*rm)[bb] = true;
302 :
303 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
304 E : if (data_block != NULL) {
305 : // Put all bb-to-bb references into the reachability queue.
306 : BasicBlock::BasicBlockReferenceMap::const_iterator ref_iter =
307 E : data_block->references().begin();
308 E : for (; ref_iter != data_block->references().end(); ++ref_iter) {
309 : if (ref_iter->second.basic_block() != NULL &&
310 E : !IsReachable(*rm, ref_iter->second.basic_block())) {
311 E : reachability_queue.insert(ref_iter->second.basic_block());
312 : }
313 E : }
314 : }
315 :
316 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
317 E : if (code_block != NULL) {
318 : // Put all instruction-to-code_block references into the
319 : // reachability queue.
320 : BasicBlock::Instructions::const_iterator inst_iter =
321 E : code_block->instructions().begin();
322 E : for (; inst_iter != code_block->instructions().end(); ++inst_iter) {
323 : BasicBlock::BasicBlockReferenceMap::const_iterator ref_iter =
324 E : inst_iter->references().begin();
325 E : for (; ref_iter != inst_iter->references().end(); ++ref_iter) {
326 : if (ref_iter->second.basic_block() != NULL &&
327 E : !IsReachable(*rm, ref_iter->second.basic_block())) {
328 E : reachability_queue.insert(ref_iter->second.basic_block());
329 : }
330 E : }
331 E : }
332 :
333 : // Put all successor-to-code_block references into the reachability queue.
334 : BasicBlock::Successors::const_iterator succ_iter =
335 E : code_block->successors().begin();
336 E : for (; succ_iter != code_block->successors().end(); ++succ_iter) {
337 : if (succ_iter->reference().basic_block() != NULL &&
338 E : !IsReachable(*rm, succ_iter->reference().basic_block())) {
339 E : reachability_queue.insert(succ_iter->reference().basic_block());
340 : }
341 E : }
342 : }
343 E : }
344 E : }
345 :
346 : bool BasicBlockSubGraph::IsReachable(const ReachabilityMap& rm,
347 E : const BasicBlock* bb) {
348 E : DCHECK(bb != NULL);
349 E : BasicBlockSubGraph::ReachabilityMap::const_iterator it = rm.find(bb);
350 E : DCHECK(it != rm.end());
351 E : return it->second;
352 E : }
353 :
354 E : bool BasicBlockSubGraph::ToString(std::string* buf) const {
355 E : DCHECK(buf != NULL);
356 :
357 E : std::stringstream out;
358 :
359 : // Output block information.
360 E : out << "BLOCK";
361 E : if (original_block_ != NULL)
362 E : out << " " << original_block_->name();
363 E : out << std::endl;
364 :
365 : const BasicBlockSubGraph::BasicBlockOrdering& original_order =
366 E : block_descriptions().front().basic_block_order;
367 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator bb_iter =
368 E : original_order.begin();
369 E : for (; bb_iter != original_order.end(); ++bb_iter) {
370 E : const BasicCodeBlock* bb = BasicCodeBlock::Cast(*bb_iter);
371 E : if (bb == NULL)
372 i : continue;
373 :
374 E : out << "bb" << bb->id() << ":" << std::endl;
375 :
376 : // Output instructions.
377 : BasicCodeBlock::Instructions::const_iterator it =
378 E : bb->instructions().begin();
379 E : for (; it != bb->instructions().end(); ++it) {
380 E : std::string instruction_string;
381 E : if (!it->ToString(&instruction_string))
382 i : return false;
383 E : out << " " << instruction_string;
384 :
385 : // Output references.
386 E : const Instruction::BasicBlockReferenceMap& references = it->references();
387 : Instruction::BasicBlockReferenceMap::const_iterator reference_it =
388 E : references.begin();
389 E : for (; reference_it != references.end(); ++reference_it) {
390 i : const BasicBlockReference& reference = reference_it->second;
391 i : if (reference.block() != NULL)
392 i : out << " block(" << reference.block()->name() << ")";
393 i : if (reference.basic_block() != NULL)
394 i : out << " basic_block(" << reference.basic_block()->id() << ")";
395 i : }
396 :
397 E : out << std::endl;
398 E : }
399 :
400 : // Output successors.
401 E : if (bb->successors().empty())
402 E : continue;
403 :
404 i : out << " ";
405 i : BasicCodeBlock::Successors::const_iterator succ = bb->successors().begin();
406 i : for (; succ != bb->successors().end(); ++succ) {
407 i : if (succ->reference().basic_block()) {
408 : out << succ->ToString()
409 : << " bb" << succ->reference().basic_block()->id()
410 i : << " ";
411 i : } else if (succ->reference().block()) {
412 : out << succ->ToString()
413 i : << " <" << succ->reference().block()->name() << "> ";
414 i : } else {
415 i : out << "<*> ";
416 : }
417 i : }
418 i : out << std::endl;
419 i : }
420 :
421 : // Commit the result.
422 E : *buf = out.str();
423 :
424 E : return true;
425 E : }
426 :
427 : } // namespace block_graph
|