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