296 // Interface from PhaseIdealLoop
297 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {
298 return clone_loop_predicates(old_entry, new_entry, clone_limit_check, this, &this->_igvn);
299 }
300
301 // Clone loop predicates to cloned loops (peeled, unswitched, split_if).
302 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry,
303 bool clone_limit_check,
304 PhaseIdealLoop* loop_phase,
305 PhaseIterGVN* igvn) {
306 #ifdef ASSERT
307 if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) {
308 if (new_entry != NULL)
309 new_entry->dump();
310 assert(false, "not IfTrue, IfFalse, Region or SafePoint");
311 }
312 #endif
313 // Search original predicates
314 Node* entry = old_entry;
315 ProjNode* limit_check_proj = NULL;
316 if (LoopLimitCheck) {
317 limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
318 if (limit_check_proj != NULL) {
319 entry = entry->in(0)->in(0);
320 }
321 }
322 if (UseLoopPredicate) {
323 ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
324 if (predicate_proj != NULL) { // right pattern that can be used by loop predication
325 // clone predicate
326 new_entry = clone_predicate(predicate_proj, new_entry,
327 Deoptimization::Reason_predicate,
328 loop_phase, igvn);
329 assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate");
330 if (TraceLoopPredicate) {
331 tty->print("Loop Predicate cloned: ");
332 debug_only( new_entry->in(0)->dump(); )
333 }
334 }
335 }
336 if (limit_check_proj != NULL && clone_limit_check) {
337 // Clone loop limit check last to insert it before loop.
338 // Don't clone a limit check which was already finalized
339 // for this counted loop (only one limit check is needed).
340 new_entry = clone_predicate(limit_check_proj, new_entry,
341 Deoptimization::Reason_loop_limit_check,
342 loop_phase, igvn);
343 assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check");
344 if (TraceLoopLimitCheck) {
345 tty->print("Loop Limit Check cloned: ");
346 debug_only( new_entry->in(0)->dump(); )
347 }
348 }
349 return new_entry;
350 }
351
352 //--------------------------skip_loop_predicates------------------------------
353 // Skip related predicates.
354 Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) {
355 Node* predicate = NULL;
356 if (LoopLimitCheck) {
357 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
358 if (predicate != NULL) {
359 entry = entry->in(0)->in(0);
360 }
361 }
362 if (UseLoopPredicate) {
363 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
364 if (predicate != NULL) { // right pattern that can be used by loop predication
365 IfNode* iff = entry->in(0)->as_If();
366 ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
367 Node* rgn = uncommon_proj->unique_ctrl_out();
368 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
369 entry = entry->in(0)->in(0);
370 while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
371 uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
372 if (uncommon_proj->unique_ctrl_out() != rgn)
373 break;
374 entry = entry->in(0)->in(0);
375 }
376 }
377 }
378 return entry;
379 }
380
381 //--------------------------find_predicate_insertion_point-------------------
382 // Find a good location to insert a predicate
383 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
384 if (start_c == NULL || !start_c->is_Proj())
385 return NULL;
386 if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {
387 return start_c->as_Proj();
388 }
389 return NULL;
390 }
391
392 //--------------------------find_predicate------------------------------------
393 // Find a predicate
394 Node* PhaseIdealLoop::find_predicate(Node* entry) {
395 Node* predicate = NULL;
396 if (LoopLimitCheck) {
397 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
398 if (predicate != NULL) { // right pattern that can be used by loop predication
399 return entry;
400 }
401 }
402 if (UseLoopPredicate) {
403 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
404 if (predicate != NULL) { // right pattern that can be used by loop predication
405 return entry;
406 }
407 }
408 return NULL;
409 }
410
411 //------------------------------Invariance-----------------------------------
412 // Helper class for loop_predication_impl to compute invariance on the fly and
413 // clone invariants.
414 class Invariance : public StackObj {
415 VectorSet _visited, _invariant;
416 Node_Stack _stack;
417 VectorSet _clone_visited;
418 Node_List _old_new; // map of old to new (clone)
419 IdealLoopTree* _lpt;
420 PhaseIdealLoop* _phase;
421
629 // as "max(scale*i + offset) u< a.length".
630 //
631 // There are two cases for max(scale*i + offset):
632 // (1) stride*scale > 0
633 // max(scale*i + offset) = scale*(limit-stride) + offset
634 // (2) stride*scale < 0
635 // max(scale*i + offset) = scale*init + offset
636 BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl,
637 int scale, Node* offset,
638 Node* init, Node* limit, Node* stride,
639 Node* range, bool upper) {
640 stringStream* predString = NULL;
641 if (TraceLoopPredicate) {
642 predString = new stringStream();
643 predString->print("rc_predicate ");
644 }
645
646 Node* max_idx_expr = init;
647 int stride_con = stride->get_int();
648 if ((stride_con > 0) == (scale > 0) == upper) {
649 if (LoopLimitCheck) {
650 // With LoopLimitCheck limit is not exact.
651 // Calculate exact limit here.
652 // Note, counted loop's test is '<' or '>'.
653 limit = exact_limit(loop);
654 max_idx_expr = new SubINode(limit, stride);
655 register_new_node(max_idx_expr, ctrl);
656 if (TraceLoopPredicate) predString->print("(limit - stride) ");
657 } else {
658 max_idx_expr = new SubINode(limit, stride);
659 register_new_node(max_idx_expr, ctrl);
660 if (TraceLoopPredicate) predString->print("(limit - stride) ");
661 }
662 } else {
663 if (TraceLoopPredicate) predString->print("init ");
664 }
665
666 if (scale != 1) {
667 ConNode* con_scale = _igvn.intcon(scale);
668 set_ctrl(con_scale, C->root());
669 max_idx_expr = new MulINode(max_idx_expr, con_scale);
670 register_new_node(max_idx_expr, ctrl);
671 if (TraceLoopPredicate) predString->print("* %d ", scale);
672 }
673
674 if (offset && (!offset->is_Con() || offset->get_int() != 0)){
675 max_idx_expr = new AddINode(max_idx_expr, offset);
676 register_new_node(max_idx_expr, ctrl);
677 if (TraceLoopPredicate)
678 if (offset->is_Con()) predString->print("+ %d ", offset->get_int());
679 else predString->print("+ offset ");
680 }
681
682 CmpUNode* cmp = new CmpUNode(max_idx_expr, range);
704
705 if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
706 // do nothing for infinite loops
707 return false;
708 }
709
710 CountedLoopNode *cl = NULL;
711 if (head->is_valid_counted_loop()) {
712 cl = head->as_CountedLoop();
713 // do nothing for iteration-splitted loops
714 if (!cl->is_normal_loop()) return false;
715 // Avoid RCE if Counted loop's test is '!='.
716 BoolTest::mask bt = cl->loopexit()->test_trip();
717 if (bt != BoolTest::lt && bt != BoolTest::gt)
718 cl = NULL;
719 }
720
721 Node* entry = head->in(LoopNode::EntryControl);
722 ProjNode *predicate_proj = NULL;
723 // Loop limit check predicate should be near the loop.
724 if (LoopLimitCheck) {
725 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
726 if (predicate_proj != NULL)
727 entry = predicate_proj->in(0)->in(0);
728 }
729
730 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
731 if (!predicate_proj) {
732 #ifndef PRODUCT
733 if (TraceLoopPredicate) {
734 tty->print("missing predicate:");
735 loop->dump_head();
736 head->dump(1);
737 }
738 #endif
739 return false;
740 }
741 ConNode* zero = _igvn.intcon(0);
742 set_ctrl(zero, C->root());
743
744 ResourceArea *area = Thread::current()->resource_area();
745 Invariance invar(area, loop);
746
747 // Create list of if-projs such that a newer proj dominates all older
748 // projs in the list, and they all dominate loop->tail()
749 Node_List if_proj_list(area);
|
296 // Interface from PhaseIdealLoop
297 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {
298 return clone_loop_predicates(old_entry, new_entry, clone_limit_check, this, &this->_igvn);
299 }
300
301 // Clone loop predicates to cloned loops (peeled, unswitched, split_if).
302 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry,
303 bool clone_limit_check,
304 PhaseIdealLoop* loop_phase,
305 PhaseIterGVN* igvn) {
306 #ifdef ASSERT
307 if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) {
308 if (new_entry != NULL)
309 new_entry->dump();
310 assert(false, "not IfTrue, IfFalse, Region or SafePoint");
311 }
312 #endif
313 // Search original predicates
314 Node* entry = old_entry;
315 ProjNode* limit_check_proj = NULL;
316 limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
317 if (limit_check_proj != NULL) {
318 entry = entry->in(0)->in(0);
319 }
320 if (UseLoopPredicate) {
321 ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
322 if (predicate_proj != NULL) { // right pattern that can be used by loop predication
323 // clone predicate
324 new_entry = clone_predicate(predicate_proj, new_entry,
325 Deoptimization::Reason_predicate,
326 loop_phase, igvn);
327 assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate");
328 if (TraceLoopPredicate) {
329 tty->print("Loop Predicate cloned: ");
330 debug_only( new_entry->in(0)->dump(); )
331 }
332 }
333 }
334 if (limit_check_proj != NULL && clone_limit_check) {
335 // Clone loop limit check last to insert it before loop.
336 // Don't clone a limit check which was already finalized
337 // for this counted loop (only one limit check is needed).
338 new_entry = clone_predicate(limit_check_proj, new_entry,
339 Deoptimization::Reason_loop_limit_check,
340 loop_phase, igvn);
341 assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check");
342 if (TraceLoopLimitCheck) {
343 tty->print("Loop Limit Check cloned: ");
344 debug_only( new_entry->in(0)->dump(); )
345 }
346 }
347 return new_entry;
348 }
349
350 //--------------------------skip_loop_predicates------------------------------
351 // Skip related predicates.
352 Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) {
353 Node* predicate = NULL;
354 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
355 if (predicate != NULL) {
356 entry = entry->in(0)->in(0);
357 }
358 if (UseLoopPredicate) {
359 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
360 if (predicate != NULL) { // right pattern that can be used by loop predication
361 IfNode* iff = entry->in(0)->as_If();
362 ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
363 Node* rgn = uncommon_proj->unique_ctrl_out();
364 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
365 entry = entry->in(0)->in(0);
366 while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
367 uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
368 if (uncommon_proj->unique_ctrl_out() != rgn)
369 break;
370 entry = entry->in(0)->in(0);
371 }
372 }
373 }
374 return entry;
375 }
376
377 //--------------------------find_predicate_insertion_point-------------------
378 // Find a good location to insert a predicate
379 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
380 if (start_c == NULL || !start_c->is_Proj())
381 return NULL;
382 if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {
383 return start_c->as_Proj();
384 }
385 return NULL;
386 }
387
388 //--------------------------find_predicate------------------------------------
389 // Find a predicate
390 Node* PhaseIdealLoop::find_predicate(Node* entry) {
391 Node* predicate = NULL;
392 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
393 if (predicate != NULL) { // right pattern that can be used by loop predication
394 return entry;
395 }
396 if (UseLoopPredicate) {
397 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
398 if (predicate != NULL) { // right pattern that can be used by loop predication
399 return entry;
400 }
401 }
402 return NULL;
403 }
404
405 //------------------------------Invariance-----------------------------------
406 // Helper class for loop_predication_impl to compute invariance on the fly and
407 // clone invariants.
408 class Invariance : public StackObj {
409 VectorSet _visited, _invariant;
410 Node_Stack _stack;
411 VectorSet _clone_visited;
412 Node_List _old_new; // map of old to new (clone)
413 IdealLoopTree* _lpt;
414 PhaseIdealLoop* _phase;
415
623 // as "max(scale*i + offset) u< a.length".
624 //
625 // There are two cases for max(scale*i + offset):
626 // (1) stride*scale > 0
627 // max(scale*i + offset) = scale*(limit-stride) + offset
628 // (2) stride*scale < 0
629 // max(scale*i + offset) = scale*init + offset
630 BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl,
631 int scale, Node* offset,
632 Node* init, Node* limit, Node* stride,
633 Node* range, bool upper) {
634 stringStream* predString = NULL;
635 if (TraceLoopPredicate) {
636 predString = new stringStream();
637 predString->print("rc_predicate ");
638 }
639
640 Node* max_idx_expr = init;
641 int stride_con = stride->get_int();
642 if ((stride_con > 0) == (scale > 0) == upper) {
643 // Limit is not exact.
644 // Calculate exact limit here.
645 // Note, counted loop's test is '<' or '>'.
646 limit = exact_limit(loop);
647 max_idx_expr = new SubINode(limit, stride);
648 register_new_node(max_idx_expr, ctrl);
649 if (TraceLoopPredicate) predString->print("(limit - stride) ");
650 } else {
651 if (TraceLoopPredicate) predString->print("init ");
652 }
653
654 if (scale != 1) {
655 ConNode* con_scale = _igvn.intcon(scale);
656 set_ctrl(con_scale, C->root());
657 max_idx_expr = new MulINode(max_idx_expr, con_scale);
658 register_new_node(max_idx_expr, ctrl);
659 if (TraceLoopPredicate) predString->print("* %d ", scale);
660 }
661
662 if (offset && (!offset->is_Con() || offset->get_int() != 0)){
663 max_idx_expr = new AddINode(max_idx_expr, offset);
664 register_new_node(max_idx_expr, ctrl);
665 if (TraceLoopPredicate)
666 if (offset->is_Con()) predString->print("+ %d ", offset->get_int());
667 else predString->print("+ offset ");
668 }
669
670 CmpUNode* cmp = new CmpUNode(max_idx_expr, range);
692
693 if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
694 // do nothing for infinite loops
695 return false;
696 }
697
698 CountedLoopNode *cl = NULL;
699 if (head->is_valid_counted_loop()) {
700 cl = head->as_CountedLoop();
701 // do nothing for iteration-splitted loops
702 if (!cl->is_normal_loop()) return false;
703 // Avoid RCE if Counted loop's test is '!='.
704 BoolTest::mask bt = cl->loopexit()->test_trip();
705 if (bt != BoolTest::lt && bt != BoolTest::gt)
706 cl = NULL;
707 }
708
709 Node* entry = head->in(LoopNode::EntryControl);
710 ProjNode *predicate_proj = NULL;
711 // Loop limit check predicate should be near the loop.
712 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
713 if (predicate_proj != NULL)
714 entry = predicate_proj->in(0)->in(0);
715 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
716 if (!predicate_proj) {
717 #ifndef PRODUCT
718 if (TraceLoopPredicate) {
719 tty->print("missing predicate:");
720 loop->dump_head();
721 head->dump(1);
722 }
723 #endif
724 return false;
725 }
726 ConNode* zero = _igvn.intcon(0);
727 set_ctrl(zero, C->root());
728
729 ResourceArea *area = Thread::current()->resource_area();
730 Invariance invar(area, loop);
731
732 // Create list of if-projs such that a newer proj dominates all older
733 // projs in the list, and they all dominate loop->tail()
734 Node_List if_proj_list(area);
|