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