311 } else {
312 assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int");
313 }
314
315 // If the condition is inverted and we will be rolling
316 // through MININT to MAXINT, then bail out.
317 if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!
318 // Odd stride
319 bt == BoolTest::ne && stride_con != 1 && stride_con != -1 ||
320 // Count down loop rolls through MAXINT
321 (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 ||
322 // Count up loop rolls through MININT
323 (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0) {
324 return false; // Bail out
325 }
326
327 const TypeInt* init_t = gvn->type(init_trip)->is_int();
328 const TypeInt* limit_t = gvn->type(limit)->is_int();
329
330 if (stride_con > 0) {
331 long init_p = (long)init_t->_lo + stride_con;
332 if (init_p > (long)max_jint || init_p > (long)limit_t->_hi)
333 return false; // cyclic loop or this loop trips only once
334 } else {
335 long init_p = (long)init_t->_hi + stride_con;
336 if (init_p < (long)min_jint || init_p < (long)limit_t->_lo)
337 return false; // cyclic loop or this loop trips only once
338 }
339
340 // =================================================
341 // ---- SUCCESS! Found A Trip-Counted Loop! -----
342 //
343 assert(x->Opcode() == Op_Loop, "regular loops only");
344 C->print_method("Before CountedLoop", 3);
345
346 Node *hook = new (C) Node(6);
347
348 if (LoopLimitCheck) {
349
350 // ===================================================
351 // Generate loop limit check to avoid integer overflow
352 // in cases like next (cyclic loops):
353 //
354 // for (i=0; i <= max_jint; i++) {}
355 // for (i=0; i < max_jint; i+=2) {}
356 //
699
700 //----------------------exact_limit-------------------------------------------
701 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
702 assert(loop->_head->is_CountedLoop(), "");
703 CountedLoopNode *cl = loop->_head->as_CountedLoop();
704 assert(cl->is_valid_counted_loop(), "");
705
706 if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 ||
707 cl->limit()->Opcode() == Op_LoopLimit) {
708 // Old code has exact limit (it could be incorrect in case of int overflow).
709 // Loop limit is exact with stride == 1. And loop may already have exact limit.
710 return cl->limit();
711 }
712 Node *limit = NULL;
713 #ifdef ASSERT
714 BoolTest::mask bt = cl->loopexit()->test_trip();
715 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
716 #endif
717 if (cl->has_exact_trip_count()) {
718 // Simple case: loop has constant boundaries.
719 // Use longs to avoid integer overflow.
720 int stride_con = cl->stride_con();
721 long init_con = cl->init_trip()->get_int();
722 long limit_con = cl->limit()->get_int();
723 julong trip_cnt = cl->trip_count();
724 long final_con = init_con + trip_cnt*stride_con;
725 int final_int = (int)final_con;
726 // The final value should be in integer range since the loop
727 // is counted and the limit was checked for overflow.
728 assert(final_con == (long)final_int, "final value should be integer");
729 limit = _igvn.intcon(final_int);
730 } else {
731 // Create new LoopLimit node to get exact limit (final iv value).
732 limit = new (C) LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride());
733 register_new_node(limit, cl->in(LoopNode::EntryControl));
734 }
735 assert(limit != NULL, "sanity");
736 return limit;
737 }
738
739 //------------------------------Ideal------------------------------------------
740 // Return a node which is more "ideal" than the current node.
741 // Attempt to convert into a counted-loop.
742 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
743 if (!can_be_counted_loop(phase)) {
744 phase->C->set_major_progress();
745 }
746 return RegionNode::Ideal(phase, can_reshape);
747 }
748
773 int CountedLoopEndNode::stride_con() const {
774 return stride()->bottom_type()->is_int()->get_con();
775 }
776
777 //=============================================================================
778 //------------------------------Value-----------------------------------------
779 const Type *LoopLimitNode::Value( PhaseTransform *phase ) const {
780 const Type* init_t = phase->type(in(Init));
781 const Type* limit_t = phase->type(in(Limit));
782 const Type* stride_t = phase->type(in(Stride));
783 // Either input is TOP ==> the result is TOP
784 if (init_t == Type::TOP) return Type::TOP;
785 if (limit_t == Type::TOP) return Type::TOP;
786 if (stride_t == Type::TOP) return Type::TOP;
787
788 int stride_con = stride_t->is_int()->get_con();
789 if (stride_con == 1)
790 return NULL; // Identity
791
792 if (init_t->is_int()->is_con() && limit_t->is_int()->is_con()) {
793 // Use longs to avoid integer overflow.
794 long init_con = init_t->is_int()->get_con();
795 long limit_con = limit_t->is_int()->get_con();
796 int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
797 long trip_count = (limit_con - init_con + stride_m)/stride_con;
798 long final_con = init_con + stride_con*trip_count;
799 int final_int = (int)final_con;
800 // The final value should be in integer range since the loop
801 // is counted and the limit was checked for overflow.
802 assert(final_con == (long)final_int, "final value should be integer");
803 return TypeInt::make(final_int);
804 }
805
806 return bottom_type(); // TypeInt::INT
807 }
808
809 //------------------------------Ideal------------------------------------------
810 // Return a node which is more "ideal" than the current node.
811 Node *LoopLimitNode::Ideal(PhaseGVN *phase, bool can_reshape) {
812 if (phase->type(in(Init)) == Type::TOP ||
813 phase->type(in(Limit)) == Type::TOP ||
814 phase->type(in(Stride)) == Type::TOP)
815 return NULL; // Dead
816
817 int stride_con = phase->type(in(Stride))->is_int()->get_con();
818 if (stride_con == 1)
819 return NULL; // Identity
820
821 if (in(Init)->is_Con() && in(Limit)->is_Con())
822 return NULL; // Value
823
824 // Delay following optimizations until all loop optimizations
825 // done to keep Ideal graph simple.
826 if (!can_reshape || phase->C->major_progress())
827 return NULL;
828
829 const TypeInt* init_t = phase->type(in(Init) )->is_int();
830 const TypeInt* limit_t = phase->type(in(Limit))->is_int();
831 int stride_p;
832 long lim, ini;
833 julong max;
834 if (stride_con > 0) {
835 stride_p = stride_con;
836 lim = limit_t->_hi;
837 ini = init_t->_lo;
838 max = (julong)max_jint;
839 } else {
840 stride_p = -stride_con;
841 lim = init_t->_hi;
842 ini = limit_t->_lo;
843 max = (julong)min_jint;
844 }
845 julong range = lim - ini + stride_p;
846 if (range <= max) {
847 // Convert to integer expression if it is not overflow.
848 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
849 Node *range = phase->transform(new (phase->C) SubINode(in(Limit), in(Init)));
850 Node *bias = phase->transform(new (phase->C) AddINode(range, stride_m));
851 Node *trip = phase->transform(new (phase->C) DivINode(0, bias, in(Stride)));
852 Node *span = phase->transform(new (phase->C) MulINode(trip, in(Stride)));
|
311 } else {
312 assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int");
313 }
314
315 // If the condition is inverted and we will be rolling
316 // through MININT to MAXINT, then bail out.
317 if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!
318 // Odd stride
319 bt == BoolTest::ne && stride_con != 1 && stride_con != -1 ||
320 // Count down loop rolls through MAXINT
321 (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 ||
322 // Count up loop rolls through MININT
323 (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0) {
324 return false; // Bail out
325 }
326
327 const TypeInt* init_t = gvn->type(init_trip)->is_int();
328 const TypeInt* limit_t = gvn->type(limit)->is_int();
329
330 if (stride_con > 0) {
331 jlong init_p = (jlong)init_t->_lo + stride_con;
332 if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
333 return false; // cyclic loop or this loop trips only once
334 } else {
335 jlong init_p = (jlong)init_t->_hi + stride_con;
336 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
337 return false; // cyclic loop or this loop trips only once
338 }
339
340 // =================================================
341 // ---- SUCCESS! Found A Trip-Counted Loop! -----
342 //
343 assert(x->Opcode() == Op_Loop, "regular loops only");
344 C->print_method("Before CountedLoop", 3);
345
346 Node *hook = new (C) Node(6);
347
348 if (LoopLimitCheck) {
349
350 // ===================================================
351 // Generate loop limit check to avoid integer overflow
352 // in cases like next (cyclic loops):
353 //
354 // for (i=0; i <= max_jint; i++) {}
355 // for (i=0; i < max_jint; i+=2) {}
356 //
699
700 //----------------------exact_limit-------------------------------------------
701 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
702 assert(loop->_head->is_CountedLoop(), "");
703 CountedLoopNode *cl = loop->_head->as_CountedLoop();
704 assert(cl->is_valid_counted_loop(), "");
705
706 if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 ||
707 cl->limit()->Opcode() == Op_LoopLimit) {
708 // Old code has exact limit (it could be incorrect in case of int overflow).
709 // Loop limit is exact with stride == 1. And loop may already have exact limit.
710 return cl->limit();
711 }
712 Node *limit = NULL;
713 #ifdef ASSERT
714 BoolTest::mask bt = cl->loopexit()->test_trip();
715 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
716 #endif
717 if (cl->has_exact_trip_count()) {
718 // Simple case: loop has constant boundaries.
719 // Use jlongs to avoid integer overflow.
720 int stride_con = cl->stride_con();
721 jlong init_con = cl->init_trip()->get_int();
722 jlong limit_con = cl->limit()->get_int();
723 julong trip_cnt = cl->trip_count();
724 jlong final_con = init_con + trip_cnt*stride_con;
725 int final_int = (int)final_con;
726 // The final value should be in integer range since the loop
727 // is counted and the limit was checked for overflow.
728 assert(final_con == (jlong)final_int, "final value should be integer");
729 limit = _igvn.intcon(final_int);
730 } else {
731 // Create new LoopLimit node to get exact limit (final iv value).
732 limit = new (C) LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride());
733 register_new_node(limit, cl->in(LoopNode::EntryControl));
734 }
735 assert(limit != NULL, "sanity");
736 return limit;
737 }
738
739 //------------------------------Ideal------------------------------------------
740 // Return a node which is more "ideal" than the current node.
741 // Attempt to convert into a counted-loop.
742 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
743 if (!can_be_counted_loop(phase)) {
744 phase->C->set_major_progress();
745 }
746 return RegionNode::Ideal(phase, can_reshape);
747 }
748
773 int CountedLoopEndNode::stride_con() const {
774 return stride()->bottom_type()->is_int()->get_con();
775 }
776
777 //=============================================================================
778 //------------------------------Value-----------------------------------------
779 const Type *LoopLimitNode::Value( PhaseTransform *phase ) const {
780 const Type* init_t = phase->type(in(Init));
781 const Type* limit_t = phase->type(in(Limit));
782 const Type* stride_t = phase->type(in(Stride));
783 // Either input is TOP ==> the result is TOP
784 if (init_t == Type::TOP) return Type::TOP;
785 if (limit_t == Type::TOP) return Type::TOP;
786 if (stride_t == Type::TOP) return Type::TOP;
787
788 int stride_con = stride_t->is_int()->get_con();
789 if (stride_con == 1)
790 return NULL; // Identity
791
792 if (init_t->is_int()->is_con() && limit_t->is_int()->is_con()) {
793 // Use jlongs to avoid integer overflow.
794 jlong init_con = init_t->is_int()->get_con();
795 jlong limit_con = limit_t->is_int()->get_con();
796 int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
797 jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
798 jlong final_con = init_con + stride_con*trip_count;
799 int final_int = (int)final_con;
800 // The final value should be in integer range since the loop
801 // is counted and the limit was checked for overflow.
802 assert(final_con == (jlong)final_int, "final value should be integer");
803 return TypeInt::make(final_int);
804 }
805
806 return bottom_type(); // TypeInt::INT
807 }
808
809 //------------------------------Ideal------------------------------------------
810 // Return a node which is more "ideal" than the current node.
811 Node *LoopLimitNode::Ideal(PhaseGVN *phase, bool can_reshape) {
812 if (phase->type(in(Init)) == Type::TOP ||
813 phase->type(in(Limit)) == Type::TOP ||
814 phase->type(in(Stride)) == Type::TOP)
815 return NULL; // Dead
816
817 int stride_con = phase->type(in(Stride))->is_int()->get_con();
818 if (stride_con == 1)
819 return NULL; // Identity
820
821 if (in(Init)->is_Con() && in(Limit)->is_Con())
822 return NULL; // Value
823
824 // Delay following optimizations until all loop optimizations
825 // done to keep Ideal graph simple.
826 if (!can_reshape || phase->C->major_progress())
827 return NULL;
828
829 const TypeInt* init_t = phase->type(in(Init) )->is_int();
830 const TypeInt* limit_t = phase->type(in(Limit))->is_int();
831 int stride_p;
832 jlong lim, ini;
833 julong max;
834 if (stride_con > 0) {
835 stride_p = stride_con;
836 lim = limit_t->_hi;
837 ini = init_t->_lo;
838 max = (julong)max_jint;
839 } else {
840 stride_p = -stride_con;
841 lim = init_t->_hi;
842 ini = limit_t->_lo;
843 max = (julong)min_jint;
844 }
845 julong range = lim - ini + stride_p;
846 if (range <= max) {
847 // Convert to integer expression if it is not overflow.
848 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
849 Node *range = phase->transform(new (phase->C) SubINode(in(Limit), in(Init)));
850 Node *bias = phase->transform(new (phase->C) AddINode(range, stride_m));
851 Node *trip = phase->transform(new (phase->C) DivINode(0, bias, in(Stride)));
852 Node *span = phase->transform(new (phase->C) MulINode(trip, in(Stride)));
|