Mercurial > hg > truffle

comparison src/share/vm/opto/ifnode.cpp @ 20707:e3d0aaab84aa

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
8066103: C2's range check smearing allows out of bound array accesses Summary: range check smearing uncorrectly adjust first range check in a list of range checks to cover all of them Reviewed-by: jrose, kvn, iveresov
author roland
date Tue, 09 Dec 2014 18:49:13 +0100
parents fb971e09d20f
children 7848fc12602b
comparison
equal deleted inserted replaced
20706:793204f5528a 20707:e3d0aaab84aa
818 return iff; 818 return iff;
819 } 819 }
820 820
821 static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff); 821 static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff);
822 822
823 struct RangeCheck {
824 Node* ctl;
825 jint off;
826 };
827
823 //------------------------------Ideal------------------------------------------ 828 //------------------------------Ideal------------------------------------------
824 // Return a node which is more "ideal" than the current node. Strip out 829 // Return a node which is more "ideal" than the current node. Strip out
825 // control copies 830 // control copies
826 Node *IfNode::Ideal(PhaseGVN *phase, bool can_reshape) { 831 Node *IfNode::Ideal(PhaseGVN *phase, bool can_reshape) {
827 if (remove_dead_region(phase, can_reshape)) return this; 832 if (remove_dead_region(phase, can_reshape)) return this;
859 // Check for range-check vs other kinds of tests 864 // Check for range-check vs other kinds of tests
860 Node *index1, *range1; 865 Node *index1, *range1;
861 jint offset1; 866 jint offset1;
862 int flip1 = is_range_check(range1, index1, offset1); 867 int flip1 = is_range_check(range1, index1, offset1);
863 if( flip1 ) { 868 if( flip1 ) {
864 Node *first_prev_dom = NULL;
865
866 // Try to remove extra range checks. All 'up_one_dom' gives up at merges 869 // 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. 870 // 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 871 // 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. 872 // then we are guaranteed to fail, so just start interpreting there.
870 // We 'expand' the top 2 range checks to include all post-dominating 873 // We 'expand' the top 3 range checks to include all post-dominating
871 // checks. 874 // checks.
872 875
873 // The top 2 range checks seen 876 // The top 3 range checks seen
874 Node *prev_chk1 = NULL; 877 const int NRC =3;
875 Node *prev_chk2 = NULL; 878 RangeCheck prev_checks[NRC];
879 int nb_checks = 0;
880
876 // Low and high offsets seen so far 881 // Low and high offsets seen so far
877 jint off_lo = offset1; 882 jint off_lo = offset1;
878 jint off_hi = offset1; 883 jint off_hi = offset1;
879 884
880 // Scan for the top 2 checks and collect range of offsets 885 bool found_immediate_dominator = false;
881 for( int dist = 0; dist < 999; dist++ ) { // Range-Check scan limit 886
882 if( dom->Opcode() == Op_If && // Not same opcode? 887 // Scan for the top checks and collect range of offsets
883 prev_dom->in(0) == dom ) { // One path of test does dominate? 888 for (int dist = 0; dist < 999; dist++) { // Range-Check scan limit
884 if( dom == this ) return NULL; // dead loop 889 if (dom->Opcode() == Op_If && // Not same opcode?
890 prev_dom->in(0) == dom) { // One path of test does dominate?
891 if (dom == this) return NULL; // dead loop
885 // See if this is a range check 892 // See if this is a range check
886 Node *index2, *range2; 893 Node *index2, *range2;
887 jint offset2; 894 jint offset2;
888 int flip2 = dom->as_If()->is_range_check(range2, index2, offset2); 895 int flip2 = dom->as_If()->is_range_check(range2, index2, offset2);
889 // See if this is a _matching_ range check, checking against 896 // See if this is a _matching_ range check, checking against
890 // the same array bounds. 897 // the same array bounds.
891 if( flip2 == flip1 && range2 == range1 && index2 == index1 && 898 if (flip2 == flip1 && range2 == range1 && index2 == index1 &&
892 dom->outcnt() == 2 ) { 899 dom->outcnt() == 2) {
900 if (nb_checks == 0 && dom->in(1) == in(1)) {
901 // Found an immediately dominating test at the same offset.
902 // This kind of back-to-back test can be eliminated locally,
903 // and there is no need to search further for dominating tests.
904 assert(offset2 == offset1, "Same test but different offsets");
905 found_immediate_dominator = true;
906 break;
907 }
893 // Gather expanded bounds 908 // Gather expanded bounds
894 off_lo = MIN2(off_lo,offset2); 909 off_lo = MIN2(off_lo,offset2);
895 off_hi = MAX2(off_hi,offset2); 910 off_hi = MAX2(off_hi,offset2);
896 // Record top 2 range checks 911 // Record top NRC range checks
897 prev_chk2 = prev_chk1; 912 prev_checks[nb_checks%NRC].ctl = prev_dom;
898 prev_chk1 = prev_dom; 913 prev_checks[nb_checks%NRC].off = offset2;
899 // If we match the test exactly, then the top test covers 914 nb_checks++;
900 // both our lower and upper bounds.
901 if( dom->in(1) == in(1) )
902 prev_chk2 = prev_chk1;
903 } 915 }
904 } 916 }
905 prev_dom = dom; 917 prev_dom = dom;
906 dom = up_one_dom( dom ); 918 dom = up_one_dom(dom);
907 if( !dom ) break; 919 if (!dom) break;
908 } 920 }
909 921
910 922 if (!found_immediate_dominator) {
911 // Attempt to widen the dominating range check to cover some later 923 // Attempt to widen the dominating range check to cover some later
912 // ones. Since range checks "fail" by uncommon-trapping to the 924 // ones. Since range checks "fail" by uncommon-trapping to the
913 // interpreter, widening a check can make us speculative enter the 925 // interpreter, widening a check can make us speculatively enter
914 // interpreter. If we see range-check deopt's, do not widen! 926 // the interpreter. If we see range-check deopt's, do not widen!
915 if (!phase->C->allow_range_check_smearing()) return NULL; 927 if (!phase->C->allow_range_check_smearing()) return NULL;
916 928
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. 929 // Didn't find prior covering check, so cannot remove anything.
933 if( !prev_chk1 ) return NULL; 930 if (nb_checks == 0) {
934 // 'Widen' the offset of the 1st and only covering check 931 return NULL;
935 adjust_check( prev_chk1, range1, index1, flip1, off_hi, igvn ); 932 }
936 // Test is now covered by prior checks, dominate it out 933 // Constant indices only need to check the upper bound.
937 prev_dom = prev_chk1; 934 // Non-constant indices must check both low and high.
938 } 935 int chk0 = (nb_checks - 1) % NRC;
939 936 if (index1) {
937 if (nb_checks == 1) {
938 return NULL;
939 } else {
940 // If the top range check's constant is the min or max of
941 // all constants we widen the next one to cover the whole
942 // range of constants.
943 RangeCheck rc0 = prev_checks[chk0];
944 int chk1 = (nb_checks - 2) % NRC;
945 RangeCheck rc1 = prev_checks[chk1];
946 if (rc0.off == off_lo) {
947 adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
948 prev_dom = rc1.ctl;
949 } else if (rc0.off == off_hi) {
950 adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
951 prev_dom = rc1.ctl;
952 } else {
953 // If the top test's constant is not the min or max of all
954 // constants, we need 3 range checks. We must leave the
955 // top test unchanged because widening it would allow the
956 // accesses it protects to successfully read/write out of
957 // bounds.
958 if (nb_checks == 2) {
959 return NULL;
960 }
961 int chk2 = (nb_checks - 3) % NRC;
962 RangeCheck rc2 = prev_checks[chk2];
963 // The top range check a+i covers interval: -a <= i < length-a
964 // The second range check b+i covers interval: -b <= i < length-b
965 if (rc1.off <= rc0.off) {
966 // if b <= a, we change the second range check to:
967 // -min_of_all_constants <= i < length-min_of_all_constants
968 // Together top and second range checks now cover:
969 // -min_of_all_constants <= i < length-a
970 // which is more restrictive than -b <= i < length-b:
971 // -b <= -min_of_all_constants <= i < length-a <= length-b
972 // The third check is then changed to:
973 // -max_of_all_constants <= i < length-max_of_all_constants
974 // so 2nd and 3rd checks restrict allowed values of i to:
975 // -min_of_all_constants <= i < length-max_of_all_constants
976 adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
977 adjust_check(rc2.ctl, range1, index1, flip1, off_hi, igvn);
978 } else {
979 // if b > a, we change the second range check to:
980 // -max_of_all_constants <= i < length-max_of_all_constants
981 // Together top and second range checks now cover:
982 // -a <= i < length-max_of_all_constants
983 // which is more restrictive than -b <= i < length-b:
984 // -b < -a <= i < length-max_of_all_constants <= length-b
985 // The third check is then changed to:
986 // -max_of_all_constants <= i < length-max_of_all_constants
987 // so 2nd and 3rd checks restrict allowed values of i to:
988 // -min_of_all_constants <= i < length-max_of_all_constants
989 adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
990 adjust_check(rc2.ctl, range1, index1, flip1, off_lo, igvn);
991 }
992 prev_dom = rc2.ctl;
993 }
994 }
995 } else {
996 RangeCheck rc0 = prev_checks[chk0];
997 // 'Widen' the offset of the 1st and only covering check
998 adjust_check(rc0.ctl, range1, index1, flip1, off_hi, igvn);
999 // Test is now covered by prior checks, dominate it out
1000 prev_dom = rc0.ctl;
1001 }
1002 }
940 1003
941 } else { // Scan for an equivalent test 1004 } else { // Scan for an equivalent test
942 1005
943 Node *cmp; 1006 Node *cmp;
944 int dist = 0; // Cutoff limit for search 1007 int dist = 0; // Cutoff limit for search
1017 // Loop predicates may have depending checks which should not 1080 // Loop predicates may have depending checks which should not
1018 // be skipped. For example, range check predicate has two checks 1081 // be skipped. For example, range check predicate has two checks
1019 // for lower and upper bounds. 1082 // for lower and upper bounds.
1020 ProjNode* unc_proj = proj_out(1 - prev_dom->as_Proj()->_con)->as_Proj(); 1083 ProjNode* unc_proj = proj_out(1 - prev_dom->as_Proj()->_con)->as_Proj();
1021 if (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate)) 1084 if (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate))
1022 prev_dom = idom; 1085 prev_dom = idom;
1023 1086
1024 // Now walk the current IfNode's projections. 1087 // Now walk the current IfNode's projections.
1025 // Loop ends when 'this' has no more uses. 1088 // Loop ends when 'this' has no more uses.
1026 for (DUIterator_Last imin, i = last_outs(imin); i >= imin; --i) { 1089 for (DUIterator_Last imin, i = last_outs(imin); i >= imin; --i) {
1027 Node *ifp = last_out(i); // Get IfTrue/IfFalse 1090 Node *ifp = last_out(i); // Get IfTrue/IfFalse