duke@435: /* duke@435: * Copyright 2005-2006 Sun Microsystems, Inc. All Rights Reserved. duke@435: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@435: * duke@435: * This code is free software; you can redistribute it and/or modify it duke@435: * under the terms of the GNU General Public License version 2 only, as duke@435: * published by the Free Software Foundation. duke@435: * duke@435: * This code is distributed in the hope that it will be useful, but WITHOUT duke@435: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@435: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@435: * version 2 for more details (a copy is included in the LICENSE file that duke@435: * accompanied this code). duke@435: * duke@435: * You should have received a copy of the GNU General Public License version duke@435: * 2 along with this work; if not, write to the Free Software Foundation, duke@435: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@435: * duke@435: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, duke@435: * CA 95054 USA or visit www.sun.com if you need additional information or duke@435: * have any questions. duke@435: * duke@435: */ duke@435: duke@435: #include "incls/_precompiled.incl" duke@435: #include "incls/_idealKit.cpp.incl" duke@435: duke@435: // Static initialization duke@435: duke@435: // This declares the position where vars are kept in the cvstate duke@435: // For some degree of consistency we use the TypeFunc enum to duke@435: // soak up spots in the inputs even though we only use early Control duke@435: // and Memory slots. (So far.) duke@435: const uint IdealKit::first_var = TypeFunc::Parms + 1; duke@435: duke@435: //----------------------------IdealKit----------------------------------------- duke@435: IdealKit::IdealKit(PhaseGVN &gvn, Node* control, Node* mem, bool delay_all_transforms) : duke@435: _gvn(gvn), C(gvn.C) { duke@435: _initial_ctrl = control; duke@435: _initial_memory = mem; duke@435: _delay_all_transforms = delay_all_transforms; duke@435: _var_ct = 0; duke@435: _cvstate = NULL; duke@435: // We can go memory state free or else we need the entire memory state duke@435: assert(mem == NULL || mem->Opcode() == Op_MergeMem, "memory must be pre-split"); duke@435: int init_size = 5; duke@435: _pending_cvstates = new (C->node_arena()) GrowableArray(C->node_arena(), init_size, 0, 0); duke@435: _delay_transform = new (C->node_arena()) GrowableArray(C->node_arena(), init_size, 0, 0); duke@435: DEBUG_ONLY(_state = new (C->node_arena()) GrowableArray(C->node_arena(), init_size, 0, 0)); duke@435: } duke@435: duke@435: //-------------------------------if_then------------------------------------- duke@435: // Create: if(left relop right) duke@435: // / \ duke@435: // iffalse iftrue duke@435: // Push the iffalse cvstate onto the stack. The iftrue becomes the current cvstate. duke@435: void IdealKit::if_then(Node* left, BoolTest::mask relop, duke@435: Node* right, float prob, float cnt, bool push_new_state) { duke@435: assert((state() & (BlockS|LoopS|IfThenS|ElseS)), "bad state for new If"); duke@435: Node* bol; duke@435: if (left->bottom_type()->isa_ptr() == NULL) { duke@435: if (left->bottom_type()->isa_int() != NULL) { duke@435: bol = Bool(CmpI(left, right), relop); duke@435: } else { duke@435: assert(left->bottom_type()->isa_long() != NULL, "what else?"); duke@435: bol = Bool(CmpL(left, right), relop); duke@435: } duke@435: duke@435: } else { duke@435: bol = Bool(CmpP(left, right), relop); duke@435: } duke@435: // Delay gvn.tranform on if-nodes until construction is finished duke@435: // to prevent a constant bool input from discarding a control output. duke@435: IfNode* iff = delay_transform(new (C, 2) IfNode(ctrl(), bol, prob, cnt))->as_If(); duke@435: Node* then = IfTrue(iff); duke@435: Node* elsen = IfFalse(iff); duke@435: Node* else_cvstate = copy_cvstate(); duke@435: else_cvstate->set_req(TypeFunc::Control, elsen); duke@435: _pending_cvstates->push(else_cvstate); duke@435: DEBUG_ONLY(if (push_new_state) _state->push(IfThenS)); duke@435: set_ctrl(then); duke@435: } duke@435: duke@435: //-------------------------------else_------------------------------------- duke@435: // Pop the else cvstate off the stack, and push the (current) then cvstate. duke@435: // The else cvstate becomes the current cvstate. duke@435: void IdealKit::else_() { duke@435: assert(state() == IfThenS, "bad state for new Else"); duke@435: Node* else_cvstate = _pending_cvstates->pop(); duke@435: DEBUG_ONLY(_state->pop()); duke@435: // save current (then) cvstate for later use at endif duke@435: _pending_cvstates->push(_cvstate); duke@435: DEBUG_ONLY(_state->push(ElseS)); duke@435: _cvstate = else_cvstate; duke@435: } duke@435: duke@435: //-------------------------------end_if------------------------------------- duke@435: // Merge the "then" and "else" cvstates. duke@435: // duke@435: // The if_then() pushed the current state for later use duke@435: // as the initial state for a future "else" clause. The duke@435: // current state then became the initial state for the duke@435: // then clause. If an "else" clause was encountered, it will duke@435: // pop the top state and use it for it's initial state. duke@435: // It will also push the current state (the state at the end of duke@435: // the "then" clause) for latter use at the end_if. duke@435: // duke@435: // At the endif, the states are: duke@435: // 1) else exists a) current state is end of "else" clause duke@435: // b) top stack state is end of "then" clause duke@435: // duke@435: // 2) no else: a) current state is end of "then" clause duke@435: // b) top stack state is from the "if_then" which duke@435: // would have been the initial state of the else. duke@435: // duke@435: // Merging the states is accomplished by: duke@435: // 1) make a label for the merge duke@435: // 2) terminate the current state with a goto to the label duke@435: // 3) pop the top state from the stack and make it the duke@435: // current state duke@435: // 4) bind the label at the current state. Binding a label duke@435: // terminates the current state with a goto to the duke@435: // label and makes the label's state the current state. duke@435: // duke@435: void IdealKit::end_if() { duke@435: assert(state() & (IfThenS|ElseS), "bad state for new Endif"); duke@435: Node* lab = make_label(1); duke@435: duke@435: // Node* join_state = _pending_cvstates->pop(); duke@435: /* merging, join */ duke@435: goto_(lab); duke@435: _cvstate = _pending_cvstates->pop(); duke@435: duke@435: bind(lab); duke@435: DEBUG_ONLY(_state->pop()); duke@435: } duke@435: duke@435: //-------------------------------loop------------------------------------- duke@435: // Create the loop head portion (*) of: duke@435: // * iv = init duke@435: // * top: (region node) duke@435: // * if (iv relop limit) { duke@435: // loop body duke@435: // i = i + 1 duke@435: // goto top duke@435: // * } else // exits loop duke@435: // duke@435: // Pushes the loop top cvstate first, then the else (loop exit) cvstate duke@435: // onto the stack. duke@435: void IdealKit::loop(IdealVariable& iv, Node* init, BoolTest::mask relop, Node* limit, float prob, float cnt) { duke@435: assert((state() & (BlockS|LoopS|IfThenS|ElseS)), "bad state for new loop"); duke@435: set(iv, init); duke@435: Node* head = make_label(1); duke@435: bind(head); duke@435: _pending_cvstates->push(head); // push for use at end_loop duke@435: _cvstate = copy_cvstate(); duke@435: if_then(value(iv), relop, limit, prob, cnt, false /* no new state */); duke@435: DEBUG_ONLY(_state->push(LoopS)); duke@435: assert(ctrl()->is_IfTrue(), "true branch stays in loop"); duke@435: assert(_pending_cvstates->top()->in(TypeFunc::Control)->is_IfFalse(), "false branch exits loop"); duke@435: } duke@435: duke@435: //-------------------------------end_loop------------------------------------- duke@435: // Creates the goto top label. duke@435: // Expects the else (loop exit) cvstate to be on top of the duke@435: // stack, and the loop top cvstate to be 2nd. duke@435: void IdealKit::end_loop() { duke@435: assert((state() == LoopS), "bad state for new end_loop"); duke@435: Node* exit = _pending_cvstates->pop(); duke@435: Node* head = _pending_cvstates->pop(); duke@435: goto_(head); duke@435: clear(head); duke@435: DEBUG_ONLY(_state->pop()); duke@435: _cvstate = exit; duke@435: } duke@435: duke@435: //-------------------------------make_label------------------------------------- duke@435: // Creates a label. The number of goto's duke@435: // must be specified (which should be 1 less than duke@435: // the number of precedessors.) duke@435: Node* IdealKit::make_label(int goto_ct) { duke@435: assert(_cvstate != NULL, "must declare variables before labels"); duke@435: Node* lab = new_cvstate(); duke@435: int sz = 1 + goto_ct + 1 /* fall thru */; duke@435: Node* reg = delay_transform(new (C, sz) RegionNode(sz)); duke@435: lab->init_req(TypeFunc::Control, reg); duke@435: return lab; duke@435: } duke@435: duke@435: //-------------------------------bind------------------------------------- duke@435: // Bind a label at the current cvstate by simulating duke@435: // a goto to the label. duke@435: void IdealKit::bind(Node* lab) { duke@435: goto_(lab, true /* bind */); duke@435: _cvstate = lab; duke@435: } duke@435: duke@435: //-------------------------------goto_------------------------------------- duke@435: // Make the current cvstate a predecessor of the label, duke@435: // creating phi's to merge values. If bind is true and duke@435: // this is not the last control edge, then ensure that duke@435: // all live values have phis created. Used to create phis duke@435: // at loop-top regions. duke@435: void IdealKit::goto_(Node* lab, bool bind) { duke@435: Node* reg = lab->in(TypeFunc::Control); duke@435: // find next empty slot in region duke@435: uint slot = 1; duke@435: while (slot < reg->req() && reg->in(slot) != NULL) slot++; duke@435: assert(slot < reg->req(), "too many gotos"); duke@435: // If this is last predecessor, then don't force phi creation duke@435: if (slot == reg->req() - 1) bind = false; duke@435: reg->init_req(slot, ctrl()); duke@435: assert(first_var + _var_ct == _cvstate->req(), "bad _cvstate size"); duke@435: for (uint i = first_var; i < _cvstate->req(); i++) { duke@435: duke@435: // l is the value of var reaching the label. Could be a single value duke@435: // reaching the label, or a phi that merges multiples values reaching duke@435: // the label. The latter is true if the label's input: in(..) is duke@435: // a phi whose control input is the region node for the label. duke@435: duke@435: Node* l = lab->in(i); duke@435: // Get the current value of the var duke@435: Node* m = _cvstate->in(i); duke@435: // If the var went unused no need for a phi duke@435: if (m == NULL) { duke@435: continue; duke@435: } else if (l == NULL || m == l) { duke@435: // Only one unique value "m" is known to reach this label so a phi duke@435: // is not yet necessary unless: duke@435: // the label is being bound and all predecessors have not been seen, duke@435: // in which case "bind" will be true. duke@435: if (bind) { duke@435: m = promote_to_phi(m, reg); duke@435: } duke@435: // Record the phi/value used for this var in the label's cvstate duke@435: lab->set_req(i, m); duke@435: } else { duke@435: // More than one value for the variable reaches this label so duke@435: // a create a phi if one does not already exist. duke@435: if (!was_promoted_to_phi(l, reg)) { duke@435: l = promote_to_phi(l, reg); duke@435: lab->set_req(i, l); duke@435: } duke@435: // Record in the phi, the var's value from the current state duke@435: l->set_req(slot, m); duke@435: } duke@435: } duke@435: do_memory_merge(_cvstate, lab); duke@435: stop(); duke@435: } duke@435: duke@435: //-----------------------------promote_to_phi----------------------------------- duke@435: Node* IdealKit::promote_to_phi(Node* n, Node* reg) { duke@435: assert(!was_promoted_to_phi(n, reg), "n already promoted to phi on this region"); duke@435: // Get a conservative type for the phi duke@435: const BasicType bt = n->bottom_type()->basic_type(); duke@435: const Type* ct = Type::get_const_basic_type(bt); duke@435: return delay_transform(PhiNode::make(reg, n, ct)); duke@435: } duke@435: duke@435: //-----------------------------declares_done----------------------------------- duke@435: void IdealKit::declares_done() { duke@435: _cvstate = new_cvstate(); // initialize current cvstate duke@435: set_ctrl(_initial_ctrl); // initialize control in current cvstate duke@435: set_all_memory(_initial_memory);// initialize memory in current cvstate duke@435: DEBUG_ONLY(_state->push(BlockS)); duke@435: } duke@435: duke@435: //-----------------------------transform----------------------------------- duke@435: Node* IdealKit::transform(Node* n) { duke@435: if (_delay_all_transforms) { duke@435: return delay_transform(n); duke@435: } else { duke@435: return gvn().transform(n); duke@435: } duke@435: } duke@435: duke@435: //-----------------------------delay_transform----------------------------------- duke@435: Node* IdealKit::delay_transform(Node* n) { duke@435: gvn().set_type(n, n->bottom_type()); duke@435: _delay_transform->push(n); duke@435: return n; duke@435: } duke@435: duke@435: //-----------------------------new_cvstate----------------------------------- duke@435: Node* IdealKit::new_cvstate() { duke@435: uint sz = _var_ct + first_var; duke@435: return new (C, sz) Node(sz); duke@435: } duke@435: duke@435: //-----------------------------copy_cvstate----------------------------------- duke@435: Node* IdealKit::copy_cvstate() { duke@435: Node* ns = new_cvstate(); duke@435: for (uint i = 0; i < ns->req(); i++) ns->init_req(i, _cvstate->in(i)); duke@435: // We must clone memory since it will be updated as we do stores. duke@435: ns->set_req(TypeFunc::Memory, MergeMemNode::make(C, ns->in(TypeFunc::Memory))); duke@435: return ns; duke@435: } duke@435: duke@435: //-----------------------------clear----------------------------------- duke@435: void IdealKit::clear(Node* m) { duke@435: for (uint i = 0; i < m->req(); i++) m->set_req(i, NULL); duke@435: } duke@435: duke@435: //-----------------------------drain_delay_transform---------------------------- duke@435: void IdealKit::drain_delay_transform() { duke@435: while (_delay_transform->length() > 0) { duke@435: Node* n = _delay_transform->pop(); duke@435: gvn().transform(n); duke@435: if (!gvn().is_IterGVN()) { duke@435: C->record_for_igvn(n); duke@435: } duke@435: } duke@435: } duke@435: duke@435: //-----------------------------IdealVariable---------------------------- duke@435: IdealVariable::IdealVariable(IdealKit &k) { duke@435: k.declare(this); duke@435: } duke@435: duke@435: Node* IdealKit::memory(uint alias_idx) { duke@435: MergeMemNode* mem = merged_memory(); duke@435: Node* p = mem->memory_at(alias_idx); duke@435: _gvn.set_type(p, Type::MEMORY); // must be mapped duke@435: return p; duke@435: } duke@435: duke@435: void IdealKit::set_memory(Node* mem, uint alias_idx) { duke@435: merged_memory()->set_memory_at(alias_idx, mem); duke@435: } duke@435: duke@435: //----------------------------- make_load ---------------------------- duke@435: Node* IdealKit::load(Node* ctl, duke@435: Node* adr, duke@435: const Type* t, duke@435: BasicType bt, duke@435: int adr_idx, duke@435: bool require_atomic_access) { duke@435: duke@435: assert(adr_idx != Compile::AliasIdxTop, "use other make_load factory" ); duke@435: const TypePtr* adr_type = NULL; // debug-mode-only argument duke@435: debug_only(adr_type = C->get_adr_type(adr_idx)); duke@435: Node* mem = memory(adr_idx); duke@435: Node* ld; duke@435: if (require_atomic_access && bt == T_LONG) { duke@435: ld = LoadLNode::make_atomic(C, ctl, mem, adr, adr_type, t); duke@435: } else { duke@435: ld = LoadNode::make(C, ctl, mem, adr, adr_type, t, bt); duke@435: } duke@435: return transform(ld); duke@435: } duke@435: duke@435: Node* IdealKit::store(Node* ctl, Node* adr, Node *val, BasicType bt, duke@435: int adr_idx, duke@435: bool require_atomic_access) { duke@435: assert(adr_idx != Compile::AliasIdxTop, "use other store_to_memory factory" ); duke@435: const TypePtr* adr_type = NULL; duke@435: debug_only(adr_type = C->get_adr_type(adr_idx)); duke@435: Node *mem = memory(adr_idx); duke@435: Node* st; duke@435: if (require_atomic_access && bt == T_LONG) { duke@435: st = StoreLNode::make_atomic(C, ctl, mem, adr, adr_type, val); duke@435: } else { duke@435: st = StoreNode::make(C, ctl, mem, adr, adr_type, val, bt); duke@435: } duke@435: st = transform(st); duke@435: set_memory(st, adr_idx); duke@435: duke@435: return st; duke@435: } duke@435: duke@435: // Card mark store. Must be ordered so that it will come after the store of duke@435: // the oop. duke@435: Node* IdealKit::storeCM(Node* ctl, Node* adr, Node *val, Node* oop_store, duke@435: BasicType bt, duke@435: int adr_idx) { duke@435: assert(adr_idx != Compile::AliasIdxTop, "use other store_to_memory factory" ); duke@435: const TypePtr* adr_type = NULL; duke@435: debug_only(adr_type = C->get_adr_type(adr_idx)); duke@435: Node *mem = memory(adr_idx); duke@435: duke@435: // Add required edge to oop_store, optimizer does not support precedence edges. duke@435: // Convert required edge to precedence edge before allocation. duke@435: Node* st = new (C, 5) StoreCMNode(ctl, mem, adr, adr_type, val, oop_store); duke@435: duke@435: st = transform(st); duke@435: set_memory(st, adr_idx); duke@435: duke@435: return st; duke@435: } duke@435: duke@435: //---------------------------- do_memory_merge -------------------------------- duke@435: // The memory from one merging cvstate needs to be merged with the memory for another duke@435: // join cvstate. If the join cvstate doesn't have a merged memory yet then we duke@435: // can just copy the state from the merging cvstate duke@435: duke@435: // Merge one slow path into the rest of memory. duke@435: void IdealKit::do_memory_merge(Node* merging, Node* join) { duke@435: duke@435: // Get the region for the join state duke@435: Node* join_region = join->in(TypeFunc::Control); duke@435: assert(join_region != NULL, "join region must exist"); duke@435: if (join->in(TypeFunc::Memory) == NULL ) { duke@435: join->set_req(TypeFunc::Memory, merging->in(TypeFunc::Memory)); duke@435: return; duke@435: } duke@435: duke@435: // The control flow for merging must have already been attached to the join region duke@435: // we need its index for the phis. duke@435: uint slot; duke@435: for (slot = 1; slot < join_region->req() ; slot ++ ) { duke@435: if (join_region->in(slot) == merging->in(TypeFunc::Control)) break; duke@435: } duke@435: assert(slot != join_region->req(), "edge must already exist"); duke@435: duke@435: MergeMemNode* join_m = join->in(TypeFunc::Memory)->as_MergeMem(); duke@435: MergeMemNode* merging_m = merging->in(TypeFunc::Memory)->as_MergeMem(); duke@435: duke@435: // join_m should be an ancestor mergemem of merging duke@435: // Slow path memory comes from the current map (which is from a slow call) duke@435: // Fast path/null path memory comes from the call's input duke@435: duke@435: // Merge the other fast-memory inputs with the new slow-default memory. duke@435: // for (MergeMemStream mms(merged_memory(), fast_mem->as_MergeMem()); mms.next_non_empty2(); ) { duke@435: for (MergeMemStream mms(join_m, merging_m); mms.next_non_empty2(); ) { duke@435: Node* join_slice = mms.force_memory(); duke@435: Node* merging_slice = mms.memory2(); duke@435: if (join_slice != merging_slice) { duke@435: PhiNode* phi; duke@435: // bool new_phi = false; duke@435: // Is the phi for this slice one that we created for this join region or simply duke@435: // one we copied? If it is ours then add duke@435: if (join_slice->is_Phi() && join_slice->as_Phi()->region() == join_region) { duke@435: phi = join_slice->as_Phi(); duke@435: } else { duke@435: // create the phi with join_slice filling supplying memory for all of the duke@435: // control edges to the join region duke@435: phi = PhiNode::make(join_region, join_slice, Type::MEMORY, mms.adr_type(C)); duke@435: phi = (PhiNode*) delay_transform(phi); duke@435: // gvn().set_type(phi, Type::MEMORY); duke@435: // new_phi = true; duke@435: } duke@435: // Now update the phi with the slice for the merging slice duke@435: phi->set_req(slot, merging_slice/* slow_path, slow_slice */); duke@435: // this updates join_m with the phi duke@435: mms.set_memory(phi); duke@435: } duke@435: } duke@435: } duke@435: duke@435: duke@435: //----------------------------- make_call ---------------------------- duke@435: // Trivial runtime call duke@435: void IdealKit::make_leaf_call(const TypeFunc *slow_call_type, duke@435: address slow_call, duke@435: const char *leaf_name, duke@435: Node* parm0, duke@435: Node* parm1, duke@435: Node* parm2) { duke@435: duke@435: // We only handle taking in RawMem and modifying RawMem duke@435: const TypePtr* adr_type = TypeRawPtr::BOTTOM; duke@435: uint adr_idx = C->get_alias_index(adr_type); duke@435: duke@435: // Clone initial memory duke@435: MergeMemNode* cloned_mem = MergeMemNode::make(C, merged_memory()); duke@435: duke@435: // Slow-path leaf call duke@435: int size = slow_call_type->domain()->cnt(); duke@435: CallNode *call = (CallNode*)new (C, size) CallLeafNode( slow_call_type, slow_call, leaf_name, adr_type); duke@435: duke@435: // Set fixed predefined input arguments duke@435: call->init_req( TypeFunc::Control, ctrl() ); duke@435: call->init_req( TypeFunc::I_O , top() ) ; // does no i/o duke@435: // Narrow memory as only memory input duke@435: call->init_req( TypeFunc::Memory , memory(adr_idx)); duke@435: call->init_req( TypeFunc::FramePtr, top() /* frameptr() */ ); duke@435: call->init_req( TypeFunc::ReturnAdr, top() ); duke@435: duke@435: if (parm0 != NULL) call->init_req(TypeFunc::Parms+0, parm0); duke@435: if (parm1 != NULL) call->init_req(TypeFunc::Parms+1, parm1); duke@435: if (parm2 != NULL) call->init_req(TypeFunc::Parms+2, parm2); duke@435: duke@435: // Node *c = _gvn.transform(call); duke@435: call = (CallNode *) _gvn.transform(call); duke@435: Node *c = call; // dbx gets confused with call call->dump() duke@435: duke@435: // Slow leaf call has no side-effects, sets few values duke@435: duke@435: set_ctrl(transform( new (C, 1) ProjNode(call,TypeFunc::Control) )); duke@435: duke@435: // Set the incoming clone of memory as current memory duke@435: set_all_memory(cloned_mem); duke@435: duke@435: // Make memory for the call duke@435: Node* mem = _gvn.transform( new (C, 1) ProjNode(call, TypeFunc::Memory) ); duke@435: duke@435: // Set the RawPtr memory state only. duke@435: set_memory(mem, adr_idx); duke@435: duke@435: assert(C->alias_type(call->adr_type()) == C->alias_type(adr_type), duke@435: "call node must be constructed correctly"); duke@435: }