11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * CSE - walk the linearized instruction flow, and
31f5207b7SJohn Levon * see if we can simplify it and apply CSE on it.
41f5207b7SJohn Levon *
51f5207b7SJohn Levon * Copyright (C) 2004 Linus Torvalds
61f5207b7SJohn Levon */
71f5207b7SJohn Levon
81f5207b7SJohn Levon #include <string.h>
91f5207b7SJohn Levon #include <stdarg.h>
101f5207b7SJohn Levon #include <stdlib.h>
111f5207b7SJohn Levon #include <stdio.h>
121f5207b7SJohn Levon #include <stddef.h>
131f5207b7SJohn Levon #include <assert.h>
141f5207b7SJohn Levon
151f5207b7SJohn Levon #include "parse.h"
161f5207b7SJohn Levon #include "expression.h"
17*c85f09ccSJohn Levon #include "flowgraph.h"
181f5207b7SJohn Levon #include "linearize.h"
191f5207b7SJohn Levon #include "flow.h"
20*c85f09ccSJohn Levon #include "cse.h"
211f5207b7SJohn Levon
221f5207b7SJohn Levon #define INSN_HASH_SIZE 256
231f5207b7SJohn Levon static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
241f5207b7SJohn Levon
phi_compare(pseudo_t phi1,pseudo_t phi2)251f5207b7SJohn Levon static int phi_compare(pseudo_t phi1, pseudo_t phi2)
261f5207b7SJohn Levon {
271f5207b7SJohn Levon const struct instruction *def1 = phi1->def;
281f5207b7SJohn Levon const struct instruction *def2 = phi2->def;
291f5207b7SJohn Levon
301f5207b7SJohn Levon if (def1->src1 != def2->src1)
311f5207b7SJohn Levon return def1->src1 < def2->src1 ? -1 : 1;
321f5207b7SJohn Levon if (def1->bb != def2->bb)
331f5207b7SJohn Levon return def1->bb < def2->bb ? -1 : 1;
341f5207b7SJohn Levon return 0;
351f5207b7SJohn Levon }
361f5207b7SJohn Levon
371f5207b7SJohn Levon
cse_collect(struct instruction * insn)38*c85f09ccSJohn Levon void cse_collect(struct instruction *insn)
391f5207b7SJohn Levon {
401f5207b7SJohn Levon unsigned long hash;
411f5207b7SJohn Levon
421f5207b7SJohn Levon hash = (insn->opcode << 3) + (insn->size >> 3);
431f5207b7SJohn Levon switch (insn->opcode) {
441f5207b7SJohn Levon case OP_SEL:
451f5207b7SJohn Levon hash += hashval(insn->src3);
461f5207b7SJohn Levon /* Fall through */
471f5207b7SJohn Levon
481f5207b7SJohn Levon /* Binary arithmetic */
491f5207b7SJohn Levon case OP_ADD: case OP_SUB:
50*c85f09ccSJohn Levon case OP_MUL:
511f5207b7SJohn Levon case OP_DIVU: case OP_DIVS:
521f5207b7SJohn Levon case OP_MODU: case OP_MODS:
531f5207b7SJohn Levon case OP_SHL:
541f5207b7SJohn Levon case OP_LSR: case OP_ASR:
551f5207b7SJohn Levon case OP_AND: case OP_OR:
561f5207b7SJohn Levon
571f5207b7SJohn Levon /* Binary logical */
58*c85f09ccSJohn Levon case OP_XOR:
591f5207b7SJohn Levon
601f5207b7SJohn Levon /* Binary comparison */
611f5207b7SJohn Levon case OP_SET_EQ: case OP_SET_NE:
621f5207b7SJohn Levon case OP_SET_LE: case OP_SET_GE:
631f5207b7SJohn Levon case OP_SET_LT: case OP_SET_GT:
641f5207b7SJohn Levon case OP_SET_B: case OP_SET_A:
651f5207b7SJohn Levon case OP_SET_BE: case OP_SET_AE:
66*c85f09ccSJohn Levon
67*c85f09ccSJohn Levon /* floating-point arithmetic & comparison */
68*c85f09ccSJohn Levon case OP_FPCMP ... OP_FPCMP_END:
69*c85f09ccSJohn Levon case OP_FADD:
70*c85f09ccSJohn Levon case OP_FSUB:
71*c85f09ccSJohn Levon case OP_FMUL:
72*c85f09ccSJohn Levon case OP_FDIV:
731f5207b7SJohn Levon hash += hashval(insn->src2);
741f5207b7SJohn Levon /* Fall through */
751f5207b7SJohn Levon
761f5207b7SJohn Levon /* Unary */
771f5207b7SJohn Levon case OP_NOT: case OP_NEG:
78*c85f09ccSJohn Levon case OP_FNEG:
79*c85f09ccSJohn Levon case OP_SYMADDR:
801f5207b7SJohn Levon hash += hashval(insn->src1);
811f5207b7SJohn Levon break;
821f5207b7SJohn Levon
831f5207b7SJohn Levon case OP_SETVAL:
841f5207b7SJohn Levon hash += hashval(insn->val);
851f5207b7SJohn Levon break;
861f5207b7SJohn Levon
87*c85f09ccSJohn Levon case OP_SETFVAL:
88*c85f09ccSJohn Levon hash += hashval(insn->fvalue);
891f5207b7SJohn Levon break;
901f5207b7SJohn Levon
91*c85f09ccSJohn Levon case OP_SEXT: case OP_ZEXT:
92*c85f09ccSJohn Levon case OP_TRUNC:
931f5207b7SJohn Levon case OP_PTRCAST:
94*c85f09ccSJohn Levon case OP_UTPTR: case OP_PTRTU:
95*c85f09ccSJohn Levon if (!insn->orig_type || insn->orig_type->bit_size < 0)
96*c85f09ccSJohn Levon return;
971f5207b7SJohn Levon hash += hashval(insn->src);
98*c85f09ccSJohn Levon
99*c85f09ccSJohn Levon // Note: see corresponding line in insn_compare()
100*c85f09ccSJohn Levon hash += hashval(insn->orig_type->bit_size);
1011f5207b7SJohn Levon break;
1021f5207b7SJohn Levon
1031f5207b7SJohn Levon /* Other */
1041f5207b7SJohn Levon case OP_PHI: {
1051f5207b7SJohn Levon pseudo_t phi;
1061f5207b7SJohn Levon FOR_EACH_PTR(insn->phi_list, phi) {
1071f5207b7SJohn Levon struct instruction *def;
1081f5207b7SJohn Levon if (phi == VOID || !phi->def)
1091f5207b7SJohn Levon continue;
1101f5207b7SJohn Levon def = phi->def;
1111f5207b7SJohn Levon hash += hashval(def->src1);
1121f5207b7SJohn Levon hash += hashval(def->bb);
1131f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
1141f5207b7SJohn Levon break;
1151f5207b7SJohn Levon }
1161f5207b7SJohn Levon
1171f5207b7SJohn Levon default:
1181f5207b7SJohn Levon /*
1191f5207b7SJohn Levon * Nothing to do, don't even bother hashing them,
1201f5207b7SJohn Levon * we're not going to try to CSE them
1211f5207b7SJohn Levon */
1221f5207b7SJohn Levon return;
1231f5207b7SJohn Levon }
1241f5207b7SJohn Levon hash += hash >> 16;
1251f5207b7SJohn Levon hash &= INSN_HASH_SIZE-1;
1261f5207b7SJohn Levon add_instruction(insn_hash_table + hash, insn);
1271f5207b7SJohn Levon }
1281f5207b7SJohn Levon
1291f5207b7SJohn Levon /* Compare two (sorted) phi-lists */
phi_list_compare(struct pseudo_list * l1,struct pseudo_list * l2)1301f5207b7SJohn Levon static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
1311f5207b7SJohn Levon {
1321f5207b7SJohn Levon pseudo_t phi1, phi2;
1331f5207b7SJohn Levon
1341f5207b7SJohn Levon PREPARE_PTR_LIST(l1, phi1);
1351f5207b7SJohn Levon PREPARE_PTR_LIST(l2, phi2);
1361f5207b7SJohn Levon for (;;) {
1371f5207b7SJohn Levon int cmp;
1381f5207b7SJohn Levon
1391f5207b7SJohn Levon while (phi1 && (phi1 == VOID || !phi1->def))
1401f5207b7SJohn Levon NEXT_PTR_LIST(phi1);
1411f5207b7SJohn Levon while (phi2 && (phi2 == VOID || !phi2->def))
1421f5207b7SJohn Levon NEXT_PTR_LIST(phi2);
1431f5207b7SJohn Levon
1441f5207b7SJohn Levon if (!phi1)
1451f5207b7SJohn Levon return phi2 ? -1 : 0;
1461f5207b7SJohn Levon if (!phi2)
1471f5207b7SJohn Levon return phi1 ? 1 : 0;
1481f5207b7SJohn Levon cmp = phi_compare(phi1, phi2);
1491f5207b7SJohn Levon if (cmp)
1501f5207b7SJohn Levon return cmp;
1511f5207b7SJohn Levon NEXT_PTR_LIST(phi1);
1521f5207b7SJohn Levon NEXT_PTR_LIST(phi2);
1531f5207b7SJohn Levon }
1541f5207b7SJohn Levon /* Not reached, but we need to make the nesting come out right */
1551f5207b7SJohn Levon FINISH_PTR_LIST(phi2);
1561f5207b7SJohn Levon FINISH_PTR_LIST(phi1);
1571f5207b7SJohn Levon }
1581f5207b7SJohn Levon
insn_compare(const void * _i1,const void * _i2)1591f5207b7SJohn Levon static int insn_compare(const void *_i1, const void *_i2)
1601f5207b7SJohn Levon {
1611f5207b7SJohn Levon const struct instruction *i1 = _i1;
1621f5207b7SJohn Levon const struct instruction *i2 = _i2;
163*c85f09ccSJohn Levon int size1, size2;
164*c85f09ccSJohn Levon int diff;
1651f5207b7SJohn Levon
1661f5207b7SJohn Levon if (i1->opcode != i2->opcode)
1671f5207b7SJohn Levon return i1->opcode < i2->opcode ? -1 : 1;
1681f5207b7SJohn Levon
1691f5207b7SJohn Levon switch (i1->opcode) {
1701f5207b7SJohn Levon
1711f5207b7SJohn Levon /* commutative binop */
1721f5207b7SJohn Levon case OP_ADD:
173*c85f09ccSJohn Levon case OP_MUL:
1741f5207b7SJohn Levon case OP_AND: case OP_OR:
1751f5207b7SJohn Levon case OP_XOR:
1761f5207b7SJohn Levon case OP_SET_EQ: case OP_SET_NE:
1771f5207b7SJohn Levon if (i1->src1 == i2->src2 && i1->src2 == i2->src1)
1781f5207b7SJohn Levon return 0;
1791f5207b7SJohn Levon goto case_binops;
1801f5207b7SJohn Levon
1811f5207b7SJohn Levon case OP_SEL:
1821f5207b7SJohn Levon if (i1->src3 != i2->src3)
1831f5207b7SJohn Levon return i1->src3 < i2->src3 ? -1 : 1;
1841f5207b7SJohn Levon /* Fall-through to binops */
1851f5207b7SJohn Levon
1861f5207b7SJohn Levon /* Binary arithmetic */
1871f5207b7SJohn Levon case OP_SUB:
1881f5207b7SJohn Levon case OP_DIVU: case OP_DIVS:
1891f5207b7SJohn Levon case OP_MODU: case OP_MODS:
1901f5207b7SJohn Levon case OP_SHL:
1911f5207b7SJohn Levon case OP_LSR: case OP_ASR:
1921f5207b7SJohn Levon
1931f5207b7SJohn Levon /* Binary comparison */
1941f5207b7SJohn Levon case OP_SET_LE: case OP_SET_GE:
1951f5207b7SJohn Levon case OP_SET_LT: case OP_SET_GT:
1961f5207b7SJohn Levon case OP_SET_B: case OP_SET_A:
1971f5207b7SJohn Levon case OP_SET_BE: case OP_SET_AE:
198*c85f09ccSJohn Levon
199*c85f09ccSJohn Levon /* floating-point arithmetic */
200*c85f09ccSJohn Levon case OP_FPCMP ... OP_FPCMP_END:
201*c85f09ccSJohn Levon case OP_FADD:
202*c85f09ccSJohn Levon case OP_FSUB:
203*c85f09ccSJohn Levon case OP_FMUL:
204*c85f09ccSJohn Levon case OP_FDIV:
2051f5207b7SJohn Levon case_binops:
2061f5207b7SJohn Levon if (i1->src2 != i2->src2)
2071f5207b7SJohn Levon return i1->src2 < i2->src2 ? -1 : 1;
2081f5207b7SJohn Levon /* Fall through to unops */
2091f5207b7SJohn Levon
2101f5207b7SJohn Levon /* Unary */
2111f5207b7SJohn Levon case OP_NOT: case OP_NEG:
212*c85f09ccSJohn Levon case OP_FNEG:
213*c85f09ccSJohn Levon case OP_SYMADDR:
2141f5207b7SJohn Levon if (i1->src1 != i2->src1)
2151f5207b7SJohn Levon return i1->src1 < i2->src1 ? -1 : 1;
2161f5207b7SJohn Levon break;
2171f5207b7SJohn Levon
2181f5207b7SJohn Levon case OP_SETVAL:
2191f5207b7SJohn Levon if (i1->val != i2->val)
2201f5207b7SJohn Levon return i1->val < i2->val ? -1 : 1;
2211f5207b7SJohn Levon break;
2221f5207b7SJohn Levon
223*c85f09ccSJohn Levon case OP_SETFVAL:
224*c85f09ccSJohn Levon diff = memcmp(&i1->fvalue, &i2->fvalue, sizeof(i1->fvalue));
225*c85f09ccSJohn Levon if (diff)
226*c85f09ccSJohn Levon return diff;
227*c85f09ccSJohn Levon break;
228*c85f09ccSJohn Levon
2291f5207b7SJohn Levon /* Other */
2301f5207b7SJohn Levon case OP_PHI:
2311f5207b7SJohn Levon return phi_list_compare(i1->phi_list, i2->phi_list);
2321f5207b7SJohn Levon
233*c85f09ccSJohn Levon case OP_SEXT: case OP_ZEXT:
234*c85f09ccSJohn Levon case OP_TRUNC:
2351f5207b7SJohn Levon case OP_PTRCAST:
236*c85f09ccSJohn Levon case OP_UTPTR: case OP_PTRTU:
2371f5207b7SJohn Levon if (i1->src != i2->src)
2381f5207b7SJohn Levon return i1->src < i2->src ? -1 : 1;
239*c85f09ccSJohn Levon
240*c85f09ccSJohn Levon // Note: if it can be guaranted that identical ->src
241*c85f09ccSJohn Levon // implies identical orig_type->bit_size, then this
242*c85f09ccSJohn Levon // test and the hashing of the original size in
243*c85f09ccSJohn Levon // cse_collect() are not needed.
244*c85f09ccSJohn Levon // It must be generaly true but it isn't guaranted (yet).
245*c85f09ccSJohn Levon size1 = i1->orig_type->bit_size;
246*c85f09ccSJohn Levon size2 = i2->orig_type->bit_size;
247*c85f09ccSJohn Levon if (size1 != size2)
248*c85f09ccSJohn Levon return size1 < size2 ? -1 : 1;
2491f5207b7SJohn Levon break;
2501f5207b7SJohn Levon
2511f5207b7SJohn Levon default:
2521f5207b7SJohn Levon warning(i1->pos, "bad instruction on hash chain");
2531f5207b7SJohn Levon }
2541f5207b7SJohn Levon if (i1->size != i2->size)
2551f5207b7SJohn Levon return i1->size < i2->size ? -1 : 1;
2561f5207b7SJohn Levon return 0;
2571f5207b7SJohn Levon }
2581f5207b7SJohn Levon
sort_instruction_list(struct instruction_list ** list)2591f5207b7SJohn Levon static void sort_instruction_list(struct instruction_list **list)
2601f5207b7SJohn Levon {
2611f5207b7SJohn Levon sort_list((struct ptr_list **)list , insn_compare);
2621f5207b7SJohn Levon }
2631f5207b7SJohn Levon
cse_one_instruction(struct instruction * insn,struct instruction * def)2641f5207b7SJohn Levon static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
2651f5207b7SJohn Levon {
2661f5207b7SJohn Levon convert_instruction_target(insn, def->target);
2671f5207b7SJohn Levon
2681f5207b7SJohn Levon kill_instruction(insn);
2691f5207b7SJohn Levon repeat_phase |= REPEAT_CSE;
2701f5207b7SJohn Levon return def;
2711f5207b7SJohn Levon }
2721f5207b7SJohn Levon
trivial_common_parent(struct basic_block * bb1,struct basic_block * bb2)2731f5207b7SJohn Levon static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
2741f5207b7SJohn Levon {
2751f5207b7SJohn Levon struct basic_block *parent;
2761f5207b7SJohn Levon
2771f5207b7SJohn Levon if (bb_list_size(bb1->parents) != 1)
2781f5207b7SJohn Levon return NULL;
2791f5207b7SJohn Levon parent = first_basic_block(bb1->parents);
2801f5207b7SJohn Levon if (bb_list_size(bb2->parents) != 1)
2811f5207b7SJohn Levon return NULL;
2821f5207b7SJohn Levon if (first_basic_block(bb2->parents) != parent)
2831f5207b7SJohn Levon return NULL;
2841f5207b7SJohn Levon return parent;
2851f5207b7SJohn Levon }
2861f5207b7SJohn Levon
remove_instruction(struct instruction_list ** list,struct instruction * insn,int count)2871f5207b7SJohn Levon static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
2881f5207b7SJohn Levon {
2891f5207b7SJohn Levon delete_ptr_list_entry((struct ptr_list **)list, insn, count);
2901f5207b7SJohn Levon }
2911f5207b7SJohn Levon
add_instruction_to_end(struct instruction * insn,struct basic_block * bb)2921f5207b7SJohn Levon static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
2931f5207b7SJohn Levon {
2941f5207b7SJohn Levon struct instruction *br = delete_last_instruction(&bb->insns);
2951f5207b7SJohn Levon insn->bb = bb;
2961f5207b7SJohn Levon add_instruction(&bb->insns, insn);
2971f5207b7SJohn Levon add_instruction(&bb->insns, br);
2981f5207b7SJohn Levon }
2991f5207b7SJohn Levon
try_to_cse(struct entrypoint * ep,struct instruction * i1,struct instruction * i2)3001f5207b7SJohn Levon static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
3011f5207b7SJohn Levon {
3021f5207b7SJohn Levon struct basic_block *b1, *b2, *common;
3031f5207b7SJohn Levon
3041f5207b7SJohn Levon /*
3051f5207b7SJohn Levon * OK, i1 and i2 are the same instruction, modulo "target".
3061f5207b7SJohn Levon * We should now see if we can combine them.
3071f5207b7SJohn Levon */
3081f5207b7SJohn Levon b1 = i1->bb;
3091f5207b7SJohn Levon b2 = i2->bb;
3101f5207b7SJohn Levon
3111f5207b7SJohn Levon /*
3121f5207b7SJohn Levon * Currently we only handle the uninteresting degenerate case where
3131f5207b7SJohn Levon * the CSE is inside one basic-block.
3141f5207b7SJohn Levon */
3151f5207b7SJohn Levon if (b1 == b2) {
3161f5207b7SJohn Levon struct instruction *insn;
3171f5207b7SJohn Levon FOR_EACH_PTR(b1->insns, insn) {
3181f5207b7SJohn Levon if (insn == i1)
3191f5207b7SJohn Levon return cse_one_instruction(i2, i1);
3201f5207b7SJohn Levon if (insn == i2)
3211f5207b7SJohn Levon return cse_one_instruction(i1, i2);
3221f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
3231f5207b7SJohn Levon warning(b1->pos, "Whaa? unable to find CSE instructions");
3241f5207b7SJohn Levon return i1;
3251f5207b7SJohn Levon }
326*c85f09ccSJohn Levon if (domtree_dominates(b1, b2))
3271f5207b7SJohn Levon return cse_one_instruction(i2, i1);
3281f5207b7SJohn Levon
329*c85f09ccSJohn Levon if (domtree_dominates(b2, b1))
3301f5207b7SJohn Levon return cse_one_instruction(i1, i2);
3311f5207b7SJohn Levon
3321f5207b7SJohn Levon /* No direct dominance - but we could try to find a common ancestor.. */
3331f5207b7SJohn Levon common = trivial_common_parent(b1, b2);
3341f5207b7SJohn Levon if (common) {
3351f5207b7SJohn Levon i1 = cse_one_instruction(i2, i1);
3361f5207b7SJohn Levon remove_instruction(&b1->insns, i1, 1);
3371f5207b7SJohn Levon add_instruction_to_end(i1, common);
338*c85f09ccSJohn Levon } else {
339*c85f09ccSJohn Levon i1 = i2;
3401f5207b7SJohn Levon }
3411f5207b7SJohn Levon
3421f5207b7SJohn Levon return i1;
3431f5207b7SJohn Levon }
3441f5207b7SJohn Levon
cse_eliminate(struct entrypoint * ep)345*c85f09ccSJohn Levon void cse_eliminate(struct entrypoint *ep)
3461f5207b7SJohn Levon {
3471f5207b7SJohn Levon int i;
3481f5207b7SJohn Levon
3491f5207b7SJohn Levon for (i = 0; i < INSN_HASH_SIZE; i++) {
3501f5207b7SJohn Levon struct instruction_list **list = insn_hash_table + i;
3511f5207b7SJohn Levon if (*list) {
3521f5207b7SJohn Levon if (instruction_list_size(*list) > 1) {
3531f5207b7SJohn Levon struct instruction *insn, *last;
3541f5207b7SJohn Levon
3551f5207b7SJohn Levon sort_instruction_list(list);
3561f5207b7SJohn Levon
3571f5207b7SJohn Levon last = NULL;
3581f5207b7SJohn Levon FOR_EACH_PTR(*list, insn) {
3591f5207b7SJohn Levon if (!insn->bb)
3601f5207b7SJohn Levon continue;
3611f5207b7SJohn Levon if (last) {
3621f5207b7SJohn Levon if (!insn_compare(last, insn))
3631f5207b7SJohn Levon insn = try_to_cse(ep, last, insn);
3641f5207b7SJohn Levon }
3651f5207b7SJohn Levon last = insn;
3661f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
3671f5207b7SJohn Levon }
368*c85f09ccSJohn Levon free_ptr_list(list);
3691f5207b7SJohn Levon }
3701f5207b7SJohn Levon }
3711f5207b7SJohn Levon }
372