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