10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "compiler/compileLog.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/callnode.hpp"
30 #include "opto/connode.hpp"
31 #include "opto/convertnode.hpp"
32 #include "opto/divnode.hpp"
33 #include "opto/loopnode.hpp"
34 #include "opto/mulnode.hpp"
35 #include "opto/movenode.hpp"
36 #include "opto/opaquenode.hpp"
37 #include "opto/rootnode.hpp"
38 #include "opto/runtime.hpp"
39 #include "opto/subnode.hpp"
40
41 //------------------------------is_loop_exit-----------------------------------
42 // Given an IfNode, return the loop-exiting projection or NULL if both
43 // arms remain in the loop.
44 Node *IdealLoopTree::is_loop_exit(Node *iff) const {
45 if( iff->outcnt() != 2 ) return NULL; // Ignore partially dead tests
46 PhaseIdealLoop *phase = _phase;
47 // Test is an IfNode, has 2 projections. If BOTH are in the loop
48 // we need loop unswitching instead of peeling.
49 if( !is_member(phase->get_loop( iff->raw_out(0) )) )
868 for( uint i = 1; i < n->req(); i++ ) {
869 Node *g = clone_up_backedge_goo( back_ctrl, preheader_ctrl, n->in(i), visited, clones );
870 if( g != n->in(i) ) {
871 if( !x ) {
872 assert(clones.find(n->_idx) == NULL, "dead loop");
873 x = n->clone();
874 clones.push(x, n->_idx);
875 }
876 x->set_req(i, g);
877 }
878 }
879 if( x ) { // x can legally float to pre-header location
880 register_new_node( x, preheader_ctrl );
881 return x;
882 } else { // raise n to cover LCA of uses
883 set_ctrl( n, find_non_split_ctrl(back_ctrl->in(0)) );
884 }
885 return n;
886 }
887
888 //------------------------------insert_pre_post_loops--------------------------
889 // Insert pre and post loops. If peel_only is set, the pre-loop can not have
890 // more iterations added. It acts as a 'peel' only, no lower-bound RCE, no
891 // alignment. Useful to unroll loops that do no array accesses.
892 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
893
894 #ifndef PRODUCT
895 if (TraceLoopOpts) {
896 if (peel_only)
897 tty->print("PeelMainPost ");
898 else
899 tty->print("PreMainPost ");
900 loop->dump_head();
901 }
902 #endif
903 C->set_major_progress();
904
905 // Find common pieces of the loop being guarded with pre & post loops
906 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
907 assert( main_head->is_normal_loop(), "" );
1063 _igvn.hash_delete( main_head );
1064 main_head->set_req(LoopNode::EntryControl, min_taken);
1065 set_idom(main_head, min_taken, dd_main_head);
1066
1067 visited.Clear();
1068 clones.clear();
1069 // Step B3: Make the fall-in values to the main-loop come from the
1070 // fall-out values of the pre-loop.
1071 for (DUIterator_Fast i2max, i2 = main_head->fast_outs(i2max); i2 < i2max; i2++) {
1072 Node* main_phi = main_head->fast_out(i2);
1073 if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0 ) {
1074 Node *pre_phi = old_new[main_phi->_idx];
1075 Node *fallpre = clone_up_backedge_goo(pre_head->back_control(),
1076 main_head->init_control(),
1077 pre_phi->in(LoopNode::LoopBackControl),
1078 visited, clones);
1079 _igvn.hash_delete(main_phi);
1080 main_phi->set_req( LoopNode::EntryControl, fallpre );
1081 }
1082 }
1083
1084 // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1085 // RCE and alignment may change this later.
1086 Node *cmp_end = pre_end->cmp_node();
1087 assert( cmp_end->in(2) == limit, "" );
1088 Node *pre_limit = new AddINode( init, stride );
1089
1090 // Save the original loop limit in this Opaque1 node for
1091 // use by range check elimination.
1092 Node *pre_opaq = new Opaque1Node(C, pre_limit, limit);
1093
1094 register_new_node( pre_limit, pre_head->in(0) );
1095 register_new_node( pre_opaq , pre_head->in(0) );
1096
1097 // Since no other users of pre-loop compare, I can hack limit directly
1098 assert( cmp_end->outcnt() == 1, "no other users" );
1099 _igvn.hash_delete(cmp_end);
1100 cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1101
1102 // Special case for not-equal loop bounds:
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "compiler/compileLog.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/callnode.hpp"
30 #include "opto/castnode.hpp"
31 #include "opto/connode.hpp"
32 #include "opto/convertnode.hpp"
33 #include "opto/divnode.hpp"
34 #include "opto/loopnode.hpp"
35 #include "opto/mulnode.hpp"
36 #include "opto/movenode.hpp"
37 #include "opto/opaquenode.hpp"
38 #include "opto/rootnode.hpp"
39 #include "opto/runtime.hpp"
40 #include "opto/subnode.hpp"
41
42 //------------------------------is_loop_exit-----------------------------------
43 // Given an IfNode, return the loop-exiting projection or NULL if both
44 // arms remain in the loop.
45 Node *IdealLoopTree::is_loop_exit(Node *iff) const {
46 if( iff->outcnt() != 2 ) return NULL; // Ignore partially dead tests
47 PhaseIdealLoop *phase = _phase;
48 // Test is an IfNode, has 2 projections. If BOTH are in the loop
49 // we need loop unswitching instead of peeling.
50 if( !is_member(phase->get_loop( iff->raw_out(0) )) )
869 for( uint i = 1; i < n->req(); i++ ) {
870 Node *g = clone_up_backedge_goo( back_ctrl, preheader_ctrl, n->in(i), visited, clones );
871 if( g != n->in(i) ) {
872 if( !x ) {
873 assert(clones.find(n->_idx) == NULL, "dead loop");
874 x = n->clone();
875 clones.push(x, n->_idx);
876 }
877 x->set_req(i, g);
878 }
879 }
880 if( x ) { // x can legally float to pre-header location
881 register_new_node( x, preheader_ctrl );
882 return x;
883 } else { // raise n to cover LCA of uses
884 set_ctrl( n, find_non_split_ctrl(back_ctrl->in(0)) );
885 }
886 return n;
887 }
888
889 bool PhaseIdealLoop::insert_castii_before_loop(Node* incr, Node* ctrl, Node* loop) {
890 Node* castii = new CastIINode(incr, TypeInt::INT, true, true);
891 castii->set_req(0, ctrl);
892 castii = _igvn.transform(castii);
893 assert(castii->Opcode() == Op_CastII, "required CastII cannot go away");
894 for (DUIterator_Fast imax, i = incr->fast_outs(imax); i < imax; i++) {
895 Node* n = incr->fast_out(i);
896 if (n->is_Phi() && n->in(0) == loop) {
897 int nrep = n->replace_edge(incr, castii);
898 return true;
899 }
900 }
901 return false;
902 }
903
904 //------------------------------insert_pre_post_loops--------------------------
905 // Insert pre and post loops. If peel_only is set, the pre-loop can not have
906 // more iterations added. It acts as a 'peel' only, no lower-bound RCE, no
907 // alignment. Useful to unroll loops that do no array accesses.
908 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
909
910 #ifndef PRODUCT
911 if (TraceLoopOpts) {
912 if (peel_only)
913 tty->print("PeelMainPost ");
914 else
915 tty->print("PreMainPost ");
916 loop->dump_head();
917 }
918 #endif
919 C->set_major_progress();
920
921 // Find common pieces of the loop being guarded with pre & post loops
922 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
923 assert( main_head->is_normal_loop(), "" );
1079 _igvn.hash_delete( main_head );
1080 main_head->set_req(LoopNode::EntryControl, min_taken);
1081 set_idom(main_head, min_taken, dd_main_head);
1082
1083 visited.Clear();
1084 clones.clear();
1085 // Step B3: Make the fall-in values to the main-loop come from the
1086 // fall-out values of the pre-loop.
1087 for (DUIterator_Fast i2max, i2 = main_head->fast_outs(i2max); i2 < i2max; i2++) {
1088 Node* main_phi = main_head->fast_out(i2);
1089 if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0 ) {
1090 Node *pre_phi = old_new[main_phi->_idx];
1091 Node *fallpre = clone_up_backedge_goo(pre_head->back_control(),
1092 main_head->init_control(),
1093 pre_phi->in(LoopNode::LoopBackControl),
1094 visited, clones);
1095 _igvn.hash_delete(main_phi);
1096 main_phi->set_req( LoopNode::EntryControl, fallpre );
1097 }
1098 }
1099
1100 // Nodes inside the loop may be control dependent on a predicate
1101 // that was moved before the preloop. If the back branch of the main
1102 // or post loops becomes dead, those nodes won't be dependent on the
1103 // test that guards that loop nest anymore which could lead to an
1104 // incorrect array access because it executes independently of the
1105 // test that was guarding the loop nest. We add a special CastII on
1106 // the if branch that enters the loop, between the input induction
1107 // variable value and the induction variable Phi to preserve correct
1108 // dependencies.
1109
1110 // CastII for the post loop:
1111 bool inserted = insert_castii_before_loop(zer_opaq->in(1), zer_taken, post_head);
1112 assert(inserted, "no castII inserted");
1113
1114 // CastII for the main loop:
1115 inserted = insert_castii_before_loop(pre_incr, min_taken, main_head);
1116 assert(inserted, "no castII inserted");
1117
1118 // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1119 // RCE and alignment may change this later.
1120 Node *cmp_end = pre_end->cmp_node();
1121 assert( cmp_end->in(2) == limit, "" );
1122 Node *pre_limit = new AddINode( init, stride );
1123
1124 // Save the original loop limit in this Opaque1 node for
1125 // use by range check elimination.
1126 Node *pre_opaq = new Opaque1Node(C, pre_limit, limit);
1127
1128 register_new_node( pre_limit, pre_head->in(0) );
1129 register_new_node( pre_opaq , pre_head->in(0) );
1130
1131 // Since no other users of pre-loop compare, I can hack limit directly
1132 assert( cmp_end->outcnt() == 1, "no other users" );
1133 _igvn.hash_delete(cmp_end);
1134 cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1135
1136 // Special case for not-equal loop bounds:
|