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 453 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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; |
953 | 954 |
954 // Try rewriting as shifts or magic multiplies. | 955 // Try rewriting as shifts or magic multiplies. |
955 walkdiv(&n, init); | 956 walkdiv(&n, init); |
956 | 957 |
957 /* | 958 /* |
958 » » * rewrite div and mod into function calls | 959 » » * rewrite 64-bit div and mod into function calls |
959 * on 32-bit architectures. | 960 * on 32-bit architectures. |
960 */ | 961 */ |
961 switch(n->op) { | 962 switch(n->op) { |
962 case OMOD: | 963 case OMOD: |
963 case ODIV: | 964 case ODIV: |
964 if(widthptr > 4 || (et != TUINT64 && et != TINT64)) | 965 if(widthptr > 4 || (et != TUINT64 && et != TINT64)) |
965 goto ret; | 966 goto ret; |
966 if(et == TINT64) | 967 if(et == TINT64) |
967 strcpy(namebuf, "int64"); | 968 strcpy(namebuf, "int64"); |
968 else | 969 else |
(...skipping 1915 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2884 | 2885 |
2885 /* | 2886 /* |
2886 * walkdiv rewrites division by a constant as less expensive | 2887 * walkdiv rewrites division by a constant as less expensive |
2887 * operations. | 2888 * operations. |
2888 */ | 2889 */ |
2889 static void | 2890 static void |
2890 walkdiv(Node **np, NodeList **init) | 2891 walkdiv(Node **np, NodeList **init) |
2891 { | 2892 { |
2892 Node *n, *nl, *nr, *nc; | 2893 Node *n, *nl, *nr, *nc; |
2893 Node *n1, *n2, *n3, *n4; | 2894 Node *n1, *n2, *n3, *n4; |
2894 » int pow; // if >= 0, nr is 1<<n | 2895 » int pow; // if >= 0, nr is 1<<pow |
2895 int s; // 1 if nr is negative. | 2896 int s; // 1 if nr is negative. |
2896 int w; | 2897 int w; |
2897 Type *twide; | 2898 Type *twide; |
2898 Magic m; | 2899 Magic m; |
2899 | 2900 |
2900 n = *np; | 2901 n = *np; |
2901 if(n->right->op != OLITERAL) | 2902 if(n->right->op != OLITERAL) |
2902 return; | 2903 return; |
2903 // nr is a constant. | 2904 // nr is a constant. |
2904 nl = cheapexpr(n->left, init); | 2905 nl = cheapexpr(n->left, init); |
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3006 n->op = ORSH; | 3007 n->op = ORSH; |
3007 nodconst(nc, types[simtype[TUINT]], pow); | 3008 nodconst(nc, types[simtype[TUINT]], pow); |
3008 } | 3009 } |
3009 n->typecheck = 0; | 3010 n->typecheck = 0; |
3010 n->right = nc; | 3011 n->right = nc; |
3011 break; | 3012 break; |
3012 } | 3013 } |
3013 goto ret; | 3014 goto ret; |
3014 | 3015 |
3015 divbymul: | 3016 divbymul: |
3016 if(n->op == OMOD) | |
3017 goto longmod; | |
3018 | |
3019 // try to do division by multiply by (2^w)/d | 3017 // try to do division by multiply by (2^w)/d |
3020 // see hacker's delight chapter 10 | 3018 // see hacker's delight chapter 10 |
3021 // TODO: support 64-bit magic multiply here. | 3019 // TODO: support 64-bit magic multiply here. |
3022 m.w = w; | 3020 m.w = w; |
3023 if(issigned[nl->type->etype]) { | 3021 if(issigned[nl->type->etype]) { |
3024 m.sd = mpgetfix(nr->val.u.xval); | 3022 m.sd = mpgetfix(nr->val.u.xval); |
3025 smagic(&m); | 3023 smagic(&m); |
3026 } else { | 3024 } else { |
3027 m.ud = mpgetfix(nr->val.u.xval); | 3025 m.ud = mpgetfix(nr->val.u.xval); |
3028 umagic(&m); | 3026 umagic(&m); |
3029 } | 3027 } |
3030 if(m.bad) | 3028 if(m.bad) |
3031 return; | 3029 return; |
3032 | 3030 |
3033 » // 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 |
3034 switch(simtype[nl->type->etype]) { | 3036 switch(simtype[nl->type->etype]) { |
3035 default: | 3037 default: |
3036 return; | 3038 return; |
3037 case TUINT8: | |
3038 case TUINT16: | |
3039 twide = types[TUINT32]; | |
3040 break; | |
3041 case TUINT32: | |
3042 twide = types[TUINT64]; | |
3043 break; | |
3044 case TINT8: | |
3045 case TINT16: | |
3046 twide = types[TINT32]; | |
3047 break; | |
3048 case TINT32: | |
3049 twide = types[TINT64]; | |
3050 break; | |
3051 } | |
3052 | |
3053 switch(simtype[nl->type->etype]) { | |
3054 default: | |
3055 return; | |
3056 | 3039 |
3057 case TUINT8: | 3040 case TUINT8: |
3058 case TUINT16: | 3041 case TUINT16: |
3059 case TUINT32: | 3042 case TUINT32: |
3060 » » // n1 = nl * magic. | 3043 » » // n1 = nl * magic >> w (HMUL) |
3061 nc = nod(OXXX, N, N); | 3044 nc = nod(OXXX, N, N); |
3062 » » nodconst(nc, twide, m.um); | 3045 » » nodconst(nc, nl->type, m.um); |
3063 » » n1 = nod(OMUL, conv(nl, twide), nc); | 3046 » » n1 = nod(OMUL, nl, nc); |
| 3047 » » typecheck(&n1, Erv); |
| 3048 » » n1->op = OHMUL; |
3064 if(m.ua) { | 3049 if(m.ua) { |
3065 » » » // add numerator. | 3050 » » » // Select a Go type with (at least) twice the width. |
3066 » » » // n2 = (n1>>w + nl) | 3051 » » » switch(simtype[nl->type->etype]) { |
3067 » » » nc = nod(OXXX, N, N); | 3052 » » » default: |
3068 » » » nodconst(nc, types[TUINT], w); | 3053 » » » » return; |
3069 » » » n2 = nod(ORSH, n1, nc); | 3054 » » » case TUINT8: |
3070 » » » 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)); |
3071 | 3073 |
3072 // shift by m.s | 3074 // shift by m.s |
3073 nc = nod(OXXX, N, N); | 3075 nc = nod(OXXX, N, N); |
3074 nodconst(nc, types[TUINT], m.s); | 3076 nodconst(nc, types[TUINT], m.s); |
3075 » » » n = conv(nod(ORSH, n3, nc), nl->type); | 3077 » » » n = conv(nod(ORSH, n2, nc), nl->type); |
3076 } else { | 3078 } else { |
3077 » » » // n = (n1>>w) >> m.s | 3079 » » » // n = n1 >> m.s |
3078 nc = nod(OXXX, N, N); | 3080 nc = nod(OXXX, N, N); |
3079 » » » nodconst(nc, types[TUINT], w+m.s); | 3081 » » » nodconst(nc, types[TUINT], m.s); |
3080 » » » n = conv(nod(ORSH, n1, nc), nl->type); | 3082 » » » n = nod(ORSH, n1, nc); |
3081 } | 3083 } |
3082 break; | 3084 break; |
3083 | 3085 |
3084 case TINT8: | 3086 case TINT8: |
3085 case TINT16: | 3087 case TINT16: |
3086 case TINT32: | 3088 case TINT32: |
3087 » » // n1 = nl * magic. | 3089 » » // n1 = nl * magic >> w |
3088 nc = nod(OXXX, N, N); | 3090 nc = nod(OXXX, N, N); |
3089 » » nodconst(nc, twide, m.sm); | 3091 » » nodconst(nc, nl->type, m.sm); |
3090 » » n1 = nod(OMUL, conv(nl, twide), nc); | 3092 » » n1 = nod(OMUL, nl, nc); |
3091 » » // take the high part with an arithmetic shift. | 3093 » » typecheck(&n1, Erv); |
3092 » » nc = nod(OXXX, N, N); | 3094 » » n1->op = OHMUL; |
3093 » » nodconst(nc, types[TUINT], w); | |
3094 » » n2 = conv(nod(ORSH, n1, nc), nl->type); | |
3095 if(m.sm < 0) { | 3095 if(m.sm < 0) { |
3096 // add the numerator. | 3096 // add the numerator. |
3097 » » » n2 = nod(OADD, n2, nl); | 3097 » » » n1 = nod(OADD, n1, nl); |
3098 } | 3098 } |
3099 // shift by m.s | 3099 // shift by m.s |
3100 nc = nod(OXXX, N, N); | 3100 nc = nod(OXXX, N, N); |
3101 nodconst(nc, types[TUINT], m.s); | 3101 nodconst(nc, types[TUINT], m.s); |
3102 » » n3 = conv(nod(ORSH, n2, nc), nl->type); | 3102 » » n2 = conv(nod(ORSH, n1, nc), nl->type); |
3103 // add 1 iff n1 is negative. | 3103 // add 1 iff n1 is negative. |
3104 nc = nod(OXXX, N, N); | 3104 nc = nod(OXXX, N, N); |
3105 nodconst(nc, types[TUINT], w-1); | 3105 nodconst(nc, types[TUINT], w-1); |
3106 » » n4 = nod(ORSH, nl, nc); // n4 = -1 iff n1 is negative. | 3106 » » n3 = nod(ORSH, nl, nc); // n4 = -1 iff n1 is negative. |
3107 » » n = nod(OSUB, n3, n4); | 3107 » » n = nod(OSUB, n2, n3); |
3108 // apply sign. | 3108 // apply sign. |
3109 if(m.sd < 0) | 3109 if(m.sd < 0) |
3110 n = nod(OMINUS, n, N); | 3110 n = nod(OMINUS, n, N); |
3111 break; | 3111 break; |
3112 } | 3112 } |
3113 goto ret; | 3113 goto ret; |
3114 | 3114 |
3115 longmod: | 3115 longmod: |
3116 // rewrite as A%B = A - (A/B*B). | 3116 // rewrite as A%B = A - (A/B*B). |
3117 n1 = nod(ODIV, nl, nr); | 3117 n1 = nod(ODIV, nl, nr); |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3223 yyerror("tracked field must be in named struct type"); | 3223 yyerror("tracked field must be in named struct type"); |
3224 if(!exportname(field->sym->name)) | 3224 if(!exportname(field->sym->name)) |
3225 yyerror("tracked field must be exported (upper case)"); | 3225 yyerror("tracked field must be exported (upper case)"); |
3226 | 3226 |
3227 l = typ(0); | 3227 l = typ(0); |
3228 l->type = field; | 3228 l->type = field; |
3229 l->down = curfn->paramfld; | 3229 l->down = curfn->paramfld; |
3230 curfn->paramfld = l; | 3230 curfn->paramfld = l; |
3231 } | 3231 } |
3232 | 3232 |
LEFT | RIGHT |