LEFT | RIGHT |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 #include <u.h> | 5 #include <u.h> |
6 #include <libc.h> | 6 #include <libc.h> |
7 #include "go.h" | 7 #include "go.h" |
8 | 8 |
9 static Node* walkprint(Node*, NodeList**, int); | 9 static Node* walkprint(Node*, NodeList**, int); |
10 static Node* mapfn(char*, Type*); | 10 static Node* mapfn(char*, Type*); |
(...skipping 464 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
475 shiftwalked: | 475 shiftwalked: |
476 t = n->left->type; | 476 t = n->left->type; |
477 n->bounded = bounded(n->right, 8*t->width); | 477 n->bounded = bounded(n->right, 8*t->width); |
478 if(debug['m'] && n->etype && !isconst(n->right, CTINT)) | 478 if(debug['m'] && n->etype && !isconst(n->right, CTINT)) |
479 warn("shift bounds check elided"); | 479 warn("shift bounds check elided"); |
480 goto ret; | 480 goto ret; |
481 | 481 |
482 case OAND: | 482 case OAND: |
483 case OSUB: | 483 case OSUB: |
484 case OMUL: | 484 case OMUL: |
| 485 case OHMUL: |
485 case OLT: | 486 case OLT: |
486 case OLE: | 487 case OLE: |
487 case OGE: | 488 case OGE: |
488 case OGT: | 489 case OGT: |
489 case OADD: | 490 case OADD: |
490 case OCOMPLEX: | 491 case OCOMPLEX: |
491 case OLROT: | 492 case OLROT: |
492 walkexpr(&n->left, init); | 493 walkexpr(&n->left, init); |
493 walkexpr(&n->right, init); | 494 walkexpr(&n->right, init); |
494 goto ret; | 495 goto ret; |
(...skipping 448 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
943 t = n->type; | 944 t = n->type; |
944 n = mkcall("complex128div", types[TCOMPLEX128], init, | 945 n = mkcall("complex128div", types[TCOMPLEX128], init, |
945 conv(n->left, types[TCOMPLEX128]), | 946 conv(n->left, types[TCOMPLEX128]), |
946 conv(n->right, types[TCOMPLEX128])); | 947 conv(n->right, types[TCOMPLEX128])); |
947 n = conv(n, t); | 948 n = conv(n, t); |
948 goto ret; | 949 goto ret; |
949 } | 950 } |
950 // Nothing to do for float divisions. | 951 // Nothing to do for float divisions. |
951 if(isfloat[et]) | 952 if(isfloat[et]) |
952 goto ret; | 953 goto ret; |
| 954 |
953 // Try rewriting as shifts or magic multiplies. | 955 // Try rewriting as shifts or magic multiplies. |
954 walkdiv(&n, init); | 956 walkdiv(&n, init); |
| 957 |
| 958 /* |
| 959 * rewrite 64-bit div and mod into function calls |
| 960 * on 32-bit architectures. |
| 961 */ |
955 switch(n->op) { | 962 switch(n->op) { |
956 default: | |
957 goto ret; | |
958 case OMOD: | 963 case OMOD: |
959 case ODIV: | 964 case ODIV: |
| 965 if(widthptr > 4 || (et != TUINT64 && et != TINT64)) |
| 966 goto ret; |
| 967 if(et == TINT64) |
| 968 strcpy(namebuf, "int64"); |
| 969 else |
| 970 strcpy(namebuf, "uint64"); |
| 971 if(n->op == ODIV) |
| 972 strcat(namebuf, "div"); |
| 973 else |
| 974 strcat(namebuf, "mod"); |
| 975 n = mkcall(namebuf, n->type, init, |
| 976 conv(n->left, types[et]), conv(n->right, types[e
t])); |
960 break; | 977 break; |
961 » » } | 978 » » default: |
962 » » /* | 979 » » » break; |
963 » » * rewrite div and mod into function calls | 980 » » } |
964 » » * on 32-bit architectures. | |
965 » » */ | |
966 » » if(widthptr > 4 || (et != TUINT64 && et != TINT64)) | |
967 » » » goto ret; | |
968 » » if(et == TINT64) | |
969 » » » strcpy(namebuf, "int64"); | |
970 » » else | |
971 » » » strcpy(namebuf, "uint64"); | |
972 » » if(n->op == ODIV) | |
973 » » » strcat(namebuf, "div"); | |
974 » » else | |
975 » » » strcat(namebuf, "mod"); | |
976 » » n = mkcall(namebuf, n->type, init, | |
977 » » » conv(n->left, types[et]), conv(n->right, types[et])); | |
978 goto ret; | 981 goto ret; |
979 | 982 |
980 case OINDEX: | 983 case OINDEX: |
981 walkexpr(&n->left, init); | 984 walkexpr(&n->left, init); |
| 985 // save the original node for bounds checking elision. |
| 986 // If it was a ODIV/OMOD walk might rewrite it. |
| 987 r = n->right; |
982 walkexpr(&n->right, init); | 988 walkexpr(&n->right, init); |
983 | 989 |
984 // if range of type cannot exceed static array bound, | 990 // if range of type cannot exceed static array bound, |
985 // disable bounds check. | 991 // disable bounds check. |
986 if(n->bounded) | 992 if(n->bounded) |
987 goto ret; | 993 goto ret; |
988 t = n->left->type; | 994 t = n->left->type; |
989 if(t != T && isptr[t->etype]) | 995 if(t != T && isptr[t->etype]) |
990 t = t->type; | 996 t = t->type; |
991 if(isfixedarray(t)) { | 997 if(isfixedarray(t)) { |
992 » » » n->bounded = bounded(n->right, t->bound); | 998 » » » n->bounded = bounded(r, t->bound); |
993 if(debug['m'] && n->bounded && !isconst(n->right, CTINT)
) | 999 if(debug['m'] && n->bounded && !isconst(n->right, CTINT)
) |
994 warn("index bounds check elided"); | 1000 warn("index bounds check elided"); |
995 if(smallintconst(n->right) && !n->bounded) | 1001 if(smallintconst(n->right) && !n->bounded) |
996 yyerror("index out of bounds"); | 1002 yyerror("index out of bounds"); |
997 } else if(isconst(n->left, CTSTR)) { | 1003 } else if(isconst(n->left, CTSTR)) { |
998 » » » n->bounded = bounded(n->right, n->left->val.u.sval->len)
; | 1004 » » » n->bounded = bounded(r, n->left->val.u.sval->len); |
999 if(debug['m'] && n->bounded && !isconst(n->right, CTINT)
) | 1005 if(debug['m'] && n->bounded && !isconst(n->right, CTINT)
) |
1000 warn("index bounds check elided"); | 1006 warn("index bounds check elided"); |
1001 if(smallintconst(n->right)) { | 1007 if(smallintconst(n->right)) { |
1002 if(!n->bounded) | 1008 if(!n->bounded) |
1003 yyerror("index out of bounds"); | 1009 yyerror("index out of bounds"); |
1004 else { | 1010 else { |
1005 // replace "abc"[2] with 'b'. | 1011 // replace "abc"[2] with 'b'. |
1006 // delayed until now because "abc"[2] is
not | 1012 // delayed until now because "abc"[2] is
not |
1007 // an ideal constant. | 1013 // an ideal constant. |
1008 v = mpgetfix(n->right->val.u.xval); | 1014 v = mpgetfix(n->right->val.u.xval); |
(...skipping 1861 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2870 ········ | 2876 ········ |
2871 // Remove rotate 0 and rotate w. | 2877 // Remove rotate 0 and rotate w. |
2872 s = mpgetfix(n->right->val.u.xval); | 2878 s = mpgetfix(n->right->val.u.xval); |
2873 if(s == 0 || s == w) | 2879 if(s == 0 || s == w) |
2874 n = n->left; | 2880 n = n->left; |
2875 | 2881 |
2876 *np = n; | 2882 *np = n; |
2877 return; | 2883 return; |
2878 } | 2884 } |
2879 | 2885 |
| 2886 /* |
| 2887 * walkdiv rewrites division by a constant as less expensive |
| 2888 * operations. |
| 2889 */ |
2880 static void | 2890 static void |
2881 walkdiv(Node **np, NodeList **init) | 2891 walkdiv(Node **np, NodeList **init) |
2882 { | 2892 { |
2883 Node *n, *nl, *nr, *nc; | 2893 Node *n, *nl, *nr, *nc; |
2884 » Node *n1, *n2, *n3; | 2894 » Node *n1, *n2, *n3, *n4; |
2885 » int pow; // if >= 0, nr is 1<<n | 2895 » int pow; // if >= 0, nr is 1<<pow |
2886 int s; // 1 if nr is negative. | 2896 int s; // 1 if nr is negative. |
2887 int w; | 2897 int w; |
2888 Type *twide; | 2898 Type *twide; |
2889 Magic m; | 2899 Magic m; |
2890 | 2900 |
2891 n = *np; | 2901 n = *np; |
2892 if(n->right->op != OLITERAL) | 2902 if(n->right->op != OLITERAL) |
2893 return; | 2903 return; |
2894 // nr is a constant. | 2904 // nr is a constant. |
2895 nl = cheapexpr(n->left, init); | 2905 nl = cheapexpr(n->left, init); |
2896 nr = n->right; | 2906 nr = n->right; |
2897 | 2907 |
2898 // special cases of mod/div | 2908 // special cases of mod/div |
2899 // by a constant | 2909 // by a constant |
2900 w = nl->type->width*8; | 2910 w = nl->type->width*8; |
2901 s = 0; | 2911 s = 0; |
2902 pow = powtwo(nr); | 2912 pow = powtwo(nr); |
2903 if(pow >= 1000) { | 2913 if(pow >= 1000) { |
2904 // negative power of 2 | 2914 // negative power of 2 |
2905 s = 1; | 2915 s = 1; |
2906 pow -= 1000; | 2916 pow -= 1000; |
2907 } | 2917 } |
2908 | 2918 |
2909 if(pow+1 >= w) { | 2919 if(pow+1 >= w) { |
2910 » » // just sign bit | 2920 » » // divisor too large. |
2911 return; | 2921 return; |
2912 } | 2922 } |
2913 if(pow < 0) { | 2923 if(pow < 0) { |
2914 goto divbymul; | 2924 goto divbymul; |
2915 } | 2925 } |
2916 | 2926 |
2917 switch(pow) { | 2927 switch(pow) { |
2918 case 0: | 2928 case 0: |
2919 if(n->op == OMOD) { | 2929 if(n->op == OMOD) { |
2920 // nl % 1 is zero. | 2930 // nl % 1 is zero. |
2921 nodconst(n, n->type, 0); | 2931 nodconst(n, n->type, 0); |
2922 } else if(s) { | 2932 } else if(s) { |
2923 // divide by -1 | 2933 // divide by -1 |
2924 n->op = OMINUS; | 2934 n->op = OMINUS; |
2925 n->right = N; | 2935 n->right = N; |
2926 } else { | 2936 } else { |
2927 // divide by 1 | 2937 // divide by 1 |
2928 n = nl; | 2938 n = nl; |
2929 } | 2939 } |
2930 break; | 2940 break; |
2931 default: | 2941 default: |
2932 if(issigned[n->type->etype]) { | 2942 if(issigned[n->type->etype]) { |
2933 if(n->op == OMOD) { | 2943 if(n->op == OMOD) { |
2934 » » » » goto longmod; | 2944 » » » » // signed modulo 2^pow is like ANDing |
| 2945 » » » » // with the last pow bits, but if nl < 0, |
| 2946 » » » » // nl & (2^pow-1) is (nl+1)%2^pow - 1. |
| 2947 » » » » nc = nod(OXXX, N, N); |
| 2948 » » » » nodconst(nc, types[simtype[TUINT]], w-1); |
| 2949 » » » » n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0. |
| 2950 » » » » if(pow == 1) { |
| 2951 » » » » » typecheck(&n1, Erv); |
| 2952 » » » » » n1 = cheapexpr(n1, init); |
| 2953 » » » » » // n = (nl+ε)&1 -ε where ε=1 iff nl<0. |
| 2954 » » » » » n2 = nod(OSUB, nl, n1); |
| 2955 » » » » » nc = nod(OXXX, N, N); |
| 2956 » » » » » nodconst(nc, nl->type, 1); |
| 2957 » » » » » n3 = nod(OAND, n2, nc); |
| 2958 » » » » » n = nod(OADD, n3, n1); |
| 2959 » » » » } else { |
| 2960 » » » » » // n = (nl+ε)&(nr-1) - ε where ε=2^pow-1
iff nl<0. |
| 2961 » » » » » nc = nod(OXXX, N, N); |
| 2962 » » » » » nodconst(nc, nl->type, (1LL<<pow)-1); |
| 2963 » » » » » n2 = nod(OAND, n1, nc); // n2 = 2^pow-1
iff nl<0. |
| 2964 » » » » » typecheck(&n2, Erv); |
| 2965 » » » » » n2 = cheapexpr(n2, init); |
| 2966 |
| 2967 » » » » » n3 = nod(OADD, nl, n2); |
| 2968 » » » » » n4 = nod(OAND, n3, nc); |
| 2969 » » » » » n = nod(OSUB, n4, n2); |
| 2970 » » » » } |
| 2971 » » » » break; |
2935 } else { | 2972 } else { |
2936 // arithmetic right shift does not give the corr
ect rounding. | 2973 // arithmetic right shift does not give the corr
ect rounding. |
2937 // if nl >= 0, nl >> n == nl / nr | 2974 // if nl >= 0, nl >> n == nl / nr |
2938 // if nl < 0, we want to add 2^n-1 first. | 2975 // if nl < 0, we want to add 2^n-1 first. |
2939 nc = nod(OXXX, N, N); | 2976 nc = nod(OXXX, N, N); |
2940 nodconst(nc, types[simtype[TUINT]], w-1); | 2977 nodconst(nc, types[simtype[TUINT]], w-1); |
2941 n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0. | 2978 n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0. |
2942 if(pow == 1) { | 2979 if(pow == 1) { |
2943 // nl+1 is nl-(-1) | 2980 // nl+1 is nl-(-1) |
2944 n->left = nod(OSUB, nl, n1); | 2981 n->left = nod(OSUB, nl, n1); |
(...skipping 25 matching lines...) Expand all Loading... |
2970 n->op = ORSH; | 3007 n->op = ORSH; |
2971 nodconst(nc, types[simtype[TUINT]], pow); | 3008 nodconst(nc, types[simtype[TUINT]], pow); |
2972 } | 3009 } |
2973 n->typecheck = 0; | 3010 n->typecheck = 0; |
2974 n->right = nc; | 3011 n->right = nc; |
2975 break; | 3012 break; |
2976 } | 3013 } |
2977 goto ret; | 3014 goto ret; |
2978 | 3015 |
2979 divbymul: | 3016 divbymul: |
2980 if(n->op == OMOD) | |
2981 goto longmod; | |
2982 | |
2983 // try to do division by multiply by (2^w)/d | 3017 // try to do division by multiply by (2^w)/d |
2984 // see hacker's delight chapter 10 | 3018 // see hacker's delight chapter 10 |
2985 // TODO: support 64-bit magic multiply here. | 3019 // TODO: support 64-bit magic multiply here. |
2986 m.w = w; | 3020 m.w = w; |
2987 if(issigned[nl->type->etype]) { | 3021 if(issigned[nl->type->etype]) { |
2988 m.sd = mpgetfix(nr->val.u.xval); | 3022 m.sd = mpgetfix(nr->val.u.xval); |
2989 smagic(&m); | 3023 smagic(&m); |
2990 } else { | 3024 } else { |
2991 m.ud = mpgetfix(nr->val.u.xval); | 3025 m.ud = mpgetfix(nr->val.u.xval); |
2992 umagic(&m); | 3026 umagic(&m); |
2993 } | 3027 } |
2994 if(m.bad) | 3028 if(m.bad) |
2995 return; | 3029 return; |
2996 | 3030 |
2997 » // Select a Go type with (at least) twice the width. | 3031 » // We have a quick division method so use it |
| 3032 » // for modulo too. |
| 3033 » if(n->op == OMOD) |
| 3034 » » goto longmod; |
| 3035 |
2998 switch(simtype[nl->type->etype]) { | 3036 switch(simtype[nl->type->etype]) { |
2999 default: | 3037 default: |
3000 return; | 3038 return; |
3001 case TUINT8: | |
3002 case TUINT16: | |
3003 twide = types[TUINT32]; | |
3004 break; | |
3005 case TUINT32: | |
3006 twide = types[TUINT64]; | |
3007 break; | |
3008 case TINT8: | |
3009 case TINT16: | |
3010 twide = types[TINT32]; | |
3011 break; | |
3012 case TINT32: | |
3013 twide = types[TINT64]; | |
3014 break; | |
3015 } | |
3016 | |
3017 switch(simtype[nl->type->etype]) { | |
3018 default: | |
3019 return; | |
3020 | 3039 |
3021 case TUINT8: | 3040 case TUINT8: |
3022 case TUINT16: | 3041 case TUINT16: |
3023 case TUINT32: | 3042 case TUINT32: |
3024 » » // n1 = nl * magic. | 3043 » » // n1 = nl * magic >> w (HMUL) |
3025 nc = nod(OXXX, N, N); | 3044 nc = nod(OXXX, N, N); |
3026 » » nodconst(nc, twide, m.um); | 3045 » » nodconst(nc, nl->type, m.um); |
3027 » » n1 = nod(OMUL, conv(nl, twide), nc); | 3046 » » n1 = nod(OMUL, nl, nc); |
| 3047 » » typecheck(&n1, Erv); |
| 3048 » » n1->op = OHMUL; |
3028 if(m.ua) { | 3049 if(m.ua) { |
3029 » » » // add numerator. | 3050 » » » // Select a Go type with (at least) twice the width. |
3030 » » » // n2 = (n1>>w + nl) | 3051 » » » switch(simtype[nl->type->etype]) { |
3031 » » » nc = nod(OXXX, N, N); | 3052 » » » default: |
3032 » » » nodconst(nc, types[TUINT], w); | 3053 » » » » return; |
3033 » » » n2 = nod(ORSH, n1, nc); | 3054 » » » case TUINT8: |
3034 » » » n3 = nod(OADD, n2, conv(nl, twide)); | 3055 » » » case TUINT16: |
| 3056 » » » » twide = types[TUINT32]; |
| 3057 » » » » break; |
| 3058 » » » case TUINT32: |
| 3059 » » » » twide = types[TUINT64]; |
| 3060 » » » » break; |
| 3061 » » » case TINT8: |
| 3062 » » » case TINT16: |
| 3063 » » » » twide = types[TINT32]; |
| 3064 » » » » break; |
| 3065 » » » case TINT32: |
| 3066 » » » » twide = types[TINT64]; |
| 3067 » » » » break; |
| 3068 » » » } |
| 3069 |
| 3070 » » » // add numerator (might overflow). |
| 3071 » » » // n2 = (n1 + nl) |
| 3072 » » » n2 = nod(OADD, conv(n1, twide), conv(nl, twide)); |
3035 | 3073 |
3036 // shift by m.s | 3074 // shift by m.s |
3037 nc = nod(OXXX, N, N); | 3075 nc = nod(OXXX, N, N); |
3038 nodconst(nc, types[TUINT], m.s); | 3076 nodconst(nc, types[TUINT], m.s); |
3039 » » » n = conv(nod(ORSH, n3, nc), nl->type); | 3077 » » » n = conv(nod(ORSH, n2, nc), nl->type); |
3040 } else { | 3078 } else { |
3041 » » » // n = (n1>>w) >> m.s | 3079 » » » // n = n1 >> m.s |
3042 nc = nod(OXXX, N, N); | 3080 nc = nod(OXXX, N, N); |
3043 » » » nodconst(nc, types[TUINT], w+m.s); | 3081 » » » nodconst(nc, types[TUINT], m.s); |
3044 » » » n = conv(nod(ORSH, n1, nc), nl->type); | 3082 » » » n = nod(ORSH, n1, nc); |
3045 } | 3083 } |
3046 break; | 3084 break; |
3047 | 3085 |
3048 case TINT8: | 3086 case TINT8: |
3049 case TINT16: | 3087 case TINT16: |
3050 case TINT32: | 3088 case TINT32: |
3051 » » // TODO: signed case. | 3089 » » // n1 = nl * magic >> w |
3052 » » return; | 3090 » » nc = nod(OXXX, N, N); |
| 3091 » » nodconst(nc, nl->type, m.sm); |
| 3092 » » n1 = nod(OMUL, nl, nc); |
| 3093 » » typecheck(&n1, Erv); |
| 3094 » » n1->op = OHMUL; |
| 3095 » » if(m.sm < 0) { |
| 3096 » » » // add the numerator. |
| 3097 » » » n1 = nod(OADD, n1, nl); |
| 3098 » » } |
| 3099 » » // shift by m.s |
| 3100 » » nc = nod(OXXX, N, N); |
| 3101 » » nodconst(nc, types[TUINT], m.s); |
| 3102 » » n2 = conv(nod(ORSH, n1, nc), nl->type); |
| 3103 » » // add 1 iff n1 is negative. |
| 3104 » » nc = nod(OXXX, N, N); |
| 3105 » » nodconst(nc, types[TUINT], w-1); |
| 3106 » » n3 = nod(ORSH, nl, nc); // n4 = -1 iff n1 is negative. |
| 3107 » » n = nod(OSUB, n2, n3); |
| 3108 » » // apply sign. |
| 3109 » » if(m.sd < 0) |
| 3110 » » » n = nod(OMINUS, n, N); |
| 3111 » » break; |
3053 } | 3112 } |
3054 goto ret; | 3113 goto ret; |
3055 | 3114 |
3056 longmod: | 3115 longmod: |
3057 // rewrite as A%B = A - (A/B*B). | 3116 // rewrite as A%B = A - (A/B*B). |
3058 n1 = nod(ODIV, nl, nr); | 3117 n1 = nod(ODIV, nl, nr); |
3059 n2 = nod(OMUL, n1, nr); | 3118 n2 = nod(OMUL, n1, nr); |
3060 n = nod(OSUB, nl, n2); | 3119 n = nod(OSUB, nl, n2); |
3061 goto ret; | 3120 goto ret; |
3062 | 3121 |
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3164 yyerror("tracked field must be in named struct type"); | 3223 yyerror("tracked field must be in named struct type"); |
3165 if(!exportname(field->sym->name)) | 3224 if(!exportname(field->sym->name)) |
3166 yyerror("tracked field must be exported (upper case)"); | 3225 yyerror("tracked field must be exported (upper case)"); |
3167 | 3226 |
3168 l = typ(0); | 3227 l = typ(0); |
3169 l->type = field; | 3228 l->type = field; |
3170 l->down = curfn->paramfld; | 3229 l->down = curfn->paramfld; |
3171 curfn->paramfld = l; | 3230 curfn->paramfld = l; |
3172 } | 3231 } |
3173 | 3232 |
LEFT | RIGHT |