1 : // Copyright 2012 Google Inc.
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 : namespace block_graph {
22 :
23 : namespace {
24 :
25 : // Returns true if any of the instructions in the range [@p start, @p end) is
26 : // a, for the purposes of basic-block decompsition, control flow instruction.
27 : bool HasControlFlow(BasicBlock::Instructions::const_iterator start,
28 E : BasicBlock::Instructions::const_iterator end) {
29 E : for (; start != end; ++start) {
30 E : if (start->IsControlFlow())
31 i : return true;
32 E : }
33 E : return false;
34 E : }
35 :
36 : } // namespace
37 :
38 E : size_t BasicBlockSubGraph::BlockDescription::GetMaxSize() const {
39 E : size_t max_size = 0;
40 E : BasicBlockOrdering::const_iterator it = basic_block_order.begin();
41 E : for (; it != basic_block_order.end(); ++it) {
42 E : max_size += (*it)->GetMaxSize();
43 E : }
44 E : return max_size;
45 E : }
46 :
47 : BasicBlockSubGraph::BasicBlockSubGraph()
48 E : : original_block_(NULL), next_basic_block_id_(0) {
49 E : }
50 :
51 : BasicBlockSubGraph::BlockDescription* BasicBlockSubGraph::AddBlockDescription(
52 : const base::StringPiece& name,
53 : BlockType type,
54 : SectionId section,
55 : Size alignment,
56 E : BlockAttributes attributes) {
57 E : block_descriptions_.push_back(BlockDescription());
58 E : BlockDescription* desc = &block_descriptions_.back();
59 E : desc->name.assign(name.begin(), name.end());
60 E : desc->type = type;
61 E : desc->section = section;
62 E : desc->alignment = alignment;
63 E : desc->attributes = attributes;
64 E : return desc;
65 E : }
66 :
67 : block_graph::BasicBlock* BasicBlockSubGraph::AddBasicBlock(
68 : const base::StringPiece& name,
69 : BasicBlockType type,
70 : Offset offset,
71 : Size size,
72 E : const uint8* data) {
73 E : DCHECK(!name.empty());
74 :
75 : typedef BBAddressSpace::Range Range;
76 :
77 : std::pair<BBCollection::iterator, bool> insert_result =
78 : basic_blocks_.insert(std::make_pair(
79 : next_basic_block_id_,
80 E : BasicBlock(next_basic_block_id_, name, type, offset, size, data)));
81 E : DCHECK(insert_result.second);
82 :
83 E : block_graph::BasicBlock* new_basic_block = &insert_result.first->second;
84 :
85 E : if (offset >= 0) {
86 E : DCHECK(original_block_ != NULL);
87 E : BBAddressSpace::Range byte_range(offset, size);
88 E : if (!original_address_space_.Insert(byte_range, new_basic_block)) {
89 E : LOG(ERROR) << "Attempted to insert overlapping basic block.";
90 E : basic_blocks_.erase(insert_result.first); // Undo bb insertion.
91 E : return NULL;
92 : }
93 : }
94 :
95 E : ++next_basic_block_id_;
96 :
97 E : return new_basic_block;
98 E : }
99 :
100 E : bool BasicBlockSubGraph::IsValid() const {
101 : return MapsBasicBlocksToAtMostOneDescription() &&
102 : HasValidSuccessors() &&
103 E : HasValidReferrers();
104 E : }
105 :
106 : bool BasicBlockSubGraph::FindBasicBlock(Offset offset,
107 : BasicBlock** basic_block,
108 E : BBAddressSpace::Range* range) const {
109 E : DCHECK_LE(0, offset);
110 E : DCHECK(basic_block != NULL);
111 E : DCHECK(range != NULL);
112 E : DCHECK(original_block_ != NULL);
113 E : DCHECK_GT(original_block_->size(), static_cast<size_t>(offset));
114 :
115 : BBAddressSpace::RangeMapConstIter bb_iter =
116 : original_address_space_.FindFirstIntersection(
117 E : BBAddressSpace::Range(offset, 1));
118 :
119 E : if (bb_iter == original_address_space_.end())
120 i : return false;
121 :
122 E : *basic_block = bb_iter->second;
123 E : *range = bb_iter->first;
124 E : return true;
125 E : }
126 :
127 E : BasicBlock* BasicBlockSubGraph::GetBasicBlockAt(Offset offset) const {
128 E : DCHECK_LE(0, offset);
129 E : DCHECK(original_block_ != NULL);
130 E : DCHECK_GT(original_block_->size(), static_cast<size_t>(offset));
131 :
132 E : BasicBlock* bb = NULL;
133 E : BBAddressSpace::Range range;
134 E : CHECK(FindBasicBlock(offset, &bb, &range));
135 E : DCHECK(bb != NULL);
136 E : DCHECK_EQ(offset, range.start());
137 E : return bb;
138 E : }
139 :
140 :
141 E : bool BasicBlockSubGraph::MapsBasicBlocksToAtMostOneDescription() const {
142 E : std::set<BasicBlock*> bb_set;
143 E : BlockDescriptionList::const_iterator desc_iter = block_descriptions_.begin();
144 E : for (; desc_iter != block_descriptions_.end(); ++desc_iter) {
145 : BasicBlockOrdering::const_iterator bb_iter =
146 E : desc_iter->basic_block_order.begin();
147 E : for (; bb_iter != desc_iter->basic_block_order.end(); ++bb_iter) {
148 E : if (!bb_set.insert(*bb_iter).second) {
149 E : LOG(ERROR) << "Basic-block '" << (*bb_iter)->name() << "' appears "
150 : << " in more than one block description.";
151 E : return false;
152 : }
153 E : }
154 E : }
155 E : return true;
156 E : }
157 :
158 E : bool BasicBlockSubGraph::HasValidSuccessors() const {
159 E : ReachabilityMap rm;
160 E : GetReachabilityMap(&rm);
161 :
162 E : BlockDescriptionList::const_iterator desc_iter = block_descriptions_.begin();
163 E : for (; desc_iter != block_descriptions_.end(); ++desc_iter) {
164 : BasicBlockOrdering::const_iterator bb_iter =
165 E : desc_iter->basic_block_order.begin();
166 E : for (; bb_iter != desc_iter->basic_block_order.end(); ++bb_iter) {
167 E : const BasicBlock* bb = *bb_iter;
168 E : if (bb->type() != BasicBlock::BASIC_CODE_BLOCK)
169 E : continue;
170 :
171 E : const BasicBlock::Instructions& instructions = bb->instructions();
172 E : const BasicBlock::Successors& successors = bb->successors();
173 :
174 : // There may be at most 2 successors.
175 E : size_t num_successors = successors.size();
176 E : switch (num_successors) {
177 : case 0: {
178 : // If there are no successors, then there must be some instructions
179 : // in the basic block.
180 E : if (instructions.empty())
181 E : return false;
182 :
183 : // There should be no control flow instructions except the last one.
184 E : if (HasControlFlow(instructions.begin(), --instructions.end()))
185 i : return false;
186 :
187 : // If this basic block is reachable then either there is an implicit
188 : // control flow instruction at the end or this basic block calls a
189 : // non-returning function. Otherwise, it should have been flagged by
190 : // the decomposer as unsafe to basic-block decompose.
191 : if (IsReachable(rm, bb) &&
192 : !instructions.back().IsImplicitControlFlow() &&
193 E : !instructions.back().CallsNonReturningFunction()) {
194 i : return false;
195 : }
196 E : break;
197 : }
198 :
199 : case 1: {
200 : // There should be no control flow instructions.
201 E : if (HasControlFlow(instructions.begin(), instructions.end()))
202 i : return false;
203 :
204 : // The successor must be unconditional.
205 E : if (successors.back().condition() != Successor::kConditionTrue)
206 E : return false;
207 :
208 E : break;
209 : }
210 :
211 : case 2: {
212 : // There should be no control flow instructions.
213 E : if (HasControlFlow(instructions.begin(), instructions.end()))
214 i : return false;
215 :
216 : // The conditions on the successors should be inverses of one another.
217 : if (successors.front().condition() !=
218 E : Successor::InvertCondition(successors.back().condition())) {
219 E : return false;
220 : }
221 :
222 E : break;
223 : }
224 :
225 : default:
226 i : NOTREACHED();
227 i : return false;
228 : }
229 E : }
230 E : }
231 :
232 : // If we get here then everything was OK.
233 E : return true;
234 E : }
235 :
236 E : bool BasicBlockSubGraph::HasValidReferrers() const {
237 E : if (original_block_ == NULL)
238 i : return true;
239 :
240 : using block_graph::BasicBlockReferrer;
241 : typedef std::map<BasicBlockReferrer,
242 : size_t,
243 : BasicBlockReferrer::CompareAsLess> ReferrerCountMap;
244 E : ReferrerCountMap external_referrers;
245 :
246 : // Copy the external referrers into the count map, initializing their
247 : // counter to zero. These must all be incremented to 1 as we visit each
248 : // referrer in the basic-block graph.
249 : Block::ReferrerSet::const_iterator orig_iter =
250 E : original_block_->referrers().begin();
251 E : for (; orig_iter != original_block_->referrers().end(); ++orig_iter) {
252 E : if (orig_iter->first != original_block_) {
253 E : BasicBlockReferrer temp_referrer(orig_iter->first, orig_iter->second);
254 E : external_referrers.insert(std::make_pair(temp_referrer, 0));
255 : }
256 E : }
257 :
258 : // For each referrer to each basic block, add or increment the count for the
259 : // number of times it will be set to point to something. This will increment
260 : // the values initialized above (accounting for all the external referrers)
261 : // and will create a record for each internal referrer.
262 E : BBCollection::const_iterator bb_iter = basic_blocks_.begin();
263 E : for (; bb_iter != basic_blocks_.end(); ++bb_iter) {
264 : typedef BasicBlock::BasicBlockReferrerSet BasicBlockReferrerSet;
265 E : const BasicBlockReferrerSet& bb_referrers = bb_iter->second.referrers();
266 E : BasicBlockReferrerSet::const_iterator ref_iter = bb_referrers.begin();
267 E : for (; ref_iter != bb_referrers.end(); ++ref_iter) {
268 E : size_t count = ++external_referrers[*ref_iter];
269 E : if (count != 1) {
270 i : LOG(ERROR) << "Basic-block composition updates a referrer with "
271 : << "multiple destinations.";
272 i : return false;
273 : }
274 E : }
275 E : }
276 :
277 : // Make sure all of the referrers were incremented to 1. If we missed any
278 : // they will still be 0.
279 E : ReferrerCountMap::const_iterator count_iter = external_referrers.begin();
280 E : for (;count_iter != external_referrers.end(); ++count_iter) {
281 E : if (count_iter->second != 1) {
282 E : LOG(ERROR) << "Basic-block composition does not properly update a "
283 : << "referrer.";
284 E : return false;
285 : }
286 E : }
287 :
288 E : return true;
289 E : }
290 :
291 E : void BasicBlockSubGraph::GetReachabilityMap(ReachabilityMap* rm) const {
292 E : DCHECK(rm != NULL);
293 E : DCHECK(rm->empty());
294 E : std::set<const BasicBlock*> reachability_queue;
295 :
296 : // Mark all basic-blocks as unreachable and put all externally referenced
297 : // basic-blocks into the reachability queue.
298 E : BBCollection::const_iterator bb_iter = basic_blocks_.begin();
299 E : for (; bb_iter != basic_blocks_.end(); ++bb_iter) {
300 E : const BasicBlock& bb = bb_iter->second;
301 E : rm->insert(std::make_pair(&bb, false));
302 : BasicBlock::BasicBlockReferrerSet::const_iterator ref_iter =
303 E : bb.referrers().begin();
304 E : for (; ref_iter != bb.referrers().end(); ++ref_iter) {
305 E : if (ref_iter->referrer_type() == BasicBlockReferrer::REFERRER_TYPE_BLOCK)
306 E : reachability_queue.insert(&bb);
307 E : }
308 E : }
309 :
310 : // Traverse the reachability queue marking basic blocks as reachable.
311 E : while (!reachability_queue.empty()) {
312 E : const BasicBlock* bb = *reachability_queue.begin();
313 E : reachability_queue.erase(reachability_queue.begin());
314 E : (*rm)[bb] = true;
315 :
316 : // Put all bb-to-bb references into the reachability queue.
317 : BasicBlock::BasicBlockReferenceMap::const_iterator ref_iter =
318 E : bb->references().begin();
319 E : for (; ref_iter != bb->references().end(); ++ref_iter) {
320 : if (ref_iter->second.basic_block() != NULL &&
321 E : !IsReachable(*rm, ref_iter->second.basic_block())) {
322 E : reachability_queue.insert(ref_iter->second.basic_block());
323 : }
324 E : }
325 :
326 : // Put all instruction-to-bb references into the reachability queue.
327 : BasicBlock::Instructions::const_iterator inst_iter =
328 E : bb->instructions().begin();
329 E : for (; inst_iter != bb->instructions().end(); ++inst_iter) {
330 E : ref_iter = inst_iter->references().begin();
331 E : for (; ref_iter != inst_iter->references().end(); ++ref_iter) {
332 : if (ref_iter->second.basic_block() != NULL &&
333 E : !IsReachable(*rm, ref_iter->second.basic_block())) {
334 E : reachability_queue.insert(ref_iter->second.basic_block());
335 : }
336 E : }
337 E : }
338 :
339 : // Put all successor-to-bb references into the reachability queue.
340 : BasicBlock::Successors::const_iterator succ_iter =
341 E : bb->successors().begin();
342 E : for (; succ_iter != bb->successors().end(); ++succ_iter) {
343 : if (succ_iter->reference().basic_block() != NULL &&
344 E : !IsReachable(*rm, succ_iter->reference().basic_block())) {
345 E : reachability_queue.insert(succ_iter->reference().basic_block());
346 : }
347 E : }
348 E : }
349 E : }
350 :
351 : bool BasicBlockSubGraph::IsReachable(const ReachabilityMap& rm,
352 E : const BasicBlock* bb) {
353 E : DCHECK(bb != NULL);
354 E : BasicBlockSubGraph::ReachabilityMap::const_iterator it = rm.find(bb);
355 E : DCHECK(it != rm.end());
356 E : return it->second;
357 E : }
358 :
359 : } // namespace block_graph
|