1 /*
2 * Copyright (c) 2005, 2025, 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 "opto/addnode.hpp"
26 #include "opto/callnode.hpp"
27 #include "opto/cfgnode.hpp"
28 #include "opto/idealKit.hpp"
29 #include "opto/runtime.hpp"
30
31 // Static initialization
32
33 // This declares the position where vars are kept in the cvstate
34 // For some degree of consistency we use the TypeFunc enum to
35 // soak up spots in the inputs even though we only use early Control
36 // and Memory slots. (So far.)
37 const uint IdealKit::first_var = TypeFunc::Parms + 1;
38
39 //----------------------------IdealKit-----------------------------------------
40 IdealKit::IdealKit(GraphKit* gkit, bool delay_all_transforms, bool has_declarations) :
41 C(gkit->C), _gvn(gkit->gvn()) {
42 _initial_ctrl = gkit->control();
43 _initial_memory = gkit->merged_memory();
44 _initial_i_o = gkit->i_o();
45 _delay_all_transforms = delay_all_transforms;
46 _var_ct = 0;
47 _cvstate = nullptr;
48 // We can go memory state free or else we need the entire memory state
49 assert(_initial_memory == nullptr || _initial_memory->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, nullptr);
52 DEBUG_ONLY(_state = new (C->node_arena()) GrowableArray<int>(C->node_arena(), init_size, 0, 0));
53 if (!has_declarations) {
54 declarations_done();
55 }
56 }
57
58 //----------------------------sync_kit-----------------------------------------
59 void IdealKit::sync_kit(GraphKit* gkit) {
60 set_all_memory(gkit->merged_memory());
61 set_i_o(gkit->i_o());
62 set_ctrl(gkit->control());
63 }
64
65 //-------------------------------if_then-------------------------------------
66 // Create: if(left relop right)
67 // / \
68 // iffalse iftrue
69 // Push the iffalse cvstate onto the stack. The iftrue becomes the current cvstate.
70 void IdealKit::if_then(Node* left, BoolTest::mask relop,
71 Node* right, float prob, float cnt, bool push_new_state) {
72 assert((state() & (BlockS|LoopS|IfThenS|ElseS)), "bad state for new If");
73 Node* bol;
74 if (left->bottom_type()->isa_ptr() == nullptr) {
75 if (left->bottom_type()->isa_int() != nullptr) {
76 bol = Bool(CmpI(left, right), relop);
77 } else {
78 assert(left->bottom_type()->isa_long() != nullptr, "what else?");
79 bol = Bool(CmpL(left, right), relop);
80 }
81 } else {
82 bol = Bool(CmpP(left, right), relop);
83 }
84 if_then(bol, prob, cnt, push_new_state);
85 }
86
87 void IdealKit::if_then(Node* bol, float prob, float cnt, bool push_new_state) {
88 // Delay gvn.transform on if-nodes until construction is finished
89 // to prevent a constant bool input from discarding a control output.
90 IfNode* iff = delay_transform(new IfNode(ctrl(), bol, prob, cnt))->as_If();
91 Node* then = IfTrue(iff);
92 Node* elsen = IfFalse(iff);
93 Node* else_cvstate = copy_cvstate();
94 else_cvstate->set_req(TypeFunc::Control, elsen);
95 _pending_cvstates->push(else_cvstate);
96 DEBUG_ONLY(if (push_new_state) _state->push(IfThenS));
97 set_ctrl(then);
98 }
99
100 //-------------------------------else_-------------------------------------
101 // Pop the else cvstate off the stack, and push the (current) then cvstate.
102 // The else cvstate becomes the current cvstate.
103 void IdealKit::else_() {
104 assert(state() == IfThenS, "bad state for new Else");
105 Node* else_cvstate = _pending_cvstates->pop();
106 DEBUG_ONLY(_state->pop());
107 // save current (then) cvstate for later use at endif
108 _pending_cvstates->push(_cvstate);
109 DEBUG_ONLY(_state->push(ElseS));
110 _cvstate = else_cvstate;
111 }
112
113 //-------------------------------end_if-------------------------------------
114 // Merge the "then" and "else" cvstates.
115 //
116 // The if_then() pushed a copy of the current state for later use
117 // as the initial state for a future "else" clause. The
118 // current state then became the initial state for the
119 // then clause. If an "else" clause was encountered, it will
120 // pop the top state and use it for it's initial state.
121 // It will also push the current state (the state at the end of
122 // the "then" clause) for latter use at the end_if.
123 //
124 // At the endif, the states are:
125 // 1) else exists a) current state is end of "else" clause
126 // b) top stack state is end of "then" clause
127 //
128 // 2) no else: a) current state is end of "then" clause
129 // b) top stack state is from the "if_then" which
130 // would have been the initial state of the else.
131 //
132 // Merging the states is accomplished by:
133 // 1) make a label for the merge
134 // 2) terminate the current state with a goto to the label
135 // 3) pop the top state from the stack and make it the
136 // current state
137 // 4) bind the label at the current state. Binding a label
138 // terminates the current state with a goto to the
139 // label and makes the label's state the current state.
140 //
141 void IdealKit::end_if() {
142 assert(state() & (IfThenS|ElseS), "bad state for new Endif");
143 Node* lab = make_label(1);
144
145 // Node* join_state = _pending_cvstates->pop();
146 /* merging, join */
147 goto_(lab);
148 _cvstate = _pending_cvstates->pop();
149
150 bind(lab);
151 DEBUG_ONLY(_state->pop());
152 }
153
154 //-------------------------------loop-------------------------------------
155 // Create the loop head portion (*) of:
156 // * iv = init
157 // * top: (region node)
158 // * if (iv relop limit) {
159 // loop body
160 // i = i + 1
161 // goto top
162 // * } else // exits loop
163 //
164 // Pushes the loop top cvstate first, then the else (loop exit) cvstate
165 // onto the stack.
166 void IdealKit::loop(GraphKit* gkit, int nargs, IdealVariable& iv, Node* init, BoolTest::mask relop, Node* limit, float prob, float cnt) {
167 assert((state() & (BlockS|LoopS|IfThenS|ElseS)), "bad state for new loop");
168 // Sync IdealKit and graphKit.
169 gkit->sync_kit(*this);
170 // Add Parse Predicates.
171 gkit->add_parse_predicates(nargs);
172 // Update IdealKit memory.
173 sync_kit(gkit);
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 != nullptr, "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) != nullptr) 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 == nullptr) {
248 continue;
249 } else if (l == nullptr || 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 Node* state = new Node(sz);
315 C->record_for_igvn(state);
316 return state;
317 }
318
319 //-----------------------------copy_cvstate-----------------------------------
320 Node* IdealKit::copy_cvstate() {
321 Node* ns = new_cvstate();
322 for (uint i = 0; i < ns->req(); i++) ns->init_req(i, _cvstate->in(i));
323 // We must clone memory since it will be updated as we do stores.
324 ns->set_req(TypeFunc::Memory, MergeMemNode::make(ns->in(TypeFunc::Memory)));
325 return ns;
326 }
327
328 //-----------------------------clear-----------------------------------
329 void IdealKit::clear(Node* m) {
330 for (uint i = 0; i < m->req(); i++) m->set_req(i, nullptr);
331 }
332
333 //-----------------------------IdealVariable----------------------------
334 IdealVariable::IdealVariable(IdealKit &k) {
335 k.declare(this);
336 }
337
338 Node* IdealKit::memory(uint alias_idx) {
339 MergeMemNode* mem = merged_memory();
340 Node* p = mem->memory_at(alias_idx);
341 _gvn.set_type(p, Type::MEMORY); // must be mapped
342 return p;
343 }
344
345 void IdealKit::set_memory(Node* mem, uint alias_idx) {
346 merged_memory()->set_memory_at(alias_idx, mem);
347 }
348
349 //----------------------------- make_load ----------------------------
350 Node* IdealKit::load(Node* ctl,
351 Node* adr,
352 const Type* t,
353 BasicType bt,
354 int adr_idx,
355 bool require_atomic_access,
356 MemNode::MemOrd mo,
357 LoadNode::ControlDependency control_dependency) {
358
359 assert(adr_idx != Compile::AliasIdxTop, "use other make_load factory" );
360 const TypePtr* adr_type = nullptr; // debug-mode-only argument
361 DEBUG_ONLY(adr_type = C->get_adr_type(adr_idx));
362 Node* mem = memory(adr_idx);
363 Node* ld = LoadNode::make(_gvn, ctl, mem, adr, adr_type, t, bt, mo, control_dependency, require_atomic_access);
364 return transform(ld);
365 }
366
367 // Load AOT runtime constant
368 Node* IdealKit::load_aot_const(Node* adr, const Type* t) {
369 BasicType bt = t->basic_type();
370 const TypePtr* adr_type = nullptr; // debug-mode-only argument
371 DEBUG_ONLY(adr_type = C->get_adr_type(Compile::AliasIdxRaw));
372 Node* ctl = (Node*)C->root(); // Raw memory access needs control
373 Node* ld = LoadNode::make(_gvn, ctl, C->immutable_memory(), adr, adr_type, t, bt, MemNode::unordered,
374 LoadNode::DependsOnlyOnTest, false, false, false, false, 0);
375 return transform(ld);
376 }
377
378 Node* IdealKit::store(Node* ctl, Node* adr, Node *val, BasicType bt,
379 int adr_idx,
380 MemNode::MemOrd mo, bool require_atomic_access,
381 bool mismatched) {
382 assert(adr_idx != Compile::AliasIdxTop, "use other store_to_memory factory");
383 const TypePtr* adr_type = nullptr;
384 DEBUG_ONLY(adr_type = C->get_adr_type(adr_idx));
385 Node *mem = memory(adr_idx);
386 Node* st = StoreNode::make(_gvn, ctl, mem, adr, adr_type, val, bt, mo, require_atomic_access);
387 if (mismatched) {
388 st->as_Store()->set_mismatched_access();
389 }
390 st = transform(st);
391 set_memory(st, adr_idx);
392
393 return st;
394 }
395
396 //---------------------------- do_memory_merge --------------------------------
397 // The memory from one merging cvstate needs to be merged with the memory for another
398 // join cvstate. If the join cvstate doesn't have a merged memory yet then we
399 // can just copy the state from the merging cvstate
400
401 // Merge one slow path into the rest of memory.
402 void IdealKit::do_memory_merge(Node* merging, Node* join) {
403
404 // Get the region for the join state
405 Node* join_region = join->in(TypeFunc::Control);
406 assert(join_region != nullptr, "join region must exist");
407 if (join->in(TypeFunc::I_O) == nullptr ) {
408 join->set_req(TypeFunc::I_O, merging->in(TypeFunc::I_O));
409 }
410 if (join->in(TypeFunc::Memory) == nullptr ) {
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 Node* join_io = join->in(TypeFunc::I_O);
458 Node* merging_io = merging->in(TypeFunc::I_O);
459 if (join_io != merging_io) {
460 PhiNode* phi;
461 if (join_io->is_Phi() && join_io->as_Phi()->region() == join_region) {
462 phi = join_io->as_Phi();
463 } else {
464 phi = PhiNode::make(join_region, join_io, Type::ABIO);
465 phi = (PhiNode*) delay_transform(phi);
466 join->set_req(TypeFunc::I_O, phi);
467 }
468 phi->set_req(slot, merging_io);
469 }
470 }
471
472
473 //----------------------------- make_call ----------------------------
474 // Trivial runtime call
475 Node* IdealKit::make_leaf_call(const TypeFunc *slow_call_type,
476 address slow_call,
477 const char *leaf_name,
478 Node* parm0,
479 Node* parm1,
480 Node* parm2,
481 Node* parm3) {
482
483 // We only handle taking in RawMem and modifying RawMem
484 const TypePtr* adr_type = TypeRawPtr::BOTTOM;
485 uint adr_idx = C->get_alias_index(adr_type);
486
487 // Slow-path leaf call
488 CallNode *call = (CallNode*)new CallLeafNode( slow_call_type, slow_call, leaf_name, adr_type);
489
490 // Set fixed predefined input arguments
491 call->init_req( TypeFunc::Control, ctrl() );
492 call->init_req( TypeFunc::I_O , top() ) ; // does no i/o
493 // Narrow memory as only memory input
494 call->init_req( TypeFunc::Memory , memory(adr_idx));
495 call->init_req( TypeFunc::FramePtr, top() /* frameptr() */ );
496 call->init_req( TypeFunc::ReturnAdr, top() );
497
498 if (parm0 != nullptr) call->init_req(TypeFunc::Parms+0, parm0);
499 if (parm1 != nullptr) call->init_req(TypeFunc::Parms+1, parm1);
500 if (parm2 != nullptr) call->init_req(TypeFunc::Parms+2, parm2);
501 if (parm3 != nullptr) call->init_req(TypeFunc::Parms+3, parm3);
502
503 // Node *c = _gvn.transform(call);
504 call = (CallNode *) _gvn.transform(call);
505 Node *c = call; // dbx gets confused with call call->dump()
506
507 // Slow leaf call has no side-effects, sets few values
508
509 set_ctrl(transform( new ProjNode(call,TypeFunc::Control) ));
510
511 // Make memory for the call
512 Node* mem = _gvn.transform( new ProjNode(call, TypeFunc::Memory) );
513
514 // Set the RawPtr memory state only.
515 set_memory(mem, adr_idx);
516
517 assert(C->alias_type(call->adr_type()) == C->alias_type(adr_type),
518 "call node must be constructed correctly");
519 Node* res = nullptr;
520 if (slow_call_type->range_sig()->cnt() > TypeFunc::Parms) {
521 assert(slow_call_type->range_sig()->cnt() == TypeFunc::Parms+1, "only one return value");
522 res = transform(new ProjNode(call, TypeFunc::Parms));
523 }
524 return res;
525 }
526
527 void IdealKit::make_leaf_call_no_fp(const TypeFunc *slow_call_type,
528 address slow_call,
529 const char *leaf_name,
530 const TypePtr* adr_type,
531 Node* parm0,
532 Node* parm1,
533 Node* parm2,
534 Node* parm3) {
535
536 // We only handle taking in RawMem and modifying RawMem
537 uint adr_idx = C->get_alias_index(adr_type);
538
539 // Slow-path leaf call
540 CallNode *call = (CallNode*)new CallLeafNoFPNode( slow_call_type, slow_call, leaf_name, adr_type);
541
542 // Set fixed predefined input arguments
543 call->init_req( TypeFunc::Control, ctrl() );
544 call->init_req( TypeFunc::I_O , top() ) ; // does no i/o
545 // Narrow memory as only memory input
546 call->init_req( TypeFunc::Memory , memory(adr_idx));
547 call->init_req( TypeFunc::FramePtr, top() /* frameptr() */ );
548 call->init_req( TypeFunc::ReturnAdr, top() );
549
550 if (parm0 != nullptr) call->init_req(TypeFunc::Parms+0, parm0);
551 if (parm1 != nullptr) call->init_req(TypeFunc::Parms+1, parm1);
552 if (parm2 != nullptr) call->init_req(TypeFunc::Parms+2, parm2);
553 if (parm3 != nullptr) call->init_req(TypeFunc::Parms+3, parm3);
554
555 // Node *c = _gvn.transform(call);
556 call = (CallNode *) _gvn.transform(call);
557 Node *c = call; // dbx gets confused with call call->dump()
558
559 // Slow leaf call has no side-effects, sets few values
560
561 set_ctrl(transform( new ProjNode(call,TypeFunc::Control) ));
562
563 // Make memory for the call
564 Node* mem = _gvn.transform( new ProjNode(call, TypeFunc::Memory) );
565
566 // Set the RawPtr memory state only.
567 set_memory(mem, adr_idx);
568
569 assert(C->alias_type(call->adr_type()) == C->alias_type(adr_type),
570 "call node must be constructed correctly");
571 }