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 : // Declares the basic block layout transform. This transform is responsible for
16 : // applying a fully specified basic block layout, allowing for basic blocks to
17 : // be ordered within a block, and split across blocks and sections. A basic
18 : // block layout also specifies a section and block ordering. This transform
19 : // modifies the provided order in-place so that it can be applied to the
20 : // post-transform image using the standard ExplicitOrderer.
21 :
22 : #ifndef SYZYGY_REORDER_TRANSFORMS_BASIC_BLOCK_LAYOUT_TRANSFORM_H_
23 : #define SYZYGY_REORDER_TRANSFORMS_BASIC_BLOCK_LAYOUT_TRANSFORM_H_
24 :
25 : #include "syzygy/block_graph/transforms/iterative_transform.h"
26 : #include "syzygy/reorder/reorderer.h"
27 :
28 : namespace reorder {
29 : namespace transforms {
30 :
31 : // A class that transforms a block graph at the basic block level, ordering
32 : // basic blocks within blocks, and splitting basic blocks across blocks and
33 : // sections (creating and modifying sections as necessary). Intended to be
34 : // paired with an ExplicitOrderer in order to fully transform and order an
35 : // image.
36 : //
37 : // There is no mechanism provided to explicitly delete a section. However, a
38 : // section that contains no blocks post-ordering will be implicitly deleted.
39 : //
40 : // The provided Order is modified as follows:
41 : //
42 : // (1) Section specifications that cause new sections to be created will have
43 : // their id's filled out with the id of the newly created section.
44 : // (2) Block specifications that include basic-block information (a non-empty
45 : // OffsetVector) will have their block pointer updated to point to the
46 : // newly created block, thus preventing the order from holding dangling
47 : // pointers. Additionally, the OffsetVector will be cleared as the BB
48 : // offsets are now meaningless in the context of the new block.
49 : //
50 : // Post-transformation the Order is a simply block-level ordering, with the
51 : // BB-level ordering having been applied and extracted out of the Order. At
52 : // this point it is able to be fed into an ExplicitOrderer for final ordering.
53 : class BasicBlockLayoutTransform
54 : : public block_graph::transforms::IterativeTransformImpl<
55 : BasicBlockLayoutTransform> {
56 : public:
57 : typedef block_graph::BlockGraph BlockGraph;
58 : typedef BlockGraph::RelativeAddress RelativeAddress;
59 : typedef Reorderer::Order Order;
60 :
61 : // Used for internal book-keeping. Exposed here so that anonymous helpers in
62 : // the implementation can access this.
63 : struct BlockInfo;
64 : typedef std::vector<BlockInfo> BlockInfos;
65 :
66 : // Constructor.
67 : // @param order the order specification to apply. The lifetime of this object
68 : // must exceed that of any calls to TransformBlockGraph on this transform.
69 : // This will be modified by the transformation. See class description for
70 : // details.
71 : explicit BasicBlockLayoutTransform(Order* order);
72 :
73 : virtual ~BasicBlockLayoutTransform();
74 :
75 : private:
76 : // @name IterativeTransformImpl implementation.
77 : // @{
78 : friend block_graph::transforms::IterativeTransformImpl<
79 : BasicBlockLayoutTransform>;
80 : bool PreBlockGraphIteration(BlockGraph* block_graph,
81 : BlockGraph::Block* header_block);
82 : bool OnBlock(BlockGraph* block_graph, BlockGraph::Block* block);
83 : // @}
84 :
85 : // @name NamedBlockGraphTransformImpl implementation.
86 : // @{
87 : friend block_graph::transforms::NamedBlockGraphTransformImpl<
88 : BasicBlockLayoutTransform>;
89 : static const char kTransformName[];
90 : // @}
91 :
92 : bool FindOrCreateSections(BlockGraph* block_graph);
93 : bool FindOrCreateSection(BlockGraph* block_graph,
94 : Order::SectionSpec* section_spec);
95 :
96 : // Builds the block information vector over order_.
97 : void BuildBlockInfos();
98 :
99 : // Gets the section ID associated with a given section specification.
100 : bool GetSectionId(const Order::SectionSpec* section_spec,
101 : BlockGraph* block_graph,
102 : BlockGraph::SectionId* section_id);
103 :
104 : // The ordering to be applied to the block graph by this transform.
105 : Order* order_;
106 :
107 : // A vector sorted by block-pointer, which allows efficient look-up of order
108 : // information for a particular source block.
109 : BlockInfos block_infos_;
110 :
111 : DISALLOW_COPY_AND_ASSIGN(BasicBlockLayoutTransform);
112 : };
113 :
114 : // A small helper structure used for efficiently looking up order information
115 : // associated with a given source block.
116 : struct BasicBlockLayoutTransform::BlockInfo {
117 : // This is a pointer to the block in the block_spec. We keep a copy of it
118 : // because it is our primary sort key and block_spec->block gets updated as
119 : // we work.
120 : const BlockGraph::Block* original_block;
121 : Order::SectionSpec* section_spec;
122 : Order::BlockSpec* block_spec;
123 : };
124 :
125 : // This basic block subgraph transform implements the layout described by the
126 : // given BasicBlockMap. It is used by the BasicBlockLayoutTransform to
127 : // transform individual blocks. This need not be publicly exposed, but is done
128 : // so for ease of unittesting.
129 : class BasicBlockSubGraphLayoutTransform
130 : : public block_graph::transforms::NamedBasicBlockSubGraphTransformImpl<
131 : BasicBlockSubGraphLayoutTransform> {
132 : public:
133 : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
134 : typedef block_graph::BlockGraph BlockGraph;
135 : typedef Reorderer::Order Order;
136 :
137 : // When exploding a block, its basic blocks may end up being mapped across
138 : // multiple output blocks. This maps basic-blocks (as offsets in the original
139 : // block) to their output block (as an integer index) and position (as an
140 : // integer position).
141 : typedef std::pair<size_t, size_t> BlockPositionPair; // (block, position).
142 : typedef std::map<Order::Offset, BlockPositionPair> BasicBlockMap;
143 :
144 : // Constructor.
145 : // @param bb_map The basic block map describing the layout of the basic blocks
146 : // in the block to be transformed. This must not be empty and it must be
147 : // well formed (block indices from 0 to block_count - 1, basic block
148 : // position indices starting at 0 and contiguous).
149 E : explicit BasicBlockSubGraphLayoutTransform(const BasicBlockMap& bb_map)
150 : : bb_map_(bb_map) {
151 E : DCHECK(!bb_map.empty());
152 E : }
153 :
154 : // @name BasicBlockSubGraphTransformInterface.
155 : // @{
156 : virtual bool TransformBasicBlockSubGraph(
157 : BlockGraph* block_graph,
158 : BasicBlockSubGraph* basic_block_subgraph) OVERRIDE;
159 : // @}
160 :
161 : private:
162 : // @named NamedBasicBlockSubGraphTransformImpl implementation.
163 : // @{
164 : friend block_graph::transforms::NamedBasicBlockSubGraphTransformImpl<
165 : BasicBlockSubGraphLayoutTransform>;
166 : static const char kTransformName[];
167 : // @}
168 :
169 : // Creates the block descriptions and ensures their basic block lists are
170 : // all empty.
171 : typedef std::vector<BasicBlockSubGraph::BlockDescription*> BlockDescriptions;
172 : bool CreateBlockDescriptions(size_t block_count,
173 : BasicBlockSubGraph* basic_block_subgraph,
174 : BlockDescriptions* block_descs);
175 :
176 : const BasicBlockMap& bb_map_;
177 :
178 : DISALLOW_COPY_AND_ASSIGN(BasicBlockSubGraphLayoutTransform);
179 : };
180 :
181 : } // namespace transforms
182 : } // namespace reorder
183 :
184 : #endif // SYZYGY_REORDER_TRANSFORMS_BASIC_BLOCK_LAYOUT_TRANSFORM_H_
|