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