1 : // Copyright 2013 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 ChainedBasicBlockTransform.
16 :
17 : #include "syzygy/optimize/transforms/chained_subgraph_transforms.h"
18 :
19 : #include <stack>
20 :
21 : #include "syzygy/block_graph/basic_block_decomposer.h"
22 : #include "syzygy/block_graph/block_builder.h"
23 : #include "syzygy/block_graph/block_util.h"
24 : #include "syzygy/optimize/transforms/subgraph_transform.h"
25 :
26 : namespace optimize {
27 : namespace transforms {
28 :
29 : namespace {
30 :
31 : using block_graph::BasicBlockDecomposer;
32 : using block_graph::BasicBlockSubGraph;
33 : using block_graph::BlockBuilder;
34 : using block_graph::BlockGraph;
35 : using block_graph::BlockVector;
36 : typedef BlockGraph::Block::ReferrerSet ReferrerSet;
37 : typedef std::list<BlockGraph::Block*> BlockOrdering;
38 :
39 : // Traverse the call-graph in reverse call order (callee to caller) and push
40 : // blocks in post-order. The resulting ordering can be iterated to visit all
41 : // blocks from leaf to root. The ordering has the guarantee that all callees
42 : // have been visited before their callers (except for recursive calls and
43 : // indirect calls).
44 : // TODO(etienneb): Hoist this function into block_graph.
45 E : void FlattenCallgraphPostOrder(BlockGraph* block_graph, BlockOrdering* order) {
46 E : DCHECK_NE(reinterpret_cast<BlockGraph*>(NULL), block_graph);
47 E : DCHECK_NE(reinterpret_cast<BlockOrdering*>(NULL), order);
48 :
49 : // The algorithms uses a std::stack allocated in the heap to avoid stack
50 : // overflow.
51 E : std::stack<BlockGraph::Block*> stack;
52 E : std::set<BlockGraph::Block*> visiting;
53 :
54 : // Traverse the call-graph in depth-first.
55 E : BlockGraph::BlockMap& blocks = block_graph->blocks_mutable();
56 E : BlockGraph::BlockMap::iterator block_iter = blocks.begin();
57 E : for (; block_iter != blocks.end(); ++block_iter) {
58 E : BlockGraph::Block* block = &block_iter->second;
59 :
60 : // This block is already visited.
61 E : if (!visiting.insert(block).second)
62 i : continue;
63 :
64 : // This block needs to be visited, add it to the stack.
65 E : stack.push(block);
66 :
67 : // Follow the referrers.
68 E : while (!stack.empty()) {
69 E : block = stack.top();
70 :
71 : // Put unvisited referrers on the stack.
72 : typedef std::map<BlockGraph::BlockId, BlockGraph::Block*> OrderedBlockMap;
73 E : OrderedBlockMap missing;
74 E : bool missing_referrers = false;
75 E : if (block->type() == BlockGraph::CODE_BLOCK) {
76 E : const ReferrerSet& referrers = block->referrers();
77 E : ReferrerSet::iterator referrer = referrers.begin();
78 E : for (; referrer != referrers.end(); ++referrer) {
79 i : BlockGraph::Block* from = referrer->first;
80 i : if (visiting.insert(from).second) {
81 i : missing.insert(std::make_pair(from->id(), from));
82 i : missing_referrers = true;
83 : }
84 i : }
85 : }
86 :
87 : // Push missing referrers into the stack, ordered by block id.
88 E : OrderedBlockMap::iterator referrer = missing.begin();
89 E : for (; referrer != missing.end(); ++referrer)
90 i : stack.push(referrer->second);
91 :
92 : // When there are no missing referrers, this block is fully visited and
93 : // can be pushed in the ordering (post-order).
94 E : if (!missing_referrers) {
95 E : order->push_front(block);
96 : // Remove this block from the stack.
97 E : DCHECK_EQ(block, stack.top());
98 E : stack.pop();
99 : }
100 E : }
101 E : }
102 E : }
103 :
104 : } // namespace
105 :
106 : const char ChainedSubgraphTransforms::kTransformName[] =
107 : "ChainedSubgraphTransforms";
108 :
109 : void ChainedSubgraphTransforms::AppendTransform(
110 E : SubGraphTransformInterface* transform) {
111 E : DCHECK_NE(reinterpret_cast<SubGraphTransformInterface*>(NULL), transform);
112 E : transforms_.push_back(transform);
113 E : }
114 :
115 : bool ChainedSubgraphTransforms::TransformBlockGraph(
116 : const TransformPolicyInterface* policy,
117 : BlockGraph* block_graph,
118 E : BlockGraph::Block* header_block) {
119 :
120 : // Avoid processing if no transforms are applied.
121 E : if (transforms_.empty())
122 E : return true;
123 :
124 E : BlockOrdering order;
125 E : FlattenCallgraphPostOrder(block_graph, &order);
126 :
127 E : BlockOrdering::iterator block_iter = order.begin();
128 E : for (; block_iter != order.end(); ++block_iter) {
129 E : BlockGraph::Block* block = *block_iter;
130 :
131 : // Use the decomposition policy to skip blocks that aren't eligible for
132 : // basic-block decomposition.
133 E : if (!policy->BlockIsSafeToBasicBlockDecompose(block))
134 E : continue;
135 :
136 : // Decompose block to basic blocks.
137 E : BasicBlockSubGraph subgraph;
138 E : BasicBlockDecomposer bb_decomposer(block, &subgraph);
139 E : if (!bb_decomposer.Decompose())
140 i : return false;
141 :
142 : // Update subgraph profile.
143 E : scoped_ptr<SubGraphProfile> subgraph_profile;
144 E : profile_->ComputeSubGraphProfile(&subgraph, &subgraph_profile);
145 :
146 : // Apply the series of basic block transforms to this block.
147 E : TransformList::const_iterator it = transforms_.begin();
148 E : for (; it != transforms_.end(); ++it) {
149 E : SubGraphTransformInterface* transform = *it;
150 E : DCHECK(transform != NULL);
151 : if (!transform->TransformBasicBlockSubGraph(policy,
152 : block_graph,
153 : &subgraph,
154 : profile_,
155 E : subgraph_profile.get())) {
156 i : return false;
157 : }
158 E : }
159 :
160 : // Update the block-graph post transform.
161 E : BlockBuilder builder(block_graph);
162 E : if (!builder.Merge(&subgraph))
163 i : return false;
164 :
165 : // TODO(etienneb): This is needed until the labels refactoring.
166 E : const BlockVector& blocks = builder.new_blocks();
167 E : BlockVector::const_iterator new_block = blocks.begin();
168 E : for (; new_block != blocks.end(); ++new_block)
169 E : (*new_block)->set_attribute(BlockGraph::BUILT_BY_SYZYGY);
170 E : }
171 :
172 E : return true;
173 E : }
174 :
175 : } // namespace transforms
176 : } // namespace optimize
|