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