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 : #include "syzygy/block_graph/analysis/liveness_analysis.h"
19 : #include "syzygy/block_graph/analysis/liveness_analysis_internal.h"
20 :
21 : namespace optimize {
22 : namespace transforms {
23 :
24 : namespace {
25 :
26 : using block_graph::BasicBlock;
27 : using block_graph::BasicBlockSubGraph;
28 : using block_graph::BasicCodeBlock;
29 : using block_graph::Instruction;
30 : using block_graph::analysis::LivenessAnalysis;
31 :
32 : typedef BasicBlockSubGraph::BBCollection BBCollection;
33 : typedef BasicBlock::Instructions Instructions;
34 :
35 : // Match a sequence of three instructions and return them into |instr1|,
36 : // |instr2| and |instr3|.
37 : bool MatchThreeInstructions(const Instructions& instructions,
38 : Instructions::iterator where,
39 : Instruction** instr1,
40 : Instruction** instr2,
41 E : Instruction** instr3) {
42 E : if (where == instructions.end())
43 i : return false;
44 E : *instr1 = &*where;
45 E : where++;
46 :
47 E : if (where == instructions.end())
48 E : return false;
49 E : *instr2 = &*where;
50 E : where++;
51 :
52 E : if (where == instructions.end())
53 E : return false;
54 E : *instr3 = &*where;
55 :
56 E : return true;
57 E : }
58 :
59 : // Validate that a given instruction has opcode |opcode| and |reg| as its
60 : // register operand.
61 : bool MatchInstructionReg(const Instruction& instr,
62 : _InstructionType opcode,
63 E : _RegisterType reg) {
64 E : const _DInst& repr = instr.representation();
65 : if (repr.opcode == opcode &&
66 : repr.ops[0].type == O_REG &&
67 E : repr.ops[0].index == reg) {
68 E : return true;
69 : }
70 :
71 E : return false;
72 E : }
73 :
74 : // Validate that a given instruction has opcode |opcode| and both |reg1| and
75 : // |reg2| as its register operands.
76 : bool MatchInstructionRegReg(const Instruction& instr,
77 : _InstructionType opcode,
78 : _RegisterType reg1,
79 E : _RegisterType reg2) {
80 E : const _DInst& repr = instr.representation();
81 : if (repr.opcode == opcode &&
82 : repr.ops[0].type == O_REG &&
83 : repr.ops[0].index == reg1 &&
84 : repr.ops[1].type == O_REG &&
85 E : repr.ops[1].index == reg2) {
86 E : return true;
87 : }
88 :
89 i : return false;
90 E : }
91 :
92 : // Validate that a given instruction has opcode |opcode| and both |reg1| and
93 : // |reg2| are register operands.
94 : // @param instr the instruction to match.
95 : // @param opcode the expected opcode.
96 : // @param reg1 receives the first register.
97 : // @param reg2 receives the second register.
98 : // @returns true on a successful match, false otherwise.
99 : bool MatchInstructionRegReg(const Instruction& instr,
100 : _InstructionType opcode,
101 : _RegisterType* reg1,
102 E : _RegisterType* reg2) {
103 E : const _DInst& repr = instr.representation();
104 : if (repr.opcode == opcode &&
105 : repr.ops[0].type == O_REG &&
106 E : repr.ops[1].type == O_REG) {
107 E : *reg1 = static_cast<_RegisterType>(repr.ops[0].index);
108 E : *reg2 = static_cast<_RegisterType>(repr.ops[1].index);
109 E : return true;
110 : }
111 :
112 E : return false;
113 E : }
114 :
115 : bool SimplifyEmptyPrologEpilog(Instructions* instructions,
116 E : Instructions::iterator* where) {
117 E : DCHECK_NE(reinterpret_cast<Instructions*>(NULL), instructions);
118 E : DCHECK_NE(reinterpret_cast<Instructions::iterator*>(NULL), where);
119 :
120 E : Instruction* instr1 = NULL;
121 E : Instruction* instr2 = NULL;
122 E : Instruction* instr3 = NULL;
123 : if (MatchThreeInstructions(*instructions, *where, &instr1,
124 : &instr2, &instr3) &&
125 : MatchInstructionReg(*instr1, I_PUSH, R_EBP) &&
126 : MatchInstructionRegReg(*instr2, I_MOV, R_EBP, R_ESP) &&
127 E : MatchInstructionReg(*instr3, I_POP, R_EBP)) {
128 : // Remove the three matched instructions.
129 E : for (int i = 0; i < 3; ++i)
130 E : *where = instructions->erase(*where);
131 E : return true;
132 : }
133 :
134 E : return false;
135 E : }
136 :
137 : // Remove identity pattern like: mov eax, eax.
138 : bool SimplifyIdentityMov(Instructions* instructions,
139 E : Instructions::iterator* where) {
140 E : DCHECK_NE(reinterpret_cast<Instructions*>(NULL), instructions);
141 E : DCHECK_NE(reinterpret_cast<Instructions::iterator*>(NULL), where);
142 :
143 E : const Instruction& instr = **where;
144 E : _RegisterType reg1 = _RegisterType();
145 E : _RegisterType reg2 = _RegisterType();
146 : if (MatchInstructionRegReg(instr, I_MOV, ®1, ®2) &&
147 E : reg1 == reg2) {
148 : // Remove the matched instruction.
149 E : *where = instructions->erase(*where);
150 E : return true;
151 : }
152 :
153 E : return false;
154 E : }
155 :
156 : // Simplify a given basic block.
157 E : bool SimplifyBasicBlock(BasicBlock* basic_block) {
158 E : DCHECK_NE(reinterpret_cast<BasicBlock*>(NULL), basic_block);
159 :
160 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(basic_block);
161 E : if (bb == NULL)
162 E : return false;
163 :
164 E : bool changed = false;
165 :
166 : // Match and rewrite based on patterns.
167 E : BasicBlock::Instructions::iterator inst_iter = bb->instructions().begin();
168 E : while (inst_iter != bb->instructions().end()) {
169 : if (SimplifyEmptyPrologEpilog(&bb->instructions(), &inst_iter) ||
170 E : SimplifyIdentityMov(&bb->instructions(), &inst_iter)) {
171 E : changed = true;
172 E : continue;
173 : }
174 :
175 : // Move to the next instruction.
176 E : ++inst_iter;
177 E : }
178 :
179 E : return changed;
180 E : }
181 :
182 : } // namespace
183 :
184 : // Simplify a given subgraph.
185 E : bool PeepholeTransform::SimplifySubgraph(BasicBlockSubGraph* subgraph) {
186 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
187 :
188 E : bool changed = false;
189 E : BBCollection& basic_blocks = subgraph->basic_blocks();
190 E : BBCollection::iterator it = basic_blocks.begin();
191 E : for (; it != basic_blocks.end(); ++it) {
192 E : if (SimplifyBasicBlock(*it))
193 E : changed = true;
194 E : }
195 :
196 E : return changed;
197 E : }
198 :
199 E : bool PeepholeTransform::RemoveDeadCodeSubgraph(BasicBlockSubGraph* subgraph) {
200 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
201 :
202 E : bool changed = false;
203 E : BBCollection& basic_blocks = subgraph->basic_blocks();
204 E : BBCollection::iterator it = basic_blocks.begin();
205 :
206 : // Perform a global liveness analysis.
207 E : LivenessAnalysis liveness;
208 E : liveness.Analyze(subgraph);
209 :
210 : // For each basic block, remove dead instructions.
211 E : for (; it != basic_blocks.end(); ++it) {
212 E : BasicCodeBlock* basic_block = BasicCodeBlock::Cast(*it);
213 E : if (basic_block == NULL)
214 E : continue;
215 :
216 : // Get the liveness state information at the end of this basic block.
217 E : LivenessAnalysis::State state;
218 E : liveness.GetStateAtExitOf(basic_block, &state);
219 :
220 : // Perform a backward traversal to cleanup the code.
221 : Instructions::reverse_iterator rev_iter_inst =
222 E : basic_block->instructions().rbegin();
223 E : while (rev_iter_inst != basic_block->instructions().rend()) {
224 E : const Instruction& instr = *rev_iter_inst;
225 :
226 : // Move to the previous instruction for next iteration.
227 E : ++rev_iter_inst;
228 :
229 : // Determine whether this instruction has side-effects.
230 E : bool has_side_effects = false;
231 :
232 E : LivenessAnalysis::State defs;
233 E : if (!LivenessAnalysis::StateHelper::GetDefsOf(instr, &defs))
234 i : has_side_effects = true;
235 :
236 E : LivenessAnalysis::State uses;
237 E : if (!LivenessAnalysis::StateHelper::GetUsesOf(instr, &uses))
238 i : has_side_effects = true;
239 :
240 : // Determine whether this instruction may modify a register used later.
241 E : uint32 id = assm::kRegisterMin;
242 E : for (; id < assm::kRegisterMax; ++id) {
243 E : assm::RegisterId reg_id = static_cast<assm::RegisterId>(id);
244 E : const assm::Register& reg = assm::Register::Get(reg_id);
245 E : if (defs.IsLive(reg) && state.IsLive(reg)) {
246 E : has_side_effects = true;
247 E : break;
248 : }
249 E : }
250 :
251 E : if (defs.AreArithmeticFlagsLive() && state.AreArithmeticFlagsLive())
252 E : has_side_effects = true;
253 :
254 : // Avoid stack manipulation.
255 : if (defs.IsLive(assm::ebp) ||
256 : defs.IsLive(assm::esp) ||
257 : uses.IsLive(assm::ebp) ||
258 E : defs.IsLive(assm::esp)) {
259 E : has_side_effects = true;
260 : }
261 :
262 : // Assume control-flow instructions have side-effects.
263 E : if (instr.IsCall() || instr.IsReturn() || instr.IsControlFlow())
264 E : has_side_effects = true;
265 :
266 : // Only consider general purpose registers.
267 E : const _DInst& repr = instr.representation();
268 E : const _Operand& op = repr.ops[0];
269 : if (op.type != O_REG ||
270 : op.index < R_EAX ||
271 E : op.index > R_EDI) {
272 E : has_side_effects = true;
273 : }
274 :
275 : // Only consider these instructions as valid candidate.
276 E : if (!has_side_effects) {
277 E : switch (repr.opcode) {
278 : case I_ADD:
279 : case I_CMP:
280 : case I_SUB:
281 : case I_AND:
282 : case I_OR:
283 : case I_XOR:
284 : case I_INC:
285 : case I_DEC:
286 : case I_SAR:
287 : case I_SHR:
288 : case I_SHL:
289 : case I_LEA:
290 : case I_MOV:
291 E : break;
292 : default:
293 i : has_side_effects = true;
294 : break;
295 : }
296 : }
297 :
298 : // If this instruction does not have side effects, remove it.
299 E : if (!has_side_effects) {
300 E : Instructions::const_iterator it = rev_iter_inst.base();
301 : rev_iter_inst = Instructions::reverse_iterator(
302 E : basic_block->instructions().erase(it));
303 E : changed = true;
304 :
305 : // Do not propagate liveness backward.
306 E : continue;
307 : }
308 :
309 : // Propagate the liveness information for the next instruction.
310 E : liveness.PropagateBackward(instr, &state);
311 E : }
312 E : }
313 :
314 E : return changed;
315 E : }
316 :
317 : bool PeepholeTransform::TransformBasicBlockSubGraph(
318 : const TransformPolicyInterface* policy,
319 : BlockGraph* block_graph,
320 : BasicBlockSubGraph* subgraph,
321 : ApplicationProfile* profile,
322 E : SubGraphProfile* subgraph_profile) {
323 E : DCHECK_NE(reinterpret_cast<TransformPolicyInterface*>(NULL), policy);
324 E : DCHECK_NE(reinterpret_cast<BlockGraph*>(NULL), block_graph);
325 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
326 E : DCHECK_NE(reinterpret_cast<ApplicationProfile*>(NULL), profile);
327 E : DCHECK_NE(reinterpret_cast<SubGraphProfile*>(NULL), subgraph_profile);
328 :
329 E : bool changed = false;
330 : do {
331 E : changed = false;
332 :
333 E : if (SimplifySubgraph(subgraph))
334 E : changed = true;
335 E : if (RemoveDeadCodeSubgraph(subgraph))
336 E : changed = true;
337 E : } while (changed);
338 :
339 E : return true;
340 E : }
341 :
342 : } // namespace transforms
343 : } // namespace optimize
|