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