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/_escape.cpp.incl"
duke@435: 
duke@435: uint PointsToNode::edge_target(uint e) const {
duke@435:   assert(_edges != NULL && e < (uint)_edges->length(), "valid edge index");
duke@435:   return (_edges->at(e) >> EdgeShift);
duke@435: }
duke@435: 
duke@435: PointsToNode::EdgeType PointsToNode::edge_type(uint e) const {
duke@435:   assert(_edges != NULL && e < (uint)_edges->length(), "valid edge index");
duke@435:   return (EdgeType) (_edges->at(e) & EdgeMask);
duke@435: }
duke@435: 
duke@435: void PointsToNode::add_edge(uint targIdx, PointsToNode::EdgeType et) {
duke@435:   uint v = (targIdx << EdgeShift) + ((uint) et);
duke@435:   if (_edges == NULL) {
duke@435:      Arena *a = Compile::current()->comp_arena();
duke@435:     _edges = new(a) GrowableArray<uint>(a, INITIAL_EDGE_COUNT, 0, 0);
duke@435:   }
duke@435:   _edges->append_if_missing(v);
duke@435: }
duke@435: 
duke@435: void PointsToNode::remove_edge(uint targIdx, PointsToNode::EdgeType et) {
duke@435:   uint v = (targIdx << EdgeShift) + ((uint) et);
duke@435: 
duke@435:   _edges->remove(v);
duke@435: }
duke@435: 
duke@435: #ifndef PRODUCT
duke@435: static char *node_type_names[] = {
duke@435:   "UnknownType",
duke@435:   "JavaObject",
duke@435:   "LocalVar",
duke@435:   "Field"
duke@435: };
duke@435: 
duke@435: static char *esc_names[] = {
duke@435:   "UnknownEscape",
duke@435:   "NoEscape     ",
duke@435:   "ArgEscape    ",
duke@435:   "GlobalEscape "
duke@435: };
duke@435: 
duke@435: static char *edge_type_suffix[] = {
duke@435:  "?", // UnknownEdge
duke@435:  "P", // PointsToEdge
duke@435:  "D", // DeferredEdge
duke@435:  "F"  // FieldEdge
duke@435: };
duke@435: 
duke@435: void PointsToNode::dump() const {
duke@435:   NodeType nt = node_type();
duke@435:   EscapeState es = escape_state();
duke@435:   tty->print("%s  %s  [[", node_type_names[(int) nt], esc_names[(int) es]);
duke@435:   for (uint i = 0; i < edge_count(); i++) {
duke@435:     tty->print(" %d%s", edge_target(i), edge_type_suffix[(int) edge_type(i)]);
duke@435:   }
duke@435:   tty->print("]]  ");
duke@435:   if (_node == NULL)
duke@435:     tty->print_cr("<null>");
duke@435:   else
duke@435:     _node->dump();
duke@435: }
duke@435: #endif
duke@435: 
duke@435: ConnectionGraph::ConnectionGraph(Compile * C) : _processed(C->comp_arena()), _node_map(C->comp_arena()) {
duke@435:   _collecting = true;
duke@435:   this->_compile = C;
duke@435:   const PointsToNode &dummy = PointsToNode();
duke@435:   _nodes = new(C->comp_arena()) GrowableArray<PointsToNode>(C->comp_arena(), (int) INITIAL_NODE_COUNT, 0, dummy);
duke@435:   _phantom_object = C->top()->_idx;
duke@435:   PointsToNode *phn = ptnode_adr(_phantom_object);
duke@435:   phn->set_node_type(PointsToNode::JavaObject);
duke@435:   phn->set_escape_state(PointsToNode::GlobalEscape);
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) {
duke@435:   PointsToNode *f = ptnode_adr(from_i);
duke@435:   PointsToNode *t = ptnode_adr(to_i);
duke@435: 
duke@435:   assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");
duke@435:   assert(f->node_type() == PointsToNode::LocalVar || f->node_type() == PointsToNode::Field, "invalid source of PointsTo edge");
duke@435:   assert(t->node_type() == PointsToNode::JavaObject, "invalid destination of PointsTo edge");
duke@435:   f->add_edge(to_i, PointsToNode::PointsToEdge);
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::add_deferred_edge(uint from_i, uint to_i) {
duke@435:   PointsToNode *f = ptnode_adr(from_i);
duke@435:   PointsToNode *t = ptnode_adr(to_i);
duke@435: 
duke@435:   assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");
duke@435:   assert(f->node_type() == PointsToNode::LocalVar || f->node_type() == PointsToNode::Field, "invalid source of Deferred edge");
duke@435:   assert(t->node_type() == PointsToNode::LocalVar || t->node_type() == PointsToNode::Field, "invalid destination of Deferred edge");
duke@435:   // don't add a self-referential edge, this can occur during removal of
duke@435:   // deferred edges
duke@435:   if (from_i != to_i)
duke@435:     f->add_edge(to_i, PointsToNode::DeferredEdge);
duke@435: }
duke@435: 
duke@435: int ConnectionGraph::type_to_offset(const Type *t) {
duke@435:   const TypePtr *t_ptr = t->isa_ptr();
duke@435:   assert(t_ptr != NULL, "must be a pointer type");
duke@435:   return t_ptr->offset();
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::add_field_edge(uint from_i, uint to_i, int offset) {
duke@435:   PointsToNode *f = ptnode_adr(from_i);
duke@435:   PointsToNode *t = ptnode_adr(to_i);
duke@435: 
duke@435:   assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");
duke@435:   assert(f->node_type() == PointsToNode::JavaObject, "invalid destination of Field edge");
duke@435:   assert(t->node_type() == PointsToNode::Field, "invalid destination of Field edge");
duke@435:   assert (t->offset() == -1 || t->offset() == offset, "conflicting field offsets");
duke@435:   t->set_offset(offset);
duke@435: 
duke@435:   f->add_edge(to_i, PointsToNode::FieldEdge);
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::set_escape_state(uint ni, PointsToNode::EscapeState es) {
duke@435:   PointsToNode *npt = ptnode_adr(ni);
duke@435:   PointsToNode::EscapeState old_es = npt->escape_state();
duke@435:   if (es > old_es)
duke@435:     npt->set_escape_state(es);
duke@435: }
duke@435: 
duke@435: PointsToNode::EscapeState ConnectionGraph::escape_state(Node *n, PhaseTransform *phase) {
duke@435:   uint idx = n->_idx;
duke@435:   PointsToNode::EscapeState es;
duke@435: 
duke@435:   // If we are still collecting we don't know the answer yet
duke@435:   if (_collecting)
duke@435:     return PointsToNode::UnknownEscape;
duke@435: 
duke@435:   // if the node was created after the escape computation, return
duke@435:   // UnknownEscape
duke@435:   if (idx >= (uint)_nodes->length())
duke@435:     return PointsToNode::UnknownEscape;
duke@435: 
duke@435:   es = _nodes->at_grow(idx).escape_state();
duke@435: 
duke@435:   // if we have already computed a value, return it
duke@435:   if (es != PointsToNode::UnknownEscape)
duke@435:     return es;
duke@435: 
duke@435:   // compute max escape state of anything this node could point to
duke@435:   VectorSet ptset(Thread::current()->resource_area());
duke@435:   PointsTo(ptset, n, phase);
duke@435:   for( VectorSetI i(&ptset); i.test() && es != PointsToNode::GlobalEscape; ++i ) {
duke@435:     uint pt = i.elem;
duke@435:     PointsToNode::EscapeState pes = _nodes->at(pt).escape_state();
duke@435:     if (pes > es)
duke@435:       es = pes;
duke@435:   }
duke@435:   // cache the computed escape state
duke@435:   assert(es != PointsToNode::UnknownEscape, "should have computed an escape state");
duke@435:   _nodes->adr_at(idx)->set_escape_state(es);
duke@435:   return es;
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase) {
duke@435:   VectorSet visited(Thread::current()->resource_area());
duke@435:   GrowableArray<uint>  worklist;
duke@435: 
duke@435:   n = skip_casts(n);
duke@435:   PointsToNode  npt = _nodes->at_grow(n->_idx);
duke@435: 
duke@435:   // If we have a JavaObject, return just that object
duke@435:   if (npt.node_type() == PointsToNode::JavaObject) {
duke@435:     ptset.set(n->_idx);
duke@435:     return;
duke@435:   }
duke@435:   // we may have a Phi which has not been processed
duke@435:   if (npt._node == NULL) {
duke@435:     assert(n->is_Phi(), "unprocessed node must be a Phi");
duke@435:     record_for_escape_analysis(n);
duke@435:     npt = _nodes->at(n->_idx);
duke@435:   }
duke@435:   worklist.push(n->_idx);
duke@435:   while(worklist.length() > 0) {
duke@435:     int ni = worklist.pop();
duke@435:     PointsToNode pn = _nodes->at_grow(ni);
duke@435:     if (!visited.test(ni)) {
duke@435:       visited.set(ni);
duke@435: 
duke@435:       // ensure that all inputs of a Phi have been processed
duke@435:       if (_collecting && pn._node->is_Phi()) {
duke@435:         PhiNode *phi = pn._node->as_Phi();
duke@435:         process_phi_escape(phi, phase);
duke@435:       }
duke@435: 
duke@435:       int edges_processed = 0;
duke@435:       for (uint e = 0; e < pn.edge_count(); e++) {
duke@435:         PointsToNode::EdgeType et = pn.edge_type(e);
duke@435:         if (et == PointsToNode::PointsToEdge) {
duke@435:           ptset.set(pn.edge_target(e));
duke@435:           edges_processed++;
duke@435:         } else if (et == PointsToNode::DeferredEdge) {
duke@435:           worklist.push(pn.edge_target(e));
duke@435:           edges_processed++;
duke@435:         }
duke@435:       }
duke@435:       if (edges_processed == 0) {
duke@435:         // no deferred or pointsto edges found.  Assume the value was set outside
duke@435:         // this method.  Add the phantom object to the pointsto set.
duke@435:         ptset.set(_phantom_object);
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::remove_deferred(uint ni) {
duke@435:   VectorSet visited(Thread::current()->resource_area());
duke@435: 
duke@435:   uint i = 0;
duke@435:   PointsToNode *ptn = ptnode_adr(ni);
duke@435: 
duke@435:   while(i < ptn->edge_count()) {
duke@435:     if (ptn->edge_type(i) != PointsToNode::DeferredEdge) {
duke@435:       i++;
duke@435:     } else {
duke@435:       uint t = ptn->edge_target(i);
duke@435:       PointsToNode *ptt = ptnode_adr(t);
duke@435:       ptn->remove_edge(t, PointsToNode::DeferredEdge);
duke@435:       if(!visited.test(t)) {
duke@435:         visited.set(t);
duke@435:         for (uint j = 0; j < ptt->edge_count(); j++) {
duke@435:           uint n1 = ptt->edge_target(j);
duke@435:           PointsToNode *pt1 = ptnode_adr(n1);
duke@435:           switch(ptt->edge_type(j)) {
duke@435:             case PointsToNode::PointsToEdge:
duke@435:                add_pointsto_edge(ni, n1);
duke@435:               break;
duke@435:             case PointsToNode::DeferredEdge:
duke@435:               add_deferred_edge(ni, n1);
duke@435:               break;
duke@435:             case PointsToNode::FieldEdge:
duke@435:               assert(false, "invalid connection graph");
duke@435:               break;
duke@435:           }
duke@435:         }
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: 
duke@435: //  Add an edge to node given by "to_i" from any field of adr_i whose offset
duke@435: //  matches "offset"  A deferred edge is added if to_i is a LocalVar, and
duke@435: //  a pointsto edge is added if it is a JavaObject
duke@435: 
duke@435: void ConnectionGraph::add_edge_from_fields(uint adr_i, uint to_i, int offs) {
duke@435:   PointsToNode an = _nodes->at_grow(adr_i);
duke@435:   PointsToNode to = _nodes->at_grow(to_i);
duke@435:   bool deferred = (to.node_type() == PointsToNode::LocalVar);
duke@435: 
duke@435:   for (uint fe = 0; fe < an.edge_count(); fe++) {
duke@435:     assert(an.edge_type(fe) == PointsToNode::FieldEdge, "expecting a field edge");
duke@435:     int fi = an.edge_target(fe);
duke@435:     PointsToNode pf = _nodes->at_grow(fi);
duke@435:     int po = pf.offset();
duke@435:     if (po == offs || po == Type::OffsetBot || offs == Type::OffsetBot) {
duke@435:       if (deferred)
duke@435:         add_deferred_edge(fi, to_i);
duke@435:       else
duke@435:         add_pointsto_edge(fi, to_i);
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: //  Add a deferred  edge from node given by "from_i" to any field of adr_i whose offset
duke@435: //  matches "offset"
duke@435: void ConnectionGraph::add_deferred_edge_to_fields(uint from_i, uint adr_i, int offs) {
duke@435:   PointsToNode an = _nodes->at_grow(adr_i);
duke@435:   for (uint fe = 0; fe < an.edge_count(); fe++) {
duke@435:     assert(an.edge_type(fe) == PointsToNode::FieldEdge, "expecting a field edge");
duke@435:     int fi = an.edge_target(fe);
duke@435:     PointsToNode pf = _nodes->at_grow(fi);
duke@435:     int po = pf.offset();
duke@435:     if (pf.edge_count() == 0) {
duke@435:       // we have not seen any stores to this field, assume it was set outside this method
duke@435:       add_pointsto_edge(fi, _phantom_object);
duke@435:     }
duke@435:     if (po == offs || po == Type::OffsetBot || offs == Type::OffsetBot) {
duke@435:       add_deferred_edge(from_i, fi);
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: //
duke@435: // Search memory chain of "mem" to find a MemNode whose address
duke@435: // is the specified alias index.  Returns the MemNode found or the
duke@435: // first non-MemNode encountered.
duke@435: //
duke@435: Node *ConnectionGraph::find_mem(Node *mem, int alias_idx, PhaseGVN  *igvn) {
duke@435:   if (mem == NULL)
duke@435:     return mem;
duke@435:   while (mem->is_Mem()) {
duke@435:     const Type *at = igvn->type(mem->in(MemNode::Address));
duke@435:     if (at != Type::TOP) {
duke@435:       assert (at->isa_ptr() != NULL, "pointer type required.");
duke@435:       int idx = _compile->get_alias_index(at->is_ptr());
duke@435:       if (idx == alias_idx)
duke@435:         break;
duke@435:     }
duke@435:     mem = mem->in(MemNode::Memory);
duke@435:   }
duke@435:   return mem;
duke@435: }
duke@435: 
duke@435: //
duke@435: // Adjust the type and inputs of an AddP which computes the
duke@435: // address of a field of an instance
duke@435: //
duke@435: void ConnectionGraph::split_AddP(Node *addp, Node *base,  PhaseGVN  *igvn) {
duke@435:   const TypeOopPtr *t = igvn->type(addp)->isa_oopptr();
duke@435:   const TypeOopPtr *base_t = igvn->type(base)->isa_oopptr();
duke@435:   assert(t != NULL,  "expecting oopptr");
duke@435:   assert(base_t != NULL && base_t->is_instance(), "expecting instance oopptr");
duke@435:   uint inst_id =  base_t->instance_id();
duke@435:   assert(!t->is_instance() || t->instance_id() == inst_id,
duke@435:                              "old type must be non-instance or match new type");
duke@435:   const TypeOopPtr *tinst = base_t->add_offset(t->offset())->is_oopptr();
duke@435:   // ensure an alias index is allocated for the instance type
duke@435:   int alias_idx = _compile->get_alias_index(tinst);
duke@435:   igvn->set_type(addp, tinst);
duke@435:   // record the allocation in the node map
duke@435:   set_map(addp->_idx, get_map(base->_idx));
duke@435:   // if the Address input is not the appropriate instance type (due to intervening
duke@435:   // casts,) insert a cast
duke@435:   Node *adr = addp->in(AddPNode::Address);
duke@435:   const TypeOopPtr  *atype = igvn->type(adr)->isa_oopptr();
duke@435:   if (atype->instance_id() != inst_id) {
duke@435:     assert(!atype->is_instance(), "no conflicting instances");
duke@435:     const TypeOopPtr *new_atype = base_t->add_offset(atype->offset())->isa_oopptr();
duke@435:     Node *acast = new (_compile, 2) CastPPNode(adr, new_atype);
duke@435:     acast->set_req(0, adr->in(0));
duke@435:     igvn->set_type(acast, new_atype);
duke@435:     record_for_optimizer(acast);
duke@435:     Node *bcast = acast;
duke@435:     Node *abase = addp->in(AddPNode::Base);
duke@435:     if (abase != adr) {
duke@435:       bcast = new (_compile, 2) CastPPNode(abase, base_t);
duke@435:       bcast->set_req(0, abase->in(0));
duke@435:       igvn->set_type(bcast, base_t);
duke@435:       record_for_optimizer(bcast);
duke@435:     }
duke@435:     igvn->hash_delete(addp);
duke@435:     addp->set_req(AddPNode::Base, bcast);
duke@435:     addp->set_req(AddPNode::Address, acast);
duke@435:     igvn->hash_insert(addp);
duke@435:     record_for_optimizer(addp);
duke@435:   }
duke@435: }
duke@435: 
duke@435: //
duke@435: // Create a new version of orig_phi if necessary. Returns either the newly
duke@435: // created phi or an existing phi.  Sets create_new to indicate wheter  a new
duke@435: // phi was created.  Cache the last newly created phi in the node map.
duke@435: //
duke@435: PhiNode *ConnectionGraph::create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn, bool &new_created) {
duke@435:   Compile *C = _compile;
duke@435:   new_created = false;
duke@435:   int phi_alias_idx = C->get_alias_index(orig_phi->adr_type());
duke@435:   // nothing to do if orig_phi is bottom memory or matches alias_idx
duke@435:   if (phi_alias_idx == Compile::AliasIdxBot || phi_alias_idx == alias_idx) {
duke@435:     return orig_phi;
duke@435:   }
duke@435:   // have we already created a Phi for this alias index?
duke@435:   PhiNode *result = get_map_phi(orig_phi->_idx);
duke@435:   const TypePtr *atype = C->get_adr_type(alias_idx);
duke@435:   if (result != NULL && C->get_alias_index(result->adr_type()) == alias_idx) {
duke@435:     return result;
duke@435:   }
kvn@473:   if ((int)C->unique() + 2*NodeLimitFudgeFactor > MaxNodeLimit) {
kvn@473:     if (C->do_escape_analysis() == true && !C->failing()) {
kvn@473:       // Retry compilation without escape analysis.
kvn@473:       // If this is the first failure, the sentinel string will "stick"
kvn@473:       // to the Compile object, and the C2Compiler will see it and retry.
kvn@473:       C->record_failure(C2Compiler::retry_no_escape_analysis());
kvn@473:     }
kvn@473:     return NULL;
kvn@473:   }
duke@435: 
duke@435:   orig_phi_worklist.append_if_missing(orig_phi);
duke@435:   result = PhiNode::make(orig_phi->in(0), NULL, Type::MEMORY, atype);
duke@435:   set_map_phi(orig_phi->_idx, result);
duke@435:   igvn->set_type(result, result->bottom_type());
duke@435:   record_for_optimizer(result);
duke@435:   new_created = true;
duke@435:   return result;
duke@435: }
duke@435: 
duke@435: //
duke@435: // Return a new version  of Memory Phi "orig_phi" with the inputs having the
duke@435: // specified alias index.
duke@435: //
duke@435: PhiNode *ConnectionGraph::split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn) {
duke@435: 
duke@435:   assert(alias_idx != Compile::AliasIdxBot, "can't split out bottom memory");
duke@435:   Compile *C = _compile;
duke@435:   bool new_phi_created;
duke@435:   PhiNode *result =  create_split_phi(orig_phi, alias_idx, orig_phi_worklist, igvn, new_phi_created);
duke@435:   if (!new_phi_created) {
duke@435:     return result;
duke@435:   }
duke@435: 
duke@435:   GrowableArray<PhiNode *>  phi_list;
duke@435:   GrowableArray<uint>  cur_input;
duke@435: 
duke@435:   PhiNode *phi = orig_phi;
duke@435:   uint idx = 1;
duke@435:   bool finished = false;
duke@435:   while(!finished) {
duke@435:     while (idx < phi->req()) {
duke@435:       Node *mem = find_mem(phi->in(idx), alias_idx, igvn);
duke@435:       if (mem != NULL && mem->is_Phi()) {
duke@435:         PhiNode *nphi = create_split_phi(mem->as_Phi(), alias_idx, orig_phi_worklist, igvn, new_phi_created);
duke@435:         if (new_phi_created) {
duke@435:           // found an phi for which we created a new split, push current one on worklist and begin
duke@435:           // processing new one
duke@435:           phi_list.push(phi);
duke@435:           cur_input.push(idx);
duke@435:           phi = mem->as_Phi();
duke@435:           result = nphi;
duke@435:           idx = 1;
duke@435:           continue;
duke@435:         } else {
duke@435:           mem = nphi;
duke@435:         }
duke@435:       }
kvn@473:       if (C->failing()) {
kvn@473:         return NULL;
kvn@473:       }
duke@435:       result->set_req(idx++, mem);
duke@435:     }
duke@435: #ifdef ASSERT
duke@435:     // verify that the new Phi has an input for each input of the original
duke@435:     assert( phi->req() == result->req(), "must have same number of inputs.");
duke@435:     assert( result->in(0) != NULL && result->in(0) == phi->in(0), "regions must match");
duke@435:     for (uint i = 1; i < phi->req(); i++) {
duke@435:       assert((phi->in(i) == NULL) == (result->in(i) == NULL), "inputs must correspond.");
duke@435:     }
duke@435: #endif
duke@435:     // we have finished processing a Phi, see if there are any more to do
duke@435:     finished = (phi_list.length() == 0 );
duke@435:     if (!finished) {
duke@435:       phi = phi_list.pop();
duke@435:       idx = cur_input.pop();
duke@435:       PhiNode *prev_phi = get_map_phi(phi->_idx);
duke@435:       prev_phi->set_req(idx++, result);
duke@435:       result = prev_phi;
duke@435:     }
duke@435:   }
duke@435:   return result;
duke@435: }
duke@435: 
duke@435: //
duke@435: //  Convert the types of unescaped object to instance types where possible,
duke@435: //  propagate the new type information through the graph, and update memory
duke@435: //  edges and MergeMem inputs to reflect the new type.
duke@435: //
duke@435: //  We start with allocations (and calls which may be allocations)  on alloc_worklist.
duke@435: //  The processing is done in 4 phases:
duke@435: //
duke@435: //  Phase 1:  Process possible allocations from alloc_worklist.  Create instance
duke@435: //            types for the CheckCastPP for allocations where possible.
duke@435: //            Propagate the the new types through users as follows:
duke@435: //               casts and Phi:  push users on alloc_worklist
duke@435: //               AddP:  cast Base and Address inputs to the instance type
duke@435: //                      push any AddP users on alloc_worklist and push any memnode
duke@435: //                      users onto memnode_worklist.
duke@435: //  Phase 2:  Process MemNode's from memnode_worklist. compute new address type and
duke@435: //            search the Memory chain for a store with the appropriate type
duke@435: //            address type.  If a Phi is found, create a new version with
duke@435: //            the approriate memory slices from each of the Phi inputs.
duke@435: //            For stores, process the users as follows:
duke@435: //               MemNode:  push on memnode_worklist
duke@435: //               MergeMem: push on mergemem_worklist
duke@435: //  Phase 3:  Process MergeMem nodes from mergemem_worklist.  Walk each memory slice
duke@435: //            moving the first node encountered of each  instance type to the
duke@435: //            the input corresponding to its alias index.
duke@435: //            appropriate memory slice.
duke@435: //  Phase 4:  Update the inputs of non-instance memory Phis and the Memory input of memnodes.
duke@435: //
duke@435: // In the following example, the CheckCastPP nodes are the cast of allocation
duke@435: // results and the allocation of node 29 is unescaped and eligible to be an
duke@435: // instance type.
duke@435: //
duke@435: // We start with:
duke@435: //
duke@435: //     7 Parm #memory
duke@435: //    10  ConI  "12"
duke@435: //    19  CheckCastPP   "Foo"
duke@435: //    20  AddP  _ 19 19 10  Foo+12  alias_index=4
duke@435: //    29  CheckCastPP   "Foo"
duke@435: //    30  AddP  _ 29 29 10  Foo+12  alias_index=4
duke@435: //
duke@435: //    40  StoreP  25   7  20   ... alias_index=4
duke@435: //    50  StoreP  35  40  30   ... alias_index=4
duke@435: //    60  StoreP  45  50  20   ... alias_index=4
duke@435: //    70  LoadP    _  60  30   ... alias_index=4
duke@435: //    80  Phi     75  50  60   Memory alias_index=4
duke@435: //    90  LoadP    _  80  30   ... alias_index=4
duke@435: //   100  LoadP    _  80  20   ... alias_index=4
duke@435: //
duke@435: //
duke@435: // Phase 1 creates an instance type for node 29 assigning it an instance id of 24
duke@435: // and creating a new alias index for node 30.  This gives:
duke@435: //
duke@435: //     7 Parm #memory
duke@435: //    10  ConI  "12"
duke@435: //    19  CheckCastPP   "Foo"
duke@435: //    20  AddP  _ 19 19 10  Foo+12  alias_index=4
duke@435: //    29  CheckCastPP   "Foo"  iid=24
duke@435: //    30  AddP  _ 29 29 10  Foo+12  alias_index=6  iid=24
duke@435: //
duke@435: //    40  StoreP  25   7  20   ... alias_index=4
duke@435: //    50  StoreP  35  40  30   ... alias_index=6
duke@435: //    60  StoreP  45  50  20   ... alias_index=4
duke@435: //    70  LoadP    _  60  30   ... alias_index=6
duke@435: //    80  Phi     75  50  60   Memory alias_index=4
duke@435: //    90  LoadP    _  80  30   ... alias_index=6
duke@435: //   100  LoadP    _  80  20   ... alias_index=4
duke@435: //
duke@435: // In phase 2, new memory inputs are computed for the loads and stores,
duke@435: // And a new version of the phi is created.  In phase 4, the inputs to
duke@435: // node 80 are updated and then the memory nodes are updated with the
duke@435: // values computed in phase 2.  This results in:
duke@435: //
duke@435: //     7 Parm #memory
duke@435: //    10  ConI  "12"
duke@435: //    19  CheckCastPP   "Foo"
duke@435: //    20  AddP  _ 19 19 10  Foo+12  alias_index=4
duke@435: //    29  CheckCastPP   "Foo"  iid=24
duke@435: //    30  AddP  _ 29 29 10  Foo+12  alias_index=6  iid=24
duke@435: //
duke@435: //    40  StoreP  25  7   20   ... alias_index=4
duke@435: //    50  StoreP  35  7   30   ... alias_index=6
duke@435: //    60  StoreP  45  40  20   ... alias_index=4
duke@435: //    70  LoadP    _  50  30   ... alias_index=6
duke@435: //    80  Phi     75  40  60   Memory alias_index=4
duke@435: //   120  Phi     75  50  50   Memory alias_index=6
duke@435: //    90  LoadP    _ 120  30   ... alias_index=6
duke@435: //   100  LoadP    _  80  20   ... alias_index=4
duke@435: //
duke@435: void ConnectionGraph::split_unique_types(GrowableArray<Node *>  &alloc_worklist) {
duke@435:   GrowableArray<Node *>  memnode_worklist;
duke@435:   GrowableArray<Node *>  mergemem_worklist;
duke@435:   GrowableArray<PhiNode *>  orig_phis;
duke@435:   PhaseGVN  *igvn = _compile->initial_gvn();
duke@435:   uint new_index_start = (uint) _compile->num_alias_types();
duke@435:   VectorSet visited(Thread::current()->resource_area());
duke@435:   VectorSet ptset(Thread::current()->resource_area());
duke@435: 
duke@435:   //  Phase 1:  Process possible allocations from alloc_worklist.  Create instance
duke@435:   //            types for the CheckCastPP for allocations where possible.
duke@435:   while (alloc_worklist.length() != 0) {
duke@435:     Node *n = alloc_worklist.pop();
duke@435:     uint ni = n->_idx;
duke@435:     if (n->is_Call()) {
duke@435:       CallNode *alloc = n->as_Call();
duke@435:       // copy escape information to call node
duke@435:       PointsToNode ptn = _nodes->at(alloc->_idx);
duke@435:       PointsToNode::EscapeState es = escape_state(alloc, igvn);
duke@435:       alloc->_escape_state = es;
duke@435:       // find CheckCastPP of call return value
duke@435:       n = alloc->proj_out(TypeFunc::Parms);
duke@435:       if (n != NULL && n->outcnt() == 1) {
duke@435:         n = n->unique_out();
duke@435:         if (n->Opcode() != Op_CheckCastPP) {
duke@435:           continue;
duke@435:         }
duke@435:       } else {
duke@435:         continue;
duke@435:       }
duke@435:       // we have an allocation or call which returns a Java object, see if it is unescaped
duke@435:       if (es != PointsToNode::NoEscape || !ptn._unique_type) {
duke@435:         continue; //  can't make a unique type
duke@435:       }
kvn@474:       if (alloc->is_Allocate()) {
kvn@474:         // Set the scalar_replaceable flag before the next check.
kvn@474:         alloc->as_Allocate()->_is_scalar_replaceable = true;
kvn@474:       }
kvn@474: 
duke@435:       set_map(alloc->_idx, n);
duke@435:       set_map(n->_idx, alloc);
duke@435:       const TypeInstPtr *t = igvn->type(n)->isa_instptr();
duke@435:       // Unique types which are arrays are not currently supported.
duke@435:       // The check for AllocateArray is needed in case an array
duke@435:       // allocation is immediately cast to Object
duke@435:       if (t == NULL || alloc->is_AllocateArray())
duke@435:         continue;  // not a TypeInstPtr
duke@435:       const TypeOopPtr *tinst = t->cast_to_instance(ni);
duke@435:       igvn->hash_delete(n);
duke@435:       igvn->set_type(n,  tinst);
duke@435:       n->raise_bottom_type(tinst);
duke@435:       igvn->hash_insert(n);
duke@435:     } else if (n->is_AddP()) {
duke@435:       ptset.Clear();
duke@435:       PointsTo(ptset, n->in(AddPNode::Address), igvn);
duke@435:       assert(ptset.Size() == 1, "AddP address is unique");
duke@435:       Node *base = get_map(ptset.getelem());
duke@435:       split_AddP(n, base, igvn);
duke@435:     } else if (n->is_Phi() || n->Opcode() == Op_CastPP || n->Opcode() == Op_CheckCastPP) {
duke@435:       if (visited.test_set(n->_idx)) {
duke@435:         assert(n->is_Phi(), "loops only through Phi's");
duke@435:         continue;  // already processed
duke@435:       }
duke@435:       ptset.Clear();
duke@435:       PointsTo(ptset, n, igvn);
duke@435:       if (ptset.Size() == 1) {
duke@435:         TypeNode *tn = n->as_Type();
duke@435:         Node *val = get_map(ptset.getelem());
duke@435:         const TypeInstPtr *val_t = igvn->type(val)->isa_instptr();;
duke@435:         assert(val_t != NULL && val_t->is_instance(), "instance type expected.");
duke@435:         const TypeInstPtr *tn_t = igvn->type(tn)->isa_instptr();;
duke@435: 
duke@435:         if (tn_t != NULL && val_t->cast_to_instance(TypeOopPtr::UNKNOWN_INSTANCE)->higher_equal(tn_t)) {
duke@435:           igvn->hash_delete(tn);
duke@435:           igvn->set_type(tn, val_t);
duke@435:           tn->set_type(val_t);
duke@435:           igvn->hash_insert(tn);
duke@435:         }
duke@435:       }
duke@435:     } else {
duke@435:       continue;
duke@435:     }
duke@435:     // push users on appropriate worklist
duke@435:     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
duke@435:       Node *use = n->fast_out(i);
duke@435:       if(use->is_Mem() && use->in(MemNode::Address) == n) {
duke@435:         memnode_worklist.push(use);
duke@435:       } else if (use->is_AddP() || use->is_Phi() || use->Opcode() == Op_CastPP || use->Opcode() == Op_CheckCastPP) {
duke@435:         alloc_worklist.push(use);
duke@435:       }
duke@435:     }
duke@435: 
duke@435:   }
duke@435:   uint new_index_end = (uint) _compile->num_alias_types();
duke@435: 
duke@435:   //  Phase 2:  Process MemNode's from memnode_worklist. compute new address type and
duke@435:   //            compute new values for Memory inputs  (the Memory inputs are not
duke@435:   //            actually updated until phase 4.)
duke@435:   if (memnode_worklist.length() == 0)
duke@435:     return;  // nothing to do
duke@435: 
duke@435: 
duke@435:   while (memnode_worklist.length() != 0) {
duke@435:     Node *n = memnode_worklist.pop();
duke@435:     if (n->is_Phi()) {
duke@435:       assert(n->as_Phi()->adr_type() != TypePtr::BOTTOM, "narrow memory slice required");
duke@435:       // we don't need to do anything, but the users must be pushed if we haven't processed
duke@435:       // this Phi before
duke@435:       if (visited.test_set(n->_idx))
duke@435:         continue;
duke@435:     } else {
duke@435:       assert(n->is_Mem(), "memory node required.");
duke@435:       Node *addr = n->in(MemNode::Address);
duke@435:       const Type *addr_t = igvn->type(addr);
duke@435:       if (addr_t == Type::TOP)
duke@435:         continue;
duke@435:       assert (addr_t->isa_ptr() != NULL, "pointer type required.");
duke@435:       int alias_idx = _compile->get_alias_index(addr_t->is_ptr());
duke@435:       Node *mem = find_mem(n->in(MemNode::Memory), alias_idx, igvn);
duke@435:       if (mem->is_Phi()) {
duke@435:         mem = split_memory_phi(mem->as_Phi(), alias_idx, orig_phis, igvn);
duke@435:       }
kvn@473:       if (_compile->failing()) {
kvn@473:         return;
kvn@473:       }
duke@435:       if (mem != n->in(MemNode::Memory))
duke@435:         set_map(n->_idx, mem);
duke@435:       if (n->is_Load()) {
duke@435:         continue;  // don't push users
duke@435:       } else if (n->is_LoadStore()) {
duke@435:         // get the memory projection
duke@435:         for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
duke@435:           Node *use = n->fast_out(i);
duke@435:           if (use->Opcode() == Op_SCMemProj) {
duke@435:             n = use;
duke@435:             break;
duke@435:           }
duke@435:         }
duke@435:         assert(n->Opcode() == Op_SCMemProj, "memory projection required");
duke@435:       }
duke@435:     }
duke@435:     // push user on appropriate worklist
duke@435:     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
duke@435:       Node *use = n->fast_out(i);
duke@435:       if (use->is_Phi()) {
duke@435:         memnode_worklist.push(use);
duke@435:       } else if(use->is_Mem() && use->in(MemNode::Memory) == n) {
duke@435:         memnode_worklist.push(use);
duke@435:       } else if (use->is_MergeMem()) {
duke@435:         mergemem_worklist.push(use);
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: 
duke@435:   //  Phase 3:  Process MergeMem nodes from mergemem_worklist.  Walk each memory slice
duke@435:   //            moving the first node encountered of each  instance type to the
duke@435:   //            the input corresponding to its alias index.
duke@435:   while (mergemem_worklist.length() != 0) {
duke@435:     Node *n = mergemem_worklist.pop();
duke@435:     assert(n->is_MergeMem(), "MergeMem node required.");
duke@435:     MergeMemNode *nmm = n->as_MergeMem();
duke@435:     // Note: we don't want to use MergeMemStream here because we only want to
duke@435:     //       scan inputs which exist at the start, not ones we add during processing
duke@435:     uint nslices = nmm->req();
duke@435:     igvn->hash_delete(nmm);
duke@435:     for (uint i = Compile::AliasIdxRaw+1; i < nslices; i++) {
duke@435:       Node * mem = nmm->in(i);
duke@435:       Node * cur = NULL;
duke@435:       if (mem == NULL || mem->is_top())
duke@435:         continue;
duke@435:       while (mem->is_Mem()) {
duke@435:         const Type *at = igvn->type(mem->in(MemNode::Address));
duke@435:         if (at != Type::TOP) {
duke@435:           assert (at->isa_ptr() != NULL, "pointer type required.");
duke@435:           uint idx = (uint)_compile->get_alias_index(at->is_ptr());
duke@435:           if (idx == i) {
duke@435:             if (cur == NULL)
duke@435:               cur = mem;
duke@435:           } else {
duke@435:             if (idx >= nmm->req() || nmm->is_empty_memory(nmm->in(idx))) {
duke@435:               nmm->set_memory_at(idx, mem);
duke@435:             }
duke@435:           }
duke@435:         }
duke@435:         mem = mem->in(MemNode::Memory);
duke@435:       }
duke@435:       nmm->set_memory_at(i, (cur != NULL) ? cur : mem);
duke@435:       if (mem->is_Phi()) {
duke@435:         // We have encountered a Phi, we need to split the Phi for
duke@435:         // any  instance of the current type if we haven't encountered
duke@435:         //  a value of the instance along the chain.
duke@435:         for (uint ni = new_index_start; ni < new_index_end; ni++) {
duke@435:           if((uint)_compile->get_general_index(ni) == i) {
duke@435:             Node *m = (ni >= nmm->req()) ? nmm->empty_memory() : nmm->in(ni);
duke@435:             if (nmm->is_empty_memory(m)) {
kvn@473:               m = split_memory_phi(mem->as_Phi(), ni, orig_phis, igvn);
kvn@473:               if (_compile->failing()) {
kvn@473:                 return;
kvn@473:               }
kvn@473:               nmm->set_memory_at(ni, m);
duke@435:             }
duke@435:           }
duke@435:         }
duke@435:       }
duke@435:     }
duke@435:     igvn->hash_insert(nmm);
duke@435:     record_for_optimizer(nmm);
duke@435:   }
duke@435: 
duke@435:   //  Phase 4:  Update the inputs of non-instance memory Phis and the Memory input of memnodes
duke@435:   //
duke@435:   // First update the inputs of any non-instance Phi's from
duke@435:   // which we split out an instance Phi.  Note we don't have
duke@435:   // to recursively process Phi's encounted on the input memory
duke@435:   // chains as is done in split_memory_phi() since they  will
duke@435:   // also be processed here.
duke@435:   while (orig_phis.length() != 0) {
duke@435:     PhiNode *phi = orig_phis.pop();
duke@435:     int alias_idx = _compile->get_alias_index(phi->adr_type());
duke@435:     igvn->hash_delete(phi);
duke@435:     for (uint i = 1; i < phi->req(); i++) {
duke@435:       Node *mem = phi->in(i);
duke@435:       Node *new_mem = find_mem(mem, alias_idx, igvn);
duke@435:       if (mem != new_mem) {
duke@435:         phi->set_req(i, new_mem);
duke@435:       }
duke@435:     }
duke@435:     igvn->hash_insert(phi);
duke@435:     record_for_optimizer(phi);
duke@435:   }
duke@435: 
duke@435:   // Update the memory inputs of MemNodes with the value we computed
duke@435:   // in Phase 2.
duke@435:   for (int i = 0; i < _nodes->length(); i++) {
duke@435:     Node *nmem = get_map(i);
duke@435:     if (nmem != NULL) {
duke@435:       Node *n = _nodes->at(i)._node;
duke@435:       if (n != NULL && n->is_Mem()) {
duke@435:         igvn->hash_delete(n);
duke@435:         n->set_req(MemNode::Memory, nmem);
duke@435:         igvn->hash_insert(n);
duke@435:         record_for_optimizer(n);
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::compute_escape() {
duke@435:   GrowableArray<int>  worklist;
duke@435:   GrowableArray<Node *>  alloc_worklist;
duke@435:   VectorSet visited(Thread::current()->resource_area());
duke@435:   PhaseGVN  *igvn = _compile->initial_gvn();
duke@435: 
duke@435:   // process Phi nodes from the deferred list, they may not have
duke@435:   while(_deferred.size() > 0) {
duke@435:     Node * n = _deferred.pop();
duke@435:     PhiNode * phi = n->as_Phi();
duke@435: 
duke@435:     process_phi_escape(phi, igvn);
duke@435:   }
duke@435: 
duke@435:   VectorSet ptset(Thread::current()->resource_area());
duke@435: 
duke@435:   // remove deferred edges from the graph and collect
duke@435:   // information we will need for type splitting
duke@435:   for (uint ni = 0; ni < (uint)_nodes->length(); ni++) {
duke@435:     PointsToNode * ptn = _nodes->adr_at(ni);
duke@435:     PointsToNode::NodeType nt = ptn->node_type();
duke@435: 
duke@435:     if (nt == PointsToNode::UnknownType) {
duke@435:       continue;  // not a node we are interested in
duke@435:     }
duke@435:     Node *n = ptn->_node;
duke@435:     if (nt == PointsToNode::LocalVar || nt == PointsToNode::Field) {
duke@435:       remove_deferred(ni);
duke@435:       if (n->is_AddP()) {
duke@435:         // if this AddP computes an address which may point to more that one
duke@435:         // object, nothing the address points to can be a unique type.
duke@435:         Node *base = n->in(AddPNode::Base);
duke@435:         ptset.Clear();
duke@435:         PointsTo(ptset, base, igvn);
duke@435:         if (ptset.Size() > 1) {
duke@435:           for( VectorSetI j(&ptset); j.test(); ++j ) {
duke@435:             PointsToNode *ptaddr = _nodes->adr_at(j.elem);
duke@435:             ptaddr->_unique_type = false;
duke@435:           }
duke@435:         }
duke@435:       }
duke@435:     } else if (n->is_Call()) {
duke@435:         // initialize _escape_state of calls to GlobalEscape
duke@435:         n->as_Call()->_escape_state = PointsToNode::GlobalEscape;
duke@435:         // push call on alloc_worlist (alocations are calls)
duke@435:         // for processing by split_unique_types()
duke@435:         alloc_worklist.push(n);
duke@435:     }
duke@435:   }
duke@435:   // push all GlobalEscape nodes on the worklist
duke@435:   for (uint nj = 0; nj < (uint)_nodes->length(); nj++) {
duke@435:     if (_nodes->at(nj).escape_state() == PointsToNode::GlobalEscape) {
duke@435:       worklist.append(nj);
duke@435:     }
duke@435:   }
duke@435:   // mark all node reachable from GlobalEscape nodes
duke@435:   while(worklist.length() > 0) {
duke@435:     PointsToNode n = _nodes->at(worklist.pop());
duke@435:     for (uint ei = 0; ei < n.edge_count(); ei++) {
duke@435:       uint npi = n.edge_target(ei);
duke@435:       PointsToNode *np = ptnode_adr(npi);
duke@435:       if (np->escape_state() != PointsToNode::GlobalEscape) {
duke@435:         np->set_escape_state(PointsToNode::GlobalEscape);
duke@435:         worklist.append_if_missing(npi);
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: 
duke@435:   // push all ArgEscape nodes on the worklist
duke@435:   for (uint nk = 0; nk < (uint)_nodes->length(); nk++) {
duke@435:     if (_nodes->at(nk).escape_state() == PointsToNode::ArgEscape)
duke@435:       worklist.push(nk);
duke@435:   }
duke@435:   // mark all node reachable from ArgEscape nodes
duke@435:   while(worklist.length() > 0) {
duke@435:     PointsToNode n = _nodes->at(worklist.pop());
duke@435: 
duke@435:     for (uint ei = 0; ei < n.edge_count(); ei++) {
duke@435:       uint npi = n.edge_target(ei);
duke@435:       PointsToNode *np = ptnode_adr(npi);
duke@435:       if (np->escape_state() != PointsToNode::ArgEscape) {
duke@435:         np->set_escape_state(PointsToNode::ArgEscape);
duke@435:         worklist.append_if_missing(npi);
duke@435:       }
duke@435:     }
duke@435:   }
duke@435:   _collecting = false;
duke@435: 
duke@435:   // Now use the escape information to create unique types for
duke@435:   // unescaped objects
duke@435:   split_unique_types(alloc_worklist);
kvn@473:   if (_compile->failing())  return;
kvn@473: 
kvn@473:   // Clean up after split unique types.
kvn@473:   ResourceMark rm;
kvn@473:   PhaseRemoveUseless pru(_compile->initial_gvn(), _compile->for_igvn());
duke@435: }
duke@435: 
duke@435: Node * ConnectionGraph::skip_casts(Node *n) {
duke@435:   while(n->Opcode() == Op_CastPP || n->Opcode() == Op_CheckCastPP) {
duke@435:     n = n->in(1);
duke@435:   }
duke@435:   return n;
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::process_phi_escape(PhiNode *phi, PhaseTransform *phase) {
duke@435: 
duke@435:   if (phi->type()->isa_oopptr() == NULL)
duke@435:     return;  // nothing to do if not an oop
duke@435: 
duke@435:   PointsToNode *ptadr = ptnode_adr(phi->_idx);
duke@435:   int incount = phi->req();
duke@435:   int non_null_inputs = 0;
duke@435: 
duke@435:   for (int i = 1; i < incount ; i++) {
duke@435:     if (phi->in(i) != NULL)
duke@435:       non_null_inputs++;
duke@435:   }
duke@435:   if (non_null_inputs == ptadr->_inputs_processed)
duke@435:     return;  // no new inputs since the last time this node was processed,
duke@435:              // the current information is valid
duke@435: 
duke@435:   ptadr->_inputs_processed = non_null_inputs;  // prevent recursive processing of this node
duke@435:   for (int j = 1; j < incount ; j++) {
duke@435:     Node * n = phi->in(j);
duke@435:     if (n == NULL)
duke@435:       continue;  // ignore NULL
duke@435:     n =  skip_casts(n);
duke@435:     if (n->is_top() || n == phi)
duke@435:       continue;  // ignore top or inputs which go back this node
duke@435:     int nopc = n->Opcode();
duke@435:     PointsToNode  npt = _nodes->at(n->_idx);
duke@435:     if (_nodes->at(n->_idx).node_type() == PointsToNode::JavaObject) {
duke@435:       add_pointsto_edge(phi->_idx, n->_idx);
duke@435:     } else {
duke@435:       add_deferred_edge(phi->_idx, n->_idx);
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::process_call_arguments(CallNode *call, PhaseTransform *phase) {
duke@435: 
duke@435:     _processed.set(call->_idx);
duke@435:     switch (call->Opcode()) {
duke@435: 
duke@435:     // arguments to allocation and locking don't escape
duke@435:     case Op_Allocate:
duke@435:     case Op_AllocateArray:
duke@435:     case Op_Lock:
duke@435:     case Op_Unlock:
duke@435:       break;
duke@435: 
duke@435:     case Op_CallStaticJava:
duke@435:     // For a static call, we know exactly what method is being called.
duke@435:     // Use bytecode estimator to record the call's escape affects
duke@435:     {
duke@435:       ciMethod *meth = call->as_CallJava()->method();
duke@435:       if (meth != NULL) {
duke@435:         const TypeTuple * d = call->tf()->domain();
duke@435:         BCEscapeAnalyzer call_analyzer(meth);
duke@435:         VectorSet ptset(Thread::current()->resource_area());
duke@435:         for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
duke@435:           const Type* at = d->field_at(i);
duke@435:           int k = i - TypeFunc::Parms;
duke@435: 
duke@435:           if (at->isa_oopptr() != NULL) {
duke@435:             Node *arg = skip_casts(call->in(i));
duke@435: 
duke@435:             if (!call_analyzer.is_arg_stack(k)) {
duke@435:               // The argument global escapes, mark everything it could point to
duke@435:               ptset.Clear();
duke@435:               PointsTo(ptset, arg, phase);
duke@435:               for( VectorSetI j(&ptset); j.test(); ++j ) {
duke@435:                 uint pt = j.elem;
duke@435: 
duke@435:                 set_escape_state(pt, PointsToNode::GlobalEscape);
duke@435:               }
duke@435:             } else if (!call_analyzer.is_arg_local(k)) {
duke@435:               // The argument itself doesn't escape, but any fields might
duke@435:               ptset.Clear();
duke@435:               PointsTo(ptset, arg, phase);
duke@435:               for( VectorSetI j(&ptset); j.test(); ++j ) {
duke@435:                 uint pt = j.elem;
duke@435:                 add_edge_from_fields(pt, _phantom_object, Type::OffsetBot);
duke@435:               }
duke@435:             }
duke@435:           }
duke@435:         }
duke@435:         call_analyzer.copy_dependencies(C()->dependencies());
duke@435:         break;
duke@435:       }
duke@435:       // fall-through if not a Java method
duke@435:     }
duke@435: 
duke@435:     default:
duke@435:     // Some other type of call, assume the worst case: all arguments
duke@435:     // globally escape.
duke@435:     {
duke@435:       // adjust escape state for  outgoing arguments
duke@435:       const TypeTuple * d = call->tf()->domain();
duke@435:       VectorSet ptset(Thread::current()->resource_area());
duke@435:       for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
duke@435:         const Type* at = d->field_at(i);
duke@435: 
duke@435:         if (at->isa_oopptr() != NULL) {
duke@435:           Node *arg = skip_casts(call->in(i));
duke@435:           ptset.Clear();
duke@435:           PointsTo(ptset, arg, phase);
duke@435:           for( VectorSetI j(&ptset); j.test(); ++j ) {
duke@435:             uint pt = j.elem;
duke@435: 
duke@435:             set_escape_state(pt, PointsToNode::GlobalEscape);
duke@435:           }
duke@435:         }
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: void ConnectionGraph::process_call_result(ProjNode *resproj, PhaseTransform *phase) {
duke@435:   CallNode *call = resproj->in(0)->as_Call();
duke@435: 
duke@435:   PointsToNode *ptadr = ptnode_adr(resproj->_idx);
duke@435: 
duke@435:   ptadr->_node = resproj;
duke@435:   ptadr->set_node_type(PointsToNode::LocalVar);
duke@435:   set_escape_state(resproj->_idx, PointsToNode::UnknownEscape);
duke@435:   _processed.set(resproj->_idx);
duke@435: 
duke@435:   switch (call->Opcode()) {
duke@435:     case Op_Allocate:
duke@435:     {
duke@435:       Node *k = call->in(AllocateNode::KlassNode);
duke@435:       const TypeKlassPtr *kt;
duke@435:       if (k->Opcode() == Op_LoadKlass) {
duke@435:         kt = k->as_Load()->type()->isa_klassptr();
duke@435:       } else {
duke@435:         kt = k->as_Type()->type()->isa_klassptr();
duke@435:       }
duke@435:       assert(kt != NULL, "TypeKlassPtr  required.");
duke@435:       ciKlass* cik = kt->klass();
duke@435:       ciInstanceKlass* ciik = cik->as_instance_klass();
duke@435: 
duke@435:       PointsToNode *ptadr = ptnode_adr(call->_idx);
duke@435:       ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:       if (cik->is_subclass_of(_compile->env()->Thread_klass()) || ciik->has_finalizer()) {
duke@435:         set_escape_state(call->_idx, PointsToNode::GlobalEscape);
duke@435:         add_pointsto_edge(resproj->_idx, _phantom_object);
duke@435:       } else {
duke@435:         set_escape_state(call->_idx, PointsToNode::NoEscape);
duke@435:         add_pointsto_edge(resproj->_idx, call->_idx);
duke@435:       }
duke@435:       _processed.set(call->_idx);
duke@435:       break;
duke@435:     }
duke@435: 
duke@435:     case Op_AllocateArray:
duke@435:     {
duke@435:       PointsToNode *ptadr = ptnode_adr(call->_idx);
duke@435:       ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:       set_escape_state(call->_idx, PointsToNode::NoEscape);
duke@435:       _processed.set(call->_idx);
duke@435:       add_pointsto_edge(resproj->_idx, call->_idx);
duke@435:       break;
duke@435:     }
duke@435: 
duke@435:     case Op_Lock:
duke@435:     case Op_Unlock:
duke@435:       break;
duke@435: 
duke@435:     case Op_CallStaticJava:
duke@435:     // For a static call, we know exactly what method is being called.
duke@435:     // Use bytecode estimator to record whether the call's return value escapes
duke@435:     {
duke@435:       const TypeTuple *r = call->tf()->range();
duke@435:       const Type* ret_type = NULL;
duke@435: 
duke@435:       if (r->cnt() > TypeFunc::Parms)
duke@435:         ret_type = r->field_at(TypeFunc::Parms);
duke@435: 
duke@435:       // Note:  we use isa_ptr() instead of isa_oopptr()  here because the
duke@435:       //        _multianewarray functions return a TypeRawPtr.
duke@435:       if (ret_type == NULL || ret_type->isa_ptr() == NULL)
duke@435:         break;  // doesn't return a pointer type
duke@435: 
duke@435:       ciMethod *meth = call->as_CallJava()->method();
duke@435:       if (meth == NULL) {
duke@435:         // not a Java method, assume global escape
duke@435:         set_escape_state(call->_idx, PointsToNode::GlobalEscape);
duke@435:         if (resproj != NULL)
duke@435:           add_pointsto_edge(resproj->_idx, _phantom_object);
duke@435:       } else {
duke@435:         BCEscapeAnalyzer call_analyzer(meth);
duke@435:         VectorSet ptset(Thread::current()->resource_area());
duke@435: 
duke@435:         if (call_analyzer.is_return_local() && resproj != NULL) {
duke@435:           // determine whether any arguments are returned
duke@435:           const TypeTuple * d = call->tf()->domain();
duke@435:           set_escape_state(call->_idx, PointsToNode::NoEscape);
duke@435:           for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
duke@435:             const Type* at = d->field_at(i);
duke@435: 
duke@435:             if (at->isa_oopptr() != NULL) {
duke@435:               Node *arg = skip_casts(call->in(i));
duke@435: 
duke@435:               if (call_analyzer.is_arg_returned(i - TypeFunc::Parms)) {
duke@435:                 PointsToNode *arg_esp = _nodes->adr_at(arg->_idx);
duke@435:                 if (arg_esp->node_type() == PointsToNode::JavaObject)
duke@435:                   add_pointsto_edge(resproj->_idx, arg->_idx);
duke@435:                 else
duke@435:                   add_deferred_edge(resproj->_idx, arg->_idx);
duke@435:                 arg_esp->_hidden_alias = true;
duke@435:               }
duke@435:             }
duke@435:           }
duke@435:         } else {
duke@435:           set_escape_state(call->_idx, PointsToNode::GlobalEscape);
duke@435:           if (resproj != NULL)
duke@435:             add_pointsto_edge(resproj->_idx, _phantom_object);
duke@435:         }
duke@435:         call_analyzer.copy_dependencies(C()->dependencies());
duke@435:       }
duke@435:       break;
duke@435:     }
duke@435: 
duke@435:     default:
duke@435:     // Some other type of call, assume the worst case that the
duke@435:     // returned value, if any, globally escapes.
duke@435:     {
duke@435:       const TypeTuple *r = call->tf()->range();
duke@435: 
duke@435:       if (r->cnt() > TypeFunc::Parms) {
duke@435:         const Type* ret_type = r->field_at(TypeFunc::Parms);
duke@435: 
duke@435:         // Note:  we use isa_ptr() instead of isa_oopptr()  here because the
duke@435:         //        _multianewarray functions return a TypeRawPtr.
duke@435:         if (ret_type->isa_ptr() != NULL) {
duke@435:           PointsToNode *ptadr = ptnode_adr(call->_idx);
duke@435:           ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:           set_escape_state(call->_idx, PointsToNode::GlobalEscape);
duke@435:           if (resproj != NULL)
duke@435:             add_pointsto_edge(resproj->_idx, _phantom_object);
duke@435:         }
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::record_for_escape_analysis(Node *n) {
duke@435:   if (_collecting) {
duke@435:     if (n->is_Phi()) {
duke@435:       PhiNode *phi = n->as_Phi();
duke@435:       const Type *pt = phi->type();
duke@435:       if ((pt->isa_oopptr() != NULL) || pt == TypePtr::NULL_PTR) {
duke@435:         PointsToNode *ptn = ptnode_adr(phi->_idx);
duke@435:         ptn->set_node_type(PointsToNode::LocalVar);
duke@435:         ptn->_node = n;
duke@435:         _deferred.push(n);
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::record_escape_work(Node *n, PhaseTransform *phase) {
duke@435: 
duke@435:   int opc = n->Opcode();
duke@435:   PointsToNode *ptadr = ptnode_adr(n->_idx);
duke@435: 
duke@435:   if (_processed.test(n->_idx))
duke@435:     return;
duke@435: 
duke@435:   ptadr->_node = n;
duke@435:   if (n->is_Call()) {
duke@435:     CallNode *call = n->as_Call();
duke@435:     process_call_arguments(call, phase);
duke@435:     return;
duke@435:   }
duke@435: 
duke@435:   switch (opc) {
duke@435:     case Op_AddP:
duke@435:     {
duke@435:       Node *base = skip_casts(n->in(AddPNode::Base));
duke@435:       ptadr->set_node_type(PointsToNode::Field);
duke@435: 
duke@435:       // create a field edge to this node from everything adr could point to
duke@435:       VectorSet ptset(Thread::current()->resource_area());
duke@435:       PointsTo(ptset, base, phase);
duke@435:       for( VectorSetI i(&ptset); i.test(); ++i ) {
duke@435:         uint pt = i.elem;
duke@435:         add_field_edge(pt, n->_idx, type_to_offset(phase->type(n)));
duke@435:       }
duke@435:       break;
duke@435:     }
duke@435:     case Op_Parm:
duke@435:     {
duke@435:       ProjNode *nproj = n->as_Proj();
duke@435:       uint con = nproj->_con;
duke@435:       if (con < TypeFunc::Parms)
duke@435:         return;
duke@435:       const Type *t = nproj->in(0)->as_Start()->_domain->field_at(con);
duke@435:       if (t->isa_ptr() == NULL)
duke@435:         return;
duke@435:       ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:       if (t->isa_oopptr() != NULL) {
duke@435:         set_escape_state(n->_idx, PointsToNode::ArgEscape);
duke@435:       } else {
duke@435:         // this must be the incoming state of an OSR compile, we have to assume anything
duke@435:         // passed in globally escapes
duke@435:         assert(_compile->is_osr_compilation(), "bad argument type for non-osr compilation");
duke@435:         set_escape_state(n->_idx, PointsToNode::GlobalEscape);
duke@435:       }
duke@435:       _processed.set(n->_idx);
duke@435:       break;
duke@435:     }
duke@435:     case Op_Phi:
duke@435:     {
duke@435:       PhiNode *phi = n->as_Phi();
duke@435:       if (phi->type()->isa_oopptr() == NULL)
duke@435:         return;  // nothing to do if not an oop
duke@435:       ptadr->set_node_type(PointsToNode::LocalVar);
duke@435:       process_phi_escape(phi, phase);
duke@435:       break;
duke@435:     }
duke@435:     case Op_CreateEx:
duke@435:     {
duke@435:       // assume that all exception objects globally escape
duke@435:       ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:       set_escape_state(n->_idx, PointsToNode::GlobalEscape);
duke@435:       _processed.set(n->_idx);
duke@435:       break;
duke@435:     }
duke@435:     case Op_ConP:
duke@435:     {
duke@435:       const Type *t = phase->type(n);
duke@435:       ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:       // assume all pointer constants globally escape except for null
duke@435:       if (t == TypePtr::NULL_PTR)
duke@435:         set_escape_state(n->_idx, PointsToNode::NoEscape);
duke@435:       else
duke@435:         set_escape_state(n->_idx, PointsToNode::GlobalEscape);
duke@435:       _processed.set(n->_idx);
duke@435:       break;
duke@435:     }
duke@435:     case Op_LoadKlass:
duke@435:     {
duke@435:       ptadr->set_node_type(PointsToNode::JavaObject);
duke@435:       set_escape_state(n->_idx, PointsToNode::GlobalEscape);
duke@435:       _processed.set(n->_idx);
duke@435:       break;
duke@435:     }
duke@435:     case Op_LoadP:
duke@435:     {
duke@435:       const Type *t = phase->type(n);
duke@435:       if (!t->isa_oopptr())
duke@435:         return;
duke@435:       ptadr->set_node_type(PointsToNode::LocalVar);
duke@435:       set_escape_state(n->_idx, PointsToNode::UnknownEscape);
duke@435: 
duke@435:       Node *adr = skip_casts(n->in(MemNode::Address));
duke@435:       const Type *adr_type = phase->type(adr);
duke@435:       Node *adr_base = skip_casts((adr->Opcode() == Op_AddP) ? adr->in(AddPNode::Base) : adr);
duke@435: 
duke@435:       // For everything "adr" could point to, create a deferred edge from
duke@435:       // this node to each field with the same offset as "adr_type"
duke@435:       VectorSet ptset(Thread::current()->resource_area());
duke@435:       PointsTo(ptset, adr_base, phase);
duke@435:       // If ptset is empty, then this value must have been set outside
duke@435:       // this method, so we add the phantom node
duke@435:       if (ptset.Size() == 0)
duke@435:         ptset.set(_phantom_object);
duke@435:       for( VectorSetI i(&ptset); i.test(); ++i ) {
duke@435:         uint pt = i.elem;
duke@435:         add_deferred_edge_to_fields(n->_idx, pt, type_to_offset(adr_type));
duke@435:       }
duke@435:       break;
duke@435:     }
duke@435:     case Op_StoreP:
duke@435:     case Op_StorePConditional:
duke@435:     case Op_CompareAndSwapP:
duke@435:     {
duke@435:       Node *adr = n->in(MemNode::Address);
duke@435:       Node *val = skip_casts(n->in(MemNode::ValueIn));
duke@435:       const Type *adr_type = phase->type(adr);
duke@435:       if (!adr_type->isa_oopptr())
duke@435:         return;
duke@435: 
duke@435:       assert(adr->Opcode() == Op_AddP, "expecting an AddP");
duke@435:       Node *adr_base = adr->in(AddPNode::Base);
duke@435: 
duke@435:       // For everything "adr_base" could point to, create a deferred edge to "val" from each field
duke@435:       // with the same offset as "adr_type"
duke@435:       VectorSet ptset(Thread::current()->resource_area());
duke@435:       PointsTo(ptset, adr_base, phase);
duke@435:       for( VectorSetI i(&ptset); i.test(); ++i ) {
duke@435:         uint pt = i.elem;
duke@435:         add_edge_from_fields(pt, val->_idx, type_to_offset(adr_type));
duke@435:       }
duke@435:       break;
duke@435:     }
duke@435:     case Op_Proj:
duke@435:     {
duke@435:       ProjNode *nproj = n->as_Proj();
duke@435:       Node *n0 = nproj->in(0);
duke@435:       // we are only interested in the result projection from a call
duke@435:       if (nproj->_con == TypeFunc::Parms && n0->is_Call() ) {
duke@435:         process_call_result(nproj, phase);
duke@435:       }
duke@435: 
duke@435:       break;
duke@435:     }
duke@435:     case Op_CastPP:
duke@435:     case Op_CheckCastPP:
duke@435:     {
duke@435:       ptadr->set_node_type(PointsToNode::LocalVar);
duke@435:       int ti = n->in(1)->_idx;
duke@435:       if (_nodes->at(ti).node_type() == PointsToNode::JavaObject) {
duke@435:         add_pointsto_edge(n->_idx, ti);
duke@435:       } else {
duke@435:         add_deferred_edge(n->_idx, ti);
duke@435:       }
duke@435:       break;
duke@435:     }
duke@435:     default:
duke@435:       ;
duke@435:       // nothing to do
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ConnectionGraph::record_escape(Node *n, PhaseTransform *phase) {
duke@435:   if (_collecting)
duke@435:     record_escape_work(n, phase);
duke@435: }
duke@435: 
duke@435: #ifndef PRODUCT
duke@435: void ConnectionGraph::dump() {
duke@435:   PhaseGVN  *igvn = _compile->initial_gvn();
duke@435:   bool first = true;
duke@435: 
duke@435:   for (uint ni = 0; ni < (uint)_nodes->length(); ni++) {
duke@435:     PointsToNode *esp = _nodes->adr_at(ni);
duke@435:     if (esp->node_type() == PointsToNode::UnknownType || esp->_node == NULL)
duke@435:       continue;
duke@435:     PointsToNode::EscapeState es = escape_state(esp->_node, igvn);
duke@435:     if (es == PointsToNode::NoEscape || (Verbose &&
duke@435:             (es != PointsToNode::UnknownEscape || esp->edge_count() != 0))) {
duke@435:       // don't print null pointer node which almost every method has
duke@435:       if (esp->_node->Opcode() != Op_ConP || igvn->type(esp->_node) != TypePtr::NULL_PTR) {
duke@435:         if (first) {
duke@435:           tty->print("======== Connection graph for ");
duke@435:           C()->method()->print_short_name();
duke@435:           tty->cr();
duke@435:           first = false;
duke@435:         }
duke@435:         tty->print("%4d  ", ni);
duke@435:         esp->dump();
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: #endif