24
25 #include "precompiled.hpp"
26 #include "opto/loopnode.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/callnode.hpp"
29 #include "opto/connode.hpp"
30 #include "opto/loopnode.hpp"
31 #include "opto/mulnode.hpp"
32 #include "opto/rootnode.hpp"
33 #include "opto/subnode.hpp"
34
35 /*
36 * The general idea of Loop Predication is to insert a predicate on the entry
37 * path to a loop, and raise a uncommon trap if the check of the condition fails.
38 * The condition checks are promoted from inside the loop body, and thus
39 * the checks inside the loop could be eliminated. Currently, loop predication
40 * optimization has been applied to remove array range check and loop invariant
41 * checks (such as null checks).
42 */
43
44 //-------------------------------is_uncommon_trap_proj----------------------------
45 // Return true if proj is the form of "proj->[region->..]call_uct"
46 bool PhaseIdealLoop::is_uncommon_trap_proj(ProjNode* proj, Deoptimization::DeoptReason reason) {
47 int path_limit = 10;
48 assert(proj, "invalid argument");
49 Node* out = proj;
50 for (int ct = 0; ct < path_limit; ct++) {
51 out = out->unique_ctrl_out();
52 if (out == NULL)
53 return false;
54 if (out->is_CallStaticJava()) {
55 int req = out->as_CallStaticJava()->uncommon_trap_request();
56 if (req != 0) {
57 Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
58 if (trap_reason == reason || reason == Deoptimization::Reason_none) {
59 return true;
60 }
61 }
62 return false; // don't do further after call
63 }
64 if (out->Opcode() != Op_Region)
65 return false;
66 }
67 return false;
68 }
69
70 //-------------------------------is_uncommon_trap_if_pattern-------------------------
71 // Return true for "if(test)-> proj -> ...
72 // |
73 // V
74 // other_proj->[region->..]call_uct"
75 //
76 // "must_reason_predicate" means the uct reason must be Reason_predicate
77 bool PhaseIdealLoop::is_uncommon_trap_if_pattern(ProjNode *proj, Deoptimization::DeoptReason reason) {
78 Node *in0 = proj->in(0);
79 if (!in0->is_If()) return false;
80 // Variation of a dead If node.
81 if (in0->outcnt() < 2) return false;
82 IfNode* iff = in0->as_If();
83
84 // we need "If(Conv2B(Opaque1(...)))" pattern for reason_predicate
85 if (reason != Deoptimization::Reason_none) {
86 if (iff->in(1)->Opcode() != Op_Conv2B ||
87 iff->in(1)->in(1)->Opcode() != Op_Opaque1) {
88 return false;
89 }
90 }
91
92 ProjNode* other_proj = iff->proj_out(1-proj->_con)->as_Proj();
93 if (is_uncommon_trap_proj(other_proj, reason)) {
94 assert(reason == Deoptimization::Reason_none ||
95 Compile::current()->is_predicate_opaq(iff->in(1)->in(1)), "should be on the list");
96 return true;
97 }
98 return false;
99 }
100
101 //-------------------------------register_control-------------------------
102 void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {
103 assert(n->is_CFG(), "must be control node");
104 _igvn.register_new_node_with_optimizer(n);
105 loop->_body.push(n);
106 set_loop(n, loop);
107 // When called from beautify_loops() idom is not constructed yet.
108 if (_idom != NULL) {
109 set_idom(n, pred, dom_depth(pred));
110 }
111 }
112
113 //------------------------------create_new_if_for_predicate------------------------
114 // create a new if above the uct_if_pattern for the predicate to be promoted.
115 //
116 // before after
117 // ---------- ----------
118 // ctrl ctrl
119 // | |
120 // | |
130 // rgn loop | iff
131 // | | / \
132 // | | / \
133 // v | v v
134 // uncommon_trap | uncommon_proj cont_proj
135 // \ \ | |
136 // \ \ | |
137 // v v v v
138 // rgn loop
139 // |
140 // |
141 // v
142 // uncommon_trap
143 //
144 //
145 // We will create a region to guard the uct call if there is no one there.
146 // The true projecttion (if_cont) of the new_iff is returned.
147 // This code is also used to clone predicates to clonned loops.
148 ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
149 Deoptimization::DeoptReason reason) {
150 assert(is_uncommon_trap_if_pattern(cont_proj, reason), "must be a uct if pattern!");
151 IfNode* iff = cont_proj->in(0)->as_If();
152
153 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
154 Node *rgn = uncommon_proj->unique_ctrl_out();
155 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
156
157 uint proj_index = 1; // region's edge corresponding to uncommon_proj
158 if (!rgn->is_Region()) { // create a region to guard the call
159 assert(rgn->is_Call(), "must be call uct");
160 CallNode* call = rgn->as_Call();
161 IdealLoopTree* loop = get_loop(call);
162 rgn = new (C) RegionNode(1);
163 rgn->add_req(uncommon_proj);
164 register_control(rgn, loop, uncommon_proj);
165 _igvn.hash_delete(call);
166 call->set_req(0, rgn);
167 // When called from beautify_loops() idom is not constructed yet.
168 if (_idom != NULL) {
169 set_idom(call, rgn, dom_depth(rgn));
170 }
218 }
219 }
220 assert(!has_phi || rgn->req() > 3, "no phis when region is created");
221
222 if (new_entry == NULL) {
223 // Attach if_cont to iff
224 _igvn.hash_delete(iff);
225 iff->set_req(0, if_cont);
226 if (_idom != NULL) {
227 set_idom(iff, if_cont, dom_depth(iff));
228 }
229 }
230 return if_cont->as_Proj();
231 }
232
233 //------------------------------create_new_if_for_predicate------------------------
234 // Create a new if below new_entry for the predicate to be cloned (IGVN optimization)
235 ProjNode* PhaseIterGVN::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
236 Deoptimization::DeoptReason reason) {
237 assert(new_entry != 0, "only used for clone predicate");
238 assert(PhaseIdealLoop::is_uncommon_trap_if_pattern(cont_proj, reason), "must be a uct if pattern!");
239 IfNode* iff = cont_proj->in(0)->as_If();
240
241 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
242 Node *rgn = uncommon_proj->unique_ctrl_out();
243 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
244
245 uint proj_index = 1; // region's edge corresponding to uncommon_proj
246 if (!rgn->is_Region()) { // create a region to guard the call
247 assert(rgn->is_Call(), "must be call uct");
248 CallNode* call = rgn->as_Call();
249 rgn = new (C) RegionNode(1);
250 register_new_node_with_optimizer(rgn);
251 rgn->add_req(uncommon_proj);
252 hash_delete(call);
253 call->set_req(0, rgn);
254 } else {
255 // Find region's edge corresponding to uncommon_proj
256 for (; proj_index < rgn->req(); proj_index++)
257 if (rgn->in(proj_index) == uncommon_proj) break;
258 assert(proj_index < rgn->req(), "sanity");
405 ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
406 Node* rgn = uncommon_proj->unique_ctrl_out();
407 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
408 entry = entry->in(0)->in(0);
409 while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
410 uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
411 if (uncommon_proj->unique_ctrl_out() != rgn)
412 break;
413 entry = entry->in(0)->in(0);
414 }
415 }
416 }
417 return entry;
418 }
419
420 //--------------------------find_predicate_insertion_point-------------------
421 // Find a good location to insert a predicate
422 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
423 if (start_c == NULL || !start_c->is_Proj())
424 return NULL;
425 if (is_uncommon_trap_if_pattern(start_c->as_Proj(), reason)) {
426 return start_c->as_Proj();
427 }
428 return NULL;
429 }
430
431 //--------------------------find_predicate------------------------------------
432 // Find a predicate
433 Node* PhaseIdealLoop::find_predicate(Node* entry) {
434 Node* predicate = NULL;
435 if (LoopLimitCheck) {
436 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
437 if (predicate != NULL) { // right pattern that can be used by loop predication
438 return entry;
439 }
440 }
441 if (UseLoopPredicate) {
442 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
443 if (predicate != NULL) { // right pattern that can be used by loop predication
444 return entry;
445 }
756 // projs in the list, and they all dominate loop->tail()
757 Node_List if_proj_list(area);
758 Node *current_proj = loop->tail(); //start from tail
759 while (current_proj != head) {
760 if (loop == get_loop(current_proj) && // still in the loop ?
761 current_proj->is_Proj() && // is a projection ?
762 current_proj->in(0)->Opcode() == Op_If) { // is a if projection ?
763 if_proj_list.push(current_proj);
764 }
765 current_proj = idom(current_proj);
766 }
767
768 bool hoisted = false; // true if at least one proj is promoted
769 while (if_proj_list.size() > 0) {
770 // Following are changed to nonnull when a predicate can be hoisted
771 ProjNode* new_predicate_proj = NULL;
772
773 ProjNode* proj = if_proj_list.pop()->as_Proj();
774 IfNode* iff = proj->in(0)->as_If();
775
776 if (!is_uncommon_trap_if_pattern(proj, Deoptimization::Reason_none)) {
777 if (loop->is_loop_exit(iff)) {
778 // stop processing the remaining projs in the list because the execution of them
779 // depends on the condition of "iff" (iff->in(1)).
780 break;
781 } else {
782 // Both arms are inside the loop. There are two cases:
783 // (1) there is one backward branch. In this case, any remaining proj
784 // in the if_proj list post-dominates "iff". So, the condition of "iff"
785 // does not determine the execution the remining projs directly, and we
786 // can safely continue.
787 // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj"
788 // does not dominate loop->tail(), so it can not be in the if_proj list.
789 continue;
790 }
791 }
792
793 Node* test = iff->in(1);
794 if (!test->is_Bool()){ //Conv2B, ...
795 continue;
796 }
|
24
25 #include "precompiled.hpp"
26 #include "opto/loopnode.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/callnode.hpp"
29 #include "opto/connode.hpp"
30 #include "opto/loopnode.hpp"
31 #include "opto/mulnode.hpp"
32 #include "opto/rootnode.hpp"
33 #include "opto/subnode.hpp"
34
35 /*
36 * The general idea of Loop Predication is to insert a predicate on the entry
37 * path to a loop, and raise a uncommon trap if the check of the condition fails.
38 * The condition checks are promoted from inside the loop body, and thus
39 * the checks inside the loop could be eliminated. Currently, loop predication
40 * optimization has been applied to remove array range check and loop invariant
41 * checks (such as null checks).
42 */
43
44 //-------------------------------register_control-------------------------
45 void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {
46 assert(n->is_CFG(), "must be control node");
47 _igvn.register_new_node_with_optimizer(n);
48 loop->_body.push(n);
49 set_loop(n, loop);
50 // When called from beautify_loops() idom is not constructed yet.
51 if (_idom != NULL) {
52 set_idom(n, pred, dom_depth(pred));
53 }
54 }
55
56 //------------------------------create_new_if_for_predicate------------------------
57 // create a new if above the uct_if_pattern for the predicate to be promoted.
58 //
59 // before after
60 // ---------- ----------
61 // ctrl ctrl
62 // | |
63 // | |
73 // rgn loop | iff
74 // | | / \
75 // | | / \
76 // v | v v
77 // uncommon_trap | uncommon_proj cont_proj
78 // \ \ | |
79 // \ \ | |
80 // v v v v
81 // rgn loop
82 // |
83 // |
84 // v
85 // uncommon_trap
86 //
87 //
88 // We will create a region to guard the uct call if there is no one there.
89 // The true projecttion (if_cont) of the new_iff is returned.
90 // This code is also used to clone predicates to clonned loops.
91 ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
92 Deoptimization::DeoptReason reason) {
93 assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!");
94 IfNode* iff = cont_proj->in(0)->as_If();
95
96 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
97 Node *rgn = uncommon_proj->unique_ctrl_out();
98 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
99
100 uint proj_index = 1; // region's edge corresponding to uncommon_proj
101 if (!rgn->is_Region()) { // create a region to guard the call
102 assert(rgn->is_Call(), "must be call uct");
103 CallNode* call = rgn->as_Call();
104 IdealLoopTree* loop = get_loop(call);
105 rgn = new (C) RegionNode(1);
106 rgn->add_req(uncommon_proj);
107 register_control(rgn, loop, uncommon_proj);
108 _igvn.hash_delete(call);
109 call->set_req(0, rgn);
110 // When called from beautify_loops() idom is not constructed yet.
111 if (_idom != NULL) {
112 set_idom(call, rgn, dom_depth(rgn));
113 }
161 }
162 }
163 assert(!has_phi || rgn->req() > 3, "no phis when region is created");
164
165 if (new_entry == NULL) {
166 // Attach if_cont to iff
167 _igvn.hash_delete(iff);
168 iff->set_req(0, if_cont);
169 if (_idom != NULL) {
170 set_idom(iff, if_cont, dom_depth(iff));
171 }
172 }
173 return if_cont->as_Proj();
174 }
175
176 //------------------------------create_new_if_for_predicate------------------------
177 // Create a new if below new_entry for the predicate to be cloned (IGVN optimization)
178 ProjNode* PhaseIterGVN::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
179 Deoptimization::DeoptReason reason) {
180 assert(new_entry != 0, "only used for clone predicate");
181 assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!");
182 IfNode* iff = cont_proj->in(0)->as_If();
183
184 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
185 Node *rgn = uncommon_proj->unique_ctrl_out();
186 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
187
188 uint proj_index = 1; // region's edge corresponding to uncommon_proj
189 if (!rgn->is_Region()) { // create a region to guard the call
190 assert(rgn->is_Call(), "must be call uct");
191 CallNode* call = rgn->as_Call();
192 rgn = new (C) RegionNode(1);
193 register_new_node_with_optimizer(rgn);
194 rgn->add_req(uncommon_proj);
195 hash_delete(call);
196 call->set_req(0, rgn);
197 } else {
198 // Find region's edge corresponding to uncommon_proj
199 for (; proj_index < rgn->req(); proj_index++)
200 if (rgn->in(proj_index) == uncommon_proj) break;
201 assert(proj_index < rgn->req(), "sanity");
348 ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
349 Node* rgn = uncommon_proj->unique_ctrl_out();
350 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
351 entry = entry->in(0)->in(0);
352 while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
353 uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
354 if (uncommon_proj->unique_ctrl_out() != rgn)
355 break;
356 entry = entry->in(0)->in(0);
357 }
358 }
359 }
360 return entry;
361 }
362
363 //--------------------------find_predicate_insertion_point-------------------
364 // Find a good location to insert a predicate
365 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
366 if (start_c == NULL || !start_c->is_Proj())
367 return NULL;
368 if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {
369 return start_c->as_Proj();
370 }
371 return NULL;
372 }
373
374 //--------------------------find_predicate------------------------------------
375 // Find a predicate
376 Node* PhaseIdealLoop::find_predicate(Node* entry) {
377 Node* predicate = NULL;
378 if (LoopLimitCheck) {
379 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
380 if (predicate != NULL) { // right pattern that can be used by loop predication
381 return entry;
382 }
383 }
384 if (UseLoopPredicate) {
385 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
386 if (predicate != NULL) { // right pattern that can be used by loop predication
387 return entry;
388 }
699 // projs in the list, and they all dominate loop->tail()
700 Node_List if_proj_list(area);
701 Node *current_proj = loop->tail(); //start from tail
702 while (current_proj != head) {
703 if (loop == get_loop(current_proj) && // still in the loop ?
704 current_proj->is_Proj() && // is a projection ?
705 current_proj->in(0)->Opcode() == Op_If) { // is a if projection ?
706 if_proj_list.push(current_proj);
707 }
708 current_proj = idom(current_proj);
709 }
710
711 bool hoisted = false; // true if at least one proj is promoted
712 while (if_proj_list.size() > 0) {
713 // Following are changed to nonnull when a predicate can be hoisted
714 ProjNode* new_predicate_proj = NULL;
715
716 ProjNode* proj = if_proj_list.pop()->as_Proj();
717 IfNode* iff = proj->in(0)->as_If();
718
719 if (!proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {
720 if (loop->is_loop_exit(iff)) {
721 // stop processing the remaining projs in the list because the execution of them
722 // depends on the condition of "iff" (iff->in(1)).
723 break;
724 } else {
725 // Both arms are inside the loop. There are two cases:
726 // (1) there is one backward branch. In this case, any remaining proj
727 // in the if_proj list post-dominates "iff". So, the condition of "iff"
728 // does not determine the execution the remining projs directly, and we
729 // can safely continue.
730 // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj"
731 // does not dominate loop->tail(), so it can not be in the if_proj list.
732 continue;
733 }
734 }
735
736 Node* test = iff->in(1);
737 if (!test->is_Bool()){ //Conv2B, ...
738 continue;
739 }
|