2 * CSE - walk the linearized instruction flow, and
3 * see if we can simplify it and apply CSE on it.
5 * Copyright (C) 2004 Linus Torvalds
16 #include "expression.h"
17 #include "linearize.h"
20 #define INSN_HASH_SIZE 65536
21 static struct instruction_list
*insn_hash_table
[INSN_HASH_SIZE
];
25 static int phi_compare(pseudo_t phi1
, pseudo_t phi2
)
27 const struct instruction
*def1
= phi1
->def
;
28 const struct instruction
*def2
= phi2
->def
;
30 if (def1
->src1
!= def2
->src1
)
31 return def1
->src1
< def2
->src1
? -1 : 1;
32 if (def1
->bb
!= def2
->bb
)
33 return def1
->bb
< def2
->bb
? -1 : 1;
38 static void clean_up_one_instruction(struct basic_block
*bb
, struct instruction
*insn
)
44 assert(insn
->bb
== bb
);
45 repeat_phase
|= simplify_instruction(insn
);
46 hash
= (insn
->opcode
<< 3) + (insn
->size
>> 3);
47 switch (insn
->opcode
) {
49 hash
+= hashval(insn
->src3
);
52 /* Binary arithmetic */
53 case OP_ADD
: case OP_SUB
:
54 case OP_MULU
: case OP_MULS
:
55 case OP_DIVU
: case OP_DIVS
:
56 case OP_MODU
: case OP_MODS
:
58 case OP_LSR
: case OP_ASR
:
59 case OP_AND
: case OP_OR
:
62 case OP_XOR
: case OP_AND_BOOL
:
65 /* Binary comparison */
66 case OP_SET_EQ
: case OP_SET_NE
:
67 case OP_SET_LE
: case OP_SET_GE
:
68 case OP_SET_LT
: case OP_SET_GT
:
69 case OP_SET_B
: case OP_SET_A
:
70 case OP_SET_BE
: case OP_SET_AE
:
71 hash
+= hashval(insn
->src2
);
75 case OP_NOT
: case OP_NEG
:
76 hash
+= hashval(insn
->src1
);
80 hash
+= hashval(insn
->val
);
84 hash
+= hashval(insn
->symbol
);
90 FOR_EACH_PTR(insn
->phi_list
, phi
) {
91 struct instruction
*def
;
92 if (phi
== VOID
|| !phi
->def
)
95 hash
+= hashval(def
->src1
);
96 hash
+= hashval(def
->bb
);
97 } END_FOR_EACH_PTR(phi
);
103 * Nothing to do, don't even bother hashing them,
104 * we're not going to try to CSE them
109 hash
&= INSN_HASH_SIZE
-1;
110 add_instruction(insn_hash_table
+ hash
, insn
);
113 static void clean_up_insns(struct entrypoint
*ep
)
115 struct basic_block
*bb
;
117 FOR_EACH_PTR(ep
->bbs
, bb
) {
118 struct instruction
*insn
;
119 FOR_EACH_PTR(bb
->insns
, insn
) {
120 clean_up_one_instruction(bb
, insn
);
121 } END_FOR_EACH_PTR(insn
);
122 } END_FOR_EACH_PTR(bb
);
125 /* Compare two (sorted) phi-lists */
126 static int phi_list_compare(struct pseudo_list
*l1
, struct pseudo_list
*l2
)
130 PREPARE_PTR_LIST(l1
, phi1
);
131 PREPARE_PTR_LIST(l2
, phi2
);
135 while (phi1
&& (phi1
== VOID
|| !phi1
->def
))
137 while (phi2
&& (phi2
== VOID
|| !phi2
->def
))
141 return phi2
? -1 : 0;
144 cmp
= phi_compare(phi1
, phi2
);
150 /* Not reached, but we need to make the nesting come out right */
151 FINISH_PTR_LIST(phi2
);
152 FINISH_PTR_LIST(phi1
);
155 static int insn_compare(const void *_i1
, const void *_i2
)
157 const struct instruction
*i1
= _i1
;
158 const struct instruction
*i2
= _i2
;
160 if (i1
->opcode
!= i2
->opcode
)
161 return i1
->opcode
< i2
->opcode
? -1 : 1;
163 switch (i1
->opcode
) {
165 if (i1
->src3
!= i2
->src3
)
166 return i1
->src3
< i2
->src3
? -1 : 1;
167 /* Fall-through to binops */
169 /* Binary arithmetic */
170 case OP_ADD
: case OP_SUB
:
171 case OP_MULU
: case OP_MULS
:
172 case OP_DIVU
: case OP_DIVS
:
173 case OP_MODU
: case OP_MODS
:
175 case OP_LSR
: case OP_ASR
:
176 case OP_AND
: case OP_OR
:
179 case OP_XOR
: case OP_AND_BOOL
:
182 /* Binary comparison */
183 case OP_SET_EQ
: case OP_SET_NE
:
184 case OP_SET_LE
: case OP_SET_GE
:
185 case OP_SET_LT
: case OP_SET_GT
:
186 case OP_SET_B
: case OP_SET_A
:
187 case OP_SET_BE
: case OP_SET_AE
:
188 if (i1
->src2
!= i2
->src2
)
189 return i1
->src2
< i2
->src2
? -1 : 1;
190 /* Fall-through to unops */
193 case OP_NOT
: case OP_NEG
:
194 if (i1
->src1
!= i2
->src1
)
195 return i1
->src1
< i2
->src1
? -1 : 1;
199 if (i1
->symbol
!= i2
->symbol
)
200 return i1
->symbol
< i2
->symbol
? -1 : 1;
204 if (i1
->val
!= i2
->val
)
205 return i1
->val
< i2
->val
? -1 : 1;
210 return phi_list_compare(i1
->phi_list
, i2
->phi_list
);
213 warning(i1
->pos
, "bad instruction on hash chain");
215 if (i1
->size
!= i2
->size
)
216 return i1
->size
< i2
->size
? -1 : 1;
220 static void sort_instruction_list(struct instruction_list
**list
)
222 sort_list((struct ptr_list
**)list
, insn_compare
);
225 static struct instruction
* cse_one_instruction(struct instruction
*insn
, struct instruction
*def
)
227 convert_instruction_target(insn
, def
->target
);
228 insn
->opcode
= OP_NOP
;
230 repeat_phase
|= REPEAT_CSE
;
235 * Does "bb1" dominate "bb2"?
237 static int bb_dominates(struct entrypoint
*ep
, struct basic_block
*bb1
, struct basic_block
*bb2
, unsigned long generation
)
239 struct basic_block
*parent
;
241 /* Nothing dominates the entrypoint.. */
242 if (bb2
== ep
->entry
->bb
)
244 FOR_EACH_PTR(bb2
->parents
, parent
) {
247 if (parent
->generation
== generation
)
249 parent
->generation
= generation
;
250 if (!bb_dominates(ep
, bb1
, parent
, generation
))
252 } END_FOR_EACH_PTR(parent
);
256 static struct basic_block
*trivial_common_parent(struct basic_block
*bb1
, struct basic_block
*bb2
)
258 struct basic_block
*parent
;
260 if (bb_list_size(bb1
->parents
) != 1)
262 parent
= first_basic_block(bb1
->parents
);
263 if (bb_list_size(bb2
->parents
) != 1)
265 if (first_basic_block(bb2
->parents
) != parent
)
270 static inline void remove_instruction(struct instruction_list
**list
, struct instruction
*insn
, int count
)
272 delete_ptr_list_entry((struct ptr_list
**)list
, insn
, count
);
275 static void add_instruction_to_end(struct instruction
*insn
, struct basic_block
*bb
)
277 struct instruction
*br
= delete_last_instruction(&bb
->insns
);
279 add_instruction(&bb
->insns
, insn
);
280 add_instruction(&bb
->insns
, br
);
283 static struct instruction
* try_to_cse(struct entrypoint
*ep
, struct instruction
*i1
, struct instruction
*i2
)
285 struct basic_block
*b1
, *b2
, *common
;
288 * Ok, i1 and i2 are the same instruction, modulo "target".
289 * We should now see if we can combine them.
295 * PHI-nodes do not care where they are - the only thing that matters
296 * are the PHI _sources_.
298 if (i1
->opcode
== OP_PHI
)
299 return cse_one_instruction(i1
, i2
);
302 * Currently we only handle the uninteresting degenerate case where
303 * the CSE is inside one basic-block.
306 struct instruction
*insn
;
307 FOR_EACH_PTR(b1
->insns
, insn
) {
309 return cse_one_instruction(i2
, i1
);
311 return cse_one_instruction(i1
, i2
);
312 } END_FOR_EACH_PTR(insn
);
313 warning(b1
->pos
, "Whaa? unable to find CSE instructions");
316 if (bb_dominates(ep
, b1
, b2
, ++bb_generation
))
317 return cse_one_instruction(i2
, i1
);
319 if (bb_dominates(ep
, b2
, b1
, ++bb_generation
))
320 return cse_one_instruction(i1
, i2
);
322 /* No direct dominance - but we could try to find a common ancestor.. */
323 common
= trivial_common_parent(b1
, b2
);
325 i1
= cse_one_instruction(i2
, i1
);
326 remove_instruction(&b1
->insns
, i1
, 1);
327 add_instruction_to_end(i1
, common
);
333 void cleanup_and_cse(struct entrypoint
*ep
)
341 for (i
= 0; i
< INSN_HASH_SIZE
; i
++) {
342 struct instruction_list
**list
= insn_hash_table
+ i
;
344 if (instruction_list_size(*list
) > 1) {
345 struct instruction
*insn
, *last
;
347 sort_instruction_list(list
);
350 FOR_EACH_PTR(*list
, insn
) {
354 if (!insn_compare(last
, insn
))
355 insn
= try_to_cse(ep
, last
, insn
);
358 } END_FOR_EACH_PTR(insn
);
360 free_ptr_list((struct ptr_list
**)list
);
364 if (repeat_phase
& REPEAT_SYMBOL_CLEANUP
)
367 if (repeat_phase
& REPEAT_CSE
)