1 : // Copyright 2013 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 : #include "syzygy/optimize/transforms/peephole_transform.h"
16 :
17 : #include "syzygy/block_graph/block_graph.h"
18 :
19 : namespace optimize {
20 : namespace transforms {
21 :
22 : namespace {
23 :
24 : using block_graph::BasicBlock;
25 : using block_graph::BasicBlockSubGraph;
26 : using block_graph::BasicCodeBlock;
27 : using block_graph::Instruction;
28 : typedef BasicBlockSubGraph::BBCollection BBCollection;
29 : typedef BasicBlock::Instructions Instructions;
30 :
31 : // Match a sequence of three instructions and return them into |instr1|,
32 : // |instr2| and |instr3|.
33 : bool MatchThreeInstructions(const Instructions& instructions,
34 : Instructions::iterator where,
35 : Instruction** instr1,
36 : Instruction** instr2,
37 E : Instruction** instr3) {
38 E : if (where == instructions.end())
39 i : return false;
40 E : *instr1 = &*where;
41 E : where++;
42 :
43 E : if (where == instructions.end())
44 E : return false;
45 E : *instr2 = &*where;
46 E : where++;
47 :
48 E : if (where == instructions.end())
49 E : return false;
50 E : *instr3 = &*where;
51 :
52 E : return true;
53 E : }
54 :
55 : // Validate that a given instruction has opcode |opcode| and |reg| as its
56 : // register operand.
57 : bool MatchInstruction1(const Instruction& instr,
58 : _InstructionType opcode,
59 E : _RegisterType reg) {
60 E : const _DInst& repr = instr.representation();
61 : if (repr.opcode == opcode &&
62 : repr.ops[0].type == O_REG &&
63 E : repr.ops[0].index == reg) {
64 E : return true;
65 : }
66 :
67 E : return false;
68 E : }
69 :
70 : // Validate that a given instruction has opcode |opcode| and both |reg1| and
71 : // |reg2| as its register operands.
72 : bool MatchInstruction2(const Instruction& instr,
73 : _InstructionType opcode,
74 : _RegisterType reg1,
75 E : _RegisterType reg2) {
76 E : const _DInst& repr = instr.representation();
77 : if (repr.opcode == opcode &&
78 : repr.ops[0].type == O_REG &&
79 : repr.ops[0].index == reg1 &&
80 : repr.ops[1].type == O_REG &&
81 E : repr.ops[1].index == reg2) {
82 E : return true;
83 : }
84 :
85 i : return false;
86 E : }
87 :
88 : bool SimplifyEmptyPrologEpilog(Instructions* instructions,
89 E : Instructions::iterator* where) {
90 E : DCHECK_NE(reinterpret_cast<Instructions*>(NULL), instructions);
91 E : DCHECK_NE(reinterpret_cast<Instructions::iterator*>(NULL), where);
92 :
93 E : Instruction* instr1 = NULL;
94 E : Instruction* instr2 = NULL;
95 E : Instruction* instr3 = NULL;
96 : if (MatchThreeInstructions(*instructions, *where, &instr1,
97 : &instr2, &instr3) &&
98 : MatchInstruction1(*instr1, I_PUSH, R_EBP) &&
99 : MatchInstruction2(*instr2, I_MOV, R_EBP, R_ESP) &&
100 E : MatchInstruction1(*instr3, I_POP, R_EBP)) {
101 : // Remove the three matched instructions.
102 E : for (int i = 0; i < 3; ++i)
103 E : *where = instructions->erase(*where);
104 E : return true;
105 : }
106 :
107 E : return false;
108 E : }
109 :
110 : // Simplify a given basic block.
111 E : bool SimplifyBasicBlock(BasicBlock* basic_block) {
112 E : DCHECK_NE(reinterpret_cast<BasicBlock*>(NULL), basic_block);
113 :
114 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(basic_block);
115 E : if (bb == NULL)
116 i : return false;
117 :
118 E : bool changed = false;
119 :
120 : // Match and rewrite based on patterns.
121 E : BasicBlock::Instructions::iterator inst_iter = bb->instructions().begin();
122 E : while (inst_iter != bb->instructions().end()) {
123 E : if (SimplifyEmptyPrologEpilog(&bb->instructions(), &inst_iter)) {
124 E : changed = true;
125 E : continue;
126 : }
127 :
128 : // Move to the next instruction.
129 E : ++inst_iter;
130 E : }
131 :
132 E : return changed;
133 E : }
134 :
135 : } // namespace
136 :
137 : // Simplify a given subgraph.
138 E : bool PeepholeTransform::SimplifySubgraph(BasicBlockSubGraph* subgraph) {
139 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
140 :
141 E : bool changed = false;
142 E : BBCollection& basic_blocks = subgraph->basic_blocks();
143 E : BBCollection::iterator it = basic_blocks.begin();
144 E : for (; it != basic_blocks.end(); ++it) {
145 E : if (SimplifyBasicBlock(*it))
146 E : changed = true;
147 E : }
148 :
149 E : return changed;
150 E : }
151 :
152 : bool PeepholeTransform::TransformBasicBlockSubGraph(
153 : const TransformPolicyInterface* policy,
154 : BlockGraph* block_graph,
155 : BasicBlockSubGraph* subgraph,
156 : ApplicationProfile* profile,
157 E : SubGraphProfile* subgraph_profile) {
158 E : DCHECK_NE(reinterpret_cast<TransformPolicyInterface*>(NULL), policy);
159 E : DCHECK_NE(reinterpret_cast<BlockGraph*>(NULL), block_graph);
160 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
161 E : DCHECK_NE(reinterpret_cast<ApplicationProfile*>(NULL), profile);
162 E : DCHECK_NE(reinterpret_cast<SubGraphProfile*>(NULL), subgraph_profile);
163 :
164 E : bool changed = false;
165 : do {
166 E : changed = SimplifySubgraph(subgraph);
167 : // TODO(etienneb): Add more peephole passes.
168 E : } while (changed);
169 :
170 E : return true;
171 E : }
172 :
173 : } // namespace transforms
174 : } // namespace optimize
|