< 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);

 713   // Convert to counted loops where possible
 714   void counted_loop( PhaseIdealLoop *phase );
 715 
 716   // Check for Node being a loop-breaking test
 717   Node *is_loop_exit(Node *iff) const;
 718 
 719   // Remove simplistic dead code from loop body
 720   void DCE_loop_body();
 721 
 722   // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
 723   // Replace with a 1-in-10 exit guess.
 724   void adjust_loop_exit_prob( PhaseIdealLoop *phase );
 725 
 726   // Return TRUE or FALSE if the loop should never be RCE'd or aligned.
 727   // Useful for unrolling loops with NO array accesses.
 728   bool policy_peel_only( PhaseIdealLoop *phase ) const;
 729 
 730   // Return TRUE or FALSE if the loop should be unswitched -- clone
 731   // loop with an invariant test
 732   bool policy_unswitching( PhaseIdealLoop *phase ) const;

 733 
 734   // Micro-benchmark spamming.  Remove empty loops.
 735   bool do_remove_empty_loop( PhaseIdealLoop *phase );
 736 
 737   // Convert one iteration loop into normal code.
 738   bool do_one_iteration_loop( PhaseIdealLoop *phase );
 739 
 740   // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
 741   // move some loop-invariant test (usually a null-check) before the loop.
 742   bool policy_peeling(PhaseIdealLoop *phase);
 743 
 744   uint estimate_peeling(PhaseIdealLoop *phase);
 745 
 746   // Return TRUE or FALSE if the loop should be maximally unrolled. Stash any
 747   // known trip count in the counted loop node.
 748   bool policy_maximally_unroll(PhaseIdealLoop *phase) const;
 749 
 750   // Return TRUE or FALSE if the loop should be unrolled or not. Apply unroll
 751   // if the loop is a counted loop and the loop body is small enough.
 752   bool policy_unroll(PhaseIdealLoop *phase);

1458 
1459  public:
1460   // Change the control input of expensive nodes to allow commoning by
1461   // IGVN when it is guaranteed to not result in a more frequent
1462   // execution of the expensive node. Return true if progress.
1463   bool process_expensive_nodes();
1464 
1465   // Check whether node has become unreachable
1466   bool is_node_unreachable(Node *n) const {
1467     return !has_node(n) || n->is_unreachable(_igvn);
1468   }
1469 
1470   // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1471   void do_range_check(IdealLoopTree* loop);
1472 
1473   // Clone loop with an invariant test (that does not exit) and
1474   // insert a clone of the test that selects which version to
1475   // execute.
1476   void do_unswitching(IdealLoopTree* loop, Node_List& old_new);
1477 
1478   IfNode* find_unswitch_candidate(const IdealLoopTree* loop) const;

1479 
1480  private:
1481   static bool has_control_dependencies_from_predicates(LoopNode* head);
1482   static void revert_to_normal_loop(const LoopNode* loop_head);
1483 
1484   void hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
1485                                    const UnswitchedLoopSelector& unswitched_loop_selector);
1486   void add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new);
1487   static void increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head);
1488   void remove_unswitch_candidate_from_loops(const Node_List& old_new, const UnswitchedLoopSelector& unswitched_loop_selector);
1489 #ifndef PRODUCT
1490   static void trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head);
1491   static void trace_loop_unswitching_impossible(const LoopNode* original_head);
1492   static void trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,

1493                                             const LoopNode* original_head, const LoopNode* new_head);
1494   static void trace_loop_multiversioning_result(const LoopSelector& loop_selector,
1495                                                 const LoopNode* original_head, const LoopNode* new_head);
1496 #endif
1497 
1498  public:
1499 
1500   // Range Check Elimination uses this function!
1501   // Constrain the main loop iterations so the affine function:
1502   //    low_limit <= scale_con * I + offset  <  upper_limit
1503   // always holds true.  That is, either increase the number of iterations in
1504   // the pre-loop or the post-loop until the condition holds true in the main
1505   // loop.  Scale_con, offset and limit are all loop invariant.
1506   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);
1507   // Helper function for add_constraint().
1508   Node* adjust_limit(bool reduce, Node* scale, Node* offset, Node* rc_limit, Node* old_limit, Node* pre_ctrl, bool round);
1509 
1510   // Partially peel loop up through last_peel node.
1511   bool partial_peel( IdealLoopTree *loop, Node_List &old_new );
1512   bool duplicate_loop_backedge(IdealLoopTree *loop, Node_List &old_new);

1612   bool intrinsify_fill(IdealLoopTree* lpt);
1613   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1614                        Node*& shift, Node*& offset);
1615 
1616 private:
1617   // Return a type based on condition control flow
1618   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1619   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, nullptr); }
1620  // Helpers for filtered type
1621   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1622 
1623   // Helper functions
1624   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1625   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1626   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 );
1627   bool split_up( Node *n, Node *blk1, Node *blk2 );
1628 
1629   Node* place_outside_loop(Node* useblock, IdealLoopTree* loop) const;
1630   Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1631   void try_move_store_after_loop(Node* n);

1632   bool identical_backtoback_ifs(Node *n);

1633   bool can_split_if(Node *n_ctrl);
1634   bool cannot_split_division(const Node* n, const Node* region) const;
1635   static bool is_divisor_loop_phi(const Node* divisor, const Node* loop);
1636   bool loop_phi_backedge_type_contains_zero(const Node* phi_divisor, const Type* zero) const;
1637 
1638   // Determine if a method is too big for a/another round of split-if, based on
1639   // a magic (approximate) ratio derived from the equally magic constant 35000,
1640   // previously used for this purpose (but without relating to the node limit).
1641   bool must_throttle_split_if() {
1642     uint threshold = C->max_node_limit() * 2 / 5;
1643     return C->live_nodes() > threshold;
1644   }
1645 
1646   // A simplistic node request tracking mechanism, where
1647   //   = UINT_MAX   Request not valid or made final.
1648   //   < UINT_MAX   Nodes currently requested (estimate).
1649   uint _nodes_required;
1650 
1651   enum { REQUIRE_MIN = 70 };
1652 

1802                      uint new_counter, Node_List& old_new, Node_List& worklist, Node_List*& split_if_set,
1803                      Node_List*& split_bool_set, Node_List*& split_cex_set);
1804 
1805   void finish_clone_loop(Node_List* split_if_set, Node_List* split_bool_set, Node_List* split_cex_set);
1806 
1807   bool at_relevant_ctrl(Node* n, const Node* blk1, const Node* blk2);
1808 
1809   bool clone_cmp_loadklass_down(Node* n, const Node* blk1, const Node* blk2);
1810   void clone_loadklass_nodes_at_cmp_index(const Node* n, Node* cmp, int i);
1811   bool clone_cmp_down(Node* n, const Node* blk1, const Node* blk2);
1812   void clone_template_assertion_expression_down(Node* node);
1813 
1814   Node* similar_subtype_check(const Node* x, Node* r_in);
1815 
1816   void update_addp_chain_base(Node* x, Node* old_base, Node* new_base);
1817 
1818   bool can_move_to_inner_loop(Node* n, LoopNode* n_loop, Node* x);
1819 
1820   void pin_array_access_nodes_dependent_on(Node* ctrl);
1821 


1822   Node* ensure_node_and_inputs_are_above_pre_end(CountedLoopEndNode* pre_end, Node* node);
1823 
1824   ConINode* intcon(jint i);
1825 
1826   ConLNode* longcon(jlong i);
1827 
1828   ConNode* makecon(const Type* t);
1829 
1830   ConNode* integercon(jlong l, BasicType bt);
1831 
1832   ConNode* zerocon(BasicType bt);
1833 };
1834 
1835 
1836 class AutoNodeBudget : public StackObj
1837 {
1838 public:
1839   enum budget_check_t { BUDGET_CHECK, NO_BUDGET_CHECK };
1840 
1841   AutoNodeBudget(PhaseIdealLoop* phase, budget_check_t chk = 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);

 716   // Convert to counted loops where possible
 717   void counted_loop( PhaseIdealLoop *phase );
 718 
 719   // Check for Node being a loop-breaking test
 720   Node *is_loop_exit(Node *iff) const;
 721 
 722   // Remove simplistic dead code from loop body
 723   void DCE_loop_body();
 724 
 725   // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
 726   // Replace with a 1-in-10 exit guess.
 727   void adjust_loop_exit_prob( PhaseIdealLoop *phase );
 728 
 729   // Return TRUE or FALSE if the loop should never be RCE'd or aligned.
 730   // Useful for unrolling loops with NO array accesses.
 731   bool policy_peel_only( PhaseIdealLoop *phase ) const;
 732 
 733   // Return TRUE or FALSE if the loop should be unswitched -- clone
 734   // loop with an invariant test
 735   bool policy_unswitching( PhaseIdealLoop *phase ) const;
 736   bool no_unswitch_candidate() const;
 737 
 738   // Micro-benchmark spamming.  Remove empty loops.
 739   bool do_remove_empty_loop( PhaseIdealLoop *phase );
 740 
 741   // Convert one iteration loop into normal code.
 742   bool do_one_iteration_loop( PhaseIdealLoop *phase );
 743 
 744   // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
 745   // move some loop-invariant test (usually a null-check) before the loop.
 746   bool policy_peeling(PhaseIdealLoop *phase);
 747 
 748   uint estimate_peeling(PhaseIdealLoop *phase);
 749 
 750   // Return TRUE or FALSE if the loop should be maximally unrolled. Stash any
 751   // known trip count in the counted loop node.
 752   bool policy_maximally_unroll(PhaseIdealLoop *phase) const;
 753 
 754   // Return TRUE or FALSE if the loop should be unrolled or not. Apply unroll
 755   // if the loop is a counted loop and the loop body is small enough.
 756   bool policy_unroll(PhaseIdealLoop *phase);

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

1618   bool intrinsify_fill(IdealLoopTree* lpt);
1619   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1620                        Node*& shift, Node*& offset);
1621 
1622 private:
1623   // Return a type based on condition control flow
1624   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1625   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, nullptr); }
1626  // Helpers for filtered type
1627   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1628 
1629   // Helper functions
1630   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1631   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1632   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 );
1633   bool split_up( Node *n, Node *blk1, Node *blk2 );
1634 
1635   Node* place_outside_loop(Node* useblock, IdealLoopTree* loop) const;
1636   Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1637   void try_move_store_after_loop(Node* n);
1638   void move_flat_array_check_out_of_loop(Node* n);
1639   bool identical_backtoback_ifs(Node *n);
1640   bool flat_array_element_type_check(Node *n);
1641   bool can_split_if(Node *n_ctrl);
1642   bool cannot_split_division(const Node* n, const Node* region) const;
1643   static bool is_divisor_loop_phi(const Node* divisor, const Node* loop);
1644   bool loop_phi_backedge_type_contains_zero(const Node* phi_divisor, const Type* zero) const;
1645 
1646   // Determine if a method is too big for a/another round of split-if, based on
1647   // a magic (approximate) ratio derived from the equally magic constant 35000,
1648   // previously used for this purpose (but without relating to the node limit).
1649   bool must_throttle_split_if() {
1650     uint threshold = C->max_node_limit() * 2 / 5;
1651     return C->live_nodes() > threshold;
1652   }
1653 
1654   // A simplistic node request tracking mechanism, where
1655   //   = UINT_MAX   Request not valid or made final.
1656   //   < UINT_MAX   Nodes currently requested (estimate).
1657   uint _nodes_required;
1658 
1659   enum { REQUIRE_MIN = 70 };
1660 

1810                      uint new_counter, Node_List& old_new, Node_List& worklist, Node_List*& split_if_set,
1811                      Node_List*& split_bool_set, Node_List*& split_cex_set);
1812 
1813   void finish_clone_loop(Node_List* split_if_set, Node_List* split_bool_set, Node_List* split_cex_set);
1814 
1815   bool at_relevant_ctrl(Node* n, const Node* blk1, const Node* blk2);
1816 
1817   bool clone_cmp_loadklass_down(Node* n, const Node* blk1, const Node* blk2);
1818   void clone_loadklass_nodes_at_cmp_index(const Node* n, Node* cmp, int i);
1819   bool clone_cmp_down(Node* n, const Node* blk1, const Node* blk2);
1820   void clone_template_assertion_expression_down(Node* node);
1821 
1822   Node* similar_subtype_check(const Node* x, Node* r_in);
1823 
1824   void update_addp_chain_base(Node* x, Node* old_base, Node* new_base);
1825 
1826   bool can_move_to_inner_loop(Node* n, LoopNode* n_loop, Node* x);
1827 
1828   void pin_array_access_nodes_dependent_on(Node* ctrl);
1829 
1830   void collect_flat_array_checks(const IdealLoopTree* loop, Node_List& flat_array_checks) const;
1831 
1832   Node* ensure_node_and_inputs_are_above_pre_end(CountedLoopEndNode* pre_end, Node* node);
1833 
1834   ConINode* intcon(jint i);
1835 
1836   ConLNode* longcon(jlong i);
1837 
1838   ConNode* makecon(const Type* t);
1839 
1840   ConNode* integercon(jlong l, BasicType bt);
1841 
1842   ConNode* zerocon(BasicType bt);
1843 };
1844 
1845 
1846 class AutoNodeBudget : public StackObj
1847 {
1848 public:
1849   enum budget_check_t { BUDGET_CHECK, NO_BUDGET_CHECK };
1850 
1851   AutoNodeBudget(PhaseIdealLoop* phase, budget_check_t chk = BUDGET_CHECK)
< prev index next >