1 /*
   2  * Copyright 2005-2008 Sun Microsystems, Inc.  All Rights Reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  20  * CA 95054 USA or visit www.sun.com if you need additional information or
  21  * have any questions.
  22  *
  23  */
  24 
  25 #include "incls/_precompiled.incl"
  26 #include "incls/_idealKit.cpp.incl"
  27 
  28 // Static initialization
  29 
  30 // This declares the position where vars are kept in the cvstate
  31 // For some degree of consistency we use the TypeFunc enum to
  32 // soak up spots in the inputs even though we only use early Control
  33 // and Memory slots. (So far.)
  34 const uint IdealKit::first_var = TypeFunc::Parms + 1;
  35 
  36 //----------------------------IdealKit-----------------------------------------
  37 IdealKit::IdealKit(PhaseGVN &gvn, Node* control, Node* mem, bool delay_all_transforms, bool has_declarations) :
  38   _gvn(gvn), C(gvn.C) {
  39   _initial_ctrl = control;
  40   _initial_memory = mem;
  41   _delay_all_transforms = delay_all_transforms;
  42   _var_ct = 0;
  43   _cvstate = NULL;
  44   // We can go memory state free or else we need the entire memory state
  45   assert(mem == NULL || mem->Opcode() == Op_MergeMem, "memory must be pre-split");
  46   int init_size = 5;
  47   _pending_cvstates = new (C->node_arena()) GrowableArray<Node*>(C->node_arena(), init_size, 0, 0);
  48   _delay_transform  = new (C->node_arena()) GrowableArray<Node*>(C->node_arena(), init_size, 0, 0);
  49   DEBUG_ONLY(_state = new (C->node_arena()) GrowableArray<int>(C->node_arena(), init_size, 0, 0));
  50   if (!has_declarations) {
  51      declarations_done();
  52   }
  53 }
  54 
  55 //-------------------------------if_then-------------------------------------
  56 // Create:  if(left relop right)
  57 //          /  \
  58 //   iffalse    iftrue
  59 // Push the iffalse cvstate onto the stack. The iftrue becomes the current cvstate.
  60 void IdealKit::if_then(Node* left, BoolTest::mask relop,
  61                        Node* right, float prob, float cnt, bool push_new_state) {
  62   assert((state() & (BlockS|LoopS|IfThenS|ElseS)), "bad state for new If");
  63   Node* bol;
  64   if (left->bottom_type()->isa_ptr() == NULL) {
  65     if (left->bottom_type()->isa_int() != NULL) {
  66       bol = Bool(CmpI(left, right), relop);
  67     } else {
  68       assert(left->bottom_type()->isa_long() != NULL, "what else?");
  69       bol = Bool(CmpL(left, right), relop);
  70     }
  71 
  72   } else {
  73     bol = Bool(CmpP(left, right), relop);
  74   }
  75   // Delay gvn.tranform on if-nodes until construction is finished
  76   // to prevent a constant bool input from discarding a control output.
  77   IfNode* iff = delay_transform(new (C, 2) IfNode(ctrl(), bol, prob, cnt))->as_If();
  78   Node* then  = IfTrue(iff);
  79   Node* elsen = IfFalse(iff);
  80   Node* else_cvstate = copy_cvstate();
  81   else_cvstate->set_req(TypeFunc::Control, elsen);
  82   _pending_cvstates->push(else_cvstate);
  83   DEBUG_ONLY(if (push_new_state) _state->push(IfThenS));
  84   set_ctrl(then);
  85 }
  86 
  87 //-------------------------------else_-------------------------------------
  88 // Pop the else cvstate off the stack, and push the (current) then cvstate.
  89 // The else cvstate becomes the current cvstate.
  90 void IdealKit::else_() {
  91   assert(state() == IfThenS, "bad state for new Else");
  92   Node* else_cvstate = _pending_cvstates->pop();
  93   DEBUG_ONLY(_state->pop());
  94   // save current (then) cvstate for later use at endif
  95   _pending_cvstates->push(_cvstate);
  96   DEBUG_ONLY(_state->push(ElseS));
  97   _cvstate = else_cvstate;
  98 }
  99 
 100 //-------------------------------end_if-------------------------------------
 101 // Merge the "then" and "else" cvstates.
 102 //
 103 // The if_then() pushed a copy of the current state for later use
 104 // as the initial state for a future "else" clause.  The
 105 // current state then became the initial state for the
 106 // then clause.  If an "else" clause was encountered, it will
 107 // pop the top state and use it for it's initial state.
 108 // It will also push the current state (the state at the end of
 109 // the "then" clause) for latter use at the end_if.
 110 //
 111 // At the endif, the states are:
 112 // 1) else exists a) current state is end of "else" clause
 113 //                b) top stack state is end of "then" clause
 114 //
 115 // 2) no else:    a) current state is end of "then" clause
 116 //                b) top stack state is from the "if_then" which
 117 //                   would have been the initial state of the else.
 118 //
 119 // Merging the states is accomplished by:
 120 //   1) make a label for the merge
 121 //   2) terminate the current state with a goto to the label
 122 //   3) pop the top state from the stack and make it the
 123 //        current state
 124 //   4) bind the label at the current state.  Binding a label
 125 //        terminates the current state with a goto to the
 126 //        label and makes the label's state the current state.
 127 //
 128 void IdealKit::end_if() {
 129   assert(state() & (IfThenS|ElseS), "bad state for new Endif");
 130   Node* lab = make_label(1);
 131 
 132   // Node* join_state = _pending_cvstates->pop();
 133                   /* merging, join */
 134   goto_(lab);
 135   _cvstate = _pending_cvstates->pop();
 136 
 137   bind(lab);
 138   DEBUG_ONLY(_state->pop());
 139 }
 140 
 141 //-------------------------------loop-------------------------------------
 142 // Create the loop head portion (*) of:
 143 //  *     iv = init
 144 //  *  top: (region node)
 145 //  *     if (iv relop limit) {
 146 //           loop body
 147 //           i = i + 1
 148 //           goto top
 149 //  *     } else // exits loop
 150 //
 151 // Pushes the loop top cvstate first, then the else (loop exit) cvstate
 152 // onto the stack.
 153 void IdealKit::loop(IdealVariable& iv, Node* init, BoolTest::mask relop, Node* limit, float prob, float cnt) {
 154   assert((state() & (BlockS|LoopS|IfThenS|ElseS)), "bad state for new loop");
 155   set(iv, init);
 156   Node* head = make_label(1);
 157   bind(head);
 158   _pending_cvstates->push(head); // push for use at end_loop
 159   _cvstate = copy_cvstate();
 160   if_then(value(iv), relop, limit, prob, cnt, false /* no new state */);
 161   DEBUG_ONLY(_state->push(LoopS));
 162   assert(ctrl()->is_IfTrue(), "true branch stays in loop");
 163   assert(_pending_cvstates->top()->in(TypeFunc::Control)->is_IfFalse(), "false branch exits loop");
 164 }
 165 
 166 //-------------------------------end_loop-------------------------------------
 167 // Creates the goto top label.
 168 // Expects the else (loop exit) cvstate to be on top of the
 169 // stack, and the loop top cvstate to be 2nd.
 170 void IdealKit::end_loop() {
 171   assert((state() == LoopS), "bad state for new end_loop");
 172   Node* exit = _pending_cvstates->pop();
 173   Node* head = _pending_cvstates->pop();
 174   goto_(head);
 175   clear(head);
 176   DEBUG_ONLY(_state->pop());
 177   _cvstate = exit;
 178 }
 179 
 180 //-------------------------------make_label-------------------------------------
 181 // Creates a label.  The number of goto's
 182 // must be specified (which should be 1 less than
 183 // the number of precedessors.)
 184 Node* IdealKit::make_label(int goto_ct) {
 185   assert(_cvstate != NULL, "must declare variables before labels");
 186   Node* lab = new_cvstate();
 187   int sz = 1 + goto_ct + 1 /* fall thru */;
 188   Node* reg = delay_transform(new (C, sz) RegionNode(sz));
 189   lab->init_req(TypeFunc::Control, reg);
 190   return lab;
 191 }
 192 
 193 //-------------------------------bind-------------------------------------
 194 // Bind a label at the current cvstate by simulating
 195 // a goto to the label.
 196 void IdealKit::bind(Node* lab) {
 197   goto_(lab, true /* bind */);
 198   _cvstate = lab;
 199 }
 200 
 201 //-------------------------------goto_-------------------------------------
 202 // Make the current cvstate a predecessor of the label,
 203 // creating phi's to merge values.  If bind is true and
 204 // this is not the last control edge, then ensure that
 205 // all live values have phis created. Used to create phis
 206 // at loop-top regions.
 207 void IdealKit::goto_(Node* lab, bool bind) {
 208   Node* reg = lab->in(TypeFunc::Control);
 209   // find next empty slot in region
 210   uint slot = 1;
 211   while (slot < reg->req() && reg->in(slot) != NULL) slot++;
 212   assert(slot < reg->req(), "too many gotos");
 213   // If this is last predecessor, then don't force phi creation
 214   if (slot == reg->req() - 1) bind = false;
 215   reg->init_req(slot, ctrl());
 216   assert(first_var + _var_ct == _cvstate->req(), "bad _cvstate size");
 217   for (uint i = first_var; i < _cvstate->req(); i++) {
 218 
 219     // l is the value of var reaching the label. Could be a single value
 220     // reaching the label, or a phi that merges multiples values reaching
 221     // the label.  The latter is true if the label's input: in(..) is
 222     // a phi whose control input is the region node for the label.
 223 
 224     Node* l = lab->in(i);
 225     // Get the current value of the var
 226     Node* m = _cvstate->in(i);
 227     // If the var went unused no need for a phi
 228     if (m == NULL) {
 229       continue;
 230     } else if (l == NULL || m == l) {
 231       // Only one unique value "m" is known to reach this label so a phi
 232       // is not yet necessary unless:
 233       //    the label is being bound and all predecessors have not been seen,
 234       //    in which case "bind" will be true.
 235       if (bind) {
 236         m = promote_to_phi(m, reg);
 237       }
 238       // Record the phi/value used for this var in the label's cvstate
 239       lab->set_req(i, m);
 240     } else {
 241       // More than one value for the variable reaches this label so
 242       // a create a phi if one does not already exist.
 243       if (!was_promoted_to_phi(l, reg)) {
 244         l = promote_to_phi(l, reg);
 245         lab->set_req(i, l);
 246       }
 247       // Record in the phi, the var's value from the current state
 248       l->set_req(slot, m);
 249     }
 250   }
 251   do_memory_merge(_cvstate, lab);
 252   stop();
 253 }
 254 
 255 //-----------------------------promote_to_phi-----------------------------------
 256 Node* IdealKit::promote_to_phi(Node* n, Node* reg) {
 257   assert(!was_promoted_to_phi(n, reg), "n already promoted to phi on this region");
 258   // Get a conservative type for the phi
 259   const BasicType bt = n->bottom_type()->basic_type();
 260   const Type* ct = Type::get_const_basic_type(bt);
 261   return delay_transform(PhiNode::make(reg, n, ct));
 262 }
 263 
 264 //-----------------------------declarations_done-------------------------------
 265 void IdealKit::declarations_done() {
 266   _cvstate = new_cvstate();   // initialize current cvstate
 267   set_ctrl(_initial_ctrl);    // initialize control in current cvstate
 268   set_all_memory(_initial_memory);// initialize memory in current cvstate
 269   DEBUG_ONLY(_state->push(BlockS));
 270 }
 271 
 272 //-----------------------------transform-----------------------------------
 273 Node* IdealKit::transform(Node* n) {
 274   if (_delay_all_transforms) {
 275     return delay_transform(n);
 276   } else {
 277     return gvn().transform(n);
 278   }
 279 }
 280 
 281 //-----------------------------delay_transform-----------------------------------
 282 Node* IdealKit::delay_transform(Node* n) {
 283   if (!gvn().is_IterGVN() || !gvn().is_IterGVN()->delay_transform()) {
 284     gvn().set_type(n, n->bottom_type());
 285   }
 286   _delay_transform->push(n);
 287   return n;
 288 }
 289 
 290 //-----------------------------new_cvstate-----------------------------------
 291 Node* IdealKit::new_cvstate() {
 292   uint sz = _var_ct + first_var;
 293   return new (C, sz) Node(sz);
 294 }
 295 
 296 //-----------------------------copy_cvstate-----------------------------------
 297 Node* IdealKit::copy_cvstate() {
 298   Node* ns = new_cvstate();
 299   for (uint i = 0; i < ns->req(); i++) ns->init_req(i, _cvstate->in(i));
 300   // We must clone memory since it will be updated as we do stores.
 301   ns->set_req(TypeFunc::Memory, MergeMemNode::make(C, ns->in(TypeFunc::Memory)));
 302   return ns;
 303 }
 304 
 305 //-----------------------------clear-----------------------------------
 306 void IdealKit::clear(Node* m) {
 307   for (uint i = 0; i < m->req(); i++) m->set_req(i, NULL);
 308 }
 309 
 310 //-----------------------------drain_delay_transform----------------------------
 311 void IdealKit::drain_delay_transform() {
 312   while (_delay_transform->length() > 0) {
 313     Node* n = _delay_transform->pop();
 314     gvn().transform(n);
 315     if (!gvn().is_IterGVN()) {
 316       C->record_for_igvn(n);
 317     }
 318   }
 319 }
 320 
 321 //-----------------------------IdealVariable----------------------------
 322 IdealVariable::IdealVariable(IdealKit &k) {
 323   k.declare(this);
 324 }
 325 
 326 Node* IdealKit::memory(uint alias_idx) {
 327   MergeMemNode* mem = merged_memory();
 328   Node* p = mem->memory_at(alias_idx);
 329   if (!gvn().is_IterGVN() || !gvn().is_IterGVN()->delay_transform()) {
 330     _gvn.set_type(p, Type::MEMORY);  // must be mapped
 331   }
 332   return p;
 333 }
 334 
 335 void IdealKit::set_memory(Node* mem, uint alias_idx) {
 336   merged_memory()->set_memory_at(alias_idx, mem);
 337 }
 338 
 339 //----------------------------- make_load ----------------------------
 340 Node* IdealKit::load(Node* ctl,
 341                      Node* adr,
 342                      const Type* t,
 343                      BasicType bt,
 344                      int adr_idx,
 345                      bool require_atomic_access) {
 346 
 347   assert(adr_idx != Compile::AliasIdxTop, "use other make_load factory" );
 348   const TypePtr* adr_type = NULL; // debug-mode-only argument
 349   debug_only(adr_type = C->get_adr_type(adr_idx));
 350   Node* mem = memory(adr_idx);
 351   Node* ld;
 352   if (require_atomic_access && bt == T_LONG) {
 353     ld = LoadLNode::make_atomic(C, ctl, mem, adr, adr_type, t);
 354   } else {
 355     ld = LoadNode::make(_gvn, ctl, mem, adr, adr_type, t, bt);
 356   }
 357   return transform(ld);
 358 }
 359 
 360 Node* IdealKit::store(Node* ctl, Node* adr, Node *val, BasicType bt,
 361                                 int adr_idx,
 362                                 bool require_atomic_access) {
 363   assert(adr_idx != Compile::AliasIdxTop, "use other store_to_memory factory" );
 364   const TypePtr* adr_type = NULL;
 365   debug_only(adr_type = C->get_adr_type(adr_idx));
 366   Node *mem = memory(adr_idx);
 367   Node* st;
 368   if (require_atomic_access && bt == T_LONG) {
 369     st = StoreLNode::make_atomic(C, ctl, mem, adr, adr_type, val);
 370   } else {
 371     st = StoreNode::make(_gvn, ctl, mem, adr, adr_type, val, bt);
 372   }
 373   st = transform(st);
 374   set_memory(st, adr_idx);
 375 
 376   return st;
 377 }
 378 
 379 // Card mark store. Must be ordered so that it will come after the store of
 380 // the oop.
 381 Node* IdealKit::storeCM(Node* ctl, Node* adr, Node *val, Node* oop_store,
 382                         BasicType bt,
 383                         int adr_idx) {
 384   assert(adr_idx != Compile::AliasIdxTop, "use other store_to_memory factory" );
 385   const TypePtr* adr_type = NULL;
 386   debug_only(adr_type = C->get_adr_type(adr_idx));
 387   Node *mem = memory(adr_idx);
 388 
 389   // Add required edge to oop_store, optimizer does not support precedence edges.
 390   // Convert required edge to precedence edge before allocation.
 391   Node* st = new (C, 5) StoreCMNode(ctl, mem, adr, adr_type, val, oop_store);
 392 
 393   st = transform(st);
 394   set_memory(st, adr_idx);
 395 
 396   return st;
 397 }
 398 
 399 //---------------------------- do_memory_merge --------------------------------
 400 // The memory from one merging cvstate needs to be merged with the memory for another
 401 // join cvstate. If the join cvstate doesn't have a merged memory yet then we
 402 // can just copy the state from the merging cvstate
 403 
 404 // Merge one slow path into the rest of memory.
 405 void IdealKit::do_memory_merge(Node* merging, Node* join) {
 406 
 407   // Get the region for the join state
 408   Node* join_region = join->in(TypeFunc::Control);
 409   assert(join_region != NULL, "join region must exist");
 410   if (join->in(TypeFunc::Memory) == NULL ) {
 411     join->set_req(TypeFunc::Memory,  merging->in(TypeFunc::Memory));
 412     return;
 413   }
 414 
 415   // The control flow for merging must have already been attached to the join region
 416   // we need its index for the phis.
 417   uint slot;
 418   for (slot = 1; slot < join_region->req() ; slot ++ ) {
 419     if (join_region->in(slot) == merging->in(TypeFunc::Control)) break;
 420   }
 421   assert(slot !=  join_region->req(), "edge must already exist");
 422 
 423   MergeMemNode* join_m    = join->in(TypeFunc::Memory)->as_MergeMem();
 424   MergeMemNode* merging_m = merging->in(TypeFunc::Memory)->as_MergeMem();
 425 
 426   // join_m should be an ancestor mergemem of merging
 427   // Slow path memory comes from the current map (which is from a slow call)
 428   // Fast path/null path memory comes from the call's input
 429 
 430   // Merge the other fast-memory inputs with the new slow-default memory.
 431   // for (MergeMemStream mms(merged_memory(), fast_mem->as_MergeMem()); mms.next_non_empty2(); ) {
 432   for (MergeMemStream mms(join_m, merging_m); mms.next_non_empty2(); ) {
 433     Node* join_slice = mms.force_memory();
 434     Node* merging_slice = mms.memory2();
 435     if (join_slice != merging_slice) {
 436       PhiNode* phi;
 437       // bool new_phi = false;
 438       // Is the phi for this slice one that we created for this join region or simply
 439       // one we copied? If it is ours then add
 440       if (join_slice->is_Phi() && join_slice->as_Phi()->region() == join_region) {
 441         phi = join_slice->as_Phi();
 442       } else {
 443         // create the phi with join_slice filling supplying memory for all of the
 444         // control edges to the join region
 445         phi = PhiNode::make(join_region, join_slice, Type::MEMORY, mms.adr_type(C));
 446         phi = (PhiNode*) delay_transform(phi);
 447         // gvn().set_type(phi, Type::MEMORY);
 448         // new_phi = true;
 449       }
 450       // Now update the phi with the slice for the merging slice
 451       phi->set_req(slot, merging_slice/* slow_path, slow_slice */);
 452       // this updates join_m with the phi
 453       mms.set_memory(phi);
 454     }
 455   }
 456 }
 457 
 458 
 459 //----------------------------- make_call  ----------------------------
 460 // Trivial runtime call
 461 void IdealKit::make_leaf_call(const TypeFunc *slow_call_type,
 462                               address slow_call,
 463                               const char *leaf_name,
 464                               Node* parm0,
 465                               Node* parm1,
 466                               Node* parm2) {
 467 
 468   // We only handle taking in RawMem and modifying RawMem
 469   const TypePtr* adr_type = TypeRawPtr::BOTTOM;
 470   uint adr_idx = C->get_alias_index(adr_type);
 471 
 472   // Slow-path leaf call
 473   int size = slow_call_type->domain()->cnt();
 474   CallNode *call =  (CallNode*)new (C, size) CallLeafNode( slow_call_type, slow_call, leaf_name, adr_type);
 475 
 476   // Set fixed predefined input arguments
 477   call->init_req( TypeFunc::Control, ctrl() );
 478   call->init_req( TypeFunc::I_O    , top() )     ;   // does no i/o
 479   // Narrow memory as only memory input
 480   call->init_req( TypeFunc::Memory , memory(adr_idx));
 481   call->init_req( TypeFunc::FramePtr, top() /* frameptr() */ );
 482   call->init_req( TypeFunc::ReturnAdr, top() );
 483 
 484   if (parm0 != NULL)  call->init_req(TypeFunc::Parms+0, parm0);
 485   if (parm1 != NULL)  call->init_req(TypeFunc::Parms+1, parm1);
 486   if (parm2 != NULL)  call->init_req(TypeFunc::Parms+2, parm2);
 487 
 488   // Node *c = _gvn.transform(call);
 489   call = (CallNode *) _gvn.transform(call);
 490   Node *c = call; // dbx gets confused with call call->dump()
 491 
 492   // Slow leaf call has no side-effects, sets few values
 493 
 494   set_ctrl(transform( new (C, 1) ProjNode(call,TypeFunc::Control) ));
 495 
 496   // Make memory for the call
 497   Node* mem = _gvn.transform( new (C, 1) ProjNode(call, TypeFunc::Memory) );
 498 
 499   // Set the RawPtr memory state only.
 500   set_memory(mem, adr_idx);
 501 
 502   assert(C->alias_type(call->adr_type()) == C->alias_type(adr_type),
 503          "call node must be constructed correctly");
 504 }