blob: 2a1574531993c88eb73019f8a32fa22415c32114 [file] [log] [blame]
/*
* CSE - walk the linearized instruction flow, and
* see if we can simplify it and apply CSE on it.
*
* Copyright (C) 2004 Linus Torvalds
*/
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <assert.h>
#include "parse.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"
#define INSN_HASH_SIZE 256
static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
int repeat_phase;
static int phi_compare(pseudo_t phi1, pseudo_t phi2)
{
const struct instruction *def1 = phi1->def;
const struct instruction *def2 = phi2->def;
if (def1->src1 != def2->src1)
return def1->src1 < def2->src1 ? -1 : 1;
if (def1->bb != def2->bb)
return def1->bb < def2->bb ? -1 : 1;
return 0;
}
static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
{
unsigned long hash;
if (!insn->bb)
return;
assert(insn->bb == bb);
repeat_phase |= simplify_instruction(insn);
hash = (insn->opcode << 3) + (insn->size >> 3);
switch (insn->opcode) {
case OP_SEL:
hash += hashval(insn->src3);
/* Fall through */
/* Binary arithmetic */
case OP_ADD: case OP_SUB:
case OP_MULU: case OP_MULS:
case OP_DIVU: case OP_DIVS:
case OP_MODU: case OP_MODS:
case OP_SHL:
case OP_LSR: case OP_ASR:
case OP_AND: case OP_OR:
/* Binary logical */
case OP_XOR: case OP_AND_BOOL:
case OP_OR_BOOL:
/* Binary comparison */
case OP_SET_EQ: case OP_SET_NE:
case OP_SET_LE: case OP_SET_GE:
case OP_SET_LT: case OP_SET_GT:
case OP_SET_B: case OP_SET_A:
case OP_SET_BE: case OP_SET_AE:
hash += hashval(insn->src2);
/* Fall through */
/* Unary */
case OP_NOT: case OP_NEG:
hash += hashval(insn->src1);
break;
case OP_SETVAL:
hash += hashval(insn->val);
break;
case OP_SYMADDR:
hash += hashval(insn->symbol);
break;
case OP_CAST:
case OP_SCAST:
case OP_PTRCAST:
/*
* This is crap! Many "orig_types" are the
* same as far as casts go, we should generate
* some kind of "type hash" that is identical
* for identical casts
*/
hash += hashval(insn->orig_type);
hash += hashval(insn->src);
break;
/* Other */
case OP_PHI: {
pseudo_t phi;
FOR_EACH_PTR(insn->phi_list, phi) {
struct instruction *def;
if (phi == VOID || !phi->def)
continue;
def = phi->def;
hash += hashval(def->src1);
hash += hashval(def->bb);
} END_FOR_EACH_PTR(phi);
break;
}
default:
/*
* Nothing to do, don't even bother hashing them,
* we're not going to try to CSE them
*/
return;
}
hash += hash >> 16;
hash &= INSN_HASH_SIZE-1;
add_instruction(insn_hash_table + hash, insn);
}
static void clean_up_insns(struct entrypoint *ep)
{
struct basic_block *bb;
FOR_EACH_PTR(ep->bbs, bb) {
struct instruction *insn;
FOR_EACH_PTR(bb->insns, insn) {
clean_up_one_instruction(bb, insn);
} END_FOR_EACH_PTR(insn);
} END_FOR_EACH_PTR(bb);
}
/* Compare two (sorted) phi-lists */
static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
{
pseudo_t phi1, phi2;
PREPARE_PTR_LIST(l1, phi1);
PREPARE_PTR_LIST(l2, phi2);
for (;;) {
int cmp;
while (phi1 && (phi1 == VOID || !phi1->def))
NEXT_PTR_LIST(phi1);
while (phi2 && (phi2 == VOID || !phi2->def))
NEXT_PTR_LIST(phi2);
if (!phi1)
return phi2 ? -1 : 0;
if (!phi2)
return phi1 ? 1 : 0;
cmp = phi_compare(phi1, phi2);
if (cmp)
return cmp;
NEXT_PTR_LIST(phi1);
NEXT_PTR_LIST(phi2);
}
/* Not reached, but we need to make the nesting come out right */
FINISH_PTR_LIST(phi2);
FINISH_PTR_LIST(phi1);
}
static int insn_compare(const void *_i1, const void *_i2)
{
const struct instruction *i1 = _i1;
const struct instruction *i2 = _i2;
if (i1->opcode != i2->opcode)
return i1->opcode < i2->opcode ? -1 : 1;
switch (i1->opcode) {
case OP_SEL:
if (i1->src3 != i2->src3)
return i1->src3 < i2->src3 ? -1 : 1;
/* Fall-through to binops */
/* Binary arithmetic */
case OP_ADD: case OP_SUB:
case OP_MULU: case OP_MULS:
case OP_DIVU: case OP_DIVS:
case OP_MODU: case OP_MODS:
case OP_SHL:
case OP_LSR: case OP_ASR:
case OP_AND: case OP_OR:
/* Binary logical */
case OP_XOR: case OP_AND_BOOL:
case OP_OR_BOOL:
/* Binary comparison */
case OP_SET_EQ: case OP_SET_NE:
case OP_SET_LE: case OP_SET_GE:
case OP_SET_LT: case OP_SET_GT:
case OP_SET_B: case OP_SET_A:
case OP_SET_BE: case OP_SET_AE:
if (i1->src2 != i2->src2)
return i1->src2 < i2->src2 ? -1 : 1;
/* Fall through to unops */
/* Unary */
case OP_NOT: case OP_NEG:
if (i1->src1 != i2->src1)
return i1->src1 < i2->src1 ? -1 : 1;
break;
case OP_SYMADDR:
if (i1->symbol != i2->symbol)
return i1->symbol < i2->symbol ? -1 : 1;
break;
case OP_SETVAL:
if (i1->val != i2->val)
return i1->val < i2->val ? -1 : 1;
break;
/* Other */
case OP_PHI:
return phi_list_compare(i1->phi_list, i2->phi_list);
case OP_CAST:
case OP_SCAST:
case OP_PTRCAST:
/*
* This is crap! See the comments on hashing.
*/
if (i1->orig_type != i2->orig_type)
return i1->orig_type < i2->orig_type ? -1 : 1;
if (i1->src != i2->src)
return i1->src < i2->src ? -1 : 1;
break;
default:
warning(i1->pos, "bad instruction on hash chain");
}
if (i1->size != i2->size)
return i1->size < i2->size ? -1 : 1;
return 0;
}
static void sort_instruction_list(struct instruction_list **list)
{
sort_list((struct ptr_list **)list , insn_compare);
}
static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
{
convert_instruction_target(insn, def->target);
insn->opcode = OP_NOP;
insn->bb = NULL;
repeat_phase |= REPEAT_CSE;
return def;
}
/*
* Does "bb1" dominate "bb2"?
*/
static int bb_dominates(struct entrypoint *ep, struct basic_block *bb1, struct basic_block *bb2, unsigned long generation)
{
struct basic_block *parent;
/* Nothing dominates the entrypoint.. */
if (bb2 == ep->entry->bb)
return 0;
FOR_EACH_PTR(bb2->parents, parent) {
if (parent == bb1)
continue;
if (parent->generation == generation)
continue;
parent->generation = generation;
if (!bb_dominates(ep, bb1, parent, generation))
return 0;
} END_FOR_EACH_PTR(parent);
return 1;
}
static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
{
struct basic_block *parent;
if (bb_list_size(bb1->parents) != 1)
return NULL;
parent = first_basic_block(bb1->parents);
if (bb_list_size(bb2->parents) != 1)
return NULL;
if (first_basic_block(bb2->parents) != parent)
return NULL;
return parent;
}
static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
{
delete_ptr_list_entry((struct ptr_list **)list, insn, count);
}
static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
{
struct instruction *br = delete_last_instruction(&bb->insns);
insn->bb = bb;
add_instruction(&bb->insns, insn);
add_instruction(&bb->insns, br);
}
static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
{
struct basic_block *b1, *b2, *common;
/*
* OK, i1 and i2 are the same instruction, modulo "target".
* We should now see if we can combine them.
*/
b1 = i1->bb;
b2 = i2->bb;
/*
* PHI-nodes do not care where they are - the only thing that matters
* are the PHI _sources_.
*/
if (i1->opcode == OP_PHI)
return cse_one_instruction(i1, i2);
/*
* Currently we only handle the uninteresting degenerate case where
* the CSE is inside one basic-block.
*/
if (b1 == b2) {
struct instruction *insn;
FOR_EACH_PTR(b1->insns, insn) {
if (insn == i1)
return cse_one_instruction(i2, i1);
if (insn == i2)
return cse_one_instruction(i1, i2);
} END_FOR_EACH_PTR(insn);
warning(b1->pos, "Whaa? unable to find CSE instructions");
return i1;
}
if (bb_dominates(ep, b1, b2, ++bb_generation))
return cse_one_instruction(i2, i1);
if (bb_dominates(ep, b2, b1, ++bb_generation))
return cse_one_instruction(i1, i2);
/* No direct dominance - but we could try to find a common ancestor.. */
common = trivial_common_parent(b1, b2);
if (common) {
i1 = cse_one_instruction(i2, i1);
remove_instruction(&b1->insns, i1, 1);
add_instruction_to_end(i1, common);
}
return i1;
}
void cleanup_and_cse(struct entrypoint *ep)
{
int i;
simplify_memops(ep);
repeat:
repeat_phase = 0;
clean_up_insns(ep);
for (i = 0; i < INSN_HASH_SIZE; i++) {
struct instruction_list **list = insn_hash_table + i;
if (*list) {
if (instruction_list_size(*list) > 1) {
struct instruction *insn, *last;
sort_instruction_list(list);
last = NULL;
FOR_EACH_PTR(*list, insn) {
if (!insn->bb)
continue;
if (last) {
if (!insn_compare(last, insn))
insn = try_to_cse(ep, last, insn);
}
last = insn;
} END_FOR_EACH_PTR(insn);
}
free_ptr_list((struct ptr_list **)list);
}
}
if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
simplify_memops(ep);
if (repeat_phase & REPEAT_CSE)
goto repeat;
}