1 /*
2 * Copyright (c) 1999, 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 "c1/c1_IR.hpp"
26 #include "c1/c1_ValueMap.hpp"
27 #include "c1/c1_ValueSet.hpp"
28 #include "c1/c1_ValueStack.hpp"
29 #include "utilities/bitMap.inline.hpp"
30
31 #ifndef PRODUCT
32
33 int ValueMap::_number_of_finds = 0;
34 int ValueMap::_number_of_hits = 0;
35 int ValueMap::_number_of_kills = 0;
36
37 #define TRACE_VALUE_NUMBERING(code) if (PrintValueNumbering) { code; }
38
39 #else
40
41 #define TRACE_VALUE_NUMBERING(code)
42
43 #endif
44
45
46 ValueMap::ValueMap()
47 : _nesting(0)
48 , _entries(ValueMapInitialSize, ValueMapInitialSize, nullptr)
49 , _killed_values()
50 , _entry_count(0)
51 {
52 NOT_PRODUCT(reset_statistics());
53 }
54
55
56 ValueMap::ValueMap(ValueMap* old)
57 : _nesting(old->_nesting + 1)
58 , _entries(old->_entries.length(), old->_entries.length(), nullptr)
59 , _killed_values()
60 , _entry_count(old->_entry_count)
61 {
62 for (int i = size() - 1; i >= 0; i--) {
63 _entries.at_put(i, old->entry_at(i));
64 }
65 _killed_values.set_from(&old->_killed_values);
66 }
67
68
69 void ValueMap::increase_table_size() {
70 int old_size = size();
71 int new_size = old_size * 2 + 1;
72
73 ValueMapEntryList worklist(8);
74 ValueMapEntryArray new_entries(new_size, new_size, nullptr);
75 int new_entry_count = 0;
76
77 TRACE_VALUE_NUMBERING(tty->print_cr("increasing table size from %d to %d", old_size, new_size));
78
79 for (int i = old_size - 1; i >= 0; i--) {
80 ValueMapEntry* entry;
81 for (entry = entry_at(i); entry != nullptr; entry = entry->next()) {
82 if (!is_killed(entry->value())) {
83 worklist.push(entry);
84 }
85 }
86
87 while (!worklist.is_empty()) {
88 entry = worklist.pop();
89 int new_index = entry_index(entry->hash(), new_size);
90
91 if (entry->nesting() != nesting() && new_entries.at(new_index) != entry->next()) {
92 // changing entries with a lower nesting than the current nesting of the table
93 // is not allowed because then the same entry is contained in multiple value maps.
94 // clone entry when next-pointer must be changed
95 entry = new ValueMapEntry(entry->hash(), entry->value(), entry->nesting(), nullptr);
96 }
97 entry->set_next(new_entries.at(new_index));
98 new_entries.at_put(new_index, entry);
99 new_entry_count++;
100 }
101 }
102
103 _entries = new_entries;
104 _entry_count = new_entry_count;
105 }
106
107
108 Value ValueMap::find_insert(Value x) {
109 const intx hash = x->hash();
110 if (hash != 0) {
111 // 0 hash means: exclude from value numbering
112 NOT_PRODUCT(_number_of_finds++);
113
114 for (ValueMapEntry* entry = entry_at(entry_index(hash, size())); entry != nullptr; entry = entry->next()) {
115 if (entry->hash() == hash) {
116 Value f = entry->value();
117
118 if (!is_killed(f) && f->is_equal(x)) {
119 NOT_PRODUCT(_number_of_hits++);
120 TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: %s %c%d equal to %c%d (size %d, entries %d, nesting-diff %d)", x->name(), x->type()->tchar(), x->id(), f->type()->tchar(), f->id(), size(), entry_count(), nesting() - entry->nesting()));
121
122 if (entry->nesting() != nesting() && f->as_Constant() == nullptr) {
123 // non-constant values of of another block must be pinned,
124 // otherwise it is possible that they are not evaluated
125 f->pin(Instruction::PinGlobalValueNumbering);
126 }
127 assert(x->type()->tag() == f->type()->tag(), "should have same type");
128
129 return f;
130
131 }
132 }
133 }
134
135 // x not found, so insert it
136 if (entry_count() >= size_threshold()) {
137 increase_table_size();
138 }
139 int idx = entry_index(hash, size());
140 _entries.at_put(idx, new ValueMapEntry(hash, x, nesting(), entry_at(idx)));
141 _entry_count++;
142
143 TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: insert %s %c%d (size %d, entries %d, nesting %d)", x->name(), x->type()->tchar(), x->id(), size(), entry_count(), nesting()));
144 }
145
146 return x;
147 }
148
149
150 #define GENERIC_KILL_VALUE(must_kill_implementation) \
151 NOT_PRODUCT(_number_of_kills++); \
152 \
153 for (int i = size() - 1; i >= 0; i--) { \
154 ValueMapEntry* prev_entry = nullptr; \
155 for (ValueMapEntry* entry = entry_at(i); entry != nullptr; entry = entry->next()) { \
156 Value value = entry->value(); \
157 \
158 must_kill_implementation(must_kill, entry, value) \
159 \
160 if (must_kill) { \
161 kill_value(value); \
162 \
163 if (prev_entry == nullptr) { \
164 _entries.at_put(i, entry->next()); \
165 _entry_count--; \
166 } else if (prev_entry->nesting() == nesting()) { \
167 prev_entry->set_next(entry->next()); \
168 _entry_count--; \
169 } else { \
170 prev_entry = entry; \
171 } \
172 \
173 TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: killed %s %c%d (size %d, entries %d, nesting-diff %d)", value->name(), value->type()->tchar(), value->id(), size(), entry_count(), nesting() - entry->nesting())); \
174 } else { \
175 prev_entry = entry; \
176 } \
177 } \
178 } \
179
180 #define MUST_KILL_MEMORY(must_kill, entry, value) \
181 bool must_kill = value->as_LoadField() != nullptr || value->as_LoadIndexed() != nullptr;
182
183 #define MUST_KILL_ARRAY(must_kill, entry, value) \
184 bool must_kill = value->as_LoadIndexed() != nullptr \
185 && value->type()->tag() == type->tag();
186
187 #define MUST_KILL_FIELD(must_kill, entry, value) \
188 /* ciField's are not unique; must compare their contents */ \
189 LoadField* lf = value->as_LoadField(); \
190 bool must_kill = lf != nullptr \
191 && lf->field()->holder() == field->holder() \
192 && (all_offsets || lf->field()->offset_in_bytes() == field->offset_in_bytes());
193
194
195 void ValueMap::kill_memory() {
196 GENERIC_KILL_VALUE(MUST_KILL_MEMORY);
197 }
198
199 void ValueMap::kill_array(ValueType* type) {
200 GENERIC_KILL_VALUE(MUST_KILL_ARRAY);
201 }
202
203 void ValueMap::kill_field(ciField* field, bool all_offsets) {
204 GENERIC_KILL_VALUE(MUST_KILL_FIELD);
205 }
206
207 void ValueMap::kill_map(ValueMap* map) {
208 assert(is_global_value_numbering(), "only for global value numbering");
209 _killed_values.set_union(&map->_killed_values);
210 }
211
212 void ValueMap::kill_all() {
213 assert(is_local_value_numbering(), "only for local value numbering");
214 for (int i = size() - 1; i >= 0; i--) {
215 _entries.at_put(i, nullptr);
216 }
217 _entry_count = 0;
218 }
219
220
221 #ifndef PRODUCT
222
223 void ValueMap::print() {
224 tty->print_cr("(size %d, entries %d, nesting %d)", size(), entry_count(), nesting());
225
226 int entries = 0;
227 for (int i = 0; i < size(); i++) {
228 if (entry_at(i) != nullptr) {
229 tty->print(" %2d: ", i);
230 for (ValueMapEntry* entry = entry_at(i); entry != nullptr; entry = entry->next()) {
231 Value value = entry->value();
232 tty->print("%s %c%d (%s%d) -> ", value->name(), value->type()->tchar(), value->id(), is_killed(value) ? "x" : "", entry->nesting());
233 entries++;
234 }
235 tty->print_cr("null");
236 }
237 }
238
239 _killed_values.print();
240 assert(entry_count() == entries, "entry_count incorrect");
241 }
242
243 void ValueMap::reset_statistics() {
244 _number_of_finds = 0;
245 _number_of_hits = 0;
246 _number_of_kills = 0;
247 }
248
249 void ValueMap::print_statistics() {
250 float hit_rate = 0;
251 if (_number_of_finds != 0) {
252 hit_rate = (float)_number_of_hits / _number_of_finds;
253 }
254
255 tty->print_cr("finds:%3d hits:%3d kills:%3d hit rate: %1.4f", _number_of_finds, _number_of_hits, _number_of_kills, hit_rate);
256 }
257
258 #endif
259
260
261
262 class ShortLoopOptimizer : public ValueNumberingVisitor {
263 private:
264 GlobalValueNumbering* _gvn;
265 BlockList _loop_blocks;
266 bool _too_complicated_loop;
267 bool _has_field_store[T_VOID];
268 bool _has_indexed_store[T_VOID];
269
270 // simplified access to methods of GlobalValueNumbering
271 ValueMap* current_map() { return _gvn->current_map(); }
272 ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); }
273
274 // implementation for abstract methods of ValueNumberingVisitor
275 void kill_memory() { _too_complicated_loop = true; }
276 void kill_field(ciField* field, bool all_offsets) {
277 current_map()->kill_field(field, all_offsets);
278 assert(field->type()->basic_type() >= 0 && field->type()->basic_type() < T_VOID, "Invalid type");
279 _has_field_store[field->type()->basic_type()] = true;
280 }
281 void kill_array(ValueType* type) {
282 current_map()->kill_array(type);
283 BasicType basic_type = as_BasicType(type); assert(basic_type < T_VOID, "Invalid type");
284 _has_indexed_store[basic_type] = true;
285 }
286
287 public:
288 ShortLoopOptimizer(GlobalValueNumbering* gvn)
289 : _gvn(gvn)
290 , _loop_blocks(ValueMapMaxLoopSize)
291 , _too_complicated_loop(false)
292 {
293 for (int i = 0; i < T_VOID; i++) {
294 _has_field_store[i] = false;
295 _has_indexed_store[i] = false;
296 }
297 }
298
299 bool has_field_store(BasicType type) {
300 assert(type < T_VOID, "Invalid type");
301 return _has_field_store[type];
302 }
303
304 bool has_indexed_store(BasicType type) {
305 assert(type < T_VOID, "Invalid type");
306 return _has_indexed_store[type];
307 }
308
309 bool process(BlockBegin* loop_header);
310 };
311
312 class LoopInvariantCodeMotion : public StackObj {
313 private:
314 GlobalValueNumbering* _gvn;
315 ShortLoopOptimizer* _short_loop_optimizer;
316 Instruction* _insertion_point;
317 ValueStack * _state;
318 bool _insert_is_pred;
319
320 bool is_invariant(Value v) const { return _gvn->is_processed(v); }
321
322 void process_block(BlockBegin* block);
323
324 public:
325 LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks);
326 };
327
328 LoopInvariantCodeMotion::LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks)
329 : _gvn(gvn), _short_loop_optimizer(slo), _insertion_point(nullptr), _state(nullptr), _insert_is_pred(false) {
330
331 TRACE_VALUE_NUMBERING(tty->print_cr("using loop invariant code motion loop_header = %d", loop_header->block_id()));
332 TRACE_VALUE_NUMBERING(tty->print_cr("** loop invariant code motion for short loop B%d", loop_header->block_id()));
333
334 BlockBegin* insertion_block = loop_header->dominator();
335 if (insertion_block->number_of_preds() == 0) {
336 return; // only the entry block does not have a predecessor
337 }
338
339 assert(insertion_block->end()->as_Base() == nullptr, "cannot insert into entry block");
340 _insertion_point = insertion_block->end()->prev();
341 _insert_is_pred = loop_header->is_predecessor(insertion_block);
342
343 BlockEnd *block_end = insertion_block->end();
344 _state = block_end->state_before();
345
346 if (!_state) {
347 // If, TableSwitch and LookupSwitch always have state_before when
348 // loop invariant code motion happens..
349 assert(block_end->as_Goto(), "Block has to be goto");
350 _state = block_end->state();
351 }
352
353 // the loop_blocks are filled by going backward from the loop header, so this processing order is best
354 assert(loop_blocks->at(0) == loop_header, "loop header must be first loop block");
355 process_block(loop_header);
356 for (int i = loop_blocks->length() - 1; i >= 1; i--) {
357 process_block(loop_blocks->at(i));
358 }
359 }
360
361 class CheckInsertionPoint : public ValueVisitor {
362 private:
363 Value _insert;
364 bool _valid = true;
365
366 void visit(Value* vp) {
367 assert(*vp != nullptr, "value should not be null");
368 if (_insert->dominator_depth() < (*vp)->dominator_depth()) {
369 _valid = false;
370 }
371 }
372
373 public:
374 bool is_valid() { return _valid; }
375 CheckInsertionPoint(Value insert)
376 : _insert(insert) {
377 assert(insert != nullptr, "insertion point should not be null");
378 }
379 };
380
381 // Check that insertion point has higher dom depth than all inputs to cur
382 static bool is_dominated_by_inputs(Instruction* insertion_point, Instruction* cur) {
383 CheckInsertionPoint v(insertion_point);
384 cur->input_values_do(&v);
385 return v.is_valid();
386 }
387
388 void LoopInvariantCodeMotion::process_block(BlockBegin* block) {
389 TRACE_VALUE_NUMBERING(tty->print_cr("processing block B%d", block->block_id()));
390
391 Instruction* prev = block;
392 Instruction* cur = block->next();
393
394 while (cur != nullptr) {
395 // determine if cur instruction is loop invariant
396 // only selected instruction types are processed here
397 bool cur_invariant = false;
398
399 if (cur->as_Constant() != nullptr) {
400 cur_invariant = !cur->can_trap();
401 } else if (cur->as_ArithmeticOp() != nullptr || cur->as_LogicOp() != nullptr || cur->as_ShiftOp() != nullptr) {
402 assert(cur->as_Op2() != nullptr, "must be Op2");
403 Op2* op2 = (Op2*)cur;
404 cur_invariant = !op2->can_trap() && is_invariant(op2->x()) && is_invariant(op2->y());
405 } else if (cur->as_LoadField() != nullptr) {
406 LoadField* lf = (LoadField*)cur;
407 // deoptimizes on NullPointerException
408 cur_invariant = !lf->needs_patching() && !lf->field()->is_volatile() && !_short_loop_optimizer->has_field_store(lf->field()->type()->basic_type()) && is_invariant(lf->obj()) && _insert_is_pred;
409 } else if (cur->as_ArrayLength() != nullptr) {
410 ArrayLength *length = cur->as_ArrayLength();
411 cur_invariant = is_invariant(length->array());
412 } else if (cur->as_LoadIndexed() != nullptr) {
413 LoadIndexed *li = (LoadIndexed *)cur->as_LoadIndexed();
414 cur_invariant = !_short_loop_optimizer->has_indexed_store(as_BasicType(cur->type())) && is_invariant(li->array()) && is_invariant(li->index()) && _insert_is_pred;
415 } else if (cur->as_NegateOp() != nullptr) {
416 NegateOp* neg = (NegateOp*)cur->as_NegateOp();
417 cur_invariant = is_invariant(neg->x());
418 } else if (cur->as_Convert() != nullptr) {
419 Convert* cvt = (Convert*)cur->as_Convert();
420 cur_invariant = is_invariant(cvt->value());
421 }
422
423 if (cur_invariant && is_dominated_by_inputs(_insertion_point, cur)) {
424 // perform value numbering and mark instruction as loop-invariant
425 _gvn->substitute(cur);
426
427 if (cur->as_Constant() == nullptr) {
428 // ensure that code for non-constant instructions is always generated
429 cur->pin();
430 }
431
432 // remove cur instruction from loop block and append it to block before loop
433 Instruction* next = cur->next();
434 Instruction* in = _insertion_point->next();
435 _insertion_point = _insertion_point->set_next(cur);
436 cur->set_next(in);
437
438 // Deoptimize on exception
439 cur->set_flag(Instruction::DeoptimizeOnException, true);
440
441 // Clear exception handlers
442 cur->set_exception_handlers(nullptr);
443
444 TRACE_VALUE_NUMBERING(tty->print_cr("Instruction %c%d is loop invariant", cur->type()->tchar(), cur->id()));
445 TRACE_VALUE_NUMBERING(cur->print_line());
446
447 if (cur->state_before() != nullptr) {
448 cur->set_state_before(_state->copy());
449 }
450 if (cur->exception_state() != nullptr) {
451 cur->set_exception_state(_state->copy());
452 }
453
454 cur = prev->set_next(next);
455 } else {
456 prev = cur;
457 cur = cur->next();
458 }
459 }
460 }
461
462 bool ShortLoopOptimizer::process(BlockBegin* loop_header) {
463 TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block"));
464
465 _too_complicated_loop = false;
466 _loop_blocks.clear();
467 _loop_blocks.append(loop_header);
468
469 for (int i = 0; i < _loop_blocks.length(); i++) {
470 BlockBegin* block = _loop_blocks.at(i);
471 TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id()));
472
473 if (block->is_set(BlockBegin::exception_entry_flag)) {
474 // this would be too complicated
475 return false;
476 }
477
478 // add predecessors to worklist
479 for (int j = block->number_of_preds() - 1; j >= 0; j--) {
480 BlockBegin* pred = block->pred_at(j);
481
482 if (pred->is_set(BlockBegin::osr_entry_flag)) {
483 return false;
484 }
485
486 ValueMap* pred_map = value_map_of(pred);
487 if (pred_map != nullptr) {
488 current_map()->kill_map(pred_map);
489 } else if (!_loop_blocks.contains(pred)) {
490 if (_loop_blocks.length() >= ValueMapMaxLoopSize) {
491 return false;
492 }
493 _loop_blocks.append(pred);
494 }
495 }
496
497 // use the instruction visitor for killing values
498 for (Value instr = block->next(); instr != nullptr; instr = instr->next()) {
499 instr->visit(this);
500 if (_too_complicated_loop) {
501 return false;
502 }
503 }
504 }
505
506 bool optimistic = this->_gvn->compilation()->is_optimistic();
507
508 if (UseLoopInvariantCodeMotion && optimistic) {
509 LoopInvariantCodeMotion code_motion(this, _gvn, loop_header, &_loop_blocks);
510 }
511
512 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized"));
513 return true;
514 }
515
516
517 GlobalValueNumbering::GlobalValueNumbering(IR* ir)
518 : _compilation(ir->compilation())
519 , _current_map(nullptr)
520 , _value_maps(ir->linear_scan_order()->length(), ir->linear_scan_order()->length(), nullptr)
521 , _has_substitutions(false)
522 {
523 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering"));
524
525 ShortLoopOptimizer short_loop_optimizer(this);
526
527 BlockList* blocks = ir->linear_scan_order();
528 int num_blocks = blocks->length();
529
530 BlockBegin* start_block = blocks->at(0);
531 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == nullptr, "must be start block");
532 assert(start_block->next()->as_Base() != nullptr && start_block->next()->next() == nullptr, "start block must not have instructions");
533
534 // method parameters are not linked in instructions list, so process them separately
535 for_each_state_value(start_block->state(), value,
536 assert(value->as_Local() != nullptr, "only method parameters allowed");
537 set_processed(value);
538 );
539
540 // initial, empty value map with nesting 0
541 set_value_map_of(start_block, new ValueMap());
542
543 for (int i = 1; i < num_blocks; i++) {
544 BlockBegin* block = blocks->at(i);
545 TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id()));
546
547 int num_preds = block->number_of_preds();
548 assert(num_preds > 0, "block must have predecessors");
549
550 BlockBegin* dominator = block->dominator();
551 assert(dominator != nullptr, "dominator must exist");
552 assert(value_map_of(dominator) != nullptr, "value map of dominator must exist");
553
554 // create new value map with increased nesting
555 _current_map = new ValueMap(value_map_of(dominator));
556
557 if (num_preds == 1 && !block->is_set(BlockBegin::exception_entry_flag)) {
558 assert(dominator == block->pred_at(0), "dominator must be equal to predecessor");
559 // nothing to do here
560
561 } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
562 // block has incoming backward branches -> try to optimize short loops
563 if (!short_loop_optimizer.process(block)) {
564 // loop is too complicated, so kill all memory loads because there might be
565 // stores to them in the loop
566 current_map()->kill_memory();
567 }
568
569 } else {
570 // only incoming forward branches that are already processed
571 for (int j = 0; j < num_preds; j++) {
572 BlockBegin* pred = block->pred_at(j);
573 ValueMap* pred_map = value_map_of(pred);
574
575 if (pred_map != nullptr) {
576 // propagate killed values of the predecessor to this block
577 current_map()->kill_map(value_map_of(pred));
578 } else {
579 // kill all memory loads because predecessor not yet processed
580 // (this can happen with non-natural loops and OSR-compiles)
581 current_map()->kill_memory();
582 }
583 }
584 }
585
586 // phi functions are not linked in instructions list, so process them separateley
587 for_each_phi_fun(block, phi,
588 set_processed(phi);
589 );
590
591 TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print());
592
593 // visit all instructions of this block
594 for (Value instr = block->next(); instr != nullptr; instr = instr->next()) {
595 // check if instruction kills any values
596 instr->visit(this);
597 // perform actual value numbering
598 substitute(instr);
599 }
600
601 // remember value map for successors
602 set_value_map_of(block, current_map());
603 }
604
605 if (_has_substitutions) {
606 SubstitutionResolver resolver(ir);
607 }
608
609 TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics());
610 }
611
612 void GlobalValueNumbering::substitute(Instruction* instr) {
613 assert(!instr->has_subst(), "substitution already set");
614 Value subst = current_map()->find_insert(instr);
615 if (subst != instr) {
616 assert(!subst->has_subst(), "can't have a substitution");
617
618 TRACE_VALUE_NUMBERING(tty->print_cr("substitution for %c%d set to %c%d", instr->type()->tchar(), instr->id(), subst->type()->tchar(), subst->id()));
619 instr->set_subst(subst);
620 _has_substitutions = true;
621 }
622 set_processed(instr);
623 }