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 block_graph::TransformPolicyInterface TransformPolicyInterface;
59 : typedef BlockGraph::RelativeAddress RelativeAddress;
60 : typedef Reorderer::Order Order;
61 :
62 : // Used for internal book-keeping. Exposed here so that anonymous helpers in
63 : // the implementation can access this.
64 : struct BlockInfo;
65 : typedef std::vector<BlockInfo> BlockInfos;
66 :
67 : // Constructor.
68 : // @param order the order specification to apply. The lifetime of this object
69 : // must exceed that of any calls to TransformBlockGraph on this transform.
70 : // This will be modified by the transformation. See class description for
71 : // details.
72 : explicit BasicBlockLayoutTransform(Order* order);
73 :
74 : virtual ~BasicBlockLayoutTransform();
75 :
76 : private:
77 : // @name IterativeTransformImpl implementation.
78 : // @{
79 : friend block_graph::transforms::IterativeTransformImpl<
80 : BasicBlockLayoutTransform>;
81 : bool PreBlockGraphIteration(const TransformPolicyInterface* policy,
82 : BlockGraph* block_graph,
83 : BlockGraph::Block* header_block);
84 : bool OnBlock(const TransformPolicyInterface* policy,
85 : BlockGraph* block_graph,
86 : BlockGraph::Block* block);
87 : // @}
88 :
89 : // @name NamedBlockGraphTransformImpl implementation.
90 : // @{
91 : friend block_graph::transforms::NamedBlockGraphTransformImpl<
92 : BasicBlockLayoutTransform>;
93 : static const char kTransformName[];
94 : // @}
95 :
96 : bool FindOrCreateSections(BlockGraph* block_graph);
97 : bool FindOrCreateSection(BlockGraph* block_graph,
98 : Order::SectionSpec* section_spec);
99 :
100 : // Builds the block information vector over order_.
101 : void BuildBlockInfos();
102 :
103 : // Gets the section ID associated with a given section specification.
104 : bool GetSectionId(const Order::SectionSpec* section_spec,
105 : BlockGraph* block_graph,
106 : BlockGraph::SectionId* section_id);
107 :
108 : // The ordering to be applied to the block graph by this transform.
109 : Order* order_;
110 :
111 : // A vector sorted by block-pointer, which allows efficient look-up of order
112 : // information for a particular source block.
113 : BlockInfos block_infos_;
114 :
115 : DISALLOW_COPY_AND_ASSIGN(BasicBlockLayoutTransform);
116 : };
117 :
118 : // A small helper structure used for efficiently looking up order information
119 : // associated with a given source block.
120 : struct BasicBlockLayoutTransform::BlockInfo {
121 : // This is a pointer to the block in the block_spec. We keep a copy of it
122 : // because it is our primary sort key and block_spec->block gets updated as
123 : // we work.
124 : const BlockGraph::Block* original_block;
125 : Order::SectionSpec* section_spec;
126 : Order::BlockSpec* block_spec;
127 : };
128 :
129 : // This basic block subgraph transform implements the layout described by the
130 : // given BasicBlockMap. It is used by the BasicBlockLayoutTransform to
131 : // transform individual blocks. This need not be publicly exposed, but is done
132 : // so for ease of unittesting.
133 : class BasicBlockSubGraphLayoutTransform
134 : : public block_graph::transforms::NamedBasicBlockSubGraphTransformImpl<
135 : BasicBlockSubGraphLayoutTransform> {
136 : public:
137 : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
138 : typedef block_graph::BlockGraph BlockGraph;
139 : typedef block_graph::TransformPolicyInterface TransformPolicyInterface;
140 : typedef Reorderer::Order Order;
141 :
142 : // When exploding a block, its basic blocks may end up being mapped across
143 : // multiple output blocks. This maps basic-blocks (as offsets in the original
144 : // block) to their output block (as an integer index) and position (as an
145 : // integer position).
146 : typedef std::pair<size_t, size_t> BlockPositionPair; // (block, position).
147 : typedef std::map<Order::Offset, BlockPositionPair> BasicBlockMap;
148 :
149 : // Constructor.
150 : // @param bb_map The basic block map describing the layout of the basic blocks
151 : // in the block to be transformed. This must not be empty and it must be
152 : // well formed (block indices from 0 to block_count - 1, basic block
153 : // position indices starting at 0 and contiguous).
154 E : explicit BasicBlockSubGraphLayoutTransform(const BasicBlockMap& bb_map)
155 : : bb_map_(bb_map) {
156 E : DCHECK(!bb_map.empty());
157 E : }
158 :
159 : // @name BasicBlockSubGraphTransformInterface.
160 : // @{
161 : virtual bool TransformBasicBlockSubGraph(
162 : const TransformPolicyInterface* policy,
163 : BlockGraph* block_graph,
164 : BasicBlockSubGraph* basic_block_subgraph) override;
165 : // @}
166 :
167 : private:
168 : // @named NamedBasicBlockSubGraphTransformImpl implementation.
169 : // @{
170 : friend block_graph::transforms::NamedBasicBlockSubGraphTransformImpl<
171 : BasicBlockSubGraphLayoutTransform>;
172 : static const char kTransformName[];
173 : // @}
174 :
175 : // Creates the block descriptions and ensures their basic block lists are
176 : // all empty.
177 : typedef std::vector<BasicBlockSubGraph::BlockDescription*> BlockDescriptions;
178 : bool CreateBlockDescriptions(size_t block_count,
179 : BasicBlockSubGraph* basic_block_subgraph,
180 : BlockDescriptions* block_descs);
181 :
182 : const BasicBlockMap& bb_map_;
183 :
184 : DISALLOW_COPY_AND_ASSIGN(BasicBlockSubGraphLayoutTransform);
185 : };
186 :
187 : } // namespace transforms
188 : } // namespace reorder
189 :
190 : #endif // SYZYGY_REORDER_TRANSFORMS_BASIC_BLOCK_LAYOUT_TRANSFORM_H_
|