From f4838f47038173fa0e0cefa919338916075bf6d2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Wed, 1 Dec 2004 12:06:16 -0700 Subject: [PATCH] Remove OP_SETCC, make OP_SEL bigger instead. This was originally done so that "struct instruction" would be smaller, but it has since grown anyway (for the memops), so splitting OP_SEL into two instructions no longer makes sense, and makes it harder on CSE. --- cse.c | 16 ++++++++++------ linearize.c | 51 +++++++++++++++++++++------------------------------ linearize.h | 7 +++---- liveness.c | 7 +------ simplify.c | 52 ++++++++++++++++++++++------------------------------ 5 files changed, 57 insertions(+), 76 deletions(-) diff --git a/cse.c b/cse.c index 21ae285c..b75a4122 100644 --- a/cse.c +++ b/cse.c @@ -46,7 +46,10 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction assert(insn->bb == bb); repeat_phase |= simplify_instruction(insn); hash = (insn->opcode << 3) + (insn->size >> 3); - switch (insn->opcode) { + switch (insn->opcode) { + case OP_SEL: + hash += hashval(insn->src3); + /* Fallthrough */ /* Binary arithmetic */ case OP_ADD: case OP_SUB: @@ -65,9 +68,8 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction 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->src1); hash += hashval(insn->src2); - break; + /* Fallthrough */ /* Unary */ case OP_NOT: case OP_NEG: @@ -163,6 +165,10 @@ static int insn_compare(const void *_i1, const void *_i2) 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: @@ -181,11 +187,9 @@ static int insn_compare(const void *_i1, const void *_i2) 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->src1 != i2->src1) - return i1->src1 < i2->src1 ? -1 : 1; if (i1->src2 != i2->src2) return i1->src2 < i2->src2 ? -1 : 1; - break; + /* Fall-through to unops */ /* Unary */ case OP_NOT: case OP_NEG: diff --git a/linearize.c b/linearize.c index 38e5cca1..dac3c2f4 100644 --- a/linearize.c +++ b/linearize.c @@ -25,7 +25,6 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt); pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr); -static void add_setcc(struct entrypoint *ep, struct expression *expr, pseudo_t val); static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right); static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val); @@ -194,8 +193,7 @@ static const char* opcodes[] = { [OP_NOT] = "not", [OP_NEG] = "neg", - /* Setcc - always in combination with a select or conditional branch */ - [OP_SETCC] = "setcc", + /* Special three-input */ [OP_SEL] = "select", /* Memory */ @@ -373,10 +371,14 @@ void show_instruction(struct instruction *insn) break; case OP_BINARY ... OP_BINARY_END: case OP_BINCMP ... OP_BINCMP_END: - case OP_SEL: buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2)); break; + case OP_SEL: + buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target), + show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3)); + break; + case OP_SLICE: buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len); break; @@ -385,9 +387,6 @@ void show_instruction(struct instruction *insn) buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1)); break; - case OP_SETCC: - buf += sprintf(buf, "%s", show_pseudo(insn->src)); - break; case OP_CONTEXT: buf += sprintf(buf, "%d", insn->increment); break; @@ -602,28 +601,25 @@ void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t true, pseudo_t false) { pseudo_t target; - struct instruction *setcc, *select; + struct instruction *select; /* Remove the 'br' */ delete_last_instruction(&bb->insns); - setcc = alloc_instruction(OP_SETCC, 1); - setcc->bb = bb; - assert(br->cond); - use_pseudo(br->cond, &setcc->src); - select = alloc_instruction(OP_SEL, phi_node->size); select->bb = bb; + assert(br->cond); + use_pseudo(br->cond, &select->src1); + target = phi_node->target; assert(target->def == phi_node); select->target = target; target->def = select; - use_pseudo(true, &select->src1); - use_pseudo(false, &select->src2); + use_pseudo(true, &select->src2); + use_pseudo(false, &select->src3); - add_instruction(&bb->insns, setcc); add_instruction(&bb->insns, select); add_instruction(&bb->insns, br); } @@ -651,18 +647,6 @@ static struct basic_block * add_label(struct entrypoint *ep, struct symbol *labe return bb; } -static void add_setcc(struct entrypoint *ep, struct expression *expr, pseudo_t val) -{ - struct basic_block *bb = ep->active; - - if (bb_reachable(bb)) { - struct instruction *cc = alloc_instruction(OP_SETCC, 1); - use_pseudo(val, &cc->src); - assert(val); - add_one_insn(ep, cc); - } -} - static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false) { struct basic_block *bb = ep->active; @@ -1141,15 +1125,22 @@ pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, s static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr) { pseudo_t cond, true, false, res; + struct instruction *insn; true = linearize_expression(ep, expr->cond_true); false = linearize_expression(ep, expr->cond_false); cond = linearize_expression(ep, expr->conditional); - add_setcc(ep, expr, cond); + insn = alloc_typed_instruction(OP_SEL, expr->ctype); if (!expr->cond_true) true = cond; - res = add_binary_op(ep, expr->ctype, OP_SEL, true, false); + use_pseudo(cond, &insn->src1); + use_pseudo(true, &insn->src2); + use_pseudo(false, &insn->src3); + + res = alloc_pseudo(insn); + insn->target = res; + add_one_insn(ep, insn); return res; } diff --git a/linearize.h b/linearize.h index c1ba1b8f..f9e5eb6f 100644 --- a/linearize.h +++ b/linearize.h @@ -62,8 +62,8 @@ struct instruction { struct symbol *orig_type; /* casts */ unsigned int offset; /* memops */ }; - struct /* binops */ { - pseudo_t src1, src2; + struct /* binops and sel */ { + pseudo_t src1, src2, src3; }; struct /* slice */ { pseudo_t base; @@ -134,8 +134,7 @@ enum opcode { OP_NOT, OP_NEG, - /* Setcc - always in combination with a select or conditional branch */ - OP_SETCC, + /* Select - three input values */ OP_SEL, /* Memory */ diff --git a/liveness.c b/liveness.c index 6f528e22..37253277 100644 --- a/liveness.c +++ b/liveness.c @@ -110,13 +110,8 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction * USES(src1); DEFINES(target); break; - /* Setcc - always in combination with a select or conditional branch */ - case OP_SETCC: - USES(src); - break; - case OP_SEL: - USES(src1); USES(src2); DEFINES(target); + USES(src1); USES(src2); USES(src3); DEFINES(target); break; /* Memory */ diff --git a/simplify.c b/simplify.c index 853b57ed..4d9af239 100644 --- a/simplify.c +++ b/simplify.c @@ -200,7 +200,7 @@ void kill_instruction(struct instruction *insn) /* * Kill trivially dead instructions */ -static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2) +static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3) { pseudo_t *usep; FOR_EACH_PTR(insn->target->users, usep) { @@ -211,6 +211,7 @@ static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2) insn->bb = NULL; kill_use(src1); kill_use(src2); + kill_use(src3); return REPEAT_CSE; } @@ -378,7 +379,7 @@ static int simplify_constant_binop(struct instruction *insn) static int simplify_binop(struct instruction *insn) { - if (dead_insn(insn, &insn->src1, &insn->src2)) + if (dead_insn(insn, &insn->src1, &insn->src2, NULL)) return REPEAT_CSE; if (constant(insn->src1)) { if (constant(insn->src2)) @@ -397,7 +398,7 @@ static int simplify_constant_unop(struct instruction *insn) static int simplify_unop(struct instruction *insn) { - if (dead_insn(insn, &insn->src1, NULL)) + if (dead_insn(insn, &insn->src1, NULL, NULL)) return REPEAT_CSE; if (constant(insn->src1)) return simplify_constant_unop(insn); @@ -464,7 +465,7 @@ static int simplify_cast(struct instruction *insn) { int orig_size; - if (dead_insn(insn, &insn->src, NULL)) + if (dead_insn(insn, &insn->src, NULL, NULL)) return REPEAT_CSE; if (insn->opcode == OP_PTRCAST) return 0; @@ -476,22 +477,23 @@ static int simplify_cast(struct instruction *insn) return replace_with_pseudo(insn, insn->src); } -static int simplify_select(struct instruction *insn, struct instruction *setcc) +static int simplify_select(struct instruction *insn) { pseudo_t cond, src1, src2; - assert(setcc && setcc->bb); - if (dead_insn(insn, &insn->src1, &insn->src2)) { - setcc->bb = NULL; + if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3)) return REPEAT_CSE; - } - cond = setcc->src; - src1 = insn->src1; - src2 = insn->src2; + + cond = insn->src1; + src1 = insn->src2; + src2 = insn->src3; if (constant(cond) || src1 == src2) { - setcc->bb = NULL; - kill_use(&setcc->cond); - replace_with_pseudo(insn, cond->value ? src1 : src2); + pseudo_t *kill, take; + kill_use(&insn->cond); + take = cond->value ? src1 : src2; + kill = cond->value ? &insn->src3 : &insn->src2; + kill_use(kill); + replace_with_pseudo(insn, take); return REPEAT_CSE; } if (constant(src1) && constant(src2)) { @@ -506,10 +508,8 @@ static int simplify_select(struct instruction *insn, struct instruction *setcc) opcode = OP_SET_NE; } insn->opcode = opcode; + /* insn->src1 is already cond */ insn->src2 = src1; /* Zero */ - use_pseudo(cond, &insn->src1); - setcc->bb = NULL; - kill_use(&setcc->cond); return REPEAT_CSE; } } @@ -586,11 +586,6 @@ found: int simplify_instruction(struct instruction *insn) { - static struct instruction *last_setcc; - struct instruction *setcc = last_setcc; - - last_setcc = NULL; - if (!insn->bb) return 0; switch (insn->opcode) { @@ -602,27 +597,24 @@ int simplify_instruction(struct instruction *insn) case OP_LOAD: case OP_STORE: return simplify_memop(insn); case OP_SETVAL: - if (dead_insn(insn, NULL, NULL)) + if (dead_insn(insn, NULL, NULL, NULL)) return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP; break; case OP_PTRCAST: case OP_CAST: return simplify_cast(insn); case OP_PHI: - if (dead_insn(insn, NULL, NULL)) { + if (dead_insn(insn, NULL, NULL, NULL)) { clear_phi(insn); return REPEAT_CSE; } return clean_up_phi(insn); case OP_PHISOURCE: - if (dead_insn(insn, &insn->src1, NULL)) + if (dead_insn(insn, &insn->src1, NULL, NULL)) return REPEAT_CSE; break; - case OP_SETCC: - last_setcc = insn; - return 0; case OP_SEL: - return simplify_select(insn, setcc); + return simplify_select(insn); case OP_BR: return simplify_branch(insn); case OP_SWITCH: -- 2.11.4.GIT