< prev index next >

src/hotspot/share/opto/loopnode.hpp

Print this page

  26 #define SHARE_OPTO_LOOPNODE_HPP
  27 
  28 #include "opto/cfgnode.hpp"
  29 #include "opto/multnode.hpp"
  30 #include "opto/phaseX.hpp"
  31 #include "opto/predicates.hpp"
  32 #include "opto/subnode.hpp"
  33 #include "opto/type.hpp"
  34 #include "utilities/checkedCast.hpp"
  35 
  36 class CmpNode;
  37 class BaseCountedLoopEndNode;
  38 class CountedLoopNode;
  39 class IdealLoopTree;
  40 class LoopNode;
  41 class Node;
  42 class OuterStripMinedLoopEndNode;
  43 class PredicateBlock;
  44 class PathFrequency;
  45 class PhaseIdealLoop;

  46 class LoopSelector;
  47 class UnswitchedLoopSelector;
  48 class VectorSet;
  49 class VSharedData;
  50 class Invariance;
  51 struct small_cache;
  52 
  53 //
  54 //                  I D E A L I Z E D   L O O P S
  55 //
  56 // Idealized loops are the set of loops I perform more interesting
  57 // transformations on, beyond simple hoisting.
  58 
  59 //------------------------------LoopNode---------------------------------------
  60 // Simple loop header.  Fall in path on left, loop-back path on right.
  61 class LoopNode : public RegionNode {
  62   // Size is bigger to hold the flags.  However, the flags do not change
  63   // the semantics so it does not appear in the hash & cmp functions.
  64   virtual uint size_of() const { return sizeof(*this); }
  65 protected:

  68   enum { Normal=0, Pre=1, Main=2, Post=3, PreMainPostFlagsMask=3,
  69          MainHasNoPreLoop      = 1<<2,
  70          HasExactTripCount     = 1<<3,
  71          InnerLoop             = 1<<4,
  72          PartialPeelLoop       = 1<<5,
  73          PartialPeelFailed     = 1<<6,
  74          WasSlpAnalyzed        = 1<<7,
  75          PassedSlpAnalysis     = 1<<8,
  76          DoUnrollOnly          = 1<<9,
  77          VectorizedLoop        = 1<<10,
  78          HasAtomicPostLoop     = 1<<11,
  79          StripMined            = 1<<12,
  80          SubwordLoop           = 1<<13,
  81          ProfileTripFailed     = 1<<14,
  82          LoopNestInnerLoop     = 1<<15,
  83          LoopNestLongOuterLoop = 1<<16,
  84          MultiversionFastLoop         = 1<<17,
  85          MultiversionSlowLoop         = 2<<17,
  86          MultiversionDelayedSlowLoop  = 3<<17,
  87          MultiversionFlagsMask        = 3<<17,
  88        };
  89   char _unswitch_count;
  90   enum { _unswitch_max=3 };
  91 
  92   // Expected trip count from profile data
  93   float _profile_trip_cnt;
  94 
  95 public:
  96   // Names for edge indices
  97   enum { Self=0, EntryControl, LoopBackControl };
  98 
  99   bool is_inner_loop() const { return _loop_flags & InnerLoop; }
 100   void set_inner_loop() { _loop_flags |= InnerLoop; }
 101 
 102   bool is_vectorized_loop() const { return _loop_flags & VectorizedLoop; }
 103   bool is_partial_peel_loop() const { return _loop_flags & PartialPeelLoop; }
 104   void set_partial_peel_loop() { _loop_flags |= PartialPeelLoop; }
 105   bool partial_peel_has_failed() const { return _loop_flags & PartialPeelFailed; }
 106   bool is_strip_mined() const { return _loop_flags & StripMined; }
 107   bool is_profile_trip_failed() const { return _loop_flags & ProfileTripFailed; }
 108   bool is_subword_loop() const { return _loop_flags & SubwordLoop; }
 109   bool is_loop_nest_inner_loop() const { return _loop_flags & LoopNestInnerLoop; }
 110   bool is_loop_nest_outer_loop() const { return _loop_flags & LoopNestLongOuterLoop; }

 111 
 112   void mark_partial_peel_failed() { _loop_flags |= PartialPeelFailed; }
 113   void mark_was_slp() { _loop_flags |= WasSlpAnalyzed; }
 114   void mark_passed_slp() { _loop_flags |= PassedSlpAnalysis; }
 115   void mark_do_unroll_only() { _loop_flags |= DoUnrollOnly; }
 116   void mark_loop_vectorized() { _loop_flags |= VectorizedLoop; }
 117   void mark_has_atomic_post_loop() { _loop_flags |= HasAtomicPostLoop; }
 118   void mark_strip_mined() { _loop_flags |= StripMined; }
 119   void clear_strip_mined() { _loop_flags &= ~StripMined; }
 120   void mark_profile_trip_failed() { _loop_flags |= ProfileTripFailed; }
 121   void mark_subword_loop() { _loop_flags |= SubwordLoop; }
 122   void mark_loop_nest_inner_loop() { _loop_flags |= LoopNestInnerLoop; }
 123   void mark_loop_nest_outer_loop() { _loop_flags |= LoopNestLongOuterLoop; }

 124 
 125   int unswitch_max() { return _unswitch_max; }
 126   int unswitch_count() { return _unswitch_count; }
 127 
 128   void set_unswitch_count(int val) {
 129     assert (val <= unswitch_max(), "too many unswitches");
 130     _unswitch_count = val;
 131   }
 132 
 133   void set_profile_trip_cnt(float ptc) { _profile_trip_cnt = ptc; }
 134   float profile_trip_cnt()             { return _profile_trip_cnt; }
 135 
 136 #ifndef PRODUCT
 137   uint _stress_peeling_attempts = 0;
 138 #endif
 139 
 140   LoopNode(Node *entry, Node *backedge)
 141     : RegionNode(3), _loop_flags(0), _unswitch_count(0),
 142       _profile_trip_cnt(COUNT_UNKNOWN) {
 143     init_class_id(Class_Loop);

 736   // Convert to counted loops where possible
 737   void counted_loop( PhaseIdealLoop *phase );
 738 
 739   // Check for Node being a loop-breaking test
 740   Node *is_loop_exit(Node *iff) const;
 741 
 742   // Remove simplistic dead code from loop body
 743   void DCE_loop_body();
 744 
 745   // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
 746   // Replace with a 1-in-10 exit guess.
 747   void adjust_loop_exit_prob( PhaseIdealLoop *phase );
 748 
 749   // Return TRUE or FALSE if the loop should never be RCE'd or aligned.
 750   // Useful for unrolling loops with NO array accesses.
 751   bool policy_peel_only( PhaseIdealLoop *phase ) const;
 752 
 753   // Return TRUE or FALSE if the loop should be unswitched -- clone
 754   // loop with an invariant test
 755   bool policy_unswitching( PhaseIdealLoop *phase ) const;

 756 
 757   // Micro-benchmark spamming.  Remove empty loops.
 758   bool do_remove_empty_loop( PhaseIdealLoop *phase );
 759 
 760   // Convert one-iteration loop into normal code.
 761   bool do_one_iteration_loop( PhaseIdealLoop *phase );
 762 
 763   // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
 764   // move some loop-invariant test (usually a null-check) before the loop.
 765   bool policy_peeling(PhaseIdealLoop *phase);
 766 
 767   uint estimate_peeling(PhaseIdealLoop *phase);
 768 
 769   // Return TRUE or FALSE if the loop should be maximally unrolled. Stash any
 770   // known trip count in the counted loop node.
 771   bool policy_maximally_unroll(PhaseIdealLoop *phase) const;
 772 
 773   // Return TRUE or FALSE if the loop should be unrolled or not. Apply unroll
 774   // if the loop is a counted loop and the loop body is small enough.
 775   bool policy_unroll(PhaseIdealLoop *phase);

1481 
1482  public:
1483   // Change the control input of expensive nodes to allow commoning by
1484   // IGVN when it is guaranteed to not result in a more frequent
1485   // execution of the expensive node. Return true if progress.
1486   bool process_expensive_nodes();
1487 
1488   // Check whether node has become unreachable
1489   bool is_node_unreachable(Node *n) const {
1490     return !has_node(n) || n->is_unreachable(_igvn);
1491   }
1492 
1493   // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1494   void do_range_check(IdealLoopTree* loop);
1495 
1496   // Clone loop with an invariant test (that does not exit) and
1497   // insert a clone of the test that selects which version to
1498   // execute.
1499   void do_unswitching(IdealLoopTree* loop, Node_List& old_new);
1500 
1501   IfNode* find_unswitch_candidate(const IdealLoopTree* loop) const;

1502 
1503  private:
1504   static bool has_control_dependencies_from_predicates(LoopNode* head);
1505   static void revert_to_normal_loop(const LoopNode* loop_head);
1506 
1507   void hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
1508                                    const UnswitchedLoopSelector& unswitched_loop_selector);
1509   void add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new);
1510   static void increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head);
1511   void remove_unswitch_candidate_from_loops(const Node_List& old_new, const UnswitchedLoopSelector& unswitched_loop_selector);
1512 #ifndef PRODUCT
1513   static void trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head);
1514   static void trace_loop_unswitching_impossible(const LoopNode* original_head);
1515   static void trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,

1516                                             const LoopNode* original_head, const LoopNode* new_head);
1517   static void trace_loop_multiversioning_result(const LoopSelector& loop_selector,
1518                                                 const LoopNode* original_head, const LoopNode* new_head);
1519 #endif
1520 
1521  public:
1522 
1523   // Range Check Elimination uses this function!
1524   // Constrain the main loop iterations so the affine function:
1525   //    low_limit <= scale_con * I + offset  <  upper_limit
1526   // always holds true.  That is, either increase the number of iterations in
1527   // the pre-loop or the post-loop until the condition holds true in the main
1528   // loop.  Scale_con, offset and limit are all loop invariant.
1529   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);
1530   // Helper function for add_constraint().
1531   Node* adjust_limit(bool reduce, Node* scale, Node* offset, Node* rc_limit, Node* old_limit, Node* pre_ctrl, bool round);
1532 
1533   // Partially peel loop up through last_peel node.
1534   bool partial_peel( IdealLoopTree *loop, Node_List &old_new );
1535   bool duplicate_loop_backedge(IdealLoopTree *loop, Node_List &old_new);

1693   bool intrinsify_fill(IdealLoopTree* lpt);
1694   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1695                        Node*& shift, Node*& offset);
1696 
1697 private:
1698   // Return a type based on condition control flow
1699   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1700   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, nullptr); }
1701  // Helpers for filtered type
1702   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1703 
1704   // Helper functions
1705   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1706   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1707   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 );
1708   bool split_up( Node *n, Node *blk1, Node *blk2 );
1709 
1710   Node* place_outside_loop(Node* useblock, IdealLoopTree* loop) const;
1711   Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1712   void try_move_store_after_loop(Node* n);

1713   bool identical_backtoback_ifs(Node *n);

1714   bool can_split_if(Node *n_ctrl);
1715   bool cannot_split_division(const Node* n, const Node* region) const;
1716   static bool is_divisor_loop_phi(const Node* divisor, const Node* loop);
1717   bool loop_phi_backedge_type_contains_zero(const Node* phi_divisor, const Type* zero) const;
1718 
1719   // Determine if a method is too big for a/another round of split-if, based on
1720   // a magic (approximate) ratio derived from the equally magic constant 35000,
1721   // previously used for this purpose (but without relating to the node limit).
1722   bool must_throttle_split_if() {
1723     uint threshold = C->max_node_limit() * 2 / 5;
1724     return C->live_nodes() > threshold;
1725   }
1726 
1727   // A simplistic node request tracking mechanism, where
1728   //   = UINT_MAX   Request not valid or made final.
1729   //   < UINT_MAX   Nodes currently requested (estimate).
1730   uint _nodes_required;
1731 
1732   enum { REQUIRE_MIN = 70 };
1733 

1883                      uint new_counter, Node_List& old_new, Node_List& worklist, Node_List*& split_if_set,
1884                      Node_List*& split_bool_set, Node_List*& split_cex_set);
1885 
1886   void finish_clone_loop(Node_List* split_if_set, Node_List* split_bool_set, Node_List* split_cex_set);
1887 
1888   bool at_relevant_ctrl(Node* n, const Node* blk1, const Node* blk2);
1889 
1890   bool clone_cmp_loadklass_down(Node* n, const Node* blk1, const Node* blk2);
1891   void clone_loadklass_nodes_at_cmp_index(const Node* n, Node* cmp, int i);
1892   bool clone_cmp_down(Node* n, const Node* blk1, const Node* blk2);
1893   void clone_template_assertion_expression_down(Node* node);
1894 
1895   Node* similar_subtype_check(const Node* x, Node* r_in);
1896 
1897   void update_addp_chain_base(Node* x, Node* old_base, Node* new_base);
1898 
1899   bool can_move_to_inner_loop(Node* n, LoopNode* n_loop, Node* x);
1900 
1901   void pin_array_access_nodes_dependent_on(Node* ctrl);
1902 


1903   Node* ensure_node_and_inputs_are_above_pre_end(CountedLoopEndNode* pre_end, Node* node);
1904 
1905   bool try_make_short_running_loop(IdealLoopTree* loop, jint stride_con, const Node_List& range_checks, const uint iters_limit);
1906 
1907   ConINode* intcon(jint i);
1908 
1909   ConLNode* longcon(jlong i);
1910 
1911   ConNode* makecon(const Type* t);
1912 
1913   ConNode* integercon(jlong l, BasicType bt);
1914 
1915   ConNode* zerocon(BasicType bt);
1916 };
1917 
1918 
1919 class AutoNodeBudget : public StackObj
1920 {
1921 public:
1922   enum budget_check_t { BUDGET_CHECK, NO_BUDGET_CHECK };

  26 #define SHARE_OPTO_LOOPNODE_HPP
  27 
  28 #include "opto/cfgnode.hpp"
  29 #include "opto/multnode.hpp"
  30 #include "opto/phaseX.hpp"
  31 #include "opto/predicates.hpp"
  32 #include "opto/subnode.hpp"
  33 #include "opto/type.hpp"
  34 #include "utilities/checkedCast.hpp"
  35 
  36 class CmpNode;
  37 class BaseCountedLoopEndNode;
  38 class CountedLoopNode;
  39 class IdealLoopTree;
  40 class LoopNode;
  41 class Node;
  42 class OuterStripMinedLoopEndNode;
  43 class PredicateBlock;
  44 class PathFrequency;
  45 class PhaseIdealLoop;
  46 class UnswitchCandidate;
  47 class LoopSelector;
  48 class UnswitchedLoopSelector;
  49 class VectorSet;
  50 class VSharedData;
  51 class Invariance;
  52 struct small_cache;
  53 
  54 //
  55 //                  I D E A L I Z E D   L O O P S
  56 //
  57 // Idealized loops are the set of loops I perform more interesting
  58 // transformations on, beyond simple hoisting.
  59 
  60 //------------------------------LoopNode---------------------------------------
  61 // Simple loop header.  Fall in path on left, loop-back path on right.
  62 class LoopNode : public RegionNode {
  63   // Size is bigger to hold the flags.  However, the flags do not change
  64   // the semantics so it does not appear in the hash & cmp functions.
  65   virtual uint size_of() const { return sizeof(*this); }
  66 protected:

  69   enum { Normal=0, Pre=1, Main=2, Post=3, PreMainPostFlagsMask=3,
  70          MainHasNoPreLoop      = 1<<2,
  71          HasExactTripCount     = 1<<3,
  72          InnerLoop             = 1<<4,
  73          PartialPeelLoop       = 1<<5,
  74          PartialPeelFailed     = 1<<6,
  75          WasSlpAnalyzed        = 1<<7,
  76          PassedSlpAnalysis     = 1<<8,
  77          DoUnrollOnly          = 1<<9,
  78          VectorizedLoop        = 1<<10,
  79          HasAtomicPostLoop     = 1<<11,
  80          StripMined            = 1<<12,
  81          SubwordLoop           = 1<<13,
  82          ProfileTripFailed     = 1<<14,
  83          LoopNestInnerLoop     = 1<<15,
  84          LoopNestLongOuterLoop = 1<<16,
  85          MultiversionFastLoop         = 1<<17,
  86          MultiversionSlowLoop         = 2<<17,
  87          MultiversionDelayedSlowLoop  = 3<<17,
  88          MultiversionFlagsMask        = 3<<17,
  89          FlatArrays            = 1<<18};
  90   char _unswitch_count;
  91   enum { _unswitch_max=3 };
  92 
  93   // Expected trip count from profile data
  94   float _profile_trip_cnt;
  95 
  96 public:
  97   // Names for edge indices
  98   enum { Self=0, EntryControl, LoopBackControl };
  99 
 100   bool is_inner_loop() const { return _loop_flags & InnerLoop; }
 101   void set_inner_loop() { _loop_flags |= InnerLoop; }
 102 
 103   bool is_vectorized_loop() const { return _loop_flags & VectorizedLoop; }
 104   bool is_partial_peel_loop() const { return _loop_flags & PartialPeelLoop; }
 105   void set_partial_peel_loop() { _loop_flags |= PartialPeelLoop; }
 106   bool partial_peel_has_failed() const { return _loop_flags & PartialPeelFailed; }
 107   bool is_strip_mined() const { return _loop_flags & StripMined; }
 108   bool is_profile_trip_failed() const { return _loop_flags & ProfileTripFailed; }
 109   bool is_subword_loop() const { return _loop_flags & SubwordLoop; }
 110   bool is_loop_nest_inner_loop() const { return _loop_flags & LoopNestInnerLoop; }
 111   bool is_loop_nest_outer_loop() const { return _loop_flags & LoopNestLongOuterLoop; }
 112   bool is_flat_arrays() const { return _loop_flags & FlatArrays; }
 113 
 114   void mark_partial_peel_failed() { _loop_flags |= PartialPeelFailed; }
 115   void mark_was_slp() { _loop_flags |= WasSlpAnalyzed; }
 116   void mark_passed_slp() { _loop_flags |= PassedSlpAnalysis; }
 117   void mark_do_unroll_only() { _loop_flags |= DoUnrollOnly; }
 118   void mark_loop_vectorized() { _loop_flags |= VectorizedLoop; }
 119   void mark_has_atomic_post_loop() { _loop_flags |= HasAtomicPostLoop; }
 120   void mark_strip_mined() { _loop_flags |= StripMined; }
 121   void clear_strip_mined() { _loop_flags &= ~StripMined; }
 122   void mark_profile_trip_failed() { _loop_flags |= ProfileTripFailed; }
 123   void mark_subword_loop() { _loop_flags |= SubwordLoop; }
 124   void mark_loop_nest_inner_loop() { _loop_flags |= LoopNestInnerLoop; }
 125   void mark_loop_nest_outer_loop() { _loop_flags |= LoopNestLongOuterLoop; }
 126   void mark_flat_arrays() { _loop_flags |= FlatArrays; }
 127 
 128   int unswitch_max() { return _unswitch_max; }
 129   int unswitch_count() { return _unswitch_count; }
 130 
 131   void set_unswitch_count(int val) {
 132     assert (val <= unswitch_max(), "too many unswitches");
 133     _unswitch_count = val;
 134   }
 135 
 136   void set_profile_trip_cnt(float ptc) { _profile_trip_cnt = ptc; }
 137   float profile_trip_cnt()             { return _profile_trip_cnt; }
 138 
 139 #ifndef PRODUCT
 140   uint _stress_peeling_attempts = 0;
 141 #endif
 142 
 143   LoopNode(Node *entry, Node *backedge)
 144     : RegionNode(3), _loop_flags(0), _unswitch_count(0),
 145       _profile_trip_cnt(COUNT_UNKNOWN) {
 146     init_class_id(Class_Loop);

 739   // Convert to counted loops where possible
 740   void counted_loop( PhaseIdealLoop *phase );
 741 
 742   // Check for Node being a loop-breaking test
 743   Node *is_loop_exit(Node *iff) const;
 744 
 745   // Remove simplistic dead code from loop body
 746   void DCE_loop_body();
 747 
 748   // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
 749   // Replace with a 1-in-10 exit guess.
 750   void adjust_loop_exit_prob( PhaseIdealLoop *phase );
 751 
 752   // Return TRUE or FALSE if the loop should never be RCE'd or aligned.
 753   // Useful for unrolling loops with NO array accesses.
 754   bool policy_peel_only( PhaseIdealLoop *phase ) const;
 755 
 756   // Return TRUE or FALSE if the loop should be unswitched -- clone
 757   // loop with an invariant test
 758   bool policy_unswitching( PhaseIdealLoop *phase ) const;
 759   bool no_unswitch_candidate() const;
 760 
 761   // Micro-benchmark spamming.  Remove empty loops.
 762   bool do_remove_empty_loop( PhaseIdealLoop *phase );
 763 
 764   // Convert one-iteration loop into normal code.
 765   bool do_one_iteration_loop( PhaseIdealLoop *phase );
 766 
 767   // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
 768   // move some loop-invariant test (usually a null-check) before the loop.
 769   bool policy_peeling(PhaseIdealLoop *phase);
 770 
 771   uint estimate_peeling(PhaseIdealLoop *phase);
 772 
 773   // Return TRUE or FALSE if the loop should be maximally unrolled. Stash any
 774   // known trip count in the counted loop node.
 775   bool policy_maximally_unroll(PhaseIdealLoop *phase) const;
 776 
 777   // Return TRUE or FALSE if the loop should be unrolled or not. Apply unroll
 778   // if the loop is a counted loop and the loop body is small enough.
 779   bool policy_unroll(PhaseIdealLoop *phase);

1485 
1486  public:
1487   // Change the control input of expensive nodes to allow commoning by
1488   // IGVN when it is guaranteed to not result in a more frequent
1489   // execution of the expensive node. Return true if progress.
1490   bool process_expensive_nodes();
1491 
1492   // Check whether node has become unreachable
1493   bool is_node_unreachable(Node *n) const {
1494     return !has_node(n) || n->is_unreachable(_igvn);
1495   }
1496 
1497   // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1498   void do_range_check(IdealLoopTree* loop);
1499 
1500   // Clone loop with an invariant test (that does not exit) and
1501   // insert a clone of the test that selects which version to
1502   // execute.
1503   void do_unswitching(IdealLoopTree* loop, Node_List& old_new);
1504 
1505   IfNode* find_unswitch_candidates(const IdealLoopTree* loop, Node_List& flat_array_checks) const;
1506   IfNode* find_unswitch_candidate_from_idoms(const IdealLoopTree* loop) const;
1507 
1508  private:
1509   static bool has_control_dependencies_from_predicates(LoopNode* head);
1510   static void revert_to_normal_loop(const LoopNode* loop_head);
1511 
1512   void hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
1513                                    const UnswitchCandidate& unswitch_candidate, const IfNode* loop_selector);
1514   void add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new);
1515   static void increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head);
1516   void remove_unswitch_candidate_from_loops(const Node_List& old_new, const UnswitchedLoopSelector& unswitched_loop_selector);
1517 #ifndef PRODUCT
1518   static void trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head);
1519   static void trace_loop_unswitching_impossible(const LoopNode* original_head);
1520   static void trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
1521                                             const UnswitchCandidate& unswitch_candidate,
1522                                             const LoopNode* original_head, const LoopNode* new_head);
1523   static void trace_loop_multiversioning_result(const LoopSelector& loop_selector,
1524                                                 const LoopNode* original_head, const LoopNode* new_head);
1525 #endif
1526 
1527  public:
1528 
1529   // Range Check Elimination uses this function!
1530   // Constrain the main loop iterations so the affine function:
1531   //    low_limit <= scale_con * I + offset  <  upper_limit
1532   // always holds true.  That is, either increase the number of iterations in
1533   // the pre-loop or the post-loop until the condition holds true in the main
1534   // loop.  Scale_con, offset and limit are all loop invariant.
1535   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);
1536   // Helper function for add_constraint().
1537   Node* adjust_limit(bool reduce, Node* scale, Node* offset, Node* rc_limit, Node* old_limit, Node* pre_ctrl, bool round);
1538 
1539   // Partially peel loop up through last_peel node.
1540   bool partial_peel( IdealLoopTree *loop, Node_List &old_new );
1541   bool duplicate_loop_backedge(IdealLoopTree *loop, Node_List &old_new);

1699   bool intrinsify_fill(IdealLoopTree* lpt);
1700   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1701                        Node*& shift, Node*& offset);
1702 
1703 private:
1704   // Return a type based on condition control flow
1705   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1706   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, nullptr); }
1707  // Helpers for filtered type
1708   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1709 
1710   // Helper functions
1711   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1712   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1713   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 );
1714   bool split_up( Node *n, Node *blk1, Node *blk2 );
1715 
1716   Node* place_outside_loop(Node* useblock, IdealLoopTree* loop) const;
1717   Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1718   void try_move_store_after_loop(Node* n);
1719   void move_flat_array_check_out_of_loop(Node* n);
1720   bool identical_backtoback_ifs(Node *n);
1721   bool flat_array_element_type_check(Node *n);
1722   bool can_split_if(Node *n_ctrl);
1723   bool cannot_split_division(const Node* n, const Node* region) const;
1724   static bool is_divisor_loop_phi(const Node* divisor, const Node* loop);
1725   bool loop_phi_backedge_type_contains_zero(const Node* phi_divisor, const Type* zero) const;
1726 
1727   // Determine if a method is too big for a/another round of split-if, based on
1728   // a magic (approximate) ratio derived from the equally magic constant 35000,
1729   // previously used for this purpose (but without relating to the node limit).
1730   bool must_throttle_split_if() {
1731     uint threshold = C->max_node_limit() * 2 / 5;
1732     return C->live_nodes() > threshold;
1733   }
1734 
1735   // A simplistic node request tracking mechanism, where
1736   //   = UINT_MAX   Request not valid or made final.
1737   //   < UINT_MAX   Nodes currently requested (estimate).
1738   uint _nodes_required;
1739 
1740   enum { REQUIRE_MIN = 70 };
1741 

1891                      uint new_counter, Node_List& old_new, Node_List& worklist, Node_List*& split_if_set,
1892                      Node_List*& split_bool_set, Node_List*& split_cex_set);
1893 
1894   void finish_clone_loop(Node_List* split_if_set, Node_List* split_bool_set, Node_List* split_cex_set);
1895 
1896   bool at_relevant_ctrl(Node* n, const Node* blk1, const Node* blk2);
1897 
1898   bool clone_cmp_loadklass_down(Node* n, const Node* blk1, const Node* blk2);
1899   void clone_loadklass_nodes_at_cmp_index(const Node* n, Node* cmp, int i);
1900   bool clone_cmp_down(Node* n, const Node* blk1, const Node* blk2);
1901   void clone_template_assertion_expression_down(Node* node);
1902 
1903   Node* similar_subtype_check(const Node* x, Node* r_in);
1904 
1905   void update_addp_chain_base(Node* x, Node* old_base, Node* new_base);
1906 
1907   bool can_move_to_inner_loop(Node* n, LoopNode* n_loop, Node* x);
1908 
1909   void pin_array_access_nodes_dependent_on(Node* ctrl);
1910 
1911   void collect_flat_array_checks(const IdealLoopTree* loop, Node_List& flat_array_checks) const;
1912 
1913   Node* ensure_node_and_inputs_are_above_pre_end(CountedLoopEndNode* pre_end, Node* node);
1914 
1915   bool try_make_short_running_loop(IdealLoopTree* loop, jint stride_con, const Node_List& range_checks, const uint iters_limit);
1916 
1917   ConINode* intcon(jint i);
1918 
1919   ConLNode* longcon(jlong i);
1920 
1921   ConNode* makecon(const Type* t);
1922 
1923   ConNode* integercon(jlong l, BasicType bt);
1924 
1925   ConNode* zerocon(BasicType bt);
1926 };
1927 
1928 
1929 class AutoNodeBudget : public StackObj
1930 {
1931 public:
1932   enum budget_check_t { BUDGET_CHECK, NO_BUDGET_CHECK };
< prev index next >