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 : #ifndef SYZYGY_REORDER_BASIC_BLOCK_OPTIMIZER_H_
16 : #define SYZYGY_REORDER_BASIC_BLOCK_OPTIMIZER_H_
17 :
18 : #include <string>
19 :
20 : #include "base/strings/string_piece.h"
21 : #include "syzygy/block_graph/basic_block.h"
22 : #include "syzygy/block_graph/basic_block_subgraph.h"
23 : #include "syzygy/block_graph/block_graph.h"
24 : #include "syzygy/grinder/basic_block_util.h"
25 : #include "syzygy/pe/image_layout.h"
26 : #include "syzygy/pe/pe_file.h"
27 : #include "syzygy/pe/pe_transform_policy.h"
28 : #include "syzygy/reorder/reorderer.h"
29 :
30 : namespace reorder {
31 :
32 : // A class to optimize the basic-block placement of a block ordering, given
33 : // basic-block entry count data.
34 : class BasicBlockOptimizer {
35 : public:
36 : typedef grinder::basic_block_util::IndexedFrequencyInformation
37 : IndexedFrequencyInformation;
38 : typedef pe::ImageLayout ImageLayout;
39 : typedef Reorderer::Order Order;
40 :
41 : // A helper class with utility functions used by the optimization functions.
42 : // Exposed as public to facilitate unit-testing.
43 : class BasicBlockOrderer;
44 :
45 : // Constructor.
46 : BasicBlockOptimizer();
47 :
48 : // @returns the name that will be assigned to the cold block section.
49 E : const std::string& cold_section_name() const { return cold_section_name_; }
50 :
51 : // Set the name that will be assigned to the cold block section.
52 E : void set_cold_section_name(const base::StringPiece& value) {
53 E : DCHECK(!value.empty());
54 E : value.CopyToString(&cold_section_name_);
55 E : }
56 :
57 : // Basic-block optimize the given @p order.
58 : bool Optimize(const ImageLayout& image_layout,
59 : const IndexedFrequencyInformation& entry_counts,
60 : Order* order);
61 :
62 : protected:
63 : typedef block_graph::BlockGraph BlockGraph;
64 : typedef block_graph::ConstBlockVector ConstBlockVector;
65 :
66 : // Optimize the layout of all basic-blocks in a block.
67 : static bool OptimizeBlock(const pe::PETransformPolicy& policy,
68 : const BlockGraph::Block* block,
69 : const ImageLayout& image_layout,
70 : const IndexedFrequencyInformation& entry_counts,
71 : Order::BlockSpecVector* warm_block_specs,
72 : Order::BlockSpecVector* cold_block_specs);
73 :
74 : // Optimize the layout of all basic-blocks in a section, as defined by the
75 : // given @p section_spec and the original @p image_layout.
76 : static bool OptimizeSection(const pe::PETransformPolicy& policy,
77 : const ImageLayout& image_layout,
78 : const IndexedFrequencyInformation& entry_counts,
79 : const ConstBlockVector& explicit_blocks,
80 : Order::SectionSpec* orig_section_spec,
81 : Order::BlockSpecVector* warm_block_specs,
82 : Order::BlockSpecVector* cold_block_specs);
83 :
84 : // The name of the (new) section in which to place cold blocks and
85 : // basic-blocks.
86 : std::string cold_section_name_;
87 :
88 : private:
89 : DISALLOW_COPY_AND_ASSIGN(BasicBlockOptimizer);
90 : };
91 :
92 : // A helper class which generates warm and cold basic-block orderings for
93 : // a given basic-block subgraph.
94 : class BasicBlockOptimizer::BasicBlockOrderer {
95 : public:
96 : typedef block_graph::BasicBlock BasicBlock;
97 : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
98 : typedef block_graph::BasicCodeBlock BasicCodeBlock;
99 : typedef block_graph::BasicDataBlock BasicDataBlock;
100 : typedef std::set<const BasicBlock*> BasicBlockSet;
101 : typedef BlockGraph::Offset Offset;
102 : typedef BlockGraph::Size Size;
103 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
104 : typedef grinder::basic_block_util::IndexedFrequencyInformation
105 : IndexedFrequencyInformation;
106 : typedef grinder::basic_block_util::RelativeAddress RelativeAddress;
107 :
108 : BasicBlockOrderer(const BasicBlockSubGraph& subgraph,
109 : const RelativeAddress& addr,
110 : Size size,
111 : const IndexedFrequencyInformation& entry_counts);
112 :
113 : // Get the number of times the block itself was entered. This assumes that
114 : // the entry point of the block is its first basic block.
115 : bool GetBlockEntryCount(EntryCountType* entry_count) const;
116 :
117 : // Generate an ordered list or warm and cold basic blocks. The warm basic-
118 : // blocks are ordered such that branches are straightened for the most common
119 : // successor. The cold basic-blocks are maintained in their original ordering
120 : // in the block.
121 : bool GetBasicBlockOrderings(Order::OffsetVector* warm_basic_blocks,
122 : Order::OffsetVector* cold_basic_blocks) const;
123 :
124 : protected:
125 : // Get the number of times a given code basic-block was entered.
126 : bool GetBasicBlockEntryCount(const BasicCodeBlock* code_bb,
127 : EntryCountType* entry_count) const;
128 :
129 : // Get the warmest not-yet-placed successor to the given code basic-block.
130 : // This may yield a NULL pointer, denoting either no successor, or no not-
131 : // yet-placed successor.
132 : bool GetWarmestSuccessor(const BasicCodeBlock* code_bb,
133 : const BasicBlockSet& placed_bbs,
134 : const BasicBlock** succ_bb) const;
135 :
136 : // Get the collection of the targets referenced from a given jmp instruction
137 : // sorted in order of decreasing entry count (i.e., highest entry count
138 : // first). Note that the sort is stable, targets having the same entry counts
139 : // are returned in the same relative order as originally in the jump table.
140 : bool GetSortedJumpTargets(const block_graph::Instruction& jmp_inst,
141 : std::vector<const BasicCodeBlock*>* targets) const;
142 :
143 : // Add all data basic-blocks referenced from @p code_bb to @p warm_references.
144 : bool AddWarmDataReferences(const BasicCodeBlock* code_bb,
145 : BasicBlockSet* warm_references) const;
146 :
147 : // Recursively add @p data_bb and all data basic-blocks referenced by
148 : // @p data_bb to @p warm references.
149 : void AddRecursiveDataReferences(const BasicDataBlock* data_bb,
150 : BasicBlockSet* warm_references) const;
151 :
152 : protected:
153 : const BasicBlockSubGraph& subgraph_;
154 : const RelativeAddress& addr_;
155 : const Size size_;
156 : const IndexedFrequencyInformation& entry_counts_;
157 :
158 : private:
159 : DISALLOW_COPY_AND_ASSIGN(BasicBlockOrderer);
160 : };
161 :
162 : } // namespace reorder
163 :
164 : #endif // SYZYGY_REORDER_BASIC_BLOCK_OPTIMIZER_H_
|