1 : // Copyright 2014 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 unreachable block transform.
16 :
17 : #include "syzygy/optimize/transforms/unreachable_block_transform.h"
18 :
19 : #include <stack>
20 :
21 : namespace optimize {
22 : namespace transforms {
23 :
24 : namespace {
25 :
26 : // Forward declaration.
27 : struct SubTreeInformation;
28 :
29 : using block_graph::BlockGraph;
30 : typedef BlockGraph::Block::ReferenceMap ReferenceMap;
31 : typedef std::set<const BlockGraph::Block*> ReachableSet;
32 : typedef std::stack<const BlockGraph::Block*> ReachableStack;
33 : typedef std::map<const BlockGraph::Block*, SubTreeInformation> RecursiveSizeMap;
34 :
35 : struct SubTreeInformation {
36 : size_t size;
37 : size_t count;
38 : };
39 :
40 : // This function computes the number and the total size of the reachable blocks
41 : // from the given root |block|.
42 : void ComputeSubTreeInformation(const BlockGraph::Block* block,
43 : const BlockGraph::BlockMap& blocks,
44 : const ReachableSet& reachable,
45 : SubTreeInformation* subtree,
46 i : ReachableSet* visited) {
47 i : DCHECK_NE(reinterpret_cast<SubTreeInformation*>(NULL), subtree);
48 i : DCHECK_NE(reinterpret_cast<ReachableSet*>(NULL), visited);
49 :
50 : // Avoid repeatedly visiting the same block within a sub-tree. Even if a block
51 : // is reachable via multiple paths, it contributes only once to the size of
52 : // the sub-tree.
53 i : if (!visited->insert(block).second)
54 i : return;
55 :
56 : // Add the size of the current block.
57 i : subtree->size += block->size();
58 i : subtree->count += 1;
59 :
60 : // Sum the size of each sub-tree by following references.
61 i : const ReferenceMap& references = block->references();
62 i : ReferenceMap::const_iterator reference = references.begin();
63 i : for (; reference != references.end(); ++reference) {
64 i : const BlockGraph::Block* reference_block = reference->second.referenced();
65 i : if (reachable.find(reference_block) != reachable.end())
66 i : continue;
67 : ComputeSubTreeInformation(
68 i : reference_block, blocks, reachable, subtree, visited);
69 i : }
70 i : }
71 :
72 : bool DumpUnreachableCallgraph(const base::FilePath& path,
73 : const BlockGraph::BlockMap& blocks,
74 E : const ReachableSet& reachable) {
75 :
76 : // A cache of computed sizes.
77 E : RecursiveSizeMap subtrees;
78 :
79 : // Dump a cachegrind file.
80 E : base::ScopedFILE file(base::OpenFile(path, "wb+"));
81 E : if (!file.get()) {
82 i : LOG(ERROR) << "Could not create file.";
83 i : return false;
84 : }
85 :
86 E : ::fprintf(file.get(), "events: Size Count\n");
87 :
88 E : BlockGraph::BlockMap::const_iterator block_iter = blocks.begin();
89 E : for (block_iter = blocks.begin(); block_iter != blocks.end(); ++block_iter) {
90 E : const BlockGraph::Block* block = &block_iter->second;
91 E : if (reachable.find(block) != reachable.end())
92 E : continue;
93 :
94 E : ::fprintf(file.get(), "ob=%s\n", block->compiland_name().c_str());
95 E : ::fprintf(file.get(), "fn=%s\n", block->name().c_str());
96 E : ::fprintf(file.get(), "%u %u %u\n", block->id(), block->size(), 1);
97 :
98 E : ReachableSet subtree_visited;
99 E : subtree_visited.insert(block);
100 :
101 E : const ReferenceMap& references = block->references();
102 E : ReferenceMap::const_iterator reference = references.begin();
103 E : for (; reference != references.end(); ++reference) {
104 i : const BlockGraph::Block* reference_block = reference->second.referenced();
105 i : if (reachable.find(reference_block) != reachable.end())
106 i : continue;
107 i : if (subtree_visited.find(reference_block) != subtree_visited.end())
108 i : continue;
109 :
110 i : SubTreeInformation subtree = {0, 0};
111 i : RecursiveSizeMap::iterator look = subtrees.find(reference_block);
112 i : if (look != subtrees.end()) {
113 i : subtree = look->second;
114 i : } else {
115 : ComputeSubTreeInformation(reference_block,
116 : blocks,
117 : reachable,
118 : &subtree,
119 i : &subtree_visited);
120 i : subtrees[reference_block] = subtree;
121 : }
122 :
123 : ::fprintf(file.get(), "cob=%s\n",
124 i : reference_block->compiland_name().c_str());
125 : ::fprintf(file.get(), "cfn=%s\n",
126 i : reference_block->name().c_str());
127 i : ::fprintf(file.get(), "calls=%u %u\n", 1, reference_block->size());
128 : ::fprintf(file.get(), "%u %u %u\n",
129 : block->id(),
130 : subtree.size,
131 i : subtree.count);
132 i : }
133 E : ::fprintf(file.get(), "\n");
134 E : }
135 :
136 E : return true;
137 E : }
138 :
139 : } // namespace
140 :
141 : const char UnreachableBlockTransform::kTransformName[] =
142 : "UnreachableBlockTransform";
143 :
144 : bool UnreachableBlockTransform::TransformBlockGraph(
145 : const TransformPolicyInterface* policy,
146 : BlockGraph* block_graph,
147 E : BlockGraph::Block* header_block) {
148 :
149 E : ReachableSet reachable;
150 E : ReachableStack working;
151 :
152 : // Mark roots as reachable.
153 E : reachable.insert(header_block);
154 E : working.push(header_block);
155 :
156 E : BlockGraph::BlockMap& blocks = block_graph->blocks_mutable();
157 E : BlockGraph::BlockMap::iterator block_iter = blocks.begin();
158 E : for (block_iter = blocks.begin(); block_iter != blocks.end(); ++block_iter) {
159 E : BlockGraph::Block* block = &block_iter->second;
160 E : if ((block->attributes() & BlockGraph::PE_PARSED) == 0)
161 E : continue;
162 E : reachable.insert(block);
163 E : working.push(block);
164 E : }
165 :
166 : // Follow the reachable graph.
167 E : while (!working.empty()) {
168 E : const BlockGraph::Block* block = working.top();
169 E : working.pop();
170 :
171 E : const ReferenceMap& references = block->references();
172 E : ReferenceMap::const_iterator reference = references.begin();
173 E : for (; reference != references.end(); ++reference) {
174 E : const BlockGraph::Block* reference_block = reference->second.referenced();
175 E : if (reachable.insert(reference_block).second)
176 E : working.push(reference_block);
177 E : }
178 E : }
179 :
180 : // Dump a cachegrind graph of unreachable blocks.
181 E : if (!unreachable_graph_path_.empty())
182 E : DumpUnreachableCallgraph(unreachable_graph_path_, blocks, reachable);
183 :
184 : // Remove references of unreachable blocks. This pass is needed because blocks
185 : // with references cannot be removed.
186 E : block_iter = blocks.begin();
187 E : std::vector<BlockGraph::BlockId> to_remove;
188 E : for (block_iter = blocks.begin(); block_iter != blocks.end(); ++block_iter) {
189 E : BlockGraph::Block* block = &block_iter->second;
190 E : if (reachable.find(block) == reachable.end()) {
191 E : block->RemoveAllReferences();
192 E : to_remove.push_back(block->id());
193 : }
194 E : }
195 :
196 : // Remove unreachable blocks from the block graph.
197 E : std::vector<BlockGraph::BlockId>::iterator dead_block = to_remove.begin();
198 E : for (; dead_block != to_remove.end(); ++dead_block)
199 E : block_graph->RemoveBlockById(*dead_block);
200 :
201 E : return true;
202 E : }
203 :
204 : } // namespace transforms
205 : } // namespace optimize
|