803 flip = 1-flip;
804 } else {
805 // Check for Phi(1,0)
806 if( phi1_t != TypeInt::ONE ) return NULL;
807 if( phi2_t != TypeInt::ZERO ) return NULL;
808 }
809 if( true_path == 2 ) {
810 flip = 1-flip;
811 }
812
813 Node* new_bol = (flip ? phase->transform( bol2->negate(phase) ) : bol2);
814 assert(new_bol != iff->in(1), "must make progress");
815 iff->set_req(1, new_bol);
816 // Intervening diamond probably goes dead
817 phase->C->set_major_progress();
818 return iff;
819 }
820
821 static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff);
822
823 //------------------------------Ideal------------------------------------------
824 // Return a node which is more "ideal" than the current node. Strip out
825 // control copies
826 Node *IfNode::Ideal(PhaseGVN *phase, bool can_reshape) {
827 if (remove_dead_region(phase, can_reshape)) return this;
828 // No Def-Use info?
829 if (!can_reshape) return NULL;
830 PhaseIterGVN *igvn = phase->is_IterGVN();
831
832 // Don't bother trying to transform a dead if
833 if (in(0)->is_top()) return NULL;
834 // Don't bother trying to transform an if with a dead test
835 if (in(1)->is_top()) return NULL;
836 // Another variation of a dead test
837 if (in(1)->is_Con()) return NULL;
838 // Another variation of a dead if
839 if (outcnt() < 2) return NULL;
840
841 // Canonicalize the test.
842 Node* idt_if = idealize_test(phase, this);
844
845 // Try to split the IF
846 Node *s = split_if(this, igvn);
847 if (s != NULL) return s;
848
849 // Check for people making a useless boolean: things like
850 // if( (x < y ? true : false) ) { ... }
851 // Replace with if( x < y ) { ... }
852 Node *bol2 = remove_useless_bool(this, phase);
853 if( bol2 ) return bol2;
854
855 // Setup to scan up the CFG looking for a dominating test
856 Node *dom = in(0);
857 Node *prev_dom = this;
858
859 // Check for range-check vs other kinds of tests
860 Node *index1, *range1;
861 jint offset1;
862 int flip1 = is_range_check(range1, index1, offset1);
863 if( flip1 ) {
864 Node *first_prev_dom = NULL;
865
866 // Try to remove extra range checks. All 'up_one_dom' gives up at merges
867 // so all checks we inspect post-dominate the top-most check we find.
868 // If we are going to fail the current check and we reach the top check
869 // then we are guaranteed to fail, so just start interpreting there.
870 // We 'expand' the top 2 range checks to include all post-dominating
871 // checks.
872
873 // The top 2 range checks seen
874 Node *prev_chk1 = NULL;
875 Node *prev_chk2 = NULL;
876 // Low and high offsets seen so far
877 jint off_lo = offset1;
878 jint off_hi = offset1;
879
880 // Scan for the top 2 checks and collect range of offsets
881 for( int dist = 0; dist < 999; dist++ ) { // Range-Check scan limit
882 if( dom->Opcode() == Op_If && // Not same opcode?
883 prev_dom->in(0) == dom ) { // One path of test does dominate?
884 if( dom == this ) return NULL; // dead loop
885 // See if this is a range check
886 Node *index2, *range2;
887 jint offset2;
888 int flip2 = dom->as_If()->is_range_check(range2, index2, offset2);
889 // See if this is a _matching_ range check, checking against
890 // the same array bounds.
891 if( flip2 == flip1 && range2 == range1 && index2 == index1 &&
892 dom->outcnt() == 2 ) {
893 // Gather expanded bounds
894 off_lo = MIN2(off_lo,offset2);
895 off_hi = MAX2(off_hi,offset2);
896 // Record top 2 range checks
897 prev_chk2 = prev_chk1;
898 prev_chk1 = prev_dom;
899 // If we match the test exactly, then the top test covers
900 // both our lower and upper bounds.
901 if( dom->in(1) == in(1) )
902 prev_chk2 = prev_chk1;
903 }
904 }
905 prev_dom = dom;
906 dom = up_one_dom( dom );
907 if( !dom ) break;
908 }
909
910
911 // Attempt to widen the dominating range check to cover some later
912 // ones. Since range checks "fail" by uncommon-trapping to the
913 // interpreter, widening a check can make us speculative enter the
914 // interpreter. If we see range-check deopt's, do not widen!
915 if (!phase->C->allow_range_check_smearing()) return NULL;
916
917 // Constant indices only need to check the upper bound.
918 // Non-constance indices must check both low and high.
919 if( index1 ) {
920 // Didn't find 2 prior covering checks, so cannot remove anything.
921 if( !prev_chk2 ) return NULL;
922 // 'Widen' the offsets of the 1st and 2nd covering check
923 adjust_check( prev_chk1, range1, index1, flip1, off_lo, igvn );
924 // Do not call adjust_check twice on the same projection
925 // as the first call may have transformed the BoolNode to a ConI
926 if( prev_chk1 != prev_chk2 ) {
927 adjust_check( prev_chk2, range1, index1, flip1, off_hi, igvn );
928 }
929 // Test is now covered by prior checks, dominate it out
930 prev_dom = prev_chk2;
931 } else {
932 // Didn't find prior covering check, so cannot remove anything.
933 if( !prev_chk1 ) return NULL;
934 // 'Widen' the offset of the 1st and only covering check
935 adjust_check( prev_chk1, range1, index1, flip1, off_hi, igvn );
936 // Test is now covered by prior checks, dominate it out
937 prev_dom = prev_chk1;
938 }
939
940
941 } else { // Scan for an equivalent test
942
943 Node *cmp;
944 int dist = 0; // Cutoff limit for search
945 int op = Opcode();
946 if( op == Op_If &&
947 (cmp=in(1)->in(1))->Opcode() == Op_CmpP ) {
948 if( cmp->in(2) != NULL && // make sure cmp is not already dead
949 cmp->in(2)->bottom_type() == TypePtr::NULL_PTR ) {
950 dist = 64; // Limit for null-pointer scans
951 } else {
952 dist = 4; // Do not bother for random pointer tests
953 }
954 } else {
955 dist = 4; // Limit for random junky scans
956 }
957
|
803 flip = 1-flip;
804 } else {
805 // Check for Phi(1,0)
806 if( phi1_t != TypeInt::ONE ) return NULL;
807 if( phi2_t != TypeInt::ZERO ) return NULL;
808 }
809 if( true_path == 2 ) {
810 flip = 1-flip;
811 }
812
813 Node* new_bol = (flip ? phase->transform( bol2->negate(phase) ) : bol2);
814 assert(new_bol != iff->in(1), "must make progress");
815 iff->set_req(1, new_bol);
816 // Intervening diamond probably goes dead
817 phase->C->set_major_progress();
818 return iff;
819 }
820
821 static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff);
822
823 struct RangeCheck {
824 Node* ctl;
825 jint off;
826 };
827
828 //------------------------------Ideal------------------------------------------
829 // Return a node which is more "ideal" than the current node. Strip out
830 // control copies
831 Node *IfNode::Ideal(PhaseGVN *phase, bool can_reshape) {
832 if (remove_dead_region(phase, can_reshape)) return this;
833 // No Def-Use info?
834 if (!can_reshape) return NULL;
835 PhaseIterGVN *igvn = phase->is_IterGVN();
836
837 // Don't bother trying to transform a dead if
838 if (in(0)->is_top()) return NULL;
839 // Don't bother trying to transform an if with a dead test
840 if (in(1)->is_top()) return NULL;
841 // Another variation of a dead test
842 if (in(1)->is_Con()) return NULL;
843 // Another variation of a dead if
844 if (outcnt() < 2) return NULL;
845
846 // Canonicalize the test.
847 Node* idt_if = idealize_test(phase, this);
849
850 // Try to split the IF
851 Node *s = split_if(this, igvn);
852 if (s != NULL) return s;
853
854 // Check for people making a useless boolean: things like
855 // if( (x < y ? true : false) ) { ... }
856 // Replace with if( x < y ) { ... }
857 Node *bol2 = remove_useless_bool(this, phase);
858 if( bol2 ) return bol2;
859
860 // Setup to scan up the CFG looking for a dominating test
861 Node *dom = in(0);
862 Node *prev_dom = this;
863
864 // Check for range-check vs other kinds of tests
865 Node *index1, *range1;
866 jint offset1;
867 int flip1 = is_range_check(range1, index1, offset1);
868 if( flip1 ) {
869 // Try to remove extra range checks. All 'up_one_dom' gives up at merges
870 // so all checks we inspect post-dominate the top-most check we find.
871 // If we are going to fail the current check and we reach the top check
872 // then we are guaranteed to fail, so just start interpreting there.
873 // We 'expand' the top 3 range checks to include all post-dominating
874 // checks.
875
876 // The top 3 range checks seen
877 struct RangeCheck prev_checks[3];
878 int nb_checks = 0;
879
880 // Low and high offsets seen so far
881 jint off_lo = offset1;
882 jint off_hi = offset1;
883
884 // Scan for the top 2 checks and collect range of offsets
885 for (int dist = 0; dist < 999; dist++) { // Range-Check scan limit
886 if (dom->Opcode() == Op_If && // Not same opcode?
887 prev_dom->in(0) == dom) { // One path of test does dominate?
888 if (dom == this) return NULL; // dead loop
889 // See if this is a range check
890 Node *index2, *range2;
891 jint offset2;
892 int flip2 = dom->as_If()->is_range_check(range2, index2, offset2);
893 // See if this is a _matching_ range check, checking against
894 // the same array bounds.
895 if (flip2 == flip1 && range2 == range1 && index2 == index1 &&
896 dom->outcnt() == 2) {
897 // Gather expanded bounds
898 off_lo = MIN2(off_lo,offset2);
899 off_hi = MAX2(off_hi,offset2);
900 // Record top 3 range checks
901 prev_checks[nb_checks%3].ctl = prev_dom;
902 prev_checks[nb_checks%3].off = offset2;
903 nb_checks++;
904 }
905 }
906 prev_dom = dom;
907 dom = up_one_dom(dom);
908 if (!dom) break;
909 }
910
911
912 // Attempt to widen the dominating range check to cover some later
913 // ones. Since range checks "fail" by uncommon-trapping to the
914 // interpreter, widening a check can make us speculative enter the
915 // interpreter. If we see range-check deopt's, do not widen!
916 if (!phase->C->allow_range_check_smearing()) return NULL;
917
918 // Constant indices only need to check the upper bound.
919 // Non-constant indices must check both low and high.
920 int chk0 = (nb_checks - 1) % 3;
921 if (index1) {
922 if (nb_checks == 0) {
923 return NULL;
924 } else {
925 struct RangeCheck rc0 = prev_checks[chk0];
926 if (nb_checks == 1) {
927 if (rc0.ctl->in(0)->in(1) == in(1)) {
928 // If we match the test exactly, then the top test covers
929 // both our lower and upper bounds. Valid only if there's
930 // a single dominating range check: for all we know this
931 // range check was widened and accesses that depend on it
932 // also depend on the previous range checks to be correct.
933 adjust_check(rc0.ctl, range1, index1, flip1, off_lo, igvn);
934 prev_dom = rc0.ctl;
935 } else {
936 return NULL;
937 }
938 } else {
939 // If the top range check's constant is the min or max of
940 // all constants we widen the next one to cover the whole
941 // range of constants.
942 int chk1 = (nb_checks - 2) % 3;
943 struct RangeCheck rc1 = prev_checks[chk1];
944 if (rc0.off == off_lo) {
945 adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
946 prev_dom = rc1.ctl;
947 } else if (rc0.off == off_hi) {
948 adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
949 prev_dom = rc1.ctl;
950 } else {
951 // If the top test's constant is not the min or max of all
952 // constants, we need 3 range checks. We must leave the
953 // top test unchanged because widening it would allow the
954 // accesses it protects to successfully read/write out of
955 // bounds.
956 if (nb_checks == 2) {
957 return NULL;
958 }
959 int chk2 = (nb_checks - 3) % 3;
960 struct RangeCheck rc2 = prev_checks[chk2];
961 // The top range check a+i covers interval: -a <= i < length-a
962 // The second range check b+i covers interval: -b <= i < length-b
963 if (rc1.off <= rc0.off) {
964 // if b <= a, we change the second range check to:
965 // -min_of_all_constants <= i < length-min_of_all_constants
966 // Together top and second range checks now cover:
967 // -min_of_all_constants <= i < length-a
968 // which is more restrictive than -b <= i < length-b:
969 // -b <= -min_of_all_constants <= i < length-a <= length-b
970 // The third check is then changed to:
971 // -max_of_all_constants <= i < length-max_of_all_constants
972 // so 2nd and 3rd checks restrict allowed values of i to:
973 // -min_of_all_constants <= i < length-max_of_all_constants
974 adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
975 adjust_check(rc2.ctl, range1, index1, flip1, off_hi, igvn);
976 } else {
977 // if b > a, we change the second range check to:
978 // -max_of_all_constants <= i < length-max_of_all_constants
979 // Together top and second range checks now cover:
980 // -a <= i < length-max_of_all_constants
981 // which is more restrictive than -b <= i < length-b:
982 // -b < -a <= i < length-max_of_all_constants <= length-b
983 // The third check is then changed to:
984 // -max_of_all_constants <= i < length-max_of_all_constants
985 // so 2nd and 3rd checks restrict allowed values of i to:
986 // -min_of_all_constants <= i < length-max_of_all_constants
987 adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
988 adjust_check(rc2.ctl, range1, index1, flip1, off_lo, igvn);
989 }
990 prev_dom = rc2.ctl;
991 }
992 }
993 }
994 } else {
995 // Didn't find prior covering check, so cannot remove anything.
996 if (nb_checks == 0) return NULL;
997 struct RangeCheck rc0 = prev_checks[chk0];
998 // 'Widen' the offset of the 1st and only covering check
999 adjust_check(rc0.ctl, range1, index1, flip1, off_hi, igvn);
1000 // Test is now covered by prior checks, dominate it out
1001 prev_dom = rc0.ctl;
1002 }
1003
1004
1005 } else { // Scan for an equivalent test
1006
1007 Node *cmp;
1008 int dist = 0; // Cutoff limit for search
1009 int op = Opcode();
1010 if( op == Op_If &&
1011 (cmp=in(1)->in(1))->Opcode() == Op_CmpP ) {
1012 if( cmp->in(2) != NULL && // make sure cmp is not already dead
1013 cmp->in(2)->bottom_type() == TypePtr::NULL_PTR ) {
1014 dist = 64; // Limit for null-pointer scans
1015 } else {
1016 dist = 4; // Do not bother for random pointer tests
1017 }
1018 } else {
1019 dist = 4; // Limit for random junky scans
1020 }
1021
|