0N/A/*
2051N/A * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
0N/A * published by the Free Software Foundation.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1472N/A * or visit www.oracle.com if you need additional information or have any
1472N/A * questions.
0N/A *
0N/A */
0N/A
1879N/A#include "precompiled.hpp"
1879N/A#include "c1/c1_Canonicalizer.hpp"
1879N/A#include "c1/c1_Optimizer.hpp"
1879N/A#include "c1/c1_ValueMap.hpp"
1879N/A#include "c1/c1_ValueSet.hpp"
1879N/A#include "c1/c1_ValueStack.hpp"
1879N/A#include "utilities/bitMap.inline.hpp"
4027N/A#include "compiler/compileLog.hpp"
0N/A
0N/Adefine_array(ValueSetArray, ValueSet*);
0N/Adefine_stack(ValueSetList, ValueSetArray);
0N/A
0N/A
0N/AOptimizer::Optimizer(IR* ir) {
0N/A assert(ir->is_valid(), "IR must be valid");
0N/A _ir = ir;
0N/A}
0N/A
0N/Aclass CE_Eliminator: public BlockClosure {
0N/A private:
0N/A IR* _hir;
0N/A int _cee_count; // the number of CEs successfully eliminated
1819N/A int _ifop_count; // the number of IfOps successfully simplified
0N/A int _has_substitution;
0N/A
0N/A public:
1819N/A CE_Eliminator(IR* hir) : _cee_count(0), _ifop_count(0), _hir(hir) {
0N/A _has_substitution = false;
0N/A _hir->iterate_preorder(this);
0N/A if (_has_substitution) {
1819N/A // substituted some ifops/phis, so resolve the substitution
0N/A SubstitutionResolver sr(_hir);
0N/A }
4027N/A
4027N/A CompileLog* log = _hir->compilation()->log();
4027N/A if (log != NULL)
4027N/A log->set_context("optimize name='cee'");
0N/A }
4027N/A
4027N/A ~CE_Eliminator() {
4027N/A CompileLog* log = _hir->compilation()->log();
4027N/A if (log != NULL)
4027N/A log->clear_context(); // skip marker if nothing was printed
4027N/A }
4027N/A
0N/A int cee_count() const { return _cee_count; }
1819N/A int ifop_count() const { return _ifop_count; }
0N/A
0N/A void adjust_exception_edges(BlockBegin* block, BlockBegin* sux) {
0N/A int e = sux->number_of_exception_handlers();
0N/A for (int i = 0; i < e; i++) {
0N/A BlockBegin* xhandler = sux->exception_handler_at(i);
0N/A block->add_exception_handler(xhandler);
0N/A
0N/A assert(xhandler->is_predecessor(sux), "missing predecessor");
0N/A if (sux->number_of_preds() == 0) {
0N/A // sux is disconnected from graph so disconnect from exception handlers
0N/A xhandler->remove_predecessor(sux);
0N/A }
0N/A if (!xhandler->is_predecessor(block)) {
0N/A xhandler->add_predecessor(block);
0N/A }
0N/A }
0N/A }
0N/A
1819N/A virtual void block_do(BlockBegin* block);
1819N/A
1819N/A private:
1819N/A Value make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval);
1819N/A};
0N/A
1819N/Avoid CE_Eliminator::block_do(BlockBegin* block) {
1819N/A // 1) find conditional expression
1819N/A // check if block ends with an If
1819N/A If* if_ = block->end()->as_If();
1819N/A if (if_ == NULL) return;
0N/A
1819N/A // check if If works on int or object types
1819N/A // (we cannot handle If's working on long, float or doubles yet,
1819N/A // since IfOp doesn't support them - these If's show up if cmp
1819N/A // operations followed by If's are eliminated)
1819N/A ValueType* if_type = if_->x()->type();
1819N/A if (!if_type->is_int() && !if_type->is_object()) return;
0N/A
1819N/A BlockBegin* t_block = if_->tsux();
1819N/A BlockBegin* f_block = if_->fsux();
1819N/A Instruction* t_cur = t_block->next();
1819N/A Instruction* f_cur = f_block->next();
0N/A
1819N/A // one Constant may be present between BlockBegin and BlockEnd
1819N/A Value t_const = NULL;
1819N/A Value f_const = NULL;
1819N/A if (t_cur->as_Constant() != NULL && !t_cur->can_trap()) {
1819N/A t_const = t_cur;
1819N/A t_cur = t_cur->next();
1819N/A }
1819N/A if (f_cur->as_Constant() != NULL && !f_cur->can_trap()) {
1819N/A f_const = f_cur;
1819N/A f_cur = f_cur->next();
1819N/A }
0N/A
1819N/A // check if both branches end with a goto
1819N/A Goto* t_goto = t_cur->as_Goto();
1819N/A if (t_goto == NULL) return;
1819N/A Goto* f_goto = f_cur->as_Goto();
1819N/A if (f_goto == NULL) return;
0N/A
1819N/A // check if both gotos merge into the same block
1819N/A BlockBegin* sux = t_goto->default_sux();
1819N/A if (sux != f_goto->default_sux()) return;
0N/A
1819N/A // check if at least one word was pushed on sux_state
3037N/A // inlining depths must match
3037N/A ValueStack* if_state = if_->state();
1819N/A ValueStack* sux_state = sux->state();
3044N/A if (if_state->scope()->level() > sux_state->scope()->level()) {
3044N/A while (sux_state->scope() != if_state->scope()) {
3044N/A if_state = if_state->caller_state();
3044N/A assert(if_state != NULL, "states do not match up");
3044N/A }
3044N/A } else if (if_state->scope()->level() < sux_state->scope()->level()) {
3044N/A while (sux_state->scope() != if_state->scope()) {
3044N/A sux_state = sux_state->caller_state();
3044N/A assert(sux_state != NULL, "states do not match up");
3044N/A }
3037N/A }
3037N/A
3037N/A if (sux_state->stack_size() <= if_state->stack_size()) return;
0N/A
1819N/A // check if phi function is present at end of successor stack and that
1819N/A // only this phi was pushed on the stack
3037N/A Value sux_phi = sux_state->stack_at(if_state->stack_size());
1819N/A if (sux_phi == NULL || sux_phi->as_Phi() == NULL || sux_phi->as_Phi()->block() != sux) return;
3037N/A if (sux_phi->type()->size() != sux_state->stack_size() - if_state->stack_size()) return;
0N/A
1819N/A // get the values that were pushed in the true- and false-branch
3037N/A Value t_value = t_goto->state()->stack_at(if_state->stack_size());
3037N/A Value f_value = f_goto->state()->stack_at(if_state->stack_size());
1819N/A
1819N/A // backend does not support floats
1819N/A assert(t_value->type()->base() == f_value->type()->base(), "incompatible types");
1819N/A if (t_value->type()->is_float_kind()) return;
0N/A
1819N/A // check that successor has no other phi functions but sux_phi
1819N/A // this can happen when t_block or f_block contained additonal stores to local variables
1819N/A // that are no longer represented by explicit instructions
1819N/A for_each_phi_fun(sux, phi,
1819N/A if (phi != sux_phi) return;
1819N/A );
1819N/A // true and false blocks can't have phis
1819N/A for_each_phi_fun(t_block, phi, return; );
1819N/A for_each_phi_fun(f_block, phi, return; );
1819N/A
1819N/A // 2) substitute conditional expression
1819N/A // with an IfOp followed by a Goto
1819N/A // cut if_ away and get node before
1819N/A Instruction* cur_end = if_->prev(block);
0N/A
1819N/A // append constants of true- and false-block if necessary
1819N/A // clone constants because original block must not be destroyed
1819N/A assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
1819N/A if (t_value == t_const) {
1819N/A t_value = new Constant(t_const->type());
1819N/A NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
1819N/A cur_end = cur_end->set_next(t_value);
1819N/A }
1819N/A if (f_value == f_const) {
1819N/A f_value = new Constant(f_const->type());
1819N/A NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
1819N/A cur_end = cur_end->set_next(f_value);
1819N/A }
0N/A
1819N/A Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);
1819N/A assert(result != NULL, "make_ifop must return a non-null instruction");
1819N/A if (!result->is_linked() && result->can_be_linked()) {
1739N/A NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));
1739N/A cur_end = cur_end->set_next(result);
1819N/A }
0N/A
1819N/A // append Goto to successor
1819N/A ValueStack* state_before = if_->is_safepoint() ? if_->state_before() : NULL;
1819N/A Goto* goto_ = new Goto(sux, state_before, if_->is_safepoint() || t_goto->is_safepoint() || f_goto->is_safepoint());
1819N/A
1819N/A // prepare state for Goto
3037N/A ValueStack* goto_state = if_state;
1819N/A goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
1819N/A goto_state->push(result->type(), result);
1819N/A assert(goto_state->is_same(sux_state), "states must match now");
1819N/A goto_->set_state(goto_state);
1819N/A
1819N/A cur_end = cur_end->set_next(goto_, goto_state->bci());
1819N/A
1819N/A // Adjust control flow graph
1819N/A BlockBegin::disconnect_edge(block, t_block);
1819N/A BlockBegin::disconnect_edge(block, f_block);
1819N/A if (t_block->number_of_preds() == 0) {
1819N/A BlockBegin::disconnect_edge(t_block, sux);
1819N/A }
1819N/A adjust_exception_edges(block, t_block);
1819N/A if (f_block->number_of_preds() == 0) {
1819N/A BlockBegin::disconnect_edge(f_block, sux);
1819N/A }
1819N/A adjust_exception_edges(block, f_block);
1819N/A
1819N/A // update block end
1819N/A block->set_end(goto_);
1819N/A
1819N/A // substitute the phi if possible
1819N/A if (sux_phi->as_Phi()->operand_count() == 1) {
1819N/A assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
1819N/A sux_phi->set_subst(result);
1819N/A _has_substitution = true;
1819N/A }
1819N/A
1819N/A // 3) successfully eliminated a conditional expression
1819N/A _cee_count++;
1819N/A if (PrintCEE) {
1819N/A 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());
1819N/A tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());
1819N/A }
0N/A
1819N/A _hir->verify();
1819N/A}
1819N/A
1819N/AValue CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval) {
1819N/A if (!OptimizeIfOps) {
1819N/A return new IfOp(x, cond, y, tval, fval);
1819N/A }
1819N/A
1819N/A tval = tval->subst();
1819N/A fval = fval->subst();
1819N/A if (tval == fval) {
1819N/A _ifop_count++;
1819N/A return tval;
1819N/A }
1819N/A
1819N/A x = x->subst();
1819N/A y = y->subst();
1819N/A
1819N/A Constant* y_const = y->as_Constant();
1819N/A if (y_const != NULL) {
1819N/A IfOp* x_ifop = x->as_IfOp();
1819N/A if (x_ifop != NULL) { // x is an ifop, y is a constant
1819N/A Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();
1819N/A Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();
0N/A
1819N/A if (x_tval_const != NULL && x_fval_const != NULL) {
1819N/A Instruction::Condition x_ifop_cond = x_ifop->cond();
1819N/A
1819N/A Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);
1819N/A Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);
1819N/A
2459N/A // not_comparable here is a valid return in case we're comparing unloaded oop constants
2459N/A if (t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable) {
2459N/A Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;
2459N/A Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;
0N/A
2459N/A _ifop_count++;
2459N/A if (new_tval == new_fval) {
2459N/A return new_tval;
2459N/A } else {
2459N/A return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);
2459N/A }
1819N/A }
1819N/A }
1819N/A } else {
1819N/A Constant* x_const = x->as_Constant();
1819N/A if (x_const != NULL) { // x and y are constants
1819N/A Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);
2459N/A // not_comparable here is a valid return in case we're comparing unloaded oop constants
2459N/A if (x_compare_res != Constant::not_comparable) {
2459N/A _ifop_count++;
2459N/A return x_compare_res == Constant::cond_true ? tval : fval;
2459N/A }
1819N/A }
0N/A }
0N/A }
1819N/A return new IfOp(x, cond, y, tval, fval);
1819N/A}
0N/A
0N/Avoid Optimizer::eliminate_conditional_expressions() {
0N/A // find conditional expressions & replace them with IfOps
0N/A CE_Eliminator ce(ir());
0N/A}
0N/A
0N/Aclass BlockMerger: public BlockClosure {
0N/A private:
0N/A IR* _hir;
0N/A int _merge_count; // the number of block pairs successfully merged
0N/A
0N/A public:
0N/A BlockMerger(IR* hir)
0N/A : _hir(hir)
0N/A , _merge_count(0)
0N/A {
0N/A _hir->iterate_preorder(this);
4027N/A CompileLog* log = _hir->compilation()->log();
4027N/A if (log != NULL)
4027N/A log->set_context("optimize name='eliminate_blocks'");
4027N/A }
4027N/A
4027N/A ~BlockMerger() {
4027N/A CompileLog* log = _hir->compilation()->log();
4027N/A if (log != NULL)
4027N/A log->clear_context(); // skip marker if nothing was printed
0N/A }
0N/A
0N/A bool try_merge(BlockBegin* block) {
0N/A BlockEnd* end = block->end();
0N/A if (end->as_Goto() != NULL) {
0N/A assert(end->number_of_sux() == 1, "end must have exactly one successor");
0N/A // Note: It would be sufficient to check for the number of successors (= 1)
0N/A // in order to decide if this block can be merged potentially. That
0N/A // would then also include switch statements w/ only a default case.
0N/A // However, in that case we would need to make sure the switch tag
0N/A // expression is executed if it can produce observable side effects.
0N/A // We should probably have the canonicalizer simplifying such switch
0N/A // statements and then we are sure we don't miss these merge opportunities
0N/A // here (was bug - gri 7/7/99).
0N/A BlockBegin* sux = end->default_sux();
0N/A if (sux->number_of_preds() == 1 && !sux->is_entry_block() && !end->is_safepoint()) {
0N/A // merge the two blocks
0N/A
0N/A#ifdef ASSERT
0N/A // verify that state at the end of block and at the beginning of sux are equal
0N/A // no phi functions must be present at beginning of sux
0N/A ValueStack* sux_state = sux->state();
0N/A ValueStack* end_state = end->state();
1739N/A
1739N/A assert(end_state->scope() == sux_state->scope(), "scopes must match");
0N/A assert(end_state->stack_size() == sux_state->stack_size(), "stack not equal");
0N/A assert(end_state->locals_size() == sux_state->locals_size(), "locals not equal");
0N/A
0N/A int index;
0N/A Value sux_value;
0N/A for_each_stack_value(sux_state, index, sux_value) {
0N/A assert(sux_value == end_state->stack_at(index), "stack not equal");
0N/A }
0N/A for_each_local_value(sux_state, index, sux_value) {
0N/A assert(sux_value == end_state->local_at(index), "locals not equal");
0N/A }
0N/A assert(sux_state->caller_state() == end_state->caller_state(), "caller not equal");
0N/A#endif
0N/A
0N/A // find instruction before end & append first instruction of sux block
0N/A Instruction* prev = end->prev(block);
0N/A Instruction* next = sux->next();
0N/A assert(prev->as_BlockEnd() == NULL, "must not be a BlockEnd");
1739N/A prev->set_next(next);
0N/A sux->disconnect_from_graph();
0N/A block->set_end(sux->end());
0N/A // add exception handlers of deleted block, if any
0N/A for (int k = 0; k < sux->number_of_exception_handlers(); k++) {
0N/A BlockBegin* xhandler = sux->exception_handler_at(k);
0N/A block->add_exception_handler(xhandler);
0N/A
0N/A // also substitute predecessor of exception handler
0N/A assert(xhandler->is_predecessor(sux), "missing predecessor");
0N/A xhandler->remove_predecessor(sux);
0N/A if (!xhandler->is_predecessor(block)) {
0N/A xhandler->add_predecessor(block);
0N/A }
0N/A }
0N/A
0N/A // debugging output
0N/A _merge_count++;
0N/A if (PrintBlockElimination) {
0N/A tty->print_cr("%d. merged B%d & B%d (stack size = %d)",
0N/A _merge_count, block->block_id(), sux->block_id(), sux->state()->stack_size());
0N/A }
0N/A
0N/A _hir->verify();
0N/A
0N/A If* if_ = block->end()->as_If();
0N/A if (if_) {
0N/A IfOp* ifop = if_->x()->as_IfOp();
0N/A Constant* con = if_->y()->as_Constant();
0N/A bool swapped = false;
0N/A if (!con || !ifop) {
0N/A ifop = if_->y()->as_IfOp();
0N/A con = if_->x()->as_Constant();
0N/A swapped = true;
0N/A }
0N/A if (con && ifop) {
0N/A Constant* tval = ifop->tval()->as_Constant();
0N/A Constant* fval = ifop->fval()->as_Constant();
0N/A if (tval && fval) {
0N/A // Find the instruction before if_, starting with ifop.
0N/A // When if_ and ifop are not in the same block, prev
0N/A // becomes NULL In such (rare) cases it is not
0N/A // profitable to perform the optimization.
0N/A Value prev = ifop;
0N/A while (prev != NULL && prev->next() != if_) {
0N/A prev = prev->next();
0N/A }
0N/A
0N/A if (prev != NULL) {
0N/A Instruction::Condition cond = if_->cond();
0N/A BlockBegin* tsux = if_->tsux();
0N/A BlockBegin* fsux = if_->fsux();
0N/A if (swapped) {
0N/A cond = Instruction::mirror(cond);
0N/A }
0N/A
0N/A BlockBegin* tblock = tval->compare(cond, con, tsux, fsux);
0N/A BlockBegin* fblock = fval->compare(cond, con, tsux, fsux);
0N/A if (tblock != fblock && !if_->is_safepoint()) {
0N/A If* newif = new If(ifop->x(), ifop->cond(), false, ifop->y(),
0N/A tblock, fblock, if_->state_before(), if_->is_safepoint());
0N/A newif->set_state(if_->state()->copy());
0N/A
0N/A assert(prev->next() == if_, "must be guaranteed by above search");
1739N/A NOT_PRODUCT(newif->set_printable_bci(if_->printable_bci()));
1739N/A prev->set_next(newif);
0N/A block->set_end(newif);
0N/A
0N/A _merge_count++;
0N/A if (PrintBlockElimination) {
0N/A tty->print_cr("%d. replaced If and IfOp at end of B%d with single If", _merge_count, block->block_id());
0N/A }
0N/A
0N/A _hir->verify();
0N/A }
0N/A }
0N/A }
0N/A }
0N/A }
0N/A
0N/A return true;
0N/A }
0N/A }
0N/A return false;
0N/A }
0N/A
0N/A virtual void block_do(BlockBegin* block) {
0N/A _hir->verify();
0N/A // repeat since the same block may merge again
0N/A while (try_merge(block)) {
0N/A _hir->verify();
0N/A }
0N/A }
0N/A};
0N/A
0N/A
0N/Avoid Optimizer::eliminate_blocks() {
0N/A // merge blocks if possible
0N/A BlockMerger bm(ir());
0N/A}
0N/A
0N/A
0N/Aclass NullCheckEliminator;
0N/Aclass NullCheckVisitor: public InstructionVisitor {
0N/Aprivate:
0N/A NullCheckEliminator* _nce;
0N/A NullCheckEliminator* nce() { return _nce; }
0N/A
0N/Apublic:
0N/A NullCheckVisitor() {}
0N/A
0N/A void set_eliminator(NullCheckEliminator* nce) { _nce = nce; }
0N/A
0N/A void do_Phi (Phi* x);
0N/A void do_Local (Local* x);
0N/A void do_Constant (Constant* x);
0N/A void do_LoadField (LoadField* x);
0N/A void do_StoreField (StoreField* x);
0N/A void do_ArrayLength (ArrayLength* x);
0N/A void do_LoadIndexed (LoadIndexed* x);
0N/A void do_StoreIndexed (StoreIndexed* x);
0N/A void do_NegateOp (NegateOp* x);
0N/A void do_ArithmeticOp (ArithmeticOp* x);
0N/A void do_ShiftOp (ShiftOp* x);
0N/A void do_LogicOp (LogicOp* x);
0N/A void do_CompareOp (CompareOp* x);
0N/A void do_IfOp (IfOp* x);
0N/A void do_Convert (Convert* x);
0N/A void do_NullCheck (NullCheck* x);
3932N/A void do_TypeCast (TypeCast* x);
0N/A void do_Invoke (Invoke* x);
0N/A void do_NewInstance (NewInstance* x);
0N/A void do_NewTypeArray (NewTypeArray* x);
0N/A void do_NewObjectArray (NewObjectArray* x);
0N/A void do_NewMultiArray (NewMultiArray* x);
0N/A void do_CheckCast (CheckCast* x);
0N/A void do_InstanceOf (InstanceOf* x);
0N/A void do_MonitorEnter (MonitorEnter* x);
0N/A void do_MonitorExit (MonitorExit* x);
0N/A void do_Intrinsic (Intrinsic* x);
0N/A void do_BlockBegin (BlockBegin* x);
0N/A void do_Goto (Goto* x);
0N/A void do_If (If* x);
0N/A void do_IfInstanceOf (IfInstanceOf* x);
0N/A void do_TableSwitch (TableSwitch* x);
0N/A void do_LookupSwitch (LookupSwitch* x);
0N/A void do_Return (Return* x);
0N/A void do_Throw (Throw* x);
0N/A void do_Base (Base* x);
0N/A void do_OsrEntry (OsrEntry* x);
0N/A void do_ExceptionObject(ExceptionObject* x);
0N/A void do_RoundFP (RoundFP* x);
0N/A void do_UnsafeGetRaw (UnsafeGetRaw* x);
0N/A void do_UnsafePutRaw (UnsafePutRaw* x);
0N/A void do_UnsafeGetObject(UnsafeGetObject* x);
0N/A void do_UnsafePutObject(UnsafePutObject* x);
4015N/A void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x);
0N/A void do_UnsafePrefetchRead (UnsafePrefetchRead* x);
0N/A void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x);
0N/A void do_ProfileCall (ProfileCall* x);
1703N/A void do_ProfileInvoke (ProfileInvoke* x);
Error!

 

There was an error!

null

java.lang.NullPointerException