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