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