1 : // Copyright 2012 Google Inc.
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 : // Declaration of BasicBlockSubGraph class.
16 :
17 : #ifndef SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_SUBGRAPH_H_
18 : #define SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_SUBGRAPH_H_
19 :
20 : #include <map>
21 : #include <set>
22 : #include <string>
23 :
24 : #include "base/basictypes.h"
25 : #include "base/string_piece.h"
26 : #include "syzygy/block_graph/basic_block.h"
27 : #include "syzygy/block_graph/block_graph.h"
28 :
29 : namespace block_graph {
30 :
31 : // A basic-block sub-graph describes the make-up and layout of one or
32 : // more blocks as a set of code, data, and/or padding basic-blocks. Optionally,
33 : // it holds a pointer to a block from which the sub-graph was originally
34 : // derived.
35 : //
36 : // In manipulating the basic block sub-graph, note that the sub-graph
37 : // acts as a basic-block factory and retains ownership of all basic-blocks
38 : // that participate in the composition.
39 : class BasicBlockSubGraph {
40 : public:
41 : typedef block_graph::BasicBlock BasicBlock;
42 : typedef BasicBlock::BasicBlockType BasicBlockType;
43 : typedef std::list<BasicBlock*> BasicBlockOrdering;
44 : typedef block_graph::BlockGraph BlockGraph;
45 : typedef BlockGraph::Block Block;
46 : typedef BlockGraph::BlockType BlockType;
47 : typedef BlockGraph::Offset Offset;
48 : typedef BlockGraph::SectionId SectionId;
49 : typedef BlockGraph::Size Size;
50 : typedef BlockGraph::BlockAttributes BlockAttributes;
51 :
52 : // A structure describing a block (its properties, attributes, and
53 : // constituent ordered basic-blocks). A given basic-block may participate
54 : // in at most one BlockDescription at any time.
55 : struct BlockDescription {
56 : std::string name;
57 : BlockType type;
58 : SectionId section;
59 : Size alignment;
60 : BlockAttributes attributes;
61 : BasicBlockOrdering basic_block_order;
62 :
63 : // Calculate the current maximum possible size of the block described by
64 : // this BlockDescription, not including any trailing padding.
65 : size_t GetMaxSize() const;
66 : };
67 :
68 : typedef std::list<BlockDescription> BlockDescriptionList;
69 : typedef std::map<BasicBlock::BlockId, BasicBlock> BBCollection;
70 : typedef core::AddressSpace<Offset, size_t, BasicBlock*> BBAddressSpace;
71 : typedef std::map<const BasicBlock*, bool> ReachabilityMap;
72 :
73 : // Initialize a basic block sub-graph.
74 : BasicBlockSubGraph();
75 :
76 : // @name Accessors.
77 : // @{
78 E : void set_original_block(const Block* block) { original_block_ = block; }
79 E : const Block* original_block() const { return original_block_; }
80 E : const BBCollection& basic_blocks() const { return basic_blocks_; }
81 E : BBCollection& basic_blocks() { return basic_blocks_; }
82 : const BBAddressSpace& original_address_space() const {
83 : return original_address_space_;
84 : }
85 E : BBAddressSpace& original_address_space() { return original_address_space_; }
86 E : const BlockDescriptionList& block_descriptions() const {
87 E : return block_descriptions_;
88 E : }
89 E : BlockDescriptionList& block_descriptions() { return block_descriptions_; }
90 : // @}
91 :
92 : // Initializes and returns a new block description.
93 : // @param name The name of the block.
94 : // @param type The type of the block.
95 : // @param section The ID of the section in which the block should reside.
96 : // @param alignment The alignment of the block.
97 : // (i.e., location % alignment == 0)
98 : // @param attributes The attributes of the block.
99 : // @returns A pointer to the newly created block description.
100 : BlockDescription* AddBlockDescription(const base::StringPiece& name,
101 : BlockType type,
102 : SectionId section,
103 : Size alignment,
104 : BlockAttributes attributes);
105 :
106 : // Add a new basic block to the sub-graph.
107 : // @param name A textual identifier for this basic block.
108 : // @param type The disposition (code, data, padding) of this basic block.
109 : // @param offset The offset (in the original block) where this basic block
110 : // originated. Set to BasicBlock::kNoOffset to indicate that this is a
111 : // generated basic block.
112 : // @param size The number of bytes this basic block occupied in the original
113 : // block. Set to 0 if this is a generated basic block.
114 : // @param data The underlying data representing the basic block.
115 : // @returns A pointer to a newly allocated basic block representing the
116 : // original source range [@p offset, @p offset + @p size), or NULL on
117 : // ERROR. Ownership of the returned basic-block (if any) is retained
118 : // by the composition.
119 : BasicBlock* AddBasicBlock(const base::StringPiece& name,
120 : BasicBlockType type,
121 : Offset offset,
122 : Size size,
123 : const uint8* data);
124 :
125 : // Returns true if the basic-block composition is valid. This tests the
126 : // for following conditions.
127 : // 1. Each basic-block is used in at most one BlockDescription.
128 : // 2. Each code basic-block has valid successors.
129 : // 3. If there is an original block, then each of it's referrers is accounted
130 : // for in the new composition.
131 : bool IsValid() const;
132 :
133 : // Find the basic block, and corresponding byte-range, that contains the
134 : // given offset.
135 : // @param offset the starting offset you with the returned basic-block/range
136 : // to contain.
137 : // @param basic_block the basic-block containing @p offset.
138 : // @param range the byte-range in which @p basic_offset resides, which
139 : // contains @p offset.
140 : bool FindBasicBlock(Offset offset,
141 : BasicBlock** basic_block,
142 : BBAddressSpace::Range* range) const;
143 :
144 : // Find the basic block that begins at the given offset.
145 : // @param offset The starting offset of the basic block you want to find.
146 : // @pre The basic block subgraph is derived from an original block (and
147 : // thus has an address space) and has been broken down into all of its
148 : // constituent basic blocks (i.e., post disassembly and basic-block
149 : // splitting).
150 : BasicBlock* GetBasicBlockAt(Offset offset) const;
151 :
152 : // Traverses the basic-block subgraph and computes the reachability of all
153 : // basic-blocks starting from the entry-point.
154 : void GetReachabilityMap(ReachabilityMap* rm) const;
155 :
156 : // A helper function for querying a reachabilty map.
157 : static bool IsReachable(const ReachabilityMap& rm, const BasicBlock* bb);
158 :
159 : protected:
160 : // @name Validation Functions.
161 : // @{
162 : bool MapsBasicBlocksToAtMostOneDescription() const;
163 : bool HasValidSuccessors() const;
164 : bool HasValidReferrers() const;
165 : // @}
166 :
167 : // The original block corresponding from which this sub-graph derives. This
168 : // is optional, and may be NULL.
169 : const Block* original_block_;
170 :
171 : // The set of basic blocks in this sub-graph. This includes any basic-blocks
172 : // created during the initial decomposition process, as well as any additional
173 : // basic-blocks synthesized thereafter.
174 : BBCollection basic_blocks_;
175 :
176 : // The breakdown and layout of the original block into basic blocks. This
177 : // may reference only a subset of the blocks in basic_blocks_;
178 : // TODO(rogerm): Move this to the BasicBlockDecomposer.
179 : BBAddressSpace original_address_space_;
180 :
181 : // A list of block descriptions for the blocks that are to be created from
182 : // this basic block sub-graph.
183 : BlockDescriptionList block_descriptions_;
184 :
185 : // An counter used to assign IDs to basic blocks as they are constructed.
186 : int next_basic_block_id_;
187 : };
188 :
189 : } // namespace block_graph
190 :
191 : #endif // SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_SUBGRAPH_H_
|