/
cfgnode.cpp
2736 lines (2516 loc) · 103 KB
/
cfgnode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Copyright (c) 1997, 2021, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "gc/shared/barrierSet.hpp"
#include "gc/shared/c2/barrierSetC2.hpp"
#include "memory/allocation.inline.hpp"
#include "memory/resourceArea.hpp"
#include "oops/objArrayKlass.hpp"
#include "opto/addnode.hpp"
#include "opto/castnode.hpp"
#include "opto/cfgnode.hpp"
#include "opto/connode.hpp"
#include "opto/convertnode.hpp"
#include "opto/loopnode.hpp"
#include "opto/machnode.hpp"
#include "opto/movenode.hpp"
#include "opto/narrowptrnode.hpp"
#include "opto/mulnode.hpp"
#include "opto/phaseX.hpp"
#include "opto/regmask.hpp"
#include "opto/runtime.hpp"
#include "opto/subnode.hpp"
#include "opto/vectornode.hpp"
#include "utilities/vmError.hpp"
// Portions of code courtesy of Clifford Click
// Optimization - Graph Style
//=============================================================================
//------------------------------Value------------------------------------------
// Compute the type of the RegionNode.
const Type* RegionNode::Value(PhaseGVN* phase) const {
for( uint i=1; i<req(); ++i ) { // For all paths in
Node *n = in(i); // Get Control source
if( !n ) continue; // Missing inputs are TOP
if( phase->type(n) == Type::CONTROL )
return Type::CONTROL;
}
return Type::TOP; // All paths dead? Then so are we
}
//------------------------------Identity---------------------------------------
// Check for Region being Identity.
Node* RegionNode::Identity(PhaseGVN* phase) {
// Cannot have Region be an identity, even if it has only 1 input.
// Phi users cannot have their Region input folded away for them,
// since they need to select the proper data input
return this;
}
//------------------------------merge_region-----------------------------------
// If a Region flows into a Region, merge into one big happy merge. This is
// hard to do if there is stuff that has to happen
static Node *merge_region(RegionNode *region, PhaseGVN *phase) {
if( region->Opcode() != Op_Region ) // Do not do to LoopNodes
return NULL;
Node *progress = NULL; // Progress flag
PhaseIterGVN *igvn = phase->is_IterGVN();
uint rreq = region->req();
for( uint i = 1; i < rreq; i++ ) {
Node *r = region->in(i);
if( r && r->Opcode() == Op_Region && // Found a region?
r->in(0) == r && // Not already collapsed?
r != region && // Avoid stupid situations
r->outcnt() == 2 ) { // Self user and 'region' user only?
assert(!r->as_Region()->has_phi(), "no phi users");
if( !progress ) { // No progress
if (region->has_phi()) {
return NULL; // Only flatten if no Phi users
// igvn->hash_delete( phi );
}
igvn->hash_delete( region );
progress = region; // Making progress
}
igvn->hash_delete( r );
// Append inputs to 'r' onto 'region'
for( uint j = 1; j < r->req(); j++ ) {
// Move an input from 'r' to 'region'
region->add_req(r->in(j));
r->set_req(j, phase->C->top());
// Update phis of 'region'
//for( uint k = 0; k < max; k++ ) {
// Node *phi = region->out(k);
// if( phi->is_Phi() ) {
// phi->add_req(phi->in(i));
// }
//}
rreq++; // One more input to Region
} // Found a region to merge into Region
igvn->_worklist.push(r);
// Clobber pointer to the now dead 'r'
region->set_req(i, phase->C->top());
}
}
return progress;
}
//--------------------------------has_phi--------------------------------------
// Helper function: Return any PhiNode that uses this region or NULL
PhiNode* RegionNode::has_phi() const {
for (DUIterator_Fast imax, i = fast_outs(imax); i < imax; i++) {
Node* phi = fast_out(i);
if (phi->is_Phi()) { // Check for Phi users
assert(phi->in(0) == (Node*)this, "phi uses region only via in(0)");
return phi->as_Phi(); // this one is good enough
}
}
return NULL;
}
//-----------------------------has_unique_phi----------------------------------
// Helper function: Return the only PhiNode that uses this region or NULL
PhiNode* RegionNode::has_unique_phi() const {
// Check that only one use is a Phi
PhiNode* only_phi = NULL;
for (DUIterator_Fast imax, i = fast_outs(imax); i < imax; i++) {
Node* phi = fast_out(i);
if (phi->is_Phi()) { // Check for Phi users
assert(phi->in(0) == (Node*)this, "phi uses region only via in(0)");
if (only_phi == NULL) {
only_phi = phi->as_Phi();
} else {
return NULL; // multiple phis
}
}
}
return only_phi;
}
//------------------------------check_phi_clipping-----------------------------
// Helper function for RegionNode's identification of FP clipping
// Check inputs to the Phi
static bool check_phi_clipping( PhiNode *phi, ConNode * &min, uint &min_idx, ConNode * &max, uint &max_idx, Node * &val, uint &val_idx ) {
min = NULL;
max = NULL;
val = NULL;
min_idx = 0;
max_idx = 0;
val_idx = 0;
uint phi_max = phi->req();
if( phi_max == 4 ) {
for( uint j = 1; j < phi_max; ++j ) {
Node *n = phi->in(j);
int opcode = n->Opcode();
switch( opcode ) {
case Op_ConI:
{
if( min == NULL ) {
min = n->Opcode() == Op_ConI ? (ConNode*)n : NULL;
min_idx = j;
} else {
max = n->Opcode() == Op_ConI ? (ConNode*)n : NULL;
max_idx = j;
if( min->get_int() > max->get_int() ) {
// Swap min and max
ConNode *temp;
uint temp_idx;
temp = min; min = max; max = temp;
temp_idx = min_idx; min_idx = max_idx; max_idx = temp_idx;
}
}
}
break;
default:
{
val = n;
val_idx = j;
}
break;
}
}
}
return ( min && max && val && (min->get_int() <= 0) && (max->get_int() >=0) );
}
//------------------------------check_if_clipping------------------------------
// Helper function for RegionNode's identification of FP clipping
// Check that inputs to Region come from two IfNodes,
//
// If
// False True
// If |
// False True |
// | | |
// RegionNode_inputs
//
static bool check_if_clipping( const RegionNode *region, IfNode * &bot_if, IfNode * &top_if ) {
top_if = NULL;
bot_if = NULL;
// Check control structure above RegionNode for (if ( if ) )
Node *in1 = region->in(1);
Node *in2 = region->in(2);
Node *in3 = region->in(3);
// Check that all inputs are projections
if( in1->is_Proj() && in2->is_Proj() && in3->is_Proj() ) {
Node *in10 = in1->in(0);
Node *in20 = in2->in(0);
Node *in30 = in3->in(0);
// Check that #1 and #2 are ifTrue and ifFalse from same If
if( in10 != NULL && in10->is_If() &&
in20 != NULL && in20->is_If() &&
in30 != NULL && in30->is_If() && in10 == in20 &&
(in1->Opcode() != in2->Opcode()) ) {
Node *in100 = in10->in(0);
Node *in1000 = (in100 != NULL && in100->is_Proj()) ? in100->in(0) : NULL;
// Check that control for in10 comes from other branch of IF from in3
if( in1000 != NULL && in1000->is_If() &&
in30 == in1000 && (in3->Opcode() != in100->Opcode()) ) {
// Control pattern checks
top_if = (IfNode*)in1000;
bot_if = (IfNode*)in10;
}
}
}
return (top_if != NULL);
}
//------------------------------check_convf2i_clipping-------------------------
// Helper function for RegionNode's identification of FP clipping
// Verify that the value input to the phi comes from "ConvF2I; LShift; RShift"
static bool check_convf2i_clipping( PhiNode *phi, uint idx, ConvF2INode * &convf2i, Node *min, Node *max) {
convf2i = NULL;
// Check for the RShiftNode
Node *rshift = phi->in(idx);
assert( rshift, "Previous checks ensure phi input is present");
if( rshift->Opcode() != Op_RShiftI ) { return false; }
// Check for the LShiftNode
Node *lshift = rshift->in(1);
assert( lshift, "Previous checks ensure phi input is present");
if( lshift->Opcode() != Op_LShiftI ) { return false; }
// Check for the ConvF2INode
Node *conv = lshift->in(1);
if( conv->Opcode() != Op_ConvF2I ) { return false; }
// Check that shift amounts are only to get sign bits set after F2I
jint max_cutoff = max->get_int();
jint min_cutoff = min->get_int();
jint left_shift = lshift->in(2)->get_int();
jint right_shift = rshift->in(2)->get_int();
jint max_post_shift = nth_bit(BitsPerJavaInteger - left_shift - 1);
if( left_shift != right_shift ||
0 > left_shift || left_shift >= BitsPerJavaInteger ||
max_post_shift < max_cutoff ||
max_post_shift < -min_cutoff ) {
// Shifts are necessary but current transformation eliminates them
return false;
}
// OK to return the result of ConvF2I without shifting
convf2i = (ConvF2INode*)conv;
return true;
}
//------------------------------check_compare_clipping-------------------------
// Helper function for RegionNode's identification of FP clipping
static bool check_compare_clipping( bool less_than, IfNode *iff, ConNode *limit, Node * & input ) {
Node *i1 = iff->in(1);
if ( !i1->is_Bool() ) { return false; }
BoolNode *bool1 = i1->as_Bool();
if( less_than && bool1->_test._test != BoolTest::le ) { return false; }
else if( !less_than && bool1->_test._test != BoolTest::lt ) { return false; }
const Node *cmpF = bool1->in(1);
if( cmpF->Opcode() != Op_CmpF ) { return false; }
// Test that the float value being compared against
// is equivalent to the int value used as a limit
Node *nodef = cmpF->in(2);
if( nodef->Opcode() != Op_ConF ) { return false; }
jfloat conf = nodef->getf();
jint coni = limit->get_int();
if( ((int)conf) != coni ) { return false; }
input = cmpF->in(1);
return true;
}
//------------------------------is_unreachable_region--------------------------
// Find if the Region node is reachable from the root.
bool RegionNode::is_unreachable_region(const PhaseGVN* phase) {
Node* top = phase->C->top();
assert(req() == 2 || (req() == 3 && in(1) != NULL && in(2) == top), "sanity check arguments");
if (_is_unreachable_region) {
// Return cached result from previous evaluation which should still be valid
assert(is_unreachable_from_root(phase), "walk the graph again and check if its indeed unreachable");
return true;
}
// First, cut the simple case of fallthrough region when NONE of
// region's phis references itself directly or through a data node.
if (is_possible_unsafe_loop(phase)) {
// If we have a possible unsafe loop, check if the region node is actually unreachable from root.
if (is_unreachable_from_root(phase)) {
_is_unreachable_region = true;
return true;
}
}
return false;
}
bool RegionNode::is_possible_unsafe_loop(const PhaseGVN* phase) const {
uint max = outcnt();
uint i;
for (i = 0; i < max; i++) {
Node* n = raw_out(i);
if (n != NULL && n->is_Phi()) {
PhiNode* phi = n->as_Phi();
assert(phi->in(0) == this, "sanity check phi");
if (phi->outcnt() == 0) {
continue; // Safe case - no loops
}
if (phi->outcnt() == 1) {
Node* u = phi->raw_out(0);
// Skip if only one use is an other Phi or Call or Uncommon trap.
// It is safe to consider this case as fallthrough.
if (u != NULL && (u->is_Phi() || u->is_CFG())) {
continue;
}
}
// Check when phi references itself directly or through an other node.
if (phi->as_Phi()->simple_data_loop_check(phi->in(1)) >= PhiNode::Unsafe) {
break; // Found possible unsafe data loop.
}
}
}
if (i >= max) {
return false; // An unsafe case was NOT found - don't need graph walk.
}
return true;
}
bool RegionNode::is_unreachable_from_root(const PhaseGVN* phase) const {
ResourceMark rm;
Node_List nstack;
VectorSet visited;
// Mark all control nodes reachable from root outputs
Node *n = (Node*)phase->C->root();
nstack.push(n);
visited.set(n->_idx);
while (nstack.size() != 0) {
n = nstack.pop();
uint max = n->outcnt();
for (uint i = 0; i < max; i++) {
Node* m = n->raw_out(i);
if (m != NULL && m->is_CFG()) {
if (m == this) {
return false; // We reached the Region node - it is not dead.
}
if (!visited.test_set(m->_idx))
nstack.push(m);
}
}
}
return true; // The Region node is unreachable - it is dead.
}
bool RegionNode::try_clean_mem_phi(PhaseGVN *phase) {
// Incremental inlining + PhaseStringOpts sometimes produce:
//
// cmpP with 1 top input
// |
// If
// / \
// IfFalse IfTrue /- Some Node
// \ / / /
// Region / /-MergeMem
// \---Phi
//
//
// It's expected by PhaseStringOpts that the Region goes away and is
// replaced by If's control input but because there's still a Phi,
// the Region stays in the graph. The top input from the cmpP is
// propagated forward and a subgraph that is useful goes away. The
// code below replaces the Phi with the MergeMem so that the Region
// is simplified.
PhiNode* phi = has_unique_phi();
if (phi && phi->type() == Type::MEMORY && req() == 3 && phi->is_diamond_phi(true)) {
MergeMemNode* m = NULL;
assert(phi->req() == 3, "same as region");
for (uint i = 1; i < 3; ++i) {
Node *mem = phi->in(i);
if (mem && mem->is_MergeMem() && in(i)->outcnt() == 1) {
// Nothing is control-dependent on path #i except the region itself.
m = mem->as_MergeMem();
uint j = 3 - i;
Node* other = phi->in(j);
if (other && other == m->base_memory()) {
// m is a successor memory to other, and is not pinned inside the diamond, so push it out.
// This will allow the diamond to collapse completely.
phase->is_IterGVN()->replace_node(phi, m);
return true;
}
}
}
}
return false;
}
//------------------------------Ideal------------------------------------------
// Return a node which is more "ideal" than the current node. Must preserve
// the CFG, but we can still strip out dead paths.
Node *RegionNode::Ideal(PhaseGVN *phase, bool can_reshape) {
if( !can_reshape && !in(0) ) return NULL; // Already degraded to a Copy
assert(!in(0) || !in(0)->is_Root(), "not a specially hidden merge");
// Check for RegionNode with no Phi users and both inputs come from either
// arm of the same IF. If found, then the control-flow split is useless.
bool has_phis = false;
if (can_reshape) { // Need DU info to check for Phi users
has_phis = (has_phi() != NULL); // Cache result
if (has_phis && try_clean_mem_phi(phase)) {
has_phis = false;
}
if (!has_phis) { // No Phi users? Nothing merging?
for (uint i = 1; i < req()-1; i++) {
Node *if1 = in(i);
if( !if1 ) continue;
Node *iff = if1->in(0);
if( !iff || !iff->is_If() ) continue;
for( uint j=i+1; j<req(); j++ ) {
if( in(j) && in(j)->in(0) == iff &&
if1->Opcode() != in(j)->Opcode() ) {
// Add the IF Projections to the worklist. They (and the IF itself)
// will be eliminated if dead.
phase->is_IterGVN()->add_users_to_worklist(iff);
set_req(i, iff->in(0));// Skip around the useless IF diamond
set_req(j, NULL);
return this; // Record progress
}
}
}
}
}
// Remove TOP or NULL input paths. If only 1 input path remains, this Region
// degrades to a copy.
bool add_to_worklist = false;
bool modified = false;
int cnt = 0; // Count of values merging
DEBUG_ONLY( int cnt_orig = req(); ) // Save original inputs count
int del_it = 0; // The last input path we delete
// For all inputs...
for( uint i=1; i<req(); ++i ){// For all paths in
Node *n = in(i); // Get the input
if( n != NULL ) {
// Remove useless control copy inputs
if( n->is_Region() && n->as_Region()->is_copy() ) {
set_req(i, n->nonnull_req());
modified = true;
i--;
continue;
}
if( n->is_Proj() ) { // Remove useless rethrows
Node *call = n->in(0);
if (call->is_Call() && call->as_Call()->entry_point() == OptoRuntime::rethrow_stub()) {
set_req(i, call->in(0));
modified = true;
i--;
continue;
}
}
if( phase->type(n) == Type::TOP ) {
set_req(i, NULL); // Ignore TOP inputs
modified = true;
i--;
continue;
}
cnt++; // One more value merging
} else if (can_reshape) { // Else found dead path with DU info
PhaseIterGVN *igvn = phase->is_IterGVN();
del_req(i); // Yank path from self
del_it = i;
uint max = outcnt();
DUIterator j;
bool progress = true;
while(progress) { // Need to establish property over all users
progress = false;
for (j = outs(); has_out(j); j++) {
Node *n = out(j);
if( n->req() != req() && n->is_Phi() ) {
assert( n->in(0) == this, "" );
igvn->hash_delete(n); // Yank from hash before hacking edges
n->set_req_X(i,NULL,igvn);// Correct DU info
n->del_req(i); // Yank path from Phis
if( max != outcnt() ) {
progress = true;
j = refresh_out_pos(j);
max = outcnt();
}
}
}
}
add_to_worklist = true;
i--;
}
}
if (can_reshape && cnt == 1) {
// Is it dead loop?
// If it is LoopNopde it had 2 (+1 itself) inputs and
// one of them was cut. The loop is dead if it was EntryContol.
// Loop node may have only one input because entry path
// is removed in PhaseIdealLoop::Dominators().
assert(!this->is_Loop() || cnt_orig <= 3, "Loop node should have 3 or less inputs");
if ((this->is_Loop() && (del_it == LoopNode::EntryControl ||
(del_it == 0 && is_unreachable_region(phase)))) ||
(!this->is_Loop() && has_phis && is_unreachable_region(phase))) {
// Yes, the region will be removed during the next step below.
// Cut the backedge input and remove phis since no data paths left.
// We don't cut outputs to other nodes here since we need to put them
// on the worklist.
PhaseIterGVN *igvn = phase->is_IterGVN();
if (in(1)->outcnt() == 1) {
igvn->_worklist.push(in(1));
}
del_req(1);
cnt = 0;
assert( req() == 1, "no more inputs expected" );
uint max = outcnt();
bool progress = true;
Node *top = phase->C->top();
DUIterator j;
while(progress) {
progress = false;
for (j = outs(); has_out(j); j++) {
Node *n = out(j);
if( n->is_Phi() ) {
assert(n->in(0) == this, "");
assert( n->req() == 2 && n->in(1) != NULL, "Only one data input expected" );
// Break dead loop data path.
// Eagerly replace phis with top to avoid regionless phis.
igvn->replace_node(n, top);
if( max != outcnt() ) {
progress = true;
j = refresh_out_pos(j);
max = outcnt();
}
}
}
}
add_to_worklist = true;
}
}
if (add_to_worklist) {
phase->is_IterGVN()->add_users_to_worklist(this); // Revisit collapsed Phis
}
if( cnt <= 1 ) { // Only 1 path in?
set_req(0, NULL); // Null control input for region copy
if( cnt == 0 && !can_reshape) { // Parse phase - leave the node as it is.
// No inputs or all inputs are NULL.
return NULL;
} else if (can_reshape) { // Optimization phase - remove the node
PhaseIterGVN *igvn = phase->is_IterGVN();
// Strip mined (inner) loop is going away, remove outer loop.
if (is_CountedLoop() &&
as_Loop()->is_strip_mined()) {
Node* outer_sfpt = as_CountedLoop()->outer_safepoint();
Node* outer_out = as_CountedLoop()->outer_loop_exit();
if (outer_sfpt != NULL && outer_out != NULL) {
Node* in = outer_sfpt->in(0);
igvn->replace_node(outer_out, in);
LoopNode* outer = as_CountedLoop()->outer_loop();
igvn->replace_input_of(outer, LoopNode::LoopBackControl, igvn->C->top());
}
}
if (is_CountedLoop()) {
Node* opaq = as_CountedLoop()->is_canonical_loop_entry();
if (opaq != NULL) {
// This is not a loop anymore. No need to keep the Opaque1 node on the test that guards the loop as it won't be
// subject to further loop opts.
assert(opaq->Opcode() == Op_Opaque1, "");
igvn->replace_node(opaq, opaq->in(1));
}
}
Node *parent_ctrl;
if( cnt == 0 ) {
assert( req() == 1, "no inputs expected" );
// During IGVN phase such region will be subsumed by TOP node
// so region's phis will have TOP as control node.
// Kill phis here to avoid it.
// Also set other user's input to top.
parent_ctrl = phase->C->top();
} else {
// The fallthrough case since we already checked dead loops above.
parent_ctrl = in(1);
assert(parent_ctrl != NULL, "Region is a copy of some non-null control");
assert(parent_ctrl != this, "Close dead loop");
}
if (!add_to_worklist)
igvn->add_users_to_worklist(this); // Check for further allowed opts
for (DUIterator_Last imin, i = last_outs(imin); i >= imin; --i) {
Node* n = last_out(i);
igvn->hash_delete(n); // Remove from worklist before modifying edges
if (n->outcnt() == 0) {
int uses_found = n->replace_edge(this, phase->C->top(), igvn);
if (uses_found > 1) { // (--i) done at the end of the loop.
i -= (uses_found - 1);
}
continue;
}
if( n->is_Phi() ) { // Collapse all Phis
// Eagerly replace phis to avoid regionless phis.
Node* in;
if( cnt == 0 ) {
assert( n->req() == 1, "No data inputs expected" );
in = parent_ctrl; // replaced by top
} else {
assert( n->req() == 2 && n->in(1) != NULL, "Only one data input expected" );
in = n->in(1); // replaced by unique input
if( n->as_Phi()->is_unsafe_data_reference(in) )
in = phase->C->top(); // replaced by top
}
igvn->replace_node(n, in);
}
else if( n->is_Region() ) { // Update all incoming edges
assert(n != this, "Must be removed from DefUse edges");
int uses_found = n->replace_edge(this, parent_ctrl, igvn);
if (uses_found > 1) { // (--i) done at the end of the loop.
i -= (uses_found - 1);
}
}
else {
assert(n->in(0) == this, "Expect RegionNode to be control parent");
n->set_req(0, parent_ctrl);
}
#ifdef ASSERT
for( uint k=0; k < n->req(); k++ ) {
assert(n->in(k) != this, "All uses of RegionNode should be gone");
}
#endif
}
// Remove the RegionNode itself from DefUse info
igvn->remove_dead_node(this);
return NULL;
}
return this; // Record progress
}
// If a Region flows into a Region, merge into one big happy merge.
if (can_reshape) {
Node *m = merge_region(this, phase);
if (m != NULL) return m;
}
// Check if this region is the root of a clipping idiom on floats
if( ConvertFloat2IntClipping && can_reshape && req() == 4 ) {
// Check that only one use is a Phi and that it simplifies to two constants +
PhiNode* phi = has_unique_phi();
if (phi != NULL) { // One Phi user
// Check inputs to the Phi
ConNode *min;
ConNode *max;
Node *val;
uint min_idx;
uint max_idx;
uint val_idx;
if( check_phi_clipping( phi, min, min_idx, max, max_idx, val, val_idx ) ) {
IfNode *top_if;
IfNode *bot_if;
if( check_if_clipping( this, bot_if, top_if ) ) {
// Control pattern checks, now verify compares
Node *top_in = NULL; // value being compared against
Node *bot_in = NULL;
if( check_compare_clipping( true, bot_if, min, bot_in ) &&
check_compare_clipping( false, top_if, max, top_in ) ) {
if( bot_in == top_in ) {
PhaseIterGVN *gvn = phase->is_IterGVN();
assert( gvn != NULL, "Only had DefUse info in IterGVN");
// Only remaining check is that bot_in == top_in == (Phi's val + mods)
// Check for the ConvF2INode
ConvF2INode *convf2i;
if( check_convf2i_clipping( phi, val_idx, convf2i, min, max ) &&
convf2i->in(1) == bot_in ) {
// Matched pattern, including LShiftI; RShiftI, replace with integer compares
// max test
Node *cmp = gvn->register_new_node_with_optimizer(new CmpINode( convf2i, min ));
Node *boo = gvn->register_new_node_with_optimizer(new BoolNode( cmp, BoolTest::lt ));
IfNode *iff = (IfNode*)gvn->register_new_node_with_optimizer(new IfNode( top_if->in(0), boo, PROB_UNLIKELY_MAG(5), top_if->_fcnt ));
Node *if_min= gvn->register_new_node_with_optimizer(new IfTrueNode (iff));
Node *ifF = gvn->register_new_node_with_optimizer(new IfFalseNode(iff));
// min test
cmp = gvn->register_new_node_with_optimizer(new CmpINode( convf2i, max ));
boo = gvn->register_new_node_with_optimizer(new BoolNode( cmp, BoolTest::gt ));
iff = (IfNode*)gvn->register_new_node_with_optimizer(new IfNode( ifF, boo, PROB_UNLIKELY_MAG(5), bot_if->_fcnt ));
Node *if_max= gvn->register_new_node_with_optimizer(new IfTrueNode (iff));
ifF = gvn->register_new_node_with_optimizer(new IfFalseNode(iff));
// update input edges to region node
set_req_X( min_idx, if_min, gvn );
set_req_X( max_idx, if_max, gvn );
set_req_X( val_idx, ifF, gvn );
// remove unnecessary 'LShiftI; RShiftI' idiom
gvn->hash_delete(phi);
phi->set_req_X( val_idx, convf2i, gvn );
gvn->hash_find_insert(phi);
// Return transformed region node
return this;
}
}
}
}
}
}
}
if (can_reshape) {
modified |= optimize_trichotomy(phase->is_IterGVN());
}
return modified ? this : NULL;
}
//------------------------------optimize_trichotomy--------------------------
// Optimize nested comparisons of the following kind:
//
// int compare(int a, int b) {
// return (a < b) ? -1 : (a == b) ? 0 : 1;
// }
//
// Shape 1:
// if (compare(a, b) == 1) { ... } -> if (a > b) { ... }
//
// Shape 2:
// if (compare(a, b) == 0) { ... } -> if (a == b) { ... }
//
// Above code leads to the following IR shapes where both Ifs compare the
// same value and two out of three region inputs idx1 and idx2 map to
// the same value and control flow.
//
// (1) If (2) If
// / \ / \
// Proj Proj Proj Proj
// | \ | \
// | If | If If
// | / \ | / \ / \
// | Proj Proj | Proj Proj ==> Proj Proj
// | / / \ | / | /
// Region / \ | / | /
// \ / \ | / | /
// Region Region Region
//
// The method returns true if 'this' is modified and false otherwise.
bool RegionNode::optimize_trichotomy(PhaseIterGVN* igvn) {
int idx1 = 1, idx2 = 2;
Node* region = NULL;
if (req() == 3 && in(1) != NULL && in(2) != NULL) {
// Shape 1: Check if one of the inputs is a region that merges two control
// inputs and has no other users (especially no Phi users).
region = in(1)->isa_Region() ? in(1) : in(2)->isa_Region();
if (region == NULL || region->outcnt() != 2 || region->req() != 3) {
return false; // No suitable region input found
}
} else if (req() == 4) {
// Shape 2: Check if two control inputs map to the same value of the unique phi
// user and treat these as if they would come from another region (shape (1)).
PhiNode* phi = has_unique_phi();
if (phi == NULL) {
return false; // No unique phi user
}
if (phi->in(idx1) != phi->in(idx2)) {
idx2 = 3;
if (phi->in(idx1) != phi->in(idx2)) {
idx1 = 2;
if (phi->in(idx1) != phi->in(idx2)) {
return false; // No equal phi inputs found
}
}
}
assert(phi->in(idx1) == phi->in(idx2), "must be"); // Region is merging same value
region = this;
}
if (region == NULL || region->in(idx1) == NULL || region->in(idx2) == NULL) {
return false; // Region does not merge two control inputs
}
// At this point we know that region->in(idx1) and region->(idx2) map to the same
// value and control flow. Now search for ifs that feed into these region inputs.
ProjNode* proj1 = region->in(idx1)->isa_Proj();
ProjNode* proj2 = region->in(idx2)->isa_Proj();
if (proj1 == NULL || proj1->outcnt() != 1 ||
proj2 == NULL || proj2->outcnt() != 1) {
return false; // No projection inputs with region as unique user found
}
assert(proj1 != proj2, "should be different projections");
IfNode* iff1 = proj1->in(0)->isa_If();
IfNode* iff2 = proj2->in(0)->isa_If();
if (iff1 == NULL || iff1->outcnt() != 2 ||
iff2 == NULL || iff2->outcnt() != 2) {
return false; // No ifs found
}
if (iff1 == iff2) {
igvn->add_users_to_worklist(iff1); // Make sure dead if is eliminated
igvn->replace_input_of(region, idx1, iff1->in(0));
igvn->replace_input_of(region, idx2, igvn->C->top());
return (region == this); // Remove useless if (both projections map to the same control/value)
}
BoolNode* bol1 = iff1->in(1)->isa_Bool();
BoolNode* bol2 = iff2->in(1)->isa_Bool();
if (bol1 == NULL || bol2 == NULL) {
return false; // No bool inputs found
}
Node* cmp1 = bol1->in(1);
Node* cmp2 = bol2->in(1);
bool commute = false;
if (!cmp1->is_Cmp() || !cmp2->is_Cmp()) {
return false; // No comparison
} else if (cmp1->Opcode() == Op_CmpF || cmp1->Opcode() == Op_CmpD ||
cmp2->Opcode() == Op_CmpF || cmp2->Opcode() == Op_CmpD ||
cmp1->Opcode() == Op_CmpP || cmp1->Opcode() == Op_CmpN ||
cmp2->Opcode() == Op_CmpP || cmp2->Opcode() == Op_CmpN ||
cmp1->is_SubTypeCheck() || cmp2->is_SubTypeCheck()) {
// Floats and pointers don't exactly obey trichotomy. To be on the safe side, don't transform their tests.
// SubTypeCheck is not commutative
return false;
} else if (cmp1 != cmp2) {
if (cmp1->in(1) == cmp2->in(2) &&
cmp1->in(2) == cmp2->in(1)) {
commute = true; // Same but swapped inputs, commute the test
} else {
return false; // Ifs are not comparing the same values
}
}
proj1 = proj1->other_if_proj();
proj2 = proj2->other_if_proj();
if (!((proj1->unique_ctrl_out() == iff2 &&
proj2->unique_ctrl_out() == this) ||
(proj2->unique_ctrl_out() == iff1 &&
proj1->unique_ctrl_out() == this))) {
return false; // Ifs are not connected through other projs
}
// Found 'iff -> proj -> iff -> proj -> this' shape where all other projs are merged
// through 'region' and map to the same value. Merge the boolean tests and replace
// the ifs by a single comparison.
BoolTest test1 = (proj1->_con == 1) ? bol1->_test : bol1->_test.negate();
BoolTest test2 = (proj2->_con == 1) ? bol2->_test : bol2->_test.negate();
test1 = commute ? test1.commute() : test1;
// After possibly commuting test1, if we can merge test1 & test2, then proj2/iff2/bol2 are the nodes to refine.
BoolTest::mask res = test1.merge(test2);
if (res == BoolTest::illegal) {
return false; // Unable to merge tests
}
// Adjust iff1 to always pass (only iff2 will remain)
igvn->replace_input_of(iff1, 1, igvn->intcon(proj1->_con));
if (res == BoolTest::never) {
// Merged test is always false, adjust iff2 to always fail
igvn->replace_input_of(iff2, 1, igvn->intcon(1 - proj2->_con));
} else {
// Replace bool input of iff2 with merged test
BoolNode* new_bol = new BoolNode(bol2->in(1), res);
igvn->replace_input_of(iff2, 1, igvn->transform((proj2->_con == 1) ? new_bol : new_bol->negate(igvn)));
if (new_bol->outcnt() == 0) {
igvn->remove_dead_node(new_bol);
}
}
return false;
}
const RegMask &RegionNode::out_RegMask() const {
return RegMask::Empty;
}
// Find the one non-null required input. RegionNode only
Node *Node::nonnull_req() const {
assert( is_Region(), "" );
for( uint i = 1; i < _cnt; i++ )
if( in(i) )
return in(i);
ShouldNotReachHere();
return NULL;
}
//=============================================================================
// note that these functions assume that the _adr_type field is flattened
uint PhiNode::hash() const {
const Type* at = _adr_type;
return TypeNode::hash() + (at ? at->hash() : 0);
}
bool PhiNode::cmp( const Node &n ) const {
return TypeNode::cmp(n) && _adr_type == ((PhiNode&)n)._adr_type;
}
static inline
const TypePtr* flatten_phi_adr_type(const TypePtr* at) {
if (at == NULL || at == TypePtr::BOTTOM) return at;
return Compile::current()->alias_type(at)->adr_type();
}
//----------------------------make---------------------------------------------
// create a new phi with edges matching r and set (initially) to x
PhiNode* PhiNode::make(Node* r, Node* x, const Type *t, const TypePtr* at) {
uint preds = r->req(); // Number of predecessor paths
assert(t != Type::MEMORY || at == flatten_phi_adr_type(at), "flatten at");
PhiNode* p = new PhiNode(r, t, at);
for (uint j = 1; j < preds; j++) {
// Fill in all inputs, except those which the region does not yet have
if (r->in(j) != NULL)
p->init_req(j, x);
}
return p;
}
PhiNode* PhiNode::make(Node* r, Node* x) {
const Type* t = x->bottom_type();
const TypePtr* at = NULL;
if (t == Type::MEMORY) at = flatten_phi_adr_type(x->adr_type());
return make(r, x, t, at);
}
PhiNode* PhiNode::make_blank(Node* r, Node* x) {
const Type* t = x->bottom_type();
const TypePtr* at = NULL;
if (t == Type::MEMORY) at = flatten_phi_adr_type(x->adr_type());
return new PhiNode(r, t, at);
}
//------------------------slice_memory-----------------------------------------
// create a new phi with narrowed memory type
PhiNode* PhiNode::slice_memory(const TypePtr* adr_type) const {
PhiNode* mem = (PhiNode*) clone();
*(const TypePtr**)&mem->_adr_type = adr_type;
// convert self-loops, or else we get a bad graph
for (uint i = 1; i < req(); i++) {
if ((const Node*)in(i) == this) mem->set_req(i, mem);
}
mem->verify_adr_type();
return mem;
}
//------------------------split_out_instance-----------------------------------
// Split out an instance type from a bottom phi.
PhiNode* PhiNode::split_out_instance(const TypePtr* at, PhaseIterGVN *igvn) const {
const TypeOopPtr *t_oop = at->isa_oopptr();
assert(t_oop != NULL && t_oop->is_known_instance(), "expecting instance oopptr");
const TypePtr *t = adr_type();
assert(type() == Type::MEMORY &&
(t == TypePtr::BOTTOM || t == TypeRawPtr::BOTTOM ||
t->isa_oopptr() && !t->is_oopptr()->is_known_instance() &&
t->is_oopptr()->cast_to_exactness(true)
->is_oopptr()->cast_to_ptr_type(t_oop->ptr())
->is_oopptr()->cast_to_instance_id(t_oop->instance_id()) == t_oop),
"bottom or raw memory required");
// Check if an appropriate node already exists.
Node *region = in(0);
for (DUIterator_Fast kmax, k = region->fast_outs(kmax); k < kmax; k++) {
Node* use = region->fast_out(k);
if( use->is_Phi()) {
PhiNode *phi2 = use->as_Phi();
if (phi2->type() == Type::MEMORY && phi2->adr_type() == at) {
return phi2;
}
}
}
Compile *C = igvn->C;
Arena *a = Thread::current()->resource_area();
Node_Array node_map = new Node_Array(a);
Node_Stack stack(a, C->live_nodes() >> 4);
PhiNode *nphi = slice_memory(at);