1.1 --- a/src/share/vm/c1/c1_Optimizer.cpp Wed Oct 13 15:38:14 2010 -0700
1.2 +++ b/src/share/vm/c1/c1_Optimizer.cpp Fri Oct 15 09:38:20 2010 +0200
1.3 @@ -38,18 +38,20 @@
1.4 private:
1.5 IR* _hir;
1.6 int _cee_count; // the number of CEs successfully eliminated
1.7 + int _ifop_count; // the number of IfOps successfully simplified
1.8 int _has_substitution;
1.9
1.10 public:
1.11 - CE_Eliminator(IR* hir) : _cee_count(0), _hir(hir) {
1.12 + CE_Eliminator(IR* hir) : _cee_count(0), _ifop_count(0), _hir(hir) {
1.13 _has_substitution = false;
1.14 _hir->iterate_preorder(this);
1.15 if (_has_substitution) {
1.16 - // substituted some phis so resolve the substitution
1.17 + // substituted some ifops/phis, so resolve the substitution
1.18 SubstitutionResolver sr(_hir);
1.19 }
1.20 }
1.21 int cee_count() const { return _cee_count; }
1.22 + int ifop_count() const { return _ifop_count; }
1.23
1.24 void adjust_exception_edges(BlockBegin* block, BlockBegin* sux) {
1.25 int e = sux->number_of_exception_handlers();
1.26 @@ -68,156 +70,214 @@
1.27 }
1.28 }
1.29
1.30 - virtual void block_do(BlockBegin* block) {
1.31 - // 1) find conditional expression
1.32 - // check if block ends with an If
1.33 - If* if_ = block->end()->as_If();
1.34 - if (if_ == NULL) return;
1.35 + virtual void block_do(BlockBegin* block);
1.36
1.37 - // check if If works on int or object types
1.38 - // (we cannot handle If's working on long, float or doubles yet,
1.39 - // since IfOp doesn't support them - these If's show up if cmp
1.40 - // operations followed by If's are eliminated)
1.41 - ValueType* if_type = if_->x()->type();
1.42 - if (!if_type->is_int() && !if_type->is_object()) return;
1.43 + private:
1.44 + Value make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval);
1.45 +};
1.46
1.47 - BlockBegin* t_block = if_->tsux();
1.48 - BlockBegin* f_block = if_->fsux();
1.49 - Instruction* t_cur = t_block->next();
1.50 - Instruction* f_cur = f_block->next();
1.51 +void CE_Eliminator::block_do(BlockBegin* block) {
1.52 + // 1) find conditional expression
1.53 + // check if block ends with an If
1.54 + If* if_ = block->end()->as_If();
1.55 + if (if_ == NULL) return;
1.56
1.57 - // one Constant may be present between BlockBegin and BlockEnd
1.58 - Value t_const = NULL;
1.59 - Value f_const = NULL;
1.60 - if (t_cur->as_Constant() != NULL && !t_cur->can_trap()) {
1.61 - t_const = t_cur;
1.62 - t_cur = t_cur->next();
1.63 - }
1.64 - if (f_cur->as_Constant() != NULL && !f_cur->can_trap()) {
1.65 - f_const = f_cur;
1.66 - f_cur = f_cur->next();
1.67 - }
1.68 + // check if If works on int or object types
1.69 + // (we cannot handle If's working on long, float or doubles yet,
1.70 + // since IfOp doesn't support them - these If's show up if cmp
1.71 + // operations followed by If's are eliminated)
1.72 + ValueType* if_type = if_->x()->type();
1.73 + if (!if_type->is_int() && !if_type->is_object()) return;
1.74
1.75 - // check if both branches end with a goto
1.76 - Goto* t_goto = t_cur->as_Goto();
1.77 - if (t_goto == NULL) return;
1.78 - Goto* f_goto = f_cur->as_Goto();
1.79 - if (f_goto == NULL) return;
1.80 + BlockBegin* t_block = if_->tsux();
1.81 + BlockBegin* f_block = if_->fsux();
1.82 + Instruction* t_cur = t_block->next();
1.83 + Instruction* f_cur = f_block->next();
1.84
1.85 - // check if both gotos merge into the same block
1.86 - BlockBegin* sux = t_goto->default_sux();
1.87 - if (sux != f_goto->default_sux()) return;
1.88 + // one Constant may be present between BlockBegin and BlockEnd
1.89 + Value t_const = NULL;
1.90 + Value f_const = NULL;
1.91 + if (t_cur->as_Constant() != NULL && !t_cur->can_trap()) {
1.92 + t_const = t_cur;
1.93 + t_cur = t_cur->next();
1.94 + }
1.95 + if (f_cur->as_Constant() != NULL && !f_cur->can_trap()) {
1.96 + f_const = f_cur;
1.97 + f_cur = f_cur->next();
1.98 + }
1.99
1.100 - // check if at least one word was pushed on sux_state
1.101 - ValueStack* sux_state = sux->state();
1.102 - if (sux_state->stack_size() <= if_->state()->stack_size()) return;
1.103 + // check if both branches end with a goto
1.104 + Goto* t_goto = t_cur->as_Goto();
1.105 + if (t_goto == NULL) return;
1.106 + Goto* f_goto = f_cur->as_Goto();
1.107 + if (f_goto == NULL) return;
1.108
1.109 - // check if phi function is present at end of successor stack and that
1.110 - // only this phi was pushed on the stack
1.111 - Value sux_phi = sux_state->stack_at(if_->state()->stack_size());
1.112 - if (sux_phi == NULL || sux_phi->as_Phi() == NULL || sux_phi->as_Phi()->block() != sux) return;
1.113 - if (sux_phi->type()->size() != sux_state->stack_size() - if_->state()->stack_size()) return;
1.114 + // check if both gotos merge into the same block
1.115 + BlockBegin* sux = t_goto->default_sux();
1.116 + if (sux != f_goto->default_sux()) return;
1.117
1.118 - // get the values that were pushed in the true- and false-branch
1.119 - Value t_value = t_goto->state()->stack_at(if_->state()->stack_size());
1.120 - Value f_value = f_goto->state()->stack_at(if_->state()->stack_size());
1.121 + // check if at least one word was pushed on sux_state
1.122 + ValueStack* sux_state = sux->state();
1.123 + if (sux_state->stack_size() <= if_->state()->stack_size()) return;
1.124
1.125 - // backend does not support floats
1.126 - assert(t_value->type()->base() == f_value->type()->base(), "incompatible types");
1.127 - if (t_value->type()->is_float_kind()) return;
1.128 + // check if phi function is present at end of successor stack and that
1.129 + // only this phi was pushed on the stack
1.130 + Value sux_phi = sux_state->stack_at(if_->state()->stack_size());
1.131 + if (sux_phi == NULL || sux_phi->as_Phi() == NULL || sux_phi->as_Phi()->block() != sux) return;
1.132 + if (sux_phi->type()->size() != sux_state->stack_size() - if_->state()->stack_size()) return;
1.133
1.134 - // check that successor has no other phi functions but sux_phi
1.135 - // this can happen when t_block or f_block contained additonal stores to local variables
1.136 - // that are no longer represented by explicit instructions
1.137 - for_each_phi_fun(sux, phi,
1.138 - if (phi != sux_phi) return;
1.139 - );
1.140 - // true and false blocks can't have phis
1.141 - for_each_phi_fun(t_block, phi, return; );
1.142 - for_each_phi_fun(f_block, phi, return; );
1.143 + // get the values that were pushed in the true- and false-branch
1.144 + Value t_value = t_goto->state()->stack_at(if_->state()->stack_size());
1.145 + Value f_value = f_goto->state()->stack_at(if_->state()->stack_size());
1.146
1.147 - // 2) substitute conditional expression
1.148 - // with an IfOp followed by a Goto
1.149 - // cut if_ away and get node before
1.150 - Instruction* cur_end = if_->prev(block);
1.151 + // backend does not support floats
1.152 + assert(t_value->type()->base() == f_value->type()->base(), "incompatible types");
1.153 + if (t_value->type()->is_float_kind()) return;
1.154
1.155 - // append constants of true- and false-block if necessary
1.156 - // clone constants because original block must not be destroyed
1.157 - assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
1.158 - if (t_value == t_const) {
1.159 - t_value = new Constant(t_const->type());
1.160 - NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
1.161 - cur_end = cur_end->set_next(t_value);
1.162 - }
1.163 - if (f_value == f_const) {
1.164 - f_value = new Constant(f_const->type());
1.165 - NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
1.166 - cur_end = cur_end->set_next(f_value);
1.167 - }
1.168 + // check that successor has no other phi functions but sux_phi
1.169 + // this can happen when t_block or f_block contained additonal stores to local variables
1.170 + // that are no longer represented by explicit instructions
1.171 + for_each_phi_fun(sux, phi,
1.172 + if (phi != sux_phi) return;
1.173 + );
1.174 + // true and false blocks can't have phis
1.175 + for_each_phi_fun(t_block, phi, return; );
1.176 + for_each_phi_fun(f_block, phi, return; );
1.177
1.178 - // it is very unlikely that the condition can be statically decided
1.179 - // (this was checked previously by the Canonicalizer), so always
1.180 - // append IfOp
1.181 - Value result = new IfOp(if_->x(), if_->cond(), if_->y(), t_value, f_value);
1.182 + // 2) substitute conditional expression
1.183 + // with an IfOp followed by a Goto
1.184 + // cut if_ away and get node before
1.185 + Instruction* cur_end = if_->prev(block);
1.186 +
1.187 + // append constants of true- and false-block if necessary
1.188 + // clone constants because original block must not be destroyed
1.189 + assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
1.190 + if (t_value == t_const) {
1.191 + t_value = new Constant(t_const->type());
1.192 + NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
1.193 + cur_end = cur_end->set_next(t_value);
1.194 + }
1.195 + if (f_value == f_const) {
1.196 + f_value = new Constant(f_const->type());
1.197 + NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
1.198 + cur_end = cur_end->set_next(f_value);
1.199 + }
1.200 +
1.201 + Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);
1.202 + assert(result != NULL, "make_ifop must return a non-null instruction");
1.203 + if (!result->is_linked() && result->can_be_linked()) {
1.204 NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));
1.205 cur_end = cur_end->set_next(result);
1.206 + }
1.207
1.208 - // append Goto to successor
1.209 - ValueStack* state_before = if_->is_safepoint() ? if_->state_before() : NULL;
1.210 - Goto* goto_ = new Goto(sux, state_before, if_->is_safepoint() || t_goto->is_safepoint() || f_goto->is_safepoint());
1.211 + // append Goto to successor
1.212 + ValueStack* state_before = if_->is_safepoint() ? if_->state_before() : NULL;
1.213 + Goto* goto_ = new Goto(sux, state_before, if_->is_safepoint() || t_goto->is_safepoint() || f_goto->is_safepoint());
1.214
1.215 - // prepare state for Goto
1.216 - ValueStack* goto_state = if_->state();
1.217 - while (sux_state->scope() != goto_state->scope()) {
1.218 - goto_state = goto_state->caller_state();
1.219 - assert(goto_state != NULL, "states do not match up");
1.220 + // prepare state for Goto
1.221 + ValueStack* goto_state = if_->state();
1.222 + while (sux_state->scope() != goto_state->scope()) {
1.223 + goto_state = goto_state->caller_state();
1.224 + assert(goto_state != NULL, "states do not match up");
1.225 + }
1.226 + goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
1.227 + goto_state->push(result->type(), result);
1.228 + assert(goto_state->is_same(sux_state), "states must match now");
1.229 + goto_->set_state(goto_state);
1.230 +
1.231 + cur_end = cur_end->set_next(goto_, goto_state->bci());
1.232 +
1.233 + // Adjust control flow graph
1.234 + BlockBegin::disconnect_edge(block, t_block);
1.235 + BlockBegin::disconnect_edge(block, f_block);
1.236 + if (t_block->number_of_preds() == 0) {
1.237 + BlockBegin::disconnect_edge(t_block, sux);
1.238 + }
1.239 + adjust_exception_edges(block, t_block);
1.240 + if (f_block->number_of_preds() == 0) {
1.241 + BlockBegin::disconnect_edge(f_block, sux);
1.242 + }
1.243 + adjust_exception_edges(block, f_block);
1.244 +
1.245 + // update block end
1.246 + block->set_end(goto_);
1.247 +
1.248 + // substitute the phi if possible
1.249 + if (sux_phi->as_Phi()->operand_count() == 1) {
1.250 + assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
1.251 + sux_phi->set_subst(result);
1.252 + _has_substitution = true;
1.253 + }
1.254 +
1.255 + // 3) successfully eliminated a conditional expression
1.256 + _cee_count++;
1.257 + if (PrintCEE) {
1.258 + tty->print_cr("%d. CEE in B%d (B%d B%d)", cee_count(), block->block_id(), t_block->block_id(), f_block->block_id());
1.259 + tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());
1.260 + }
1.261 +
1.262 + _hir->verify();
1.263 +}
1.264 +
1.265 +Value CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval) {
1.266 + if (!OptimizeIfOps) {
1.267 + return new IfOp(x, cond, y, tval, fval);
1.268 + }
1.269 +
1.270 + tval = tval->subst();
1.271 + fval = fval->subst();
1.272 + if (tval == fval) {
1.273 + _ifop_count++;
1.274 + return tval;
1.275 + }
1.276 +
1.277 + x = x->subst();
1.278 + y = y->subst();
1.279 +
1.280 + Constant* y_const = y->as_Constant();
1.281 + if (y_const != NULL) {
1.282 + IfOp* x_ifop = x->as_IfOp();
1.283 + if (x_ifop != NULL) { // x is an ifop, y is a constant
1.284 + Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();
1.285 + Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();
1.286 +
1.287 + if (x_tval_const != NULL && x_fval_const != NULL) {
1.288 + Instruction::Condition x_ifop_cond = x_ifop->cond();
1.289 +
1.290 + Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);
1.291 + Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);
1.292 +
1.293 + guarantee(t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable, "incomparable constants in IfOp");
1.294 +
1.295 + Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;
1.296 + Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;
1.297 +
1.298 + _ifop_count++;
1.299 + if (new_tval == new_fval) {
1.300 + return new_tval;
1.301 + } else {
1.302 + return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);
1.303 + }
1.304 + }
1.305 + } else {
1.306 + Constant* x_const = x->as_Constant();
1.307 + if (x_const != NULL) { // x and y are constants
1.308 + Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);
1.309 + guarantee(x_compare_res != Constant::not_comparable, "incomparable constants in IfOp");
1.310 +
1.311 + _ifop_count++;
1.312 + return x_compare_res == Constant::cond_true ? tval : fval;
1.313 + }
1.314 }
1.315 - goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
1.316 - goto_state->push(result->type(), result);
1.317 - assert(goto_state->is_same(sux_state), "states must match now");
1.318 - goto_->set_state(goto_state);
1.319 -
1.320 - cur_end = cur_end->set_next(goto_, goto_state->bci());
1.321 -
1.322 - // Adjust control flow graph
1.323 - BlockBegin::disconnect_edge(block, t_block);
1.324 - BlockBegin::disconnect_edge(block, f_block);
1.325 - if (t_block->number_of_preds() == 0) {
1.326 - BlockBegin::disconnect_edge(t_block, sux);
1.327 - }
1.328 - adjust_exception_edges(block, t_block);
1.329 - if (f_block->number_of_preds() == 0) {
1.330 - BlockBegin::disconnect_edge(f_block, sux);
1.331 - }
1.332 - adjust_exception_edges(block, f_block);
1.333 -
1.334 - // update block end
1.335 - block->set_end(goto_);
1.336 -
1.337 - // substitute the phi if possible
1.338 - if (sux_phi->as_Phi()->operand_count() == 1) {
1.339 - assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
1.340 - sux_phi->set_subst(result);
1.341 - _has_substitution = true;
1.342 - }
1.343 -
1.344 - // 3) successfully eliminated a conditional expression
1.345 - _cee_count++;
1.346 - if (PrintCEE) {
1.347 - tty->print_cr("%d. CEE in B%d (B%d B%d)", cee_count(), block->block_id(), t_block->block_id(), f_block->block_id());
1.348 - }
1.349 -
1.350 - _hir->verify();
1.351 }
1.352 -};
1.353 -
1.354 + return new IfOp(x, cond, y, tval, fval);
1.355 +}
1.356
1.357 void Optimizer::eliminate_conditional_expressions() {
1.358 // find conditional expressions & replace them with IfOps
1.359 CE_Eliminator ce(ir());
1.360 }
1.361
1.362 -
1.363 class BlockMerger: public BlockClosure {
1.364 private:
1.365 IR* _hir;
