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

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

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

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

1487 
1488  private:
1489   static bool has_control_dependencies_from_predicates(LoopNode* head);
1490   static void revert_to_normal_loop(const LoopNode* loop_head);
1491 
1492   void hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
1493                                    const UnswitchedLoopSelector& unswitched_loop_selector);
1494   void add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new);
1495   static void increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head);
1496   void remove_unswitch_candidate_from_loops(const Node_List& old_new, const UnswitchedLoopSelector& unswitched_loop_selector);
1497 #ifndef PRODUCT
1498   static void trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head);
1499   static void trace_loop_unswitching_impossible(const LoopNode* original_head);
1500   static void trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,

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

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

1640   bool identical_backtoback_ifs(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   Node* ensure_node_and_inputs_are_above_pre_end(CountedLoopEndNode* pre_end, Node* node);
1831 
1832   ConINode* intcon(jint i);
1833 
1834   ConLNode* longcon(jlong i);
1835 
1836   ConNode* makecon(const Type* t);
1837 
1838   ConNode* integercon(jlong l, BasicType bt);
1839 
1840   ConNode* zerocon(BasicType bt);
1841 };
1842 
1843 
1844 class AutoNodeBudget : public StackObj
1845 {
1846 public:
1847   enum budget_check_t { BUDGET_CHECK, NO_BUDGET_CHECK };
1848 
1849   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);

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

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

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

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