21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_OPTO_LOOPNODE_HPP
26 #define SHARE_VM_OPTO_LOOPNODE_HPP
27
28 #include "opto/cfgnode.hpp"
29 #include "opto/multnode.hpp"
30 #include "opto/phaseX.hpp"
31 #include "opto/subnode.hpp"
32 #include "opto/type.hpp"
33
34 class CmpNode;
35 class CountedLoopEndNode;
36 class CountedLoopNode;
37 class IdealLoopTree;
38 class LoopNode;
39 class Node;
40 class OuterStripMinedLoopEndNode;
41 class PathFrequency;
42 class PhaseIdealLoop;
43 class CountedLoopReserveKit;
44 class VectorSet;
45 class Invariance;
46 struct small_cache;
47
48 //
49 // I D E A L I Z E D L O O P S
50 //
51 // Idealized loops are the set of loops I perform more interesting
52 // transformations on, beyond simple hoisting.
53
54 //------------------------------LoopNode---------------------------------------
55 // Simple loop header. Fall in path on left, loop-back path on right.
56 class LoopNode : public RegionNode {
57 // Size is bigger to hold the flags. However, the flags do not change
58 // the semantics so it does not appear in the hash & cmp functions.
59 virtual uint size_of() const { return sizeof(*this); }
60 protected:
619 bool is_inner() { return is_loop() && _child == NULL; }
620 bool is_counted() { return is_loop() && _head != NULL && _head->is_CountedLoop(); }
621
622 void remove_main_post_loops(CountedLoopNode *cl, PhaseIdealLoop *phase);
623
624 #ifndef PRODUCT
625 void dump_head( ) const; // Dump loop head only
626 void dump() const; // Dump this loop recursively
627 void verify_tree(IdealLoopTree *loop, const IdealLoopTree *parent) const;
628 #endif
629
630 };
631
632 // -----------------------------PhaseIdealLoop---------------------------------
633 // Computes the mapping from Nodes to IdealLoopTrees. Organizes IdealLoopTrees into a
634 // loop tree. Drives the loop-based transformations on the ideal graph.
635 class PhaseIdealLoop : public PhaseTransform {
636 friend class IdealLoopTree;
637 friend class SuperWord;
638 friend class CountedLoopReserveKit;
639
640 // Pre-computed def-use info
641 PhaseIterGVN &_igvn;
642
643 // Head of loop tree
644 IdealLoopTree *_ltree_root;
645
646 // Array of pre-order numbers, plus post-visited bit.
647 // ZERO for not pre-visited. EVEN for pre-visited but not post-visited.
648 // ODD for post-visited. Other bits are the pre-order number.
649 uint *_preorders;
650 uint _max_preorder;
651
652 const PhaseIdealLoop* _verify_me;
653 bool _verify_only;
654
655 // Allocate _preorders[] array
656 void allocate_preorders() {
657 _max_preorder = C->unique()+8;
658 _preorders = NEW_RESOURCE_ARRAY(uint, _max_preorder);
846 // forwarding pointer.
847 _nodes.map(old_node->_idx, (Node*)((intptr_t)new_node + 1));
848 }
849 void lazy_replace(Node *old_node, Node *new_node) {
850 _igvn.replace_node(old_node, new_node);
851 lazy_update(old_node, new_node);
852 }
853
854 private:
855
856 // Place 'n' in some loop nest, where 'n' is a CFG node
857 void build_loop_tree();
858 int build_loop_tree_impl( Node *n, int pre_order );
859 // Insert loop into the existing loop tree. 'innermost' is a leaf of the
860 // loop tree, not the root.
861 IdealLoopTree *sort( IdealLoopTree *loop, IdealLoopTree *innermost );
862
863 // Place Data nodes in some loop nest
864 void build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
865 void build_loop_late ( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
866 void build_loop_late_post ( Node* n );
867 void verify_strip_mined_scheduling(Node *n, Node* least);
868
869 // Array of immediate dominance info for each CFG node indexed by node idx
870 private:
871 uint _idom_size;
872 Node **_idom; // Array of immediate dominators
873 uint *_dom_depth; // Used for fast LCA test
874 GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
875
876 public:
877 Node* idom_no_update(Node* d) const {
878 return idom_no_update(d->_idx);
879 }
880
881 Node* idom_no_update(uint didx) const {
882 assert(didx < _idom_size, "oob");
883 Node* n = _idom[didx];
884 assert(n != NULL,"Bad immediate dominator info.");
885 while (n->in(0) == NULL) { // Skip dead CFG nodes
886 n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);
1292 void sink_use( Node *use, Node *post_loop );
1293 Node *place_near_use( Node *useblock ) const;
1294 Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1295 void try_move_store_after_loop(Node* n);
1296 bool identical_backtoback_ifs(Node *n);
1297 bool can_split_if(Node *n_ctrl);
1298
1299 bool _created_loop_node;
1300 public:
1301 void set_created_loop_node() { _created_loop_node = true; }
1302 bool created_loop_node() { return _created_loop_node; }
1303 void register_new_node( Node *n, Node *blk );
1304
1305 #ifdef ASSERT
1306 void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1307 #endif
1308
1309 #ifndef PRODUCT
1310 void dump( ) const;
1311 void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;
1312 void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1313 void verify() const; // Major slow :-)
1314 void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1315 IdealLoopTree *get_loop_idx(Node* n) const {
1316 // Dead nodes have no loop, so return the top level loop instead
1317 return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1318 }
1319 // Print some stats
1320 static void print_statistics();
1321 static int _loop_invokes; // Count of PhaseIdealLoop invokes
1322 static int _loop_work; // Sum of PhaseIdealLoop x _unique
1323 #endif
1324 };
1325
1326 // This kit may be used for making of a reserved copy of a loop before this loop
1327 // goes under non-reversible changes.
1328 //
1329 // Function create_reserve() creates a reserved copy (clone) of the loop.
1330 // The reserved copy is created by calling
1331 // PhaseIdealLoop::create_reserve_version_of_loop - see there how
1332 // the original and reserved loops are connected in the outer graph.
1333 // If create_reserve succeeded, it returns 'true' and _has_reserved is set to 'true'.
1334 //
1335 // By default the reserved copy (clone) of the loop is created as dead code - it is
1336 // dominated in the outer loop by this node chain:
1337 // intcon(1)->If->IfFalse->reserved_copy.
1338 // The original loop is dominated by the the same node chain but IfTrue projection:
1339 // intcon(0)->If->IfTrue->original_loop.
1340 //
1341 // In this implementation of CountedLoopReserveKit the ctor includes create_reserve()
1342 // and the dtor, checks _use_new value.
1343 // If _use_new == false, it "switches" control to reserved copy of the loop
|
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_OPTO_LOOPNODE_HPP
26 #define SHARE_VM_OPTO_LOOPNODE_HPP
27
28 #include "opto/cfgnode.hpp"
29 #include "opto/multnode.hpp"
30 #include "opto/phaseX.hpp"
31 #include "opto/subnode.hpp"
32 #include "opto/type.hpp"
33
34 class CmpNode;
35 class CountedLoopEndNode;
36 class CountedLoopNode;
37 class IdealLoopTree;
38 class LoopNode;
39 class Node;
40 class OuterStripMinedLoopEndNode;
41 class ShenandoahBarrierNode;
42 class ShenandoahWriteBarrierNode;
43 class PathFrequency;
44 class PhaseIdealLoop;
45 class CountedLoopReserveKit;
46 class VectorSet;
47 class Invariance;
48 struct small_cache;
49
50 //
51 // I D E A L I Z E D L O O P S
52 //
53 // Idealized loops are the set of loops I perform more interesting
54 // transformations on, beyond simple hoisting.
55
56 //------------------------------LoopNode---------------------------------------
57 // Simple loop header. Fall in path on left, loop-back path on right.
58 class LoopNode : public RegionNode {
59 // Size is bigger to hold the flags. However, the flags do not change
60 // the semantics so it does not appear in the hash & cmp functions.
61 virtual uint size_of() const { return sizeof(*this); }
62 protected:
621 bool is_inner() { return is_loop() && _child == NULL; }
622 bool is_counted() { return is_loop() && _head != NULL && _head->is_CountedLoop(); }
623
624 void remove_main_post_loops(CountedLoopNode *cl, PhaseIdealLoop *phase);
625
626 #ifndef PRODUCT
627 void dump_head( ) const; // Dump loop head only
628 void dump() const; // Dump this loop recursively
629 void verify_tree(IdealLoopTree *loop, const IdealLoopTree *parent) const;
630 #endif
631
632 };
633
634 // -----------------------------PhaseIdealLoop---------------------------------
635 // Computes the mapping from Nodes to IdealLoopTrees. Organizes IdealLoopTrees into a
636 // loop tree. Drives the loop-based transformations on the ideal graph.
637 class PhaseIdealLoop : public PhaseTransform {
638 friend class IdealLoopTree;
639 friend class SuperWord;
640 friend class CountedLoopReserveKit;
641 friend class ShenandoahBarrierNode;
642 friend class ShenandoahWriteBarrierNode;
643
644 // Pre-computed def-use info
645 PhaseIterGVN &_igvn;
646
647 // Head of loop tree
648 IdealLoopTree *_ltree_root;
649
650 // Array of pre-order numbers, plus post-visited bit.
651 // ZERO for not pre-visited. EVEN for pre-visited but not post-visited.
652 // ODD for post-visited. Other bits are the pre-order number.
653 uint *_preorders;
654 uint _max_preorder;
655
656 const PhaseIdealLoop* _verify_me;
657 bool _verify_only;
658
659 // Allocate _preorders[] array
660 void allocate_preorders() {
661 _max_preorder = C->unique()+8;
662 _preorders = NEW_RESOURCE_ARRAY(uint, _max_preorder);
850 // forwarding pointer.
851 _nodes.map(old_node->_idx, (Node*)((intptr_t)new_node + 1));
852 }
853 void lazy_replace(Node *old_node, Node *new_node) {
854 _igvn.replace_node(old_node, new_node);
855 lazy_update(old_node, new_node);
856 }
857
858 private:
859
860 // Place 'n' in some loop nest, where 'n' is a CFG node
861 void build_loop_tree();
862 int build_loop_tree_impl( Node *n, int pre_order );
863 // Insert loop into the existing loop tree. 'innermost' is a leaf of the
864 // loop tree, not the root.
865 IdealLoopTree *sort( IdealLoopTree *loop, IdealLoopTree *innermost );
866
867 // Place Data nodes in some loop nest
868 void build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
869 void build_loop_late ( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
870 void build_loop_late_post_work(Node* n, bool pinned);
871 void build_loop_late_post(Node* n);
872 void verify_strip_mined_scheduling(Node *n, Node* least);
873
874 // Array of immediate dominance info for each CFG node indexed by node idx
875 private:
876 uint _idom_size;
877 Node **_idom; // Array of immediate dominators
878 uint *_dom_depth; // Used for fast LCA test
879 GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
880
881 public:
882 Node* idom_no_update(Node* d) const {
883 return idom_no_update(d->_idx);
884 }
885
886 Node* idom_no_update(uint didx) const {
887 assert(didx < _idom_size, "oob");
888 Node* n = _idom[didx];
889 assert(n != NULL,"Bad immediate dominator info.");
890 while (n->in(0) == NULL) { // Skip dead CFG nodes
891 n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);
1297 void sink_use( Node *use, Node *post_loop );
1298 Node *place_near_use( Node *useblock ) const;
1299 Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1300 void try_move_store_after_loop(Node* n);
1301 bool identical_backtoback_ifs(Node *n);
1302 bool can_split_if(Node *n_ctrl);
1303
1304 bool _created_loop_node;
1305 public:
1306 void set_created_loop_node() { _created_loop_node = true; }
1307 bool created_loop_node() { return _created_loop_node; }
1308 void register_new_node( Node *n, Node *blk );
1309
1310 #ifdef ASSERT
1311 void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1312 #endif
1313
1314 #ifndef PRODUCT
1315 void dump( ) const;
1316 void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;
1317 void verify() const; // Major slow :-)
1318 void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1319 IdealLoopTree *get_loop_idx(Node* n) const {
1320 // Dead nodes have no loop, so return the top level loop instead
1321 return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1322 }
1323 // Print some stats
1324 static void print_statistics();
1325 static int _loop_invokes; // Count of PhaseIdealLoop invokes
1326 static int _loop_work; // Sum of PhaseIdealLoop x _unique
1327 #endif
1328 void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1329 };
1330
1331 // This kit may be used for making of a reserved copy of a loop before this loop
1332 // goes under non-reversible changes.
1333 //
1334 // Function create_reserve() creates a reserved copy (clone) of the loop.
1335 // The reserved copy is created by calling
1336 // PhaseIdealLoop::create_reserve_version_of_loop - see there how
1337 // the original and reserved loops are connected in the outer graph.
1338 // If create_reserve succeeded, it returns 'true' and _has_reserved is set to 'true'.
1339 //
1340 // By default the reserved copy (clone) of the loop is created as dead code - it is
1341 // dominated in the outer loop by this node chain:
1342 // intcon(1)->If->IfFalse->reserved_copy.
1343 // The original loop is dominated by the the same node chain but IfTrue projection:
1344 // intcon(0)->If->IfTrue->original_loop.
1345 //
1346 // In this implementation of CountedLoopReserveKit the ctor includes create_reserve()
1347 // and the dtor, checks _use_new value.
1348 // If _use_new == false, it "switches" control to reserved copy of the loop
|