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 = block_graph_->GetSectionById(section_id);
99 E : SectionInfo* section_info = GetSectionInfo(section);
100 E : DCHECK(section_info != NULL);
101 :
102 E : Block* block = &block_it->second;
103 :
104 E : OrderedSection* ordered_section = §ion_info->ordered_section;
105 E : block_infos_[i].ordered_section = ordered_section;
106 : block_infos_[i].it = ordered_section->ordered_blocks_.insert(
107 E : ordered_section->ordered_blocks_.end(), block);
108 E : }
109 :
110 : // Sort the BlockInfos so that we can use GetBlockInfo.
111 E : std::sort(block_infos_.begin(), block_infos_.end(), CompareBlockInfo());
112 E : }
113 :
114 : const OrderedBlockGraph::OrderedSection& OrderedBlockGraph::ordered_section(
115 E : const Section* section) const {
116 E : const SectionInfo* section_info = GetSectionInfo(section);
117 E : DCHECK(section_info != NULL);
118 E : return section_info->ordered_section;
119 E : }
120 :
121 : OrderedBlockGraph::BlockList::const_iterator OrderedBlockGraph::begin(
122 : const Section* section) const {
123 : return ordered_section(section).ordered_blocks().begin();
124 : }
125 :
126 : OrderedBlockGraph::BlockList::const_iterator OrderedBlockGraph::end(
127 : const Section* section) const {
128 : return ordered_section(section).ordered_blocks().end();
129 : }
130 :
131 E : void OrderedBlockGraph::PlaceAtHead(const Section* section) {
132 E : DCHECK(section != NULL);
133 :
134 E : SectionInfo* section_info = GetSectionInfo(section);
135 E : DCHECK(section_info != NULL);
136 :
137 : // Already there? Do nothing!
138 E : if (section_info->it == ordered_sections_.begin())
139 E : return;
140 :
141 : // We use splice to avoid an allocation.
142 : ordered_sections_.splice(ordered_sections_.begin(),
143 : ordered_sections_,
144 E : section_info->it);
145 :
146 : // Splice invalidates the iterator.
147 E : section_info->it = ordered_sections_.begin();
148 E : DCHECK_EQ(*(section_info->it), §ion_info->ordered_section);
149 E : }
150 :
151 E : void OrderedBlockGraph::PlaceAtTail(const Section* section) {
152 E : DCHECK(section != NULL);
153 :
154 E : SectionInfo* section_info = GetSectionInfo(section);
155 E : DCHECK(section_info != NULL);
156 :
157 : // Already there? Do nothing!
158 E : if (section_info->it == --ordered_sections_.end())
159 E : return;
160 :
161 : // We use splice to avoid an allocation.
162 : ordered_sections_.splice(ordered_sections_.end(),
163 : ordered_sections_,
164 E : section_info->it);
165 :
166 : // Splice invalidates the iterator.
167 E : --(section_info->it = ordered_sections_.end());
168 E : DCHECK_EQ(*(section_info->it), §ion_info->ordered_section);
169 E : }
170 :
171 : void OrderedBlockGraph::PlaceBefore(const Section* anchored_section,
172 E : const Section* moved_section) {
173 E : DCHECK(anchored_section != NULL);
174 E : DCHECK(moved_section != NULL);
175 E : DCHECK_NE(anchored_section, moved_section);
176 :
177 E : SectionInfo* anchored = GetSectionInfo(anchored_section);
178 E : SectionInfo* moved = GetSectionInfo(moved_section);
179 E : DCHECK(anchored != NULL);
180 E : DCHECK(moved != NULL);
181 E : DCHECK_NE(anchored, moved);
182 :
183 : // Already there? Do nothing!
184 E : if (++Copy(moved->it) == anchored->it)
185 E : return;
186 :
187 : ordered_sections_.splice(anchored->it,
188 : ordered_sections_,
189 E : moved->it);
190 E : --(moved->it = anchored->it);
191 E : DCHECK_EQ(*(moved->it), &moved->ordered_section);
192 E : }
193 :
194 : void OrderedBlockGraph::PlaceAfter(const Section* anchored_section,
195 E : const Section* moved_section) {
196 E : DCHECK(anchored_section != NULL);
197 E : DCHECK(moved_section != NULL);
198 E : DCHECK_NE(anchored_section, moved_section);
199 :
200 E : SectionInfo* anchored = GetSectionInfo(anchored_section);
201 E : SectionInfo* moved = GetSectionInfo(moved_section);
202 E : DCHECK(anchored != NULL);
203 E : DCHECK(moved != NULL);
204 E : DCHECK_NE(anchored, moved);
205 :
206 E : SectionList::iterator anchor_it = anchored->it;
207 E : ++anchor_it;
208 :
209 : // Already there? Do nothing!
210 E : if (moved->it == anchor_it)
211 E : return;
212 :
213 : ordered_sections_.splice(anchor_it,
214 : ordered_sections_,
215 E : moved->it);
216 E : --(moved->it = anchor_it);
217 E : DCHECK_EQ(*(moved->it), &moved->ordered_section);
218 E : }
219 :
220 : void OrderedBlockGraph::PlaceAtHead(const Section* section,
221 E : BlockGraph::Block* block) {
222 E : DCHECK(block != NULL);
223 :
224 E : SectionInfo* section_info = GetSectionInfo(section);
225 E : BlockInfo* block_info = GetBlockInfo(block);
226 E : DCHECK(section_info != NULL);
227 E : DCHECK(block_info != NULL);
228 :
229 E : BlockList& blocks(section_info->ordered_section.ordered_blocks_);
230 :
231 : // Already there? Do nothing!
232 : if (&blocks == &block_info->ordered_section->ordered_blocks_ &&
233 E : block_info->it == blocks.begin()) {
234 E : return;
235 : }
236 :
237 : blocks.splice(blocks.begin(),
238 : block_info->ordered_section->ordered_blocks_,
239 E : block_info->it);
240 E : block_info->it = blocks.begin();
241 E : block_info->ordered_section = §ion_info->ordered_section;
242 E : block->set_section(section_info->id());
243 E : DCHECK_EQ(*(block_info->it), block);
244 E : }
245 :
246 : void OrderedBlockGraph::PlaceAtTail(const Section* section,
247 E : BlockGraph::Block* block) {
248 E : DCHECK(block != NULL);
249 :
250 E : SectionInfo* section_info = GetSectionInfo(section);
251 E : BlockInfo* block_info = GetBlockInfo(block);
252 E : DCHECK(section_info != NULL);
253 E : DCHECK(block_info != NULL);
254 :
255 E : BlockList& blocks(section_info->ordered_section.ordered_blocks_);
256 :
257 : // Already there? Do nothing!
258 : if (&blocks == &block_info->ordered_section->ordered_blocks_ &&
259 E : block_info->it == --blocks.end()) {
260 E : return;
261 : }
262 :
263 : blocks.splice(blocks.end(),
264 : block_info->ordered_section->ordered_blocks_,
265 E : block_info->it);
266 E : --(block_info->it = blocks.end());
267 E : block_info->ordered_section = §ion_info->ordered_section;
268 E : block->set_section(section_info->id());
269 E : DCHECK_EQ(*(block_info->it), block);
270 E : }
271 :
272 : void OrderedBlockGraph::PlaceBefore(const BlockGraph::Block* anchored_block,
273 E : BlockGraph::Block* moved_block) {
274 E : DCHECK(anchored_block != NULL);
275 E : DCHECK(moved_block != NULL);
276 E : DCHECK_NE(anchored_block, moved_block);
277 :
278 E : BlockInfo* anchored = GetBlockInfo(anchored_block);
279 E : BlockInfo* moved = GetBlockInfo(moved_block);
280 E : DCHECK(anchored != NULL);
281 E : DCHECK(moved != NULL);
282 E : DCHECK_NE(anchored, moved);
283 :
284 E : BlockList& ablocks(anchored->ordered_section->ordered_blocks_);
285 E : BlockList& mblocks(moved->ordered_section->ordered_blocks_);
286 :
287 : // Already there? Do nothing!
288 E : if (&ablocks == &mblocks && ++Copy(moved->it) == anchored->it)
289 E : return;
290 :
291 E : ablocks.splice(anchored->it, mblocks, moved->it);
292 E : --(moved->it = anchored->it);
293 E : moved->ordered_section = anchored->ordered_section;
294 E : moved_block->set_section(anchored->ordered_section->id());
295 E : DCHECK_EQ(*(moved->it), moved_block);
296 E : }
297 :
298 : void OrderedBlockGraph::PlaceAfter(const BlockGraph::Block* anchored_block,
299 E : BlockGraph::Block* moved_block) {
300 E : DCHECK(anchored_block != NULL);
301 E : DCHECK(moved_block != NULL);
302 E : DCHECK_NE(anchored_block, moved_block);
303 :
304 E : BlockInfo* anchored = GetBlockInfo(anchored_block);
305 E : BlockInfo* moved = GetBlockInfo(moved_block);
306 E : DCHECK(anchored != NULL);
307 E : DCHECK(moved != NULL);
308 E : DCHECK_NE(anchored, moved);
309 :
310 E : BlockList& ablocks(anchored->ordered_section->ordered_blocks_);
311 E : BlockList& mblocks(moved->ordered_section->ordered_blocks_);
312 :
313 E : BlockList::iterator anchored_it = anchored->it;
314 E : ++anchored_it;
315 :
316 : // Already there? Do nothing!
317 E : if (&ablocks == &mblocks && moved->it == anchored_it)
318 E : return;
319 :
320 E : ablocks.splice(anchored_it, mblocks, moved->it);
321 E : --(moved->it = anchored_it);
322 E : moved->ordered_section = anchored->ordered_section;
323 E : moved_block->set_section(anchored->ordered_section->id());
324 E : DCHECK_EQ(*(moved->it), moved_block);
325 E : }
326 :
327 : const OrderedBlockGraph::SectionInfo* OrderedBlockGraph::GetSectionInfo(
328 E : const Section* section) const {
329 : // Special case: the catch all section, which actually does not correspond
330 : // to any section in the block-graph.
331 E : if (section == NULL) {
332 E : DCHECK(section_infos_[0].ordered_section.section_ == NULL);
333 E : return §ion_infos_[0];
334 : }
335 :
336 : std::vector<SectionInfo>::const_iterator it =
337 : std::lower_bound(section_infos_.begin() + 1,
338 : section_infos_.end(),
339 : section,
340 E : CompareSectionInfo());
341 E : DCHECK(it != section_infos_.end());
342 E : DCHECK_EQ(section, it->ordered_section.section_);
343 E : return &(*it);
344 E : }
345 :
346 : OrderedBlockGraph::SectionInfo* OrderedBlockGraph::GetSectionInfo(
347 E : const Section* section) {
348 : // We use the const version, and cast away constness.
349 : return const_cast<SectionInfo*>(
350 E : const_cast<const OrderedBlockGraph*>(this)->GetSectionInfo(section));
351 E : }
352 :
353 : const OrderedBlockGraph::BlockInfo* OrderedBlockGraph::GetBlockInfo(
354 E : const Block* block) const {
355 : std::vector<BlockInfo>::const_iterator it =
356 : std::lower_bound(block_infos_.begin(),
357 : block_infos_.end(),
358 : block,
359 E : CompareBlockInfo());
360 E : DCHECK(it != block_infos_.end());
361 E : DCHECK_EQ(block, *(it->it));
362 E : return &(*it);
363 E : }
364 :
365 : OrderedBlockGraph::BlockInfo* OrderedBlockGraph::GetBlockInfo(
366 E : const Block* block) {
367 : // We use the const version, and cast away constness.
368 : return const_cast<BlockInfo*>(
369 E : const_cast<const OrderedBlockGraph*>(this)->GetBlockInfo(block));
370 E : }
371 :
372 E : void OrderedBlockGraph::RebuildSectionIndex() {
373 E : SectionList::iterator it = ordered_sections_.begin();
374 E : for (; it != ordered_sections_.end(); ++it) {
375 E : SectionInfo* info = GetSectionInfo((*it)->section_);
376 E : DCHECK(info != NULL);
377 E : info->it = it;
378 E : }
379 E : }
380 :
381 E : BlockGraph::SectionId OrderedBlockGraph::OrderedSection::id() const {
382 E : if (section_ == NULL)
383 E : return BlockGraph::kInvalidSectionId;
384 E : return section_->id();
385 E : }
386 :
387 : } // namespace block_graph
|