60 protected:
61 uint _loop_flags;
62 // Names for flag bitfields
63 enum { Normal=0, Pre=1, Main=2, Post=3, PreMainPostFlagsMask=3,
64 MainHasNoPreLoop = 1<<2,
65 HasExactTripCount = 1<<3,
66 InnerLoop = 1<<4,
67 PartialPeelLoop = 1<<5,
68 PartialPeelFailed = 1<<6,
69 HasReductions = 1<<7,
70 WasSlpAnalyzed = 1<<8,
71 PassedSlpAnalysis = 1<<9,
72 DoUnrollOnly = 1<<10,
73 VectorizedLoop = 1<<11,
74 HasAtomicPostLoop = 1<<12,
75 HasRangeChecks = 1<<13,
76 IsMultiversioned = 1<<14,
77 StripMined = 1<<15,
78 SubwordLoop = 1<<16,
79 ProfileTripFailed = 1<<17,
80 LoopNestInnerLoop = 1 << 18,
81 LoopNestLongOuterLoop = 1 << 19};
82 char _unswitch_count;
83 enum { _unswitch_max=3 };
84 char _postloop_flags;
85 enum { LoopNotRCEChecked = 0, LoopRCEChecked = 1, RCEPostLoop = 2 };
86
87 // Expected trip count from profile data
88 float _profile_trip_cnt;
89
90 public:
91 // Names for edge indices
92 enum { Self=0, EntryControl, LoopBackControl };
93
94 bool is_inner_loop() const { return _loop_flags & InnerLoop; }
95 void set_inner_loop() { _loop_flags |= InnerLoop; }
96
97 bool range_checks_present() const { return _loop_flags & HasRangeChecks; }
98 bool is_multiversioned() const { return _loop_flags & IsMultiversioned; }
99 bool is_vectorized_loop() const { return _loop_flags & VectorizedLoop; }
100 bool is_partial_peel_loop() const { return _loop_flags & PartialPeelLoop; }
101 void set_partial_peel_loop() { _loop_flags |= PartialPeelLoop; }
102 bool partial_peel_has_failed() const { return _loop_flags & PartialPeelFailed; }
103 bool is_strip_mined() const { return _loop_flags & StripMined; }
104 bool is_profile_trip_failed() const { return _loop_flags & ProfileTripFailed; }
105 bool is_subword_loop() const { return _loop_flags & SubwordLoop; }
106 bool is_loop_nest_inner_loop() const { return _loop_flags & LoopNestInnerLoop; }
107 bool is_loop_nest_outer_loop() const { return _loop_flags & LoopNestLongOuterLoop; }
108
109 void mark_partial_peel_failed() { _loop_flags |= PartialPeelFailed; }
110 void mark_has_reductions() { _loop_flags |= HasReductions; }
111 void mark_was_slp() { _loop_flags |= WasSlpAnalyzed; }
112 void mark_passed_slp() { _loop_flags |= PassedSlpAnalysis; }
113 void mark_do_unroll_only() { _loop_flags |= DoUnrollOnly; }
114 void mark_loop_vectorized() { _loop_flags |= VectorizedLoop; }
115 void mark_has_atomic_post_loop() { _loop_flags |= HasAtomicPostLoop; }
116 void mark_has_range_checks() { _loop_flags |= HasRangeChecks; }
117 void clear_has_range_checks() { _loop_flags &= ~HasRangeChecks; }
118 void mark_is_multiversioned() { _loop_flags |= IsMultiversioned; }
119 void mark_strip_mined() { _loop_flags |= StripMined; }
120 void clear_strip_mined() { _loop_flags &= ~StripMined; }
121 void mark_profile_trip_failed() { _loop_flags |= ProfileTripFailed; }
122 void mark_subword_loop() { _loop_flags |= SubwordLoop; }
123 void mark_loop_nest_inner_loop() { _loop_flags |= LoopNestInnerLoop; }
124 void mark_loop_nest_outer_loop() { _loop_flags |= LoopNestLongOuterLoop; }
125
126 int unswitch_max() { return _unswitch_max; }
127 int unswitch_count() { return _unswitch_count; }
128
129 int has_been_range_checked() const { return _postloop_flags & LoopRCEChecked; }
130 void set_has_been_range_checked() { _postloop_flags |= LoopRCEChecked; }
131 int is_rce_post_loop() const { return _postloop_flags & RCEPostLoop; }
132 void set_is_rce_post_loop() { _postloop_flags |= RCEPostLoop; }
133
134 void set_unswitch_count(int val) {
135 assert (val <= unswitch_max(), "too many unswitches");
136 _unswitch_count = val;
137 }
138
139 void set_profile_trip_cnt(float ptc) { _profile_trip_cnt = ptc; }
140 float profile_trip_cnt() { return _profile_trip_cnt; }
141
142 LoopNode(Node *entry, Node *backedge)
143 : RegionNode(3), _loop_flags(0), _unswitch_count(0),
144 _postloop_flags(0), _profile_trip_cnt(COUNT_UNKNOWN) {
1413 return !has_node(n) || n->is_unreachable(_igvn);
1414 }
1415
1416 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1417 int do_range_check( IdealLoopTree *loop, Node_List &old_new );
1418
1419 // Check to see if do_range_check(...) cleaned the main loop of range-checks
1420 void has_range_checks(IdealLoopTree *loop);
1421
1422 // Process post loops which have range checks and try to build a multi-version
1423 // guard to safely determine if we can execute the post loop which was RCE'd.
1424 bool multi_version_post_loops(IdealLoopTree *rce_loop, IdealLoopTree *legacy_loop);
1425
1426 // Cause the rce'd post loop to optimized away, this happens if we cannot complete multiverioning
1427 void poison_rce_post_loop(IdealLoopTree *rce_loop);
1428
1429 // Create a slow version of the loop by cloning the loop
1430 // and inserting an if to select fast-slow versions.
1431 // Return the inserted if.
1432 IfNode* create_slow_version_of_loop(IdealLoopTree *loop,
1433 Node_List &old_new,
1434 IfNode* unswitch_iff,
1435 CloneLoopMode mode);
1436
1437 // Clone a loop and return the clone head (clone_loop_head).
1438 // Added nodes include int(1), int(0) - disconnected, If, IfTrue, IfFalse,
1439 // This routine was created for usage in CountedLoopReserveKit.
1440 //
1441 // int(1) -> If -> IfTrue -> original_loop_head
1442 // |
1443 // V
1444 // IfFalse -> clone_loop_head (returned by function pointer)
1445 //
1446 LoopNode* create_reserve_version_of_loop(IdealLoopTree *loop, CountedLoopReserveKit* lk);
1447 // Clone loop with an invariant test (that does not exit) and
1448 // insert a clone of the test that selects which version to
1449 // execute.
1450 void do_unswitching (IdealLoopTree *loop, Node_List &old_new);
1451
1452 // Find candidate "if" for unswitching
1453 IfNode* find_unswitching_candidate(const IdealLoopTree *loop) const;
1454
1455 // Range Check Elimination uses this function!
1456 // Constrain the main loop iterations so the affine function:
1457 // low_limit <= scale_con * I + offset < upper_limit
1458 // always holds true. That is, either increase the number of iterations in
1459 // the pre-loop or the post-loop until the condition holds true in the main
1460 // loop. Scale_con, offset and limit are all loop invariant.
1461 void add_constraint(jlong stride_con, jlong scale_con, Node* offset, Node* low_limit, Node* upper_limit, Node* pre_ctrl, Node** pre_limit, Node** main_limit);
1462 // Helper function for add_constraint().
1463 Node* adjust_limit(bool reduce, Node* scale, Node* offset, Node* rc_limit, Node* old_limit, Node* pre_ctrl, bool round);
1464
1465 // Partially peel loop up through last_peel node.
1466 bool partial_peel( IdealLoopTree *loop, Node_List &old_new );
1467 bool duplicate_loop_backedge(IdealLoopTree *loop, Node_List &old_new);
1468
1469 // Create a scheduled list of nodes control dependent on ctrl set.
1470 void scheduled_nodelist( IdealLoopTree *loop, VectorSet& ctrl, Node_List &sched );
1471 // Has a use in the vector set
1472 bool has_use_in_set( Node* n, VectorSet& vset );
1473 // Has use internal to the vector set (ie. not in a phi at the loop head)
1556 bool intrinsify_fill(IdealLoopTree* lpt);
1557 bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1558 Node*& shift, Node*& offset);
1559
1560 private:
1561 // Return a type based on condition control flow
1562 const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1563 const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1564 // Helpers for filtered type
1565 const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1566
1567 // Helper functions
1568 Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1569 Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1570 void handle_use( Node *use, Node *def, small_cache *cache, Node *region_dom, Node *new_false, Node *new_true, Node *old_false, Node *old_true );
1571 bool split_up( Node *n, Node *blk1, Node *blk2 );
1572 void sink_use( Node *use, Node *post_loop );
1573 Node* place_outside_loop(Node* useblock, IdealLoopTree* loop) const;
1574 Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1575 void try_move_store_after_loop(Node* n);
1576 bool identical_backtoback_ifs(Node *n);
1577 bool can_split_if(Node *n_ctrl);
1578
1579 // Determine if a method is too big for a/another round of split-if, based on
1580 // a magic (approximate) ratio derived from the equally magic constant 35000,
1581 // previously used for this purpose (but without relating to the node limit).
1582 bool must_throttle_split_if() {
1583 uint threshold = C->max_node_limit() * 2 / 5;
1584 return C->live_nodes() > threshold;
1585 }
1586
1587 // A simplistic node request tracking mechanism, where
1588 // = UINT_MAX Request not valid or made final.
1589 // < UINT_MAX Nodes currently requested (estimate).
1590 uint _nodes_required;
1591
1592 enum { REQUIRE_MIN = 70 };
1593
1594 uint nodes_required() const { return _nodes_required; }
1595
1596 // Given the _currently_ available number of nodes, check whether there is
|
60 protected:
61 uint _loop_flags;
62 // Names for flag bitfields
63 enum { Normal=0, Pre=1, Main=2, Post=3, PreMainPostFlagsMask=3,
64 MainHasNoPreLoop = 1<<2,
65 HasExactTripCount = 1<<3,
66 InnerLoop = 1<<4,
67 PartialPeelLoop = 1<<5,
68 PartialPeelFailed = 1<<6,
69 HasReductions = 1<<7,
70 WasSlpAnalyzed = 1<<8,
71 PassedSlpAnalysis = 1<<9,
72 DoUnrollOnly = 1<<10,
73 VectorizedLoop = 1<<11,
74 HasAtomicPostLoop = 1<<12,
75 HasRangeChecks = 1<<13,
76 IsMultiversioned = 1<<14,
77 StripMined = 1<<15,
78 SubwordLoop = 1<<16,
79 ProfileTripFailed = 1<<17,
80 LoopNestInnerLoop = 1<< 18,
81 LoopNestLongOuterLoop = 1<< 19,
82 FlattenedArrays = 1<<20};
83
84 char _unswitch_count;
85 enum { _unswitch_max=3 };
86 char _postloop_flags;
87 enum { LoopNotRCEChecked = 0, LoopRCEChecked = 1, RCEPostLoop = 2 };
88
89 // Expected trip count from profile data
90 float _profile_trip_cnt;
91
92 public:
93 // Names for edge indices
94 enum { Self=0, EntryControl, LoopBackControl };
95
96 bool is_inner_loop() const { return _loop_flags & InnerLoop; }
97 void set_inner_loop() { _loop_flags |= InnerLoop; }
98
99 bool range_checks_present() const { return _loop_flags & HasRangeChecks; }
100 bool is_multiversioned() const { return _loop_flags & IsMultiversioned; }
101 bool is_vectorized_loop() const { return _loop_flags & VectorizedLoop; }
102 bool is_partial_peel_loop() const { return _loop_flags & PartialPeelLoop; }
103 void set_partial_peel_loop() { _loop_flags |= PartialPeelLoop; }
104 bool partial_peel_has_failed() const { return _loop_flags & PartialPeelFailed; }
105 bool is_strip_mined() const { return _loop_flags & StripMined; }
106 bool is_profile_trip_failed() const { return _loop_flags & ProfileTripFailed; }
107 bool is_subword_loop() const { return _loop_flags & SubwordLoop; }
108 bool is_loop_nest_inner_loop() const { return _loop_flags & LoopNestInnerLoop; }
109 bool is_loop_nest_outer_loop() const { return _loop_flags & LoopNestLongOuterLoop; }
110 bool is_flattened_arrays() const { return _loop_flags & FlattenedArrays; }
111
112 void mark_partial_peel_failed() { _loop_flags |= PartialPeelFailed; }
113 void mark_has_reductions() { _loop_flags |= HasReductions; }
114 void mark_was_slp() { _loop_flags |= WasSlpAnalyzed; }
115 void mark_passed_slp() { _loop_flags |= PassedSlpAnalysis; }
116 void mark_do_unroll_only() { _loop_flags |= DoUnrollOnly; }
117 void mark_loop_vectorized() { _loop_flags |= VectorizedLoop; }
118 void mark_has_atomic_post_loop() { _loop_flags |= HasAtomicPostLoop; }
119 void mark_has_range_checks() { _loop_flags |= HasRangeChecks; }
120 void clear_has_range_checks() { _loop_flags &= ~HasRangeChecks; }
121 void mark_is_multiversioned() { _loop_flags |= IsMultiversioned; }
122 void mark_strip_mined() { _loop_flags |= StripMined; }
123 void clear_strip_mined() { _loop_flags &= ~StripMined; }
124 void mark_profile_trip_failed() { _loop_flags |= ProfileTripFailed; }
125 void mark_subword_loop() { _loop_flags |= SubwordLoop; }
126 void mark_loop_nest_inner_loop() { _loop_flags |= LoopNestInnerLoop; }
127 void mark_loop_nest_outer_loop() { _loop_flags |= LoopNestLongOuterLoop; }
128 void mark_flattened_arrays() { _loop_flags |= FlattenedArrays; }
129
130 int unswitch_max() { return _unswitch_max; }
131 int unswitch_count() { return _unswitch_count; }
132
133 int has_been_range_checked() const { return _postloop_flags & LoopRCEChecked; }
134 void set_has_been_range_checked() { _postloop_flags |= LoopRCEChecked; }
135 int is_rce_post_loop() const { return _postloop_flags & RCEPostLoop; }
136 void set_is_rce_post_loop() { _postloop_flags |= RCEPostLoop; }
137
138 void set_unswitch_count(int val) {
139 assert (val <= unswitch_max(), "too many unswitches");
140 _unswitch_count = val;
141 }
142
143 void set_profile_trip_cnt(float ptc) { _profile_trip_cnt = ptc; }
144 float profile_trip_cnt() { return _profile_trip_cnt; }
145
146 LoopNode(Node *entry, Node *backedge)
147 : RegionNode(3), _loop_flags(0), _unswitch_count(0),
148 _postloop_flags(0), _profile_trip_cnt(COUNT_UNKNOWN) {
1417 return !has_node(n) || n->is_unreachable(_igvn);
1418 }
1419
1420 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1421 int do_range_check( IdealLoopTree *loop, Node_List &old_new );
1422
1423 // Check to see if do_range_check(...) cleaned the main loop of range-checks
1424 void has_range_checks(IdealLoopTree *loop);
1425
1426 // Process post loops which have range checks and try to build a multi-version
1427 // guard to safely determine if we can execute the post loop which was RCE'd.
1428 bool multi_version_post_loops(IdealLoopTree *rce_loop, IdealLoopTree *legacy_loop);
1429
1430 // Cause the rce'd post loop to optimized away, this happens if we cannot complete multiverioning
1431 void poison_rce_post_loop(IdealLoopTree *rce_loop);
1432
1433 // Create a slow version of the loop by cloning the loop
1434 // and inserting an if to select fast-slow versions.
1435 // Return the inserted if.
1436 IfNode* create_slow_version_of_loop(IdealLoopTree *loop,
1437 Node_List &old_new,
1438 Node_List &unswitch_iffs,
1439 CloneLoopMode mode);
1440
1441 // Clone a loop and return the clone head (clone_loop_head).
1442 // Added nodes include int(1), int(0) - disconnected, If, IfTrue, IfFalse,
1443 // This routine was created for usage in CountedLoopReserveKit.
1444 //
1445 // int(1) -> If -> IfTrue -> original_loop_head
1446 // |
1447 // V
1448 // IfFalse -> clone_loop_head (returned by function pointer)
1449 //
1450 LoopNode* create_reserve_version_of_loop(IdealLoopTree *loop, CountedLoopReserveKit* lk);
1451 // Clone loop with an invariant test (that does not exit) and
1452 // insert a clone of the test that selects which version to
1453 // execute.
1454 void do_unswitching (IdealLoopTree *loop, Node_List &old_new);
1455
1456 // Find candidate "if" for unswitching
1457 IfNode* find_unswitching_candidate(const IdealLoopTree *loop, Node_List& unswitch_iffs) const;
1458
1459 // Range Check Elimination uses this function!
1460 // Constrain the main loop iterations so the affine function:
1461 // low_limit <= scale_con * I + offset < upper_limit
1462 // always holds true. That is, either increase the number of iterations in
1463 // the pre-loop or the post-loop until the condition holds true in the main
1464 // loop. Scale_con, offset and limit are all loop invariant.
1465 void add_constraint(jlong stride_con, jlong scale_con, Node* offset, Node* low_limit, Node* upper_limit, Node* pre_ctrl, Node** pre_limit, Node** main_limit);
1466 // Helper function for add_constraint().
1467 Node* adjust_limit(bool reduce, Node* scale, Node* offset, Node* rc_limit, Node* old_limit, Node* pre_ctrl, bool round);
1468
1469 // Partially peel loop up through last_peel node.
1470 bool partial_peel( IdealLoopTree *loop, Node_List &old_new );
1471 bool duplicate_loop_backedge(IdealLoopTree *loop, Node_List &old_new);
1472
1473 // Create a scheduled list of nodes control dependent on ctrl set.
1474 void scheduled_nodelist( IdealLoopTree *loop, VectorSet& ctrl, Node_List &sched );
1475 // Has a use in the vector set
1476 bool has_use_in_set( Node* n, VectorSet& vset );
1477 // Has use internal to the vector set (ie. not in a phi at the loop head)
1560 bool intrinsify_fill(IdealLoopTree* lpt);
1561 bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1562 Node*& shift, Node*& offset);
1563
1564 private:
1565 // Return a type based on condition control flow
1566 const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1567 const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1568 // Helpers for filtered type
1569 const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1570
1571 // Helper functions
1572 Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1573 Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1574 void handle_use( Node *use, Node *def, small_cache *cache, Node *region_dom, Node *new_false, Node *new_true, Node *old_false, Node *old_true );
1575 bool split_up( Node *n, Node *blk1, Node *blk2 );
1576 void sink_use( Node *use, Node *post_loop );
1577 Node* place_outside_loop(Node* useblock, IdealLoopTree* loop) const;
1578 Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1579 void try_move_store_after_loop(Node* n);
1580 void move_flat_array_check_out_of_loop(Node* n);
1581 bool identical_backtoback_ifs(Node *n);
1582 bool flatten_array_element_type_check(Node *n);
1583 bool can_split_if(Node *n_ctrl);
1584
1585 // Determine if a method is too big for a/another round of split-if, based on
1586 // a magic (approximate) ratio derived from the equally magic constant 35000,
1587 // previously used for this purpose (but without relating to the node limit).
1588 bool must_throttle_split_if() {
1589 uint threshold = C->max_node_limit() * 2 / 5;
1590 return C->live_nodes() > threshold;
1591 }
1592
1593 // A simplistic node request tracking mechanism, where
1594 // = UINT_MAX Request not valid or made final.
1595 // < UINT_MAX Nodes currently requested (estimate).
1596 uint _nodes_required;
1597
1598 enum { REQUIRE_MIN = 70 };
1599
1600 uint nodes_required() const { return _nodes_required; }
1601
1602 // Given the _currently_ available number of nodes, check whether there is
|