< 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   LoopNode(Node *entry, Node *backedge)
 137     : RegionNode(3), _loop_flags(0), _unswitch_count(0),
 138       _profile_trip_cnt(COUNT_UNKNOWN) {
 139     init_class_id(Class_Loop);
 140     init_req(EntryControl, entry);
 141     init_req(LoopBackControl, backedge);
 142   }
 143 

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

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

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

1471 
1472  private:
1473   static bool has_control_dependencies_from_predicates(LoopNode* head);
1474   static void revert_to_normal_loop(const LoopNode* loop_head);
1475 
1476   void hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
1477                                    const UnswitchedLoopSelector& unswitched_loop_selector);
1478   void add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new);
1479   static void increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head);
1480   void remove_unswitch_candidate_from_loops(const Node_List& old_new, const UnswitchedLoopSelector& unswitched_loop_selector);
1481 #ifndef PRODUCT
1482   static void trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head);
1483   static void trace_loop_unswitching_impossible(const LoopNode* original_head);
1484   static void trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,

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

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

1626   bool identical_backtoback_ifs(Node *n);

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

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


1816   Node* ensure_node_and_inputs_are_above_pre_end(CountedLoopEndNode* pre_end, Node* node);
1817 
1818   ConINode* intcon(jint i);
1819 
1820   ConLNode* longcon(jlong i);
1821 
1822   ConNode* makecon(const Type* t);
1823 
1824   ConNode* integercon(jlong l, BasicType bt);
1825 
1826   ConNode* zerocon(BasicType bt);
1827 };
1828 
1829 
1830 class AutoNodeBudget : public StackObj
1831 {
1832 public:
1833   enum budget_check_t { BUDGET_CHECK, NO_BUDGET_CHECK };
1834 
1835   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   LoopNode(Node *entry, Node *backedge)
 140     : RegionNode(3), _loop_flags(0), _unswitch_count(0),
 141       _profile_trip_cnt(COUNT_UNKNOWN) {
 142     init_class_id(Class_Loop);
 143     init_req(EntryControl, entry);
 144     init_req(LoopBackControl, backedge);
 145   }
 146 

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

1454 
1455  public:
1456   // Change the control input of expensive nodes to allow commoning by
1457   // IGVN when it is guaranteed to not result in a more frequent
1458   // execution of the expensive node. Return true if progress.
1459   bool process_expensive_nodes();
1460 
1461   // Check whether node has become unreachable
1462   bool is_node_unreachable(Node *n) const {
1463     return !has_node(n) || n->is_unreachable(_igvn);
1464   }
1465 
1466   // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1467   void do_range_check(IdealLoopTree* loop);
1468 
1469   // Clone loop with an invariant test (that does not exit) and
1470   // insert a clone of the test that selects which version to
1471   // execute.
1472   void do_unswitching(IdealLoopTree* loop, Node_List& old_new);
1473 
1474   IfNode* find_unswitch_candidates(const IdealLoopTree* loop, Node_List& flat_array_checks) const;
1475   IfNode* find_unswitch_candidate_from_idoms(const IdealLoopTree* loop) const;
1476 
1477  private:
1478   static bool has_control_dependencies_from_predicates(LoopNode* head);
1479   static void revert_to_normal_loop(const LoopNode* loop_head);
1480 
1481   void hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
1482                                    const UnswitchCandidate& unswitch_candidate, const IfNode* loop_selector);
1483   void add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new);
1484   static void increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head);
1485   void remove_unswitch_candidate_from_loops(const Node_List& old_new, const UnswitchedLoopSelector& unswitched_loop_selector);
1486 #ifndef PRODUCT
1487   static void trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head);
1488   static void trace_loop_unswitching_impossible(const LoopNode* original_head);
1489   static void trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
1490                                             const UnswitchCandidate& unswitch_candidate,
1491                                             const LoopNode* original_head, const LoopNode* new_head);
1492   static void trace_loop_multiversioning_result(const LoopSelector& loop_selector,
1493                                                 const LoopNode* original_head, const LoopNode* new_head);
1494 #endif
1495 
1496  public:
1497 
1498   // Range Check Elimination uses this function!
1499   // Constrain the main loop iterations so the affine function:
1500   //    low_limit <= scale_con * I + offset  <  upper_limit
1501   // always holds true.  That is, either increase the number of iterations in
1502   // the pre-loop or the post-loop until the condition holds true in the main
1503   // loop.  Scale_con, offset and limit are all loop invariant.
1504   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);
1505   // Helper function for add_constraint().
1506   Node* adjust_limit(bool reduce, Node* scale, Node* offset, Node* rc_limit, Node* old_limit, Node* pre_ctrl, bool round);
1507 
1508   // Partially peel loop up through last_peel node.
1509   bool partial_peel( IdealLoopTree *loop, Node_List &old_new );
1510   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   void move_flat_array_check_out_of_loop(Node* n);
1633   bool identical_backtoback_ifs(Node *n);
1634   bool flat_array_element_type_check(Node *n);
1635   bool can_split_if(Node *n_ctrl);
1636   bool cannot_split_division(const Node* n, const Node* region) const;
1637   static bool is_divisor_loop_phi(const Node* divisor, const Node* loop);
1638   bool loop_phi_backedge_type_contains_zero(const Node* phi_divisor, const Type* zero) const;
1639 
1640   // Determine if a method is too big for a/another round of split-if, based on
1641   // a magic (approximate) ratio derived from the equally magic constant 35000,
1642   // previously used for this purpose (but without relating to the node limit).
1643   bool must_throttle_split_if() {
1644     uint threshold = C->max_node_limit() * 2 / 5;
1645     return C->live_nodes() > threshold;
1646   }
1647 
1648   // A simplistic node request tracking mechanism, where
1649   //   = UINT_MAX   Request not valid or made final.
1650   //   < UINT_MAX   Nodes currently requested (estimate).
1651   uint _nodes_required;
1652 
1653   enum { REQUIRE_MIN = 70 };
1654 

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