/
loopnode.hpp
1915 lines (1604 loc) · 79.3 KB
/
loopnode.hpp
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) 1998, 2022, 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.
*
*/
#ifndef SHARE_OPTO_LOOPNODE_HPP
#define SHARE_OPTO_LOOPNODE_HPP
#include "opto/cfgnode.hpp"
#include "opto/multnode.hpp"
#include "opto/phaseX.hpp"
#include "opto/subnode.hpp"
#include "opto/type.hpp"
class CmpNode;
class BaseCountedLoopEndNode;
class CountedLoopNode;
class IdealLoopTree;
class LoopNode;
class Node;
class OuterStripMinedLoopEndNode;
class PathFrequency;
class PhaseIdealLoop;
class CountedLoopReserveKit;
class VectorSet;
class Invariance;
struct small_cache;
//
// I D E A L I Z E D L O O P S
//
// Idealized loops are the set of loops I perform more interesting
// transformations on, beyond simple hoisting.
//------------------------------LoopNode---------------------------------------
// Simple loop header. Fall in path on left, loop-back path on right.
class LoopNode : public RegionNode {
// Size is bigger to hold the flags. However, the flags do not change
// the semantics so it does not appear in the hash & cmp functions.
virtual uint size_of() const { return sizeof(*this); }
protected:
uint _loop_flags;
// Names for flag bitfields
enum { Normal=0, Pre=1, Main=2, Post=3, PreMainPostFlagsMask=3,
MainHasNoPreLoop = 1<<2,
HasExactTripCount = 1<<3,
InnerLoop = 1<<4,
PartialPeelLoop = 1<<5,
PartialPeelFailed = 1<<6,
HasReductions = 1<<7,
WasSlpAnalyzed = 1<<8,
PassedSlpAnalysis = 1<<9,
DoUnrollOnly = 1<<10,
VectorizedLoop = 1<<11,
HasAtomicPostLoop = 1<<12,
HasRangeChecks = 1<<13,
IsMultiversioned = 1<<14,
StripMined = 1<<15,
SubwordLoop = 1<<16,
ProfileTripFailed = 1<<17,
LoopNestInnerLoop = 1 << 18,
LoopNestLongOuterLoop = 1 << 19};
char _unswitch_count;
enum { _unswitch_max=3 };
char _postloop_flags;
enum { LoopNotRCEChecked = 0, LoopRCEChecked = 1, RCEPostLoop = 2 };
// Expected trip count from profile data
float _profile_trip_cnt;
public:
// Names for edge indices
enum { Self=0, EntryControl, LoopBackControl };
bool is_inner_loop() const { return _loop_flags & InnerLoop; }
void set_inner_loop() { _loop_flags |= InnerLoop; }
bool range_checks_present() const { return _loop_flags & HasRangeChecks; }
bool is_multiversioned() const { return _loop_flags & IsMultiversioned; }
bool is_vectorized_loop() const { return _loop_flags & VectorizedLoop; }
bool is_partial_peel_loop() const { return _loop_flags & PartialPeelLoop; }
void set_partial_peel_loop() { _loop_flags |= PartialPeelLoop; }
bool partial_peel_has_failed() const { return _loop_flags & PartialPeelFailed; }
bool is_strip_mined() const { return _loop_flags & StripMined; }
bool is_profile_trip_failed() const { return _loop_flags & ProfileTripFailed; }
bool is_subword_loop() const { return _loop_flags & SubwordLoop; }
bool is_loop_nest_inner_loop() const { return _loop_flags & LoopNestInnerLoop; }
bool is_loop_nest_outer_loop() const { return _loop_flags & LoopNestLongOuterLoop; }
void mark_partial_peel_failed() { _loop_flags |= PartialPeelFailed; }
void mark_has_reductions() { _loop_flags |= HasReductions; }
void mark_was_slp() { _loop_flags |= WasSlpAnalyzed; }
void mark_passed_slp() { _loop_flags |= PassedSlpAnalysis; }
void mark_do_unroll_only() { _loop_flags |= DoUnrollOnly; }
void mark_loop_vectorized() { _loop_flags |= VectorizedLoop; }
void mark_has_atomic_post_loop() { _loop_flags |= HasAtomicPostLoop; }
void mark_has_range_checks() { _loop_flags |= HasRangeChecks; }
void clear_has_range_checks() { _loop_flags &= ~HasRangeChecks; }
void mark_is_multiversioned() { _loop_flags |= IsMultiversioned; }
void mark_strip_mined() { _loop_flags |= StripMined; }
void clear_strip_mined() { _loop_flags &= ~StripMined; }
void mark_profile_trip_failed() { _loop_flags |= ProfileTripFailed; }
void mark_subword_loop() { _loop_flags |= SubwordLoop; }
void mark_loop_nest_inner_loop() { _loop_flags |= LoopNestInnerLoop; }
void mark_loop_nest_outer_loop() { _loop_flags |= LoopNestLongOuterLoop; }
int unswitch_max() { return _unswitch_max; }
int unswitch_count() { return _unswitch_count; }
int has_been_range_checked() const { return _postloop_flags & LoopRCEChecked; }
void set_has_been_range_checked() { _postloop_flags |= LoopRCEChecked; }
int is_rce_post_loop() const { return _postloop_flags & RCEPostLoop; }
void set_is_rce_post_loop() { _postloop_flags |= RCEPostLoop; }
void set_unswitch_count(int val) {
assert (val <= unswitch_max(), "too many unswitches");
_unswitch_count = val;
}
void set_profile_trip_cnt(float ptc) { _profile_trip_cnt = ptc; }
float profile_trip_cnt() { return _profile_trip_cnt; }
LoopNode(Node *entry, Node *backedge)
: RegionNode(3), _loop_flags(0), _unswitch_count(0),
_postloop_flags(0), _profile_trip_cnt(COUNT_UNKNOWN) {
init_class_id(Class_Loop);
init_req(EntryControl, entry);
init_req(LoopBackControl, backedge);
}
virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
virtual int Opcode() const;
bool can_be_counted_loop(PhaseTransform* phase) const {
return req() == 3 && in(0) != NULL &&
in(1) != NULL && phase->type(in(1)) != Type::TOP &&
in(2) != NULL && phase->type(in(2)) != Type::TOP;
}
bool is_valid_counted_loop(BasicType bt) const;
#ifndef PRODUCT
virtual void dump_spec(outputStream *st) const;
#endif
void verify_strip_mined(int expect_skeleton) const NOT_DEBUG_RETURN;
virtual LoopNode* skip_strip_mined(int expect_skeleton = 1) { return this; }
virtual IfTrueNode* outer_loop_tail() const { ShouldNotReachHere(); return NULL; }
virtual OuterStripMinedLoopEndNode* outer_loop_end() const { ShouldNotReachHere(); return NULL; }
virtual IfFalseNode* outer_loop_exit() const { ShouldNotReachHere(); return NULL; }
virtual SafePointNode* outer_safepoint() const { ShouldNotReachHere(); return NULL; }
};
//------------------------------Counted Loops----------------------------------
// Counted loops are all trip-counted loops, with exactly 1 trip-counter exit
// path (and maybe some other exit paths). The trip-counter exit is always
// last in the loop. The trip-counter have to stride by a constant;
// the exit value is also loop invariant.
// CountedLoopNodes and CountedLoopEndNodes come in matched pairs. The
// CountedLoopNode has the incoming loop control and the loop-back-control
// which is always the IfTrue before the matching CountedLoopEndNode. The
// CountedLoopEndNode has an incoming control (possibly not the
// CountedLoopNode if there is control flow in the loop), the post-increment
// trip-counter value, and the limit. The trip-counter value is always of
// the form (Op old-trip-counter stride). The old-trip-counter is produced
// by a Phi connected to the CountedLoopNode. The stride is constant.
// The Op is any commutable opcode, including Add, Mul, Xor. The
// CountedLoopEndNode also takes in the loop-invariant limit value.
// From a CountedLoopNode I can reach the matching CountedLoopEndNode via the
// loop-back control. From CountedLoopEndNodes I can reach CountedLoopNodes
// via the old-trip-counter from the Op node.
//------------------------------CountedLoopNode--------------------------------
// CountedLoopNodes head simple counted loops. CountedLoopNodes have as
// inputs the incoming loop-start control and the loop-back control, so they
// act like RegionNodes. They also take in the initial trip counter, the
// loop-invariant stride and the loop-invariant limit value. CountedLoopNodes
// produce a loop-body control and the trip counter value. Since
// CountedLoopNodes behave like RegionNodes I still have a standard CFG model.
class BaseCountedLoopNode : public LoopNode {
public:
BaseCountedLoopNode(Node *entry, Node *backedge)
: LoopNode(entry, backedge) {
}
Node *init_control() const { return in(EntryControl); }
Node *back_control() const { return in(LoopBackControl); }
Node* init_trip() const;
Node* stride() const;
bool stride_is_con() const;
Node* limit() const;
Node* incr() const;
Node* phi() const;
BaseCountedLoopEndNode* loopexit_or_null() const;
BaseCountedLoopEndNode* loopexit() const;
virtual BasicType bt() const = 0;
jlong stride_con() const;
static BaseCountedLoopNode* make(Node* entry, Node* backedge, BasicType bt);
};
class CountedLoopNode : public BaseCountedLoopNode {
// Size is bigger to hold _main_idx. However, _main_idx does not change
// the semantics so it does not appear in the hash & cmp functions.
virtual uint size_of() const { return sizeof(*this); }
// For Pre- and Post-loops during debugging ONLY, this holds the index of
// the Main CountedLoop. Used to assert that we understand the graph shape.
node_idx_t _main_idx;
// Known trip count calculated by compute_exact_trip_count()
uint _trip_count;
// Log2 of original loop bodies in unrolled loop
int _unrolled_count_log2;
// Node count prior to last unrolling - used to decide if
// unroll,optimize,unroll,optimize,... is making progress
int _node_count_before_unroll;
// If slp analysis is performed we record the maximum
// vector mapped unroll factor here
int _slp_maximum_unroll_factor;
// The eventual count of vectorizable packs in slp
int _slp_vector_pack_count;
public:
CountedLoopNode(Node *entry, Node *backedge)
: BaseCountedLoopNode(entry, backedge), _main_idx(0), _trip_count(max_juint),
_unrolled_count_log2(0), _node_count_before_unroll(0),
_slp_maximum_unroll_factor(0), _slp_vector_pack_count(0) {
init_class_id(Class_CountedLoop);
// Initialize _trip_count to the largest possible value.
// Will be reset (lower) if the loop's trip count is known.
}
virtual int Opcode() const;
virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
CountedLoopEndNode* loopexit_or_null() const { return (CountedLoopEndNode*) BaseCountedLoopNode::loopexit_or_null(); }
CountedLoopEndNode* loopexit() const { return (CountedLoopEndNode*) BaseCountedLoopNode::loopexit(); }
int stride_con() const;
// Match increment with optional truncation
static Node*
match_incr_with_optional_truncation(Node* expr, Node** trunc1, Node** trunc2, const TypeInteger** trunc_type,
BasicType bt);
// A 'main' loop has a pre-loop and a post-loop. The 'main' loop
// can run short a few iterations and may start a few iterations in.
// It will be RCE'd and unrolled and aligned.
// A following 'post' loop will run any remaining iterations. Used
// during Range Check Elimination, the 'post' loop will do any final
// iterations with full checks. Also used by Loop Unrolling, where
// the 'post' loop will do any epilog iterations needed. Basically,
// a 'post' loop can not profitably be further unrolled or RCE'd.
// A preceding 'pre' loop will run at least 1 iteration (to do peeling),
// it may do under-flow checks for RCE and may do alignment iterations
// so the following main loop 'knows' that it is striding down cache
// lines.
// A 'main' loop that is ONLY unrolled or peeled, never RCE'd or
// Aligned, may be missing it's pre-loop.
bool is_normal_loop () const { return (_loop_flags&PreMainPostFlagsMask) == Normal; }
bool is_pre_loop () const { return (_loop_flags&PreMainPostFlagsMask) == Pre; }
bool is_main_loop () const { return (_loop_flags&PreMainPostFlagsMask) == Main; }
bool is_post_loop () const { return (_loop_flags&PreMainPostFlagsMask) == Post; }
bool is_reduction_loop() const { return (_loop_flags&HasReductions) == HasReductions; }
bool was_slp_analyzed () const { return (_loop_flags&WasSlpAnalyzed) == WasSlpAnalyzed; }
bool has_passed_slp () const { return (_loop_flags&PassedSlpAnalysis) == PassedSlpAnalysis; }
bool is_unroll_only () const { return (_loop_flags&DoUnrollOnly) == DoUnrollOnly; }
bool is_main_no_pre_loop() const { return _loop_flags & MainHasNoPreLoop; }
bool has_atomic_post_loop () const { return (_loop_flags & HasAtomicPostLoop) == HasAtomicPostLoop; }
void set_main_no_pre_loop() { _loop_flags |= MainHasNoPreLoop; }
int main_idx() const { return _main_idx; }
void set_pre_loop (CountedLoopNode *main) { assert(is_normal_loop(),""); _loop_flags |= Pre ; _main_idx = main->_idx; }
void set_main_loop ( ) { assert(is_normal_loop(),""); _loop_flags |= Main; }
void set_post_loop (CountedLoopNode *main) { assert(is_normal_loop(),""); _loop_flags |= Post; _main_idx = main->_idx; }
void set_normal_loop( ) { _loop_flags &= ~PreMainPostFlagsMask; }
void set_trip_count(uint tc) { _trip_count = tc; }
uint trip_count() { return _trip_count; }
bool has_exact_trip_count() const { return (_loop_flags & HasExactTripCount) != 0; }
void set_exact_trip_count(uint tc) {
_trip_count = tc;
_loop_flags |= HasExactTripCount;
}
void set_nonexact_trip_count() {
_loop_flags &= ~HasExactTripCount;
}
void set_notpassed_slp() {
_loop_flags &= ~PassedSlpAnalysis;
}
void double_unrolled_count() { _unrolled_count_log2++; }
int unrolled_count() { return 1 << MIN2(_unrolled_count_log2, BitsPerInt-3); }
void set_node_count_before_unroll(int ct) { _node_count_before_unroll = ct; }
int node_count_before_unroll() { return _node_count_before_unroll; }
void set_slp_max_unroll(int unroll_factor) { _slp_maximum_unroll_factor = unroll_factor; }
int slp_max_unroll() const { return _slp_maximum_unroll_factor; }
void set_slp_pack_count(int pack_count) { _slp_vector_pack_count = pack_count; }
int slp_pack_count() const { return _slp_vector_pack_count; }
virtual LoopNode* skip_strip_mined(int expect_skeleton = 1);
OuterStripMinedLoopNode* outer_loop() const;
virtual IfTrueNode* outer_loop_tail() const;
virtual OuterStripMinedLoopEndNode* outer_loop_end() const;
virtual IfFalseNode* outer_loop_exit() const;
virtual SafePointNode* outer_safepoint() const;
// If this is a main loop in a pre/main/post loop nest, walk over
// the predicates that were inserted by
// duplicate_predicates()/add_range_check_predicate()
static Node* skip_predicates_from_entry(Node* ctrl);
Node* skip_predicates();
virtual BasicType bt() const {
return T_INT;
}
Node* is_canonical_loop_entry();
#ifndef PRODUCT
virtual void dump_spec(outputStream *st) const;
#endif
};
class LongCountedLoopNode : public BaseCountedLoopNode {
public:
LongCountedLoopNode(Node *entry, Node *backedge)
: BaseCountedLoopNode(entry, backedge) {
init_class_id(Class_LongCountedLoop);
}
virtual int Opcode() const;
virtual BasicType bt() const {
return T_LONG;
}
LongCountedLoopEndNode* loopexit_or_null() const { return (LongCountedLoopEndNode*) BaseCountedLoopNode::loopexit_or_null(); }
LongCountedLoopEndNode* loopexit() const { return (LongCountedLoopEndNode*) BaseCountedLoopNode::loopexit(); }
};
//------------------------------CountedLoopEndNode-----------------------------
// CountedLoopEndNodes end simple trip counted loops. They act much like
// IfNodes.
class BaseCountedLoopEndNode : public IfNode {
public:
enum { TestControl, TestValue };
BaseCountedLoopEndNode(Node *control, Node *test, float prob, float cnt)
: IfNode(control, test, prob, cnt) {
init_class_id(Class_BaseCountedLoopEnd);
}
Node *cmp_node() const { return (in(TestValue)->req() >=2) ? in(TestValue)->in(1) : NULL; }
Node* incr() const { Node* tmp = cmp_node(); return (tmp && tmp->req() == 3) ? tmp->in(1) : NULL; }
Node* limit() const { Node* tmp = cmp_node(); return (tmp && tmp->req() == 3) ? tmp->in(2) : NULL; }
Node* stride() const { Node* tmp = incr(); return (tmp && tmp->req() == 3) ? tmp->in(2) : NULL; }
Node* init_trip() const { Node* tmp = phi(); return (tmp && tmp->req() == 3) ? tmp->in(1) : NULL; }
bool stride_is_con() const { Node *tmp = stride(); return (tmp != NULL && tmp->is_Con()); }
PhiNode* phi() const {
Node* tmp = incr();
if (tmp && tmp->req() == 3) {
Node* phi = tmp->in(1);
if (phi->is_Phi()) {
return phi->as_Phi();
}
}
return NULL;
}
BaseCountedLoopNode* loopnode() const {
// The CountedLoopNode that goes with this CountedLoopEndNode may
// have been optimized out by the IGVN so be cautious with the
// pattern matching on the graph
PhiNode* iv_phi = phi();
if (iv_phi == NULL) {
return NULL;
}
Node* ln = iv_phi->in(0);
if (!ln->is_BaseCountedLoop() || ln->as_BaseCountedLoop()->loopexit_or_null() != this) {
return NULL;
}
if (ln->as_BaseCountedLoop()->bt() != bt()) {
return NULL;
}
return ln->as_BaseCountedLoop();
}
BoolTest::mask test_trip() const { return in(TestValue)->as_Bool()->_test._test; }
jlong stride_con() const;
virtual BasicType bt() const = 0;
static BaseCountedLoopEndNode* make(Node* control, Node* test, float prob, float cnt, BasicType bt);
};
class CountedLoopEndNode : public BaseCountedLoopEndNode {
public:
CountedLoopEndNode(Node *control, Node *test, float prob, float cnt)
: BaseCountedLoopEndNode(control, test, prob, cnt) {
init_class_id(Class_CountedLoopEnd);
}
virtual int Opcode() const;
CountedLoopNode* loopnode() const {
return (CountedLoopNode*) BaseCountedLoopEndNode::loopnode();
}
virtual BasicType bt() const {
return T_INT;
}
#ifndef PRODUCT
virtual void dump_spec(outputStream *st) const;
#endif
};
class LongCountedLoopEndNode : public BaseCountedLoopEndNode {
public:
LongCountedLoopEndNode(Node *control, Node *test, float prob, float cnt)
: BaseCountedLoopEndNode(control, test, prob, cnt) {
init_class_id(Class_LongCountedLoopEnd);
}
LongCountedLoopNode* loopnode() const {
return (LongCountedLoopNode*) BaseCountedLoopEndNode::loopnode();
}
virtual int Opcode() const;
virtual BasicType bt() const {
return T_LONG;
}
};
inline BaseCountedLoopEndNode* BaseCountedLoopNode::loopexit_or_null() const {
Node* bctrl = back_control();
if (bctrl == NULL) return NULL;
Node* lexit = bctrl->in(0);
if (!lexit->is_BaseCountedLoopEnd()) {
return NULL;
}
BaseCountedLoopEndNode* result = lexit->as_BaseCountedLoopEnd();
if (result->bt() != bt()) {
return NULL;
}
return result;
}
inline BaseCountedLoopEndNode* BaseCountedLoopNode::loopexit() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
assert(cle != NULL, "loopexit is NULL");
return cle;
}
inline Node* BaseCountedLoopNode::init_trip() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL ? cle->init_trip() : NULL;
}
inline Node* BaseCountedLoopNode::stride() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL ? cle->stride() : NULL;
}
inline bool BaseCountedLoopNode::stride_is_con() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL && cle->stride_is_con();
}
inline Node* BaseCountedLoopNode::limit() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL ? cle->limit() : NULL;
}
inline Node* BaseCountedLoopNode::incr() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL ? cle->incr() : NULL;
}
inline Node* BaseCountedLoopNode::phi() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL ? cle->phi() : NULL;
}
inline jlong BaseCountedLoopNode::stride_con() const {
BaseCountedLoopEndNode* cle = loopexit_or_null();
return cle != NULL ? cle->stride_con() : 0;
}
//------------------------------LoopLimitNode-----------------------------
// Counted Loop limit node which represents exact final iterator value:
// trip_count = (limit - init_trip + stride - 1)/stride
// final_value= trip_count * stride + init_trip.
// Use HW instructions to calculate it when it can overflow in integer.
// Note, final_value should fit into integer since counted loop has
// limit check: limit <= max_int-stride.
class LoopLimitNode : public Node {
enum { Init=1, Limit=2, Stride=3 };
public:
LoopLimitNode( Compile* C, Node *init, Node *limit, Node *stride ) : Node(0,init,limit,stride) {
// Put it on the Macro nodes list to optimize during macro nodes expansion.
init_flags(Flag_is_macro);
C->add_macro_node(this);
}
virtual int Opcode() const;
virtual const Type *bottom_type() const { return TypeInt::INT; }
virtual uint ideal_reg() const { return Op_RegI; }
virtual const Type* Value(PhaseGVN* phase) const;
virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
virtual Node* Identity(PhaseGVN* phase);
};
// Support for strip mining
class OuterStripMinedLoopNode : public LoopNode {
private:
static void fix_sunk_stores(CountedLoopEndNode* inner_cle, LoopNode* inner_cl, PhaseIterGVN* igvn, PhaseIdealLoop* iloop);
public:
OuterStripMinedLoopNode(Compile* C, Node *entry, Node *backedge)
: LoopNode(entry, backedge) {
init_class_id(Class_OuterStripMinedLoop);
init_flags(Flag_is_macro);
C->add_macro_node(this);
}
virtual int Opcode() const;
virtual IfTrueNode* outer_loop_tail() const;
virtual OuterStripMinedLoopEndNode* outer_loop_end() const;
virtual IfFalseNode* outer_loop_exit() const;
virtual SafePointNode* outer_safepoint() const;
void adjust_strip_mined_loop(PhaseIterGVN* igvn);
void remove_outer_loop_and_safepoint(PhaseIterGVN* igvn) const;
void transform_to_counted_loop(PhaseIterGVN* igvn, PhaseIdealLoop* iloop);
static Node* register_new_node(Node* node, LoopNode* ctrl, PhaseIterGVN* igvn, PhaseIdealLoop* iloop);
Node* register_control(Node* node, Node* loop, Node* idom, PhaseIterGVN* igvn,
PhaseIdealLoop* iloop);
};
class OuterStripMinedLoopEndNode : public IfNode {
public:
OuterStripMinedLoopEndNode(Node *control, Node *test, float prob, float cnt)
: IfNode(control, test, prob, cnt) {
init_class_id(Class_OuterStripMinedLoopEnd);
}
virtual int Opcode() const;
virtual const Type* Value(PhaseGVN* phase) const;
virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
bool is_expanded(PhaseGVN *phase) const;
};
// -----------------------------IdealLoopTree----------------------------------
class IdealLoopTree : public ResourceObj {
public:
IdealLoopTree *_parent; // Parent in loop tree
IdealLoopTree *_next; // Next sibling in loop tree
IdealLoopTree *_child; // First child in loop tree
// The head-tail backedge defines the loop.
// If a loop has multiple backedges, this is addressed during cleanup where
// we peel off the multiple backedges, merging all edges at the bottom and
// ensuring that one proper backedge flow into the loop.
Node *_head; // Head of loop
Node *_tail; // Tail of loop
inline Node *tail(); // Handle lazy update of _tail field
inline Node *head(); // Handle lazy update of _head field
PhaseIdealLoop* _phase;
int _local_loop_unroll_limit;
int _local_loop_unroll_factor;
Node_List _body; // Loop body for inner loops
uint16_t _nest; // Nesting depth
uint8_t _irreducible:1, // True if irreducible
_has_call:1, // True if has call safepoint
_has_sfpt:1, // True if has non-call safepoint
_rce_candidate:1; // True if candidate for range check elimination
Node_List* _safepts; // List of safepoints in this loop
Node_List* _required_safept; // A inner loop cannot delete these safepts;
bool _allow_optimizations; // Allow loop optimizations
IdealLoopTree( PhaseIdealLoop* phase, Node *head, Node *tail )
: _parent(0), _next(0), _child(0),
_head(head), _tail(tail),
_phase(phase),
_local_loop_unroll_limit(0), _local_loop_unroll_factor(0),
_nest(0), _irreducible(0), _has_call(0), _has_sfpt(0), _rce_candidate(0),
_safepts(NULL),
_required_safept(NULL),
_allow_optimizations(true)
{
precond(_head != NULL);
precond(_tail != NULL);
}
// Is 'l' a member of 'this'?
bool is_member(const IdealLoopTree *l) const; // Test for nested membership
// Set loop nesting depth. Accumulate has_call bits.
int set_nest( uint depth );
// Split out multiple fall-in edges from the loop header. Move them to a
// private RegionNode before the loop. This becomes the loop landing pad.
void split_fall_in( PhaseIdealLoop *phase, int fall_in_cnt );
// Split out the outermost loop from this shared header.
void split_outer_loop( PhaseIdealLoop *phase );
// Merge all the backedges from the shared header into a private Region.
// Feed that region as the one backedge to this loop.
void merge_many_backedges( PhaseIdealLoop *phase );
// Split shared headers and insert loop landing pads.
// Insert a LoopNode to replace the RegionNode.
// Returns TRUE if loop tree is structurally changed.
bool beautify_loops( PhaseIdealLoop *phase );
// Perform optimization to use the loop predicates for null checks and range checks.
// Applies to any loop level (not just the innermost one)
bool loop_predication( PhaseIdealLoop *phase);
// Perform iteration-splitting on inner loops. Split iterations to
// avoid range checks or one-shot null checks. Returns false if the
// current round of loop opts should stop.
bool iteration_split( PhaseIdealLoop *phase, Node_List &old_new );
// Driver for various flavors of iteration splitting. Returns false
// if the current round of loop opts should stop.
bool iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new );
// Given dominators, try to find loops with calls that must always be
// executed (call dominates loop tail). These loops do not need non-call
// safepoints (ncsfpt).
void check_safepts(VectorSet &visited, Node_List &stack);
// Allpaths backwards scan from loop tail, terminating each path at first safepoint
// encountered.
void allpaths_check_safepts(VectorSet &visited, Node_List &stack);
// Remove safepoints from loop. Optionally keeping one.
void remove_safepoints(PhaseIdealLoop* phase, bool keep_one);
// Convert to counted loops where possible
void counted_loop( PhaseIdealLoop *phase );
// Check for Node being a loop-breaking test
Node *is_loop_exit(Node *iff) const;
// Remove simplistic dead code from loop body
void DCE_loop_body();
// Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
// Replace with a 1-in-10 exit guess.
void adjust_loop_exit_prob( PhaseIdealLoop *phase );
// Return TRUE or FALSE if the loop should never be RCE'd or aligned.
// Useful for unrolling loops with NO array accesses.
bool policy_peel_only( PhaseIdealLoop *phase ) const;
// Return TRUE or FALSE if the loop should be unswitched -- clone
// loop with an invariant test
bool policy_unswitching( PhaseIdealLoop *phase ) const;
// Micro-benchmark spamming. Remove empty loops.
bool do_remove_empty_loop( PhaseIdealLoop *phase );
// Convert one iteration loop into normal code.
bool do_one_iteration_loop( PhaseIdealLoop *phase );
// Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
// move some loop-invariant test (usually a null-check) before the loop.
bool policy_peeling(PhaseIdealLoop *phase);
uint estimate_peeling(PhaseIdealLoop *phase);
// Return TRUE or FALSE if the loop should be maximally unrolled. Stash any
// known trip count in the counted loop node.
bool policy_maximally_unroll(PhaseIdealLoop *phase) const;
// Return TRUE or FALSE if the loop should be unrolled or not. Apply unroll
// if the loop is a counted loop and the loop body is small enough.
bool policy_unroll(PhaseIdealLoop *phase);
// Loop analyses to map to a maximal superword unrolling for vectorization.
void policy_unroll_slp_analysis(CountedLoopNode *cl, PhaseIdealLoop *phase, int future_unroll_ct);
// Return TRUE or FALSE if the loop should be range-check-eliminated.
// Gather a list of IF tests that are dominated by iteration splitting;
// also gather the end of the first split and the start of the 2nd split.
bool policy_range_check(PhaseIdealLoop* phase, bool provisional, BasicType bt) const;
// Return TRUE if "iff" is a range check.
bool is_range_check_if(IfNode *iff, PhaseIdealLoop *phase, Invariance& invar DEBUG_ONLY(COMMA ProjNode *predicate_proj)) const;
bool is_range_check_if(IfNode* iff, PhaseIdealLoop* phase, BasicType bt, Node* iv, Node*& range, Node*& offset,
jlong& scale) const;
// Estimate the number of nodes required when cloning a loop (body).
uint est_loop_clone_sz(uint factor) const;
// Estimate the number of nodes required when unrolling a loop (body).
uint est_loop_unroll_sz(uint factor) const;
// Compute loop trip count if possible
void compute_trip_count(PhaseIdealLoop* phase);
// Compute loop trip count from profile data
float compute_profile_trip_cnt_helper(Node* n);
void compute_profile_trip_cnt( PhaseIdealLoop *phase );
// Reassociate invariant expressions.
void reassociate_invariants(PhaseIdealLoop *phase);
// Reassociate invariant binary expressions.
Node* reassociate(Node* n1, PhaseIdealLoop *phase);
// Reassociate invariant add and subtract expressions.
Node* reassociate_add_sub(Node* n1, int inv1_idx, int inv2_idx, PhaseIdealLoop *phase);
// Return nonzero index of invariant operand if invariant and variant
// are combined with an associative binary. Helper for reassociate_invariants.
int find_invariant(Node* n, PhaseIdealLoop *phase);
// Return TRUE if "n" is associative.
bool is_associative(Node* n, Node* base=NULL);
// Return true if n is invariant
bool is_invariant(Node* n) const;
// Put loop body on igvn work list
void record_for_igvn();
bool is_root() { return _parent == NULL; }
// A proper/reducible loop w/o any (occasional) dead back-edge.
bool is_loop() { return !_irreducible && !tail()->is_top(); }
bool is_counted() { return is_loop() && _head->is_CountedLoop(); }
bool is_innermost() { return is_loop() && _child == NULL; }
void remove_main_post_loops(CountedLoopNode *cl, PhaseIdealLoop *phase);
#ifndef PRODUCT
void dump_head() const; // Dump loop head only
void dump() const; // Dump this loop recursively
void verify_tree(IdealLoopTree *loop, const IdealLoopTree *parent) const;
#endif
private:
enum { EMPTY_LOOP_SIZE = 7 }; // Number of nodes in an empty loop.
// Estimate the number of nodes resulting from control and data flow merge.
uint est_loop_flow_merge_sz() const;
// Check if the number of residual iterations is large with unroll_cnt.
// Return true if the residual iterations are more than 10% of the trip count.
bool is_residual_iters_large(int unroll_cnt, CountedLoopNode *cl) const {
return (unroll_cnt - 1) * (100.0 / LoopPercentProfileLimit) > cl->profile_trip_cnt();
}
};
// -----------------------------PhaseIdealLoop---------------------------------
// Computes the mapping from Nodes to IdealLoopTrees. Organizes IdealLoopTrees
// into a loop tree. Drives the loop-based transformations on the ideal graph.
class PhaseIdealLoop : public PhaseTransform {
friend class IdealLoopTree;
friend class SuperWord;
friend class CountedLoopReserveKit;
friend class ShenandoahBarrierC2Support;
friend class AutoNodeBudget;
// Pre-computed def-use info
PhaseIterGVN &_igvn;
// Head of loop tree
IdealLoopTree* _ltree_root;
// Array of pre-order numbers, plus post-visited bit.
// ZERO for not pre-visited. EVEN for pre-visited but not post-visited.
// ODD for post-visited. Other bits are the pre-order number.
uint *_preorders;
uint _max_preorder;
const PhaseIdealLoop* _verify_me;
bool _verify_only;
// Allocate _preorders[] array
void allocate_preorders() {
_max_preorder = C->unique()+8;
_preorders = NEW_RESOURCE_ARRAY(uint, _max_preorder);
memset(_preorders, 0, sizeof(uint) * _max_preorder);
}
// Allocate _preorders[] array
void reallocate_preorders() {
if ( _max_preorder < C->unique() ) {
_preorders = REALLOC_RESOURCE_ARRAY(uint, _preorders, _max_preorder, C->unique());
_max_preorder = C->unique();
}
memset(_preorders, 0, sizeof(uint) * _max_preorder);
}
// Check to grow _preorders[] array for the case when build_loop_tree_impl()
// adds new nodes.
void check_grow_preorders( ) {
if ( _max_preorder < C->unique() ) {
uint newsize = _max_preorder<<1; // double size of array
_preorders = REALLOC_RESOURCE_ARRAY(uint, _preorders, _max_preorder, newsize);
memset(&_preorders[_max_preorder],0,sizeof(uint)*(newsize-_max_preorder));
_max_preorder = newsize;
}
}
// Check for pre-visited. Zero for NOT visited; non-zero for visited.
int is_visited( Node *n ) const { return _preorders[n->_idx]; }
// Pre-order numbers are written to the Nodes array as low-bit-set values.
void set_preorder_visited( Node *n, int pre_order ) {
assert( !is_visited( n ), "already set" );
_preorders[n->_idx] = (pre_order<<1);
};
// Return pre-order number.
int get_preorder( Node *n ) const { assert( is_visited(n), "" ); return _preorders[n->_idx]>>1; }
// Check for being post-visited.
// Should be previsited already (checked with assert(is_visited(n))).
int is_postvisited( Node *n ) const { assert( is_visited(n), "" ); return _preorders[n->_idx]&1; }
// Mark as post visited
void set_postvisited( Node *n ) { assert( !is_postvisited( n ), "" ); _preorders[n->_idx] |= 1; }
public:
// Set/get control node out. Set lower bit to distinguish from IdealLoopTree
// Returns true if "n" is a data node, false if it's a control node.
bool has_ctrl( Node *n ) const { return ((intptr_t)_nodes[n->_idx]) & 1; }
private:
// clear out dead code after build_loop_late
Node_List _deadlist;
// Support for faster execution of get_late_ctrl()/dom_lca()
// when a node has many uses and dominator depth is deep.
GrowableArray<jlong> _dom_lca_tags;
uint _dom_lca_tags_round;
void init_dom_lca_tags();
// Helper for debugging bad dominance relationships
bool verify_dominance(Node* n, Node* use, Node* LCA, Node* early);
Node* compute_lca_of_uses(Node* n, Node* early, bool verify = false);
// Inline wrapper for frequent cases:
// 1) only one use
// 2) a use is the same as the current LCA passed as 'n1'
Node *dom_lca_for_get_late_ctrl( Node *lca, Node *n, Node *tag ) {
assert( n->is_CFG(), "" );
// Fast-path NULL lca
if( lca != NULL && lca != n ) {
assert( lca->is_CFG(), "" );
// find LCA of all uses
n = dom_lca_for_get_late_ctrl_internal( lca, n, tag );
}
return find_non_split_ctrl(n);
}
Node *dom_lca_for_get_late_ctrl_internal( Node *lca, Node *n, Node *tag );
// Helper function for directing control inputs away from CFG split points.
Node *find_non_split_ctrl( Node *ctrl ) const {
if (ctrl != NULL) {
if (ctrl->is_MultiBranch()) {
ctrl = ctrl->in(0);
}
assert(ctrl->is_CFG(), "CFG");
}
return ctrl;
}
Node* cast_incr_before_loop(Node* incr, Node* ctrl, Node* loop);
#ifdef ASSERT
void ensure_zero_trip_guard_proj(Node* node, bool is_main_loop);
#endif
void copy_skeleton_predicates_to_main_loop_helper(Node* predicate, Node* init, Node* stride, IdealLoopTree* outer_loop, LoopNode* outer_main_head,
uint dd_main_head, const uint idx_before_pre_post, const uint idx_after_post_before_pre,
Node* zero_trip_guard_proj_main, Node* zero_trip_guard_proj_post, const Node_List &old_new);
void copy_skeleton_predicates_to_main_loop(CountedLoopNode* pre_head, Node* init, Node* stride, IdealLoopTree* outer_loop, LoopNode* outer_main_head,
uint dd_main_head, const uint idx_before_pre_post, const uint idx_after_post_before_pre,
Node* zero_trip_guard_proj_main, Node* zero_trip_guard_proj_post, const Node_List &old_new);
Node* clone_skeleton_predicate_and_initialize(Node* iff, Node* new_init, Node* new_stride, Node* predicate, Node* uncommon_proj, Node* control,
IdealLoopTree* outer_loop, Node* input_proj);
Node* clone_skeleton_predicate_bool(Node* iff, Node* new_init, Node* new_stride, Node* control);
static bool skeleton_predicate_has_opaque(IfNode* iff);
static void count_opaque_loop_nodes(Node* n, uint& init, uint& stride);
static bool subgraph_has_opaque(Node* n);
static void get_skeleton_predicates(Node* predicate, Unique_Node_List& list, bool get_opaque = false);
void update_main_loop_skeleton_predicates(Node* ctrl, CountedLoopNode* loop_head, Node* init, int stride_con);
void copy_skeleton_predicates_to_post_loop(LoopNode* main_loop_head, CountedLoopNode* post_loop_head, Node* init, Node* stride);
void initialize_skeleton_predicates_for_peeled_loop(ProjNode* predicate, LoopNode* outer_loop_head, int dd_outer_loop_head,
Node* init, Node* stride, IdealLoopTree* outer_loop,
const uint idx_before_clone, const Node_List& old_new);
void insert_loop_limit_check(ProjNode* limit_check_proj, Node* cmp_limit, Node* bol);
#ifdef ASSERT
bool only_has_infinite_loops();
#endif
void log_loop_tree();
public:
PhaseIterGVN &igvn() const { return _igvn; }
bool has_node( Node* n ) const {
guarantee(n != NULL, "No Node.");
return _nodes[n->_idx] != NULL;
}
// check if transform created new nodes that need _ctrl recorded
Node *get_late_ctrl( Node *n, Node *early );
Node *get_early_ctrl( Node *n );
Node *get_early_ctrl_for_expensive(Node *n, Node* earliest);
void set_early_ctrl(Node* n, bool update_body);
void set_subtree_ctrl(Node* n, bool update_body);
void set_ctrl( Node *n, Node *ctrl ) {
assert( !has_node(n) || has_ctrl(n), "" );
assert( ctrl->in(0), "cannot set dead control node" );
assert( ctrl == find_non_split_ctrl(ctrl), "must set legal crtl" );
_nodes.map( n->_idx, (Node*)((intptr_t)ctrl + 1) );
}
// Set control and update loop membership
void set_ctrl_and_loop(Node* n, Node* ctrl) {
IdealLoopTree* old_loop = get_loop(get_ctrl(n));
IdealLoopTree* new_loop = get_loop(ctrl);
if (old_loop != new_loop) {
if (old_loop->_child == NULL) old_loop->_body.yank(n);
if (new_loop->_child == NULL) new_loop->_body.push(n);
}
set_ctrl(n, ctrl);
}
// Control nodes can be replaced or subsumed. During this pass they
// get their replacement Node in slot 1. Instead of updating the block
// location of all Nodes in the subsumed block, we lazily do it. As we
// pull such a subsumed block out of the array, we write back the final
// correct block.
Node *get_ctrl( Node *i ) {
assert(has_node(i), "");
Node *n = get_ctrl_no_update(i);
_nodes.map( i->_idx, (Node*)((intptr_t)n + 1) );
assert(has_node(i) && has_ctrl(i), "");
assert(n == find_non_split_ctrl(n), "must return legal ctrl" );
return n;
}
// true if CFG node d dominates CFG node n
bool is_dominator(Node *d, Node *n);
// return get_ctrl for a data node and self(n) for a CFG node
Node* ctrl_or_self(Node* n) {
if (has_ctrl(n))
return get_ctrl(n);
else {
assert (n->is_CFG(), "must be a CFG node");
return n;
}
}
Node *get_ctrl_no_update_helper(Node *i) const {