1 /* 2 * Copyright (c) 2005, 2009, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * 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, int oop_adr_idx, 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, oop_adr_idx); 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 }