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 : #include "syzygy/block_graph/ordered_block_graph.h"
16 :
17 : namespace block_graph {
18 :
19 : namespace {
20 :
21 : // Produces a copy of an object.
22 E : template<typename T> T Copy(const T& t) { return T(t); }
23 :
24 : } // namespace
25 :
26 : // This is used for sorting and searching through the section index.
27 : struct OrderedBlockGraph::CompareSectionInfo {
28 E : bool operator()(const SectionInfo& s1, const SectionInfo& s2) const {
29 E : return s1.ordered_section.section() < s2.ordered_section.section();
30 E : }
31 E : bool operator()(const SectionInfo& s1, const Section* s2) const {
32 E : return s1.ordered_section.section() < s2;
33 E : }
34 : bool operator()(const Section* s1, const SectionInfo& s2) const {
35 : return s1 < s2.ordered_section.section();
36 : }
37 : };
38 :
39 : // This is used for sorting and searching through the block index.
40 : struct OrderedBlockGraph::CompareBlockInfo {
41 E : bool operator()(const BlockInfo& b1, const BlockInfo& b2) const {
42 E : return *b1.it < *b2.it;
43 E : }
44 E : bool operator()(const BlockInfo& b1, const Block* b2) const {
45 E : return *b1.it < b2;
46 E : }
47 : bool operator()(const Block* b1, const BlockInfo& b2) const {
48 : return b1 < *b2.it;
49 : }
50 : };
51 :
52 : OrderedBlockGraph::OrderedBlockGraph(BlockGraph* block_graph)
53 E : : block_graph_(block_graph) {
54 E : DCHECK(block_graph != NULL);
55 :
56 : // Create the section infos. There is an extra one which catches all blocks
57 : // not belonging to an explicit section. This ensures that all blocks belong
58 : // to exactly one BlockList (and OrderedSection) at all times.
59 E : section_infos_.resize(block_graph_->sections().size() + 1);
60 : // We don't add this special section to the list of ordered sections.
61 E : section_infos_[0].ordered_section.section_ = NULL;
62 : BlockGraph::SectionMap::iterator section_it =
63 E : block_graph_->sections_mutable().begin();
64 : BlockGraph::SectionMap::iterator section_end =
65 E : block_graph_->sections_mutable().end();
66 E : for (size_t i = 1; section_it != section_end; ++section_it, ++i) {
67 E : DCHECK_LT(i, section_infos_.size());
68 E : section_infos_[i].ordered_section.section_ = §ion_it->second;
69 E : }
70 :
71 : // Sort these based on Section* values, except for the first one which we
72 : // leave in its place.
73 : std::sort(section_infos_.begin() + 1, section_infos_.end(),
74 E : CompareSectionInfo());
75 :
76 : // Now that the ordered sections have been sorted we can get stable pointers
77 : // to them. We get them in the order they appear in the original block graph.
78 E : section_it = block_graph_->sections_mutable().begin();
79 E : for (; section_it != section_end; ++section_it) {
80 E : SectionInfo* section_info = GetSectionInfo(§ion_it->second);
81 : section_info->it = ordered_sections_.insert(
82 E : ordered_sections_.end(), §ion_info->ordered_section);
83 E : }
84 E : DCHECK_EQ(ordered_sections_.size(), block_graph_->sections().size());
85 :
86 : // Iterate through the blocks and place them into the appropriate BlockLists.
87 : // Each sections BlockList will contain the blocks in the order of their
88 : // block graph ID.
89 E : block_infos_.resize(block_graph_->blocks().size());
90 : BlockGraph::BlockMap::iterator block_it =
91 E : block_graph_->blocks_mutable().begin();
92 : BlockGraph::BlockMap::iterator block_end =
93 E : block_graph_->blocks_mutable().end();
94 E : for (size_t i = 0; block_it != block_end; ++block_it, ++i) {
95 E : DCHECK_LT(i, block_infos_.size());
96 : // Get the SectionInfo for the section containing the block.
97 E : BlockGraph::SectionId section_id = block_it->second.section();
98 E : const Section* section = NULL;
99 E : if (section_id != BlockGraph::kInvalidSectionId) {
100 : BlockGraph::SectionMap::const_iterator section_it =
101 E : block_graph_->sections().find(section_id);
102 : // Blocks can have orphaned section IDs if the section has been deleted
103 : // from underneath them.
104 E : if (section_it != block_graph_->sections().end())
105 E : section = §ion_it->second;
106 : }
107 E : SectionInfo* section_info = GetSectionInfo(section);
108 E : DCHECK(section_info != NULL);
109 :
110 E : Block* block = &block_it->second;
111 :
112 E : OrderedSection* ordered_section = §ion_info->ordered_section;
113 E : block_infos_[i].ordered_section = ordered_section;
114 : block_infos_[i].it = ordered_section->ordered_blocks_.insert(
115 E : ordered_section->ordered_blocks_.end(), block);
116 E : }
117 :
118 : // Sort the BlockInfos so that we can use GetBlockInfo.
119 E : std::sort(block_infos_.begin(), block_infos_.end(), CompareBlockInfo());
120 E : }
121 :
122 : const OrderedBlockGraph::OrderedSection& OrderedBlockGraph::ordered_section(
123 E : const Section* section) const {
124 E : const SectionInfo* section_info = GetSectionInfo(section);
125 E : DCHECK(section_info != NULL);
126 E : return section_info->ordered_section;
127 E : }
128 :
129 : OrderedBlockGraph::BlockList::const_iterator OrderedBlockGraph::begin(
130 : const Section* section) const {
131 : return ordered_section(section).ordered_blocks().begin();
132 : }
133 :
134 : OrderedBlockGraph::BlockList::const_iterator OrderedBlockGraph::end(
135 : const Section* section) const {
136 : return ordered_section(section).ordered_blocks().end();
137 : }
138 :
139 E : void OrderedBlockGraph::PlaceAtHead(const Section* section) {
140 E : DCHECK(section != NULL);
141 :
142 E : SectionInfo* section_info = GetSectionInfo(section);
143 E : DCHECK(section_info != NULL);
144 :
145 : // Already there? Do nothing!
146 E : if (section_info->it == ordered_sections_.begin())
147 E : return;
148 :
149 : // We use splice to avoid an allocation.
150 : ordered_sections_.splice(ordered_sections_.begin(),
151 : ordered_sections_,
152 E : section_info->it);
153 :
154 : // Splice invalidates the iterator.
155 E : section_info->it = ordered_sections_.begin();
156 E : DCHECK_EQ(*(section_info->it), §ion_info->ordered_section);
157 E : }
158 :
159 E : void OrderedBlockGraph::PlaceAtTail(const Section* section) {
160 E : DCHECK(section != NULL);
161 :
162 E : SectionInfo* section_info = GetSectionInfo(section);
163 E : DCHECK(section_info != NULL);
164 :
165 : // Already there? Do nothing!
166 E : if (section_info->it == --ordered_sections_.end())
167 E : return;
168 :
169 : // We use splice to avoid an allocation.
170 : ordered_sections_.splice(ordered_sections_.end(),
171 : ordered_sections_,
172 E : section_info->it);
173 :
174 : // Splice invalidates the iterator.
175 E : --(section_info->it = ordered_sections_.end());
176 E : DCHECK_EQ(*(section_info->it), §ion_info->ordered_section);
177 E : }
178 :
179 : void OrderedBlockGraph::PlaceBefore(const Section* anchored_section,
180 E : const Section* moved_section) {
181 E : DCHECK(anchored_section != NULL);
182 E : DCHECK(moved_section != NULL);
183 E : DCHECK_NE(anchored_section, moved_section);
184 :
185 E : SectionInfo* anchored = GetSectionInfo(anchored_section);
186 E : SectionInfo* moved = GetSectionInfo(moved_section);
187 E : DCHECK(anchored != NULL);
188 E : DCHECK(moved != NULL);
189 E : DCHECK_NE(anchored, moved);
190 :
191 : // Already there? Do nothing!
192 E : if (++Copy(moved->it) == anchored->it)
193 E : return;
194 :
195 : ordered_sections_.splice(anchored->it,
196 : ordered_sections_,
197 E : moved->it);
198 E : --(moved->it = anchored->it);
199 E : DCHECK_EQ(*(moved->it), &moved->ordered_section);
200 E : }
201 :
202 : void OrderedBlockGraph::PlaceAfter(const Section* anchored_section,
203 E : const Section* moved_section) {
204 E : DCHECK(anchored_section != NULL);
205 E : DCHECK(moved_section != NULL);
206 E : DCHECK_NE(anchored_section, moved_section);
207 :
208 E : SectionInfo* anchored = GetSectionInfo(anchored_section);
209 E : SectionInfo* moved = GetSectionInfo(moved_section);
210 E : DCHECK(anchored != NULL);
211 E : DCHECK(moved != NULL);
212 E : DCHECK_NE(anchored, moved);
213 :
214 E : SectionList::iterator anchor_it = anchored->it;
215 E : ++anchor_it;
216 :
217 : // Already there? Do nothing!
218 E : if (moved->it == anchor_it)
219 E : return;
220 :
221 : ordered_sections_.splice(anchor_it,
222 : ordered_sections_,
223 E : moved->it);
224 E : --(moved->it = anchor_it);
225 E : DCHECK_EQ(*(moved->it), &moved->ordered_section);
226 E : }
227 :
228 : void OrderedBlockGraph::PlaceAtHead(const Section* section,
229 E : BlockGraph::Block* block) {
230 E : DCHECK(block != NULL);
231 :
232 E : SectionInfo* section_info = GetSectionInfo(section);
233 E : BlockInfo* block_info = GetBlockInfo(block);
234 E : DCHECK(section_info != NULL);
235 E : DCHECK(block_info != NULL);
236 :
237 E : BlockList& blocks(section_info->ordered_section.ordered_blocks_);
238 :
239 : // Already there? Do nothing!
240 : if (&blocks == &block_info->ordered_section->ordered_blocks_ &&
241 E : block_info->it == blocks.begin()) {
242 E : return;
243 : }
244 :
245 : blocks.splice(blocks.begin(),
246 : block_info->ordered_section->ordered_blocks_,
247 E : block_info->it);
248 E : block_info->it = blocks.begin();
249 E : block_info->ordered_section = §ion_info->ordered_section;
250 E : block->set_section(section_info->id());
251 E : DCHECK_EQ(*(block_info->it), block);
252 E : }
253 :
254 : void OrderedBlockGraph::PlaceAtTail(const Section* section,
255 E : BlockGraph::Block* block) {
256 E : DCHECK(block != NULL);
257 :
258 E : SectionInfo* section_info = GetSectionInfo(section);
259 E : BlockInfo* block_info = GetBlockInfo(block);
260 E : DCHECK(section_info != NULL);
261 E : DCHECK(block_info != NULL);
262 :
263 E : BlockList& blocks(section_info->ordered_section.ordered_blocks_);
264 :
265 : // Already there? Do nothing!
266 : if (&blocks == &block_info->ordered_section->ordered_blocks_ &&
267 E : block_info->it == --blocks.end()) {
268 E : return;
269 : }
270 :
271 : blocks.splice(blocks.end(),
272 : block_info->ordered_section->ordered_blocks_,
273 E : block_info->it);
274 E : --(block_info->it = blocks.end());
275 E : block_info->ordered_section = §ion_info->ordered_section;
276 E : block->set_section(section_info->id());
277 E : DCHECK_EQ(*(block_info->it), block);
278 E : }
279 :
280 : void OrderedBlockGraph::PlaceBefore(const BlockGraph::Block* anchored_block,
281 E : BlockGraph::Block* moved_block) {
282 E : DCHECK(anchored_block != NULL);
283 E : DCHECK(moved_block != NULL);
284 E : DCHECK_NE(anchored_block, moved_block);
285 :
286 E : BlockInfo* anchored = GetBlockInfo(anchored_block);
287 E : BlockInfo* moved = GetBlockInfo(moved_block);
288 E : DCHECK(anchored != NULL);
289 E : DCHECK(moved != NULL);
290 E : DCHECK_NE(anchored, moved);
291 :
292 E : BlockList& ablocks(anchored->ordered_section->ordered_blocks_);
293 E : BlockList& mblocks(moved->ordered_section->ordered_blocks_);
294 :
295 : // Already there? Do nothing!
296 E : if (&ablocks == &mblocks && ++Copy(moved->it) == anchored->it)
297 E : return;
298 :
299 E : ablocks.splice(anchored->it, mblocks, moved->it);
300 E : --(moved->it = anchored->it);
301 E : moved->ordered_section = anchored->ordered_section;
302 E : moved_block->set_section(anchored->ordered_section->id());
303 E : DCHECK_EQ(*(moved->it), moved_block);
304 E : }
305 :
306 : void OrderedBlockGraph::PlaceAfter(const BlockGraph::Block* anchored_block,
307 E : BlockGraph::Block* moved_block) {
308 E : DCHECK(anchored_block != NULL);
309 E : DCHECK(moved_block != NULL);
310 E : DCHECK_NE(anchored_block, moved_block);
311 :
312 E : BlockInfo* anchored = GetBlockInfo(anchored_block);
313 E : BlockInfo* moved = GetBlockInfo(moved_block);
314 E : DCHECK(anchored != NULL);
315 E : DCHECK(moved != NULL);
316 E : DCHECK_NE(anchored, moved);
317 :
318 E : BlockList& ablocks(anchored->ordered_section->ordered_blocks_);
319 E : BlockList& mblocks(moved->ordered_section->ordered_blocks_);
320 :
321 E : BlockList::iterator anchored_it = anchored->it;
322 E : ++anchored_it;
323 :
324 : // Already there? Do nothing!
325 E : if (&ablocks == &mblocks && moved->it == anchored_it)
326 E : return;
327 :
328 E : ablocks.splice(anchored_it, mblocks, moved->it);
329 E : --(moved->it = anchored_it);
330 E : moved->ordered_section = anchored->ordered_section;
331 E : moved_block->set_section(anchored->ordered_section->id());
332 E : DCHECK_EQ(*(moved->it), moved_block);
333 E : }
334 :
335 : const OrderedBlockGraph::SectionInfo* OrderedBlockGraph::GetSectionInfo(
336 E : const Section* section) const {
337 : // Special case: the catch all section, which actually does not correspond
338 : // to any section in the block-graph.
339 E : if (section == NULL) {
340 E : DCHECK(section_infos_[0].ordered_section.section_ == NULL);
341 E : return §ion_infos_[0];
342 : }
343 :
344 : std::vector<SectionInfo>::const_iterator it =
345 : std::lower_bound(section_infos_.begin() + 1,
346 : section_infos_.end(),
347 : section,
348 E : CompareSectionInfo());
349 E : DCHECK(it != section_infos_.end());
350 E : DCHECK_EQ(section, it->ordered_section.section_);
351 E : return &(*it);
352 E : }
353 :
354 : OrderedBlockGraph::SectionInfo* OrderedBlockGraph::GetSectionInfo(
355 E : const Section* section) {
356 : // We use the const version, and cast away constness.
357 : return const_cast<SectionInfo*>(
358 E : const_cast<const OrderedBlockGraph*>(this)->GetSectionInfo(section));
359 E : }
360 :
361 : const OrderedBlockGraph::BlockInfo* OrderedBlockGraph::GetBlockInfo(
362 E : const Block* block) const {
363 : std::vector<BlockInfo>::const_iterator it =
364 : std::lower_bound(block_infos_.begin(),
365 : block_infos_.end(),
366 : block,
367 E : CompareBlockInfo());
368 E : DCHECK(it != block_infos_.end());
369 E : DCHECK_EQ(block, *(it->it));
370 E : return &(*it);
371 E : }
372 :
373 : OrderedBlockGraph::BlockInfo* OrderedBlockGraph::GetBlockInfo(
374 E : const Block* block) {
375 : // We use the const version, and cast away constness.
376 : return const_cast<BlockInfo*>(
377 E : const_cast<const OrderedBlockGraph*>(this)->GetBlockInfo(block));
378 E : }
379 :
380 E : void OrderedBlockGraph::RebuildSectionIndex() {
381 E : SectionList::iterator it = ordered_sections_.begin();
382 E : for (; it != ordered_sections_.end(); ++it) {
383 E : SectionInfo* info = GetSectionInfo((*it)->section_);
384 E : DCHECK(info != NULL);
385 E : info->it = it;
386 E : }
387 E : }
388 :
389 E : BlockGraph::SectionId OrderedBlockGraph::OrderedSection::id() const {
390 E : if (section_ == NULL)
391 E : return BlockGraph::kInvalidSectionId;
392 E : return section_->id();
393 E : }
394 :
395 : } // namespace block_graph
|