From 66f2ebe4482738dd45d2eee233e6c306d880e811 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Thu, 9 Apr 2020 19:31:18 +0300 Subject: [PATCH] Register allocator refactoring --- ext/opcache/jit/zend_jit.c | 84 +++++++++++++++++++++---------- ext/opcache/jit/zend_jit.h | 20 ++++++-- ext/opcache/jit/zend_jit_x86.dasc | 14 +++--- ext/opcache/jit/zend_jit_x86.h | 6 +-- 4 files changed, 83 insertions(+), 41 deletions(-) diff --git a/ext/opcache/jit/zend_jit.c b/ext/opcache/jit/zend_jit.c index b5c4ca82d7..2ff1b07eec 100644 --- a/ext/opcache/jit/zend_jit.c +++ b/ext/opcache/jit/zend_jit.c @@ -133,6 +133,19 @@ static zend_bool zend_ssa_is_last_use(const zend_op_array *op_array, const zend_ return use < 0 || zend_ssa_is_no_val_use(op_array->opcodes + use, ssa->ops + use, var); } +static zend_bool zend_ival_is_last_use(const zend_lifetime_interval *ival, int use) +{ + if (ival->flags & ZREG_LAST_USE) { + const zend_life_range *range = &ival->range; + + while (range->next) { + range = range->next; + } + return range->end == use; + } + return 0; +} + static zend_bool zend_is_commutative(zend_uchar opcode) { return @@ -702,9 +715,7 @@ static int zend_jit_add_range(zend_lifetime_interval **intervals, int var, uint3 } ival->ssa_var = var; ival->reg = ZREG_NONE; - ival->split = 0; - ival->store = 0; - ival->load = 0; + ival->flags = 0; ival->range.start = from; ival->range.end = to; ival->range.next = NULL; @@ -831,13 +842,12 @@ static int zend_jit_split_interval(zend_lifetime_interval *current, uint32_t pos } } - current->store = 1; + current->flags |= ZREG_STORE; ival->ssa_var = current->ssa_var; ival->reg = ZREG_NONE; - ival->split = 1; - ival->store = 0; - ival->load = 1; + ival->flags |= ZREG_SPLIT | ZREG_LOAD; + ival->flags &= ZREG_STORE; ival->hint = NULL; do { @@ -1431,7 +1441,7 @@ static int zend_jit_try_allocate_free_reg(const zend_op_array *op_array, zend_ss /* See "Linear Scan Register Allocation on SSA Form", Christian Wimmer and Michael Franz, CGO'10 (2010), Figure 6. */ - if (current->split) { + if (current->flags & ZREG_SPLIT) { /* for each interval it in inactive intersecting with current do */ /* freeUntilPos[it.reg] = next intersection of it with current */ it = inactive; @@ -1451,9 +1461,13 @@ static int zend_jit_try_allocate_free_reg(const zend_op_array *op_array, zend_ss range = ¤t->range; do { uint32_t line = range->start; + uint32_t last_use_line = (uint32_t)-1; zend_regset regset; zend_reg reg; + if ((current->flags & ZREG_LAST_USE) && !range->next) { + last_use_line = range->end; + } if (ssa->ops[line].op1_def == current->ssa_var || ssa->ops[line].op2_def == current->ssa_var || ssa->ops[line].result_def == current->ssa_var) { @@ -1463,7 +1477,7 @@ static int zend_jit_try_allocate_free_reg(const zend_op_array *op_array, zend_ss regset = zend_jit_get_scratch_regset( op_array->opcodes + line, ssa->ops + line, - op_array, ssa, current->ssa_var); + op_array, ssa, current->ssa_var, line == last_use_line); ZEND_REGSET_FOREACH(regset, reg) { if (line < freeUntilPos[reg]) { freeUntilPos[reg] = line; @@ -1717,6 +1731,22 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array goto failure; } + if (list) { + /* Set ZREG_LAST_USE flags */ + ival = list; + while (ival) { + zend_life_range *range = &ival->range; + + while (range->next) { + range = range->next; + } + if (zend_ssa_is_last_use(op_array, ssa, ival->ssa_var, range->end)) { + ival->flags |= ZREG_LAST_USE; + } + ival = ival->list_next; + } + } + if (list) { if (ZCG(accel_directives).jit_debug & ZEND_JIT_DEBUG_REG_ALLOC) { fprintf(stderr, "Live Ranges \"%s\"\n", op_array->function_name ? ZSTR_VAL(op_array->function_name) : "[main]"); @@ -1733,10 +1763,10 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array fprintf(stderr, ", %u-%u", range->start, range->end); range = range->next; } - if (ival->load) { + if (ival->flags & ZREG_LOAD) { fprintf(stderr, " load"); } - if (ival->store) { + if (ival->flags & ZREG_STORE) { fprintf(stderr, " store"); } if (ival->hint) { @@ -1781,13 +1811,13 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array src = phi->sources[0]; if (intervals[i]) { if (!intervals[src]) { - intervals[i]->load = 1; + intervals[i]->flags |= ZREG_LOAD; } else if (intervals[i]->reg != intervals[src]->reg) { - intervals[i]->load = 1; - intervals[src]->store = 1; + intervals[i]->flags |= ZREG_LOAD; + intervals[src]->flags |= ZREG_STORE; } } else if (intervals[src]) { - intervals[src]->store = 1; + intervals[src]->flags |= ZREG_STORE; } } } else { @@ -1815,7 +1845,7 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array } if (need_move) { if (intervals[i]) { - intervals[i]->load = 1; + intervals[i]->flags |= ZREG_LOAD; } for (k = 0; k < ssa->cfg.blocks[phi->block].predecessors_count; k++) { src = phi->sources[k]; @@ -1827,7 +1857,7 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array src = ssa->vars[src].definition_phi->sources[0]; } if (intervals[src]) { - intervals[src]->store = 1; + intervals[src]->flags |= ZREG_STORE; } } } @@ -1838,15 +1868,15 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array /* Remove useless register allocation */ for (i = 0; i < ssa->vars_count; i++) { if (intervals[i] && - (intervals[i]->load || - (intervals[i]->store && ssa->vars[i].definition >= 0)) && + ((intervals[i]->flags & ZREG_LOAD) || + ((intervals[i]->flags & ZREG_STORE) && ssa->vars[i].definition >= 0)) && ssa->vars[i].use_chain < 0) { zend_bool may_remove = 1; zend_ssa_phi *phi = ssa->vars[i].phi_use_chain; while (phi) { if (intervals[phi->ssa_var] && - !intervals[phi->ssa_var]->load) { + !(intervals[phi->ssa_var]->flags & ZREG_LOAD)) { may_remove = 0; break; } @@ -1860,8 +1890,8 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array /* Remove intervals used once */ for (i = 0; i < ssa->vars_count; i++) { if (intervals[i] && - intervals[i]->load && - intervals[i]->store && + (intervals[i]->flags & ZREG_LOAD) && + (intervals[i]->flags & ZREG_STORE) && (ssa->vars[i].use_chain < 0 || zend_ssa_next_use(ssa->ops, i, ssa->vars[i].use_chain) < 0)) { zend_bool may_remove = 1; @@ -1869,7 +1899,7 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array while (phi) { if (intervals[phi->ssa_var] && - !intervals[phi->ssa_var]->load) { + !(intervals[phi->ssa_var]->flags & ZREG_LOAD)) { may_remove = 0; break; } @@ -1899,10 +1929,10 @@ static zend_lifetime_interval** zend_jit_allocate_registers(const zend_op_array range = range->next; } fprintf(stderr, " (%s)", zend_reg_name[ival->reg]); - if (ival->load) { + if (ival->flags & ZREG_LOAD) { fprintf(stderr, " load"); } - if (ival->store) { + if (ival->flags & ZREG_STORE) { fprintf(stderr, " store"); } if (ival->hint) { @@ -2131,13 +2161,13 @@ static int zend_jit(const zend_op_array *op_array, zend_ssa *ssa, const zend_op zend_lifetime_interval *ival = ra[phi->ssa_var]; if (ival) { - if (ival->load) { + if (ival->flags & ZREG_LOAD) { ZEND_ASSERT(ival->reg != ZREG_NONE); if (!zend_jit_load_var(&dasm_state, ssa->var_info[phi->ssa_var].type, ssa->vars[phi->ssa_var].var, ival->reg)) { goto jit_failure; } - } else if (ival->store) { + } else if (ival->flags & ZREG_STORE) { ZEND_ASSERT(ival->reg != ZREG_NONE); if (!zend_jit_store_var(&dasm_state, ssa->var_info[phi->ssa_var].type, ssa->vars[phi->ssa_var].var, ival->reg)) { diff --git a/ext/opcache/jit/zend_jit.h b/ext/opcache/jit/zend_jit.h index e53c88e19c..cecd263eb8 100644 --- a/ext/opcache/jit/zend_jit.h +++ b/ext/opcache/jit/zend_jit.h @@ -105,12 +105,24 @@ struct _zend_life_range { zend_life_range *next; }; +#define ZREG_FLAGS_SHIFT 8 + +#define ZREG_STORE (1<<0) +#define ZREG_LOAD (1<<1) +#define ZREG_LAST_USE (1<<2) +#define ZREG_SPLIT (1<<3) + struct _zend_lifetime_interval { int ssa_var; - int8_t reg; - zend_bool split; - zend_bool store; - zend_bool load; + union { + struct { + ZEND_ENDIAN_LOHI_3( + int8_t reg, + uint8_t flags, + uint16_t reserved + )}; + uint32_t reg_flags; + }; zend_life_range range; zend_lifetime_interval *hint; zend_lifetime_interval *used_as_hint; diff --git a/ext/opcache/jit/zend_jit_x86.dasc b/ext/opcache/jit/zend_jit_x86.dasc index b5c71f2cbb..7fa4f108ea 100644 --- a/ext/opcache/jit/zend_jit_x86.dasc +++ b/ext/opcache/jit/zend_jit_x86.dasc @@ -11114,7 +11114,7 @@ static zend_bool zend_needs_extra_reg_for_const(const zend_op_array *op_array, c return 0; } -static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend_ssa_op *ssa_op, const zend_op_array *op_array, zend_ssa *ssa, int current_var) +static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend_ssa_op *ssa_op, const zend_op_array *op_array, zend_ssa *ssa, int current_var, zend_bool last_use) { uint32_t op1_info, op2_info, res_info; zend_regset regset = ZEND_REGSET_SCRATCH; @@ -11222,7 +11222,7 @@ static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend regset = ZEND_REGSET_EMPTY; if ((op1_info & MAY_BE_LONG) && (op2_info & MAY_BE_LONG)) { if (ssa_op->result_def != current_var && - (ssa_op->op1_use != current_var || !zend_ssa_is_last_use(op_array, ssa, current_var, ssa_op - ssa->ops))) { + (ssa_op->op1_use != current_var || !last_use)) { ZEND_REGSET_INCL(regset, ZREG_R0); } res_info = OP1_INFO(); @@ -11244,14 +11244,14 @@ static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend } else { ZEND_REGSET_INCL(regset, ZREG_XMM0); if (ssa_op->result_def != current_var && - (ssa_op->op1_use != current_var || !zend_ssa_is_last_use(op_array, ssa, current_var, ssa_op - ssa->ops))) { + (ssa_op->op1_use != current_var || !last_use)) { ZEND_REGSET_INCL(regset, ZREG_XMM1); } } } if ((op1_info & MAY_BE_DOUBLE) && (op2_info & MAY_BE_DOUBLE)) { if (ssa_op->result_def != current_var && - (ssa_op->op1_use != current_var || !zend_ssa_is_last_use(op_array, ssa, current_var, ssa_op - ssa->ops))) { + (ssa_op->op1_use != current_var || !last_use)) { ZEND_REGSET_INCL(regset, ZREG_XMM0); } } @@ -11270,7 +11270,7 @@ static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend !(op2_info & ((MAY_BE_ANY|MAY_BE_REF|MAY_BE_UNDEF)-MAY_BE_LONG))) { regset = ZEND_REGSET_EMPTY; if (ssa_op->result_def != current_var && - (ssa_op->op1_use != current_var || !zend_ssa_is_last_use(op_array, ssa, current_var, ssa_op - ssa->ops))) { + (ssa_op->op1_use != current_var || !last_use)) { ZEND_REGSET_INCL(regset, ZREG_R0); } } @@ -11283,7 +11283,7 @@ static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend !(op2_info & ((MAY_BE_ANY|MAY_BE_REF|MAY_BE_UNDEF)-MAY_BE_LONG))) { regset = ZEND_REGSET_EMPTY; if (ssa_op->result_def != current_var && - (ssa_op->op1_use != current_var || !zend_ssa_is_last_use(op_array, ssa, current_var, ssa_op - ssa->ops))) { + (ssa_op->op1_use != current_var || !last_use)) { ZEND_REGSET_INCL(regset, ZREG_R0); } if (opline->op2_type != IS_CONST && ssa_op->op2_use != current_var) { @@ -11301,7 +11301,7 @@ static zend_regset zend_jit_get_scratch_regset(const zend_op *opline, const zend Z_TYPE_P(RT_CONSTANT(opline, opline->op2)) == IS_LONG && zend_long_is_power_of_two(Z_LVAL_P(RT_CONSTANT(opline, opline->op2)))) { if (ssa_op->result_def != current_var && - (ssa_op->op1_use != current_var || !zend_ssa_is_last_use(op_array, ssa, current_var, ssa_op - ssa->ops))) { + (ssa_op->op1_use != current_var || !last_use)) { ZEND_REGSET_INCL(regset, ZREG_R0); } } else { diff --git a/ext/opcache/jit/zend_jit_x86.h b/ext/opcache/jit/zend_jit_x86.h index 8b2365efad..9a81c7f74b 100644 --- a/ext/opcache/jit/zend_jit_x86.h +++ b/ext/opcache/jit/zend_jit_x86.h @@ -249,9 +249,9 @@ typedef uintptr_t zend_jit_addr; #define OP_REG(ssa_op, op) \ (ra && ssa_op->op >= 0 && ra[ssa_op->op] ? \ OP_REG_EX(ra[ssa_op->op]->reg, \ - ra[ssa_op->op]->store, \ - ra[ssa_op->op]->load, \ - zend_ssa_is_last_use(op_array, ssa, ssa_op->op, ssa_op - ssa->ops) \ + (ra[ssa_op->op]->flags & ZREG_STORE), \ + (ra[ssa_op->op]->flags & ZREG_LOAD), \ + zend_ival_is_last_use(ra[ssa_op->op], ssa_op - ssa->ops) \ ) : ZREG_NONE) static zend_always_inline zend_jit_addr _zend_jit_decode_op(zend_uchar op_type, znode_op op, const zend_op *opline, zend_reg reg) -- 2.40.0