OLD | NEW |
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 #undef EXTERN | 5 #undef EXTERN |
6 #define EXTERN | 6 #define EXTERN |
7 #include <u.h> | 7 #include <u.h> |
8 #include <libc.h> | 8 #include <libc.h> |
9 #include "gg.h" | 9 #include "gg.h" |
10 #include "opt.h" | 10 #include "opt.h" |
(...skipping 583 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
594 } | 594 } |
595 | 595 |
596 /* | 596 /* |
597 * generate division according to op, one of: | 597 * generate division according to op, one of: |
598 * res = nl / nr | 598 * res = nl / nr |
599 * res = nl % nr | 599 * res = nl % nr |
600 */ | 600 */ |
601 void | 601 void |
602 cgen_div(int op, Node *nl, Node *nr, Node *res) | 602 cgen_div(int op, Node *nl, Node *nr, Node *res) |
603 { | 603 { |
604 » Node n1, n2, n3, savl, savr; | 604 » Node n1, n2, n3; |
605 » Node ax, dx, oldax, olddx; | 605 » int w, a; |
606 » int n, w, s, a; | |
607 Magic m; | 606 Magic m; |
608 | 607 |
609 if(nl->ullman >= UINF) { | |
610 tempname(&savl, nl->type); | |
611 cgen(nl, &savl); | |
612 nl = &savl; | |
613 } | |
614 if(nr->ullman >= UINF) { | |
615 tempname(&savr, nr->type); | |
616 cgen(nr, &savr); | |
617 nr = &savr; | |
618 } | |
619 | |
620 if(nr->op != OLITERAL) | 608 if(nr->op != OLITERAL) |
621 goto longdiv; | 609 goto longdiv; |
| 610 w = nl->type->width*8; |
622 | 611 |
623 » // special cases of mod/div | 612 » // Front end handled 32-bit division. We only need to handle 64-bit. |
624 » // by a constant | |
625 » w = nl->type->width*8; | |
626 » s = 0; | |
627 » n = powtwo(nr); | |
628 » if(n >= 1000) { | |
629 » » // negative power of 2 | |
630 » » s = 1; | |
631 » » n -= 1000; | |
632 » } | |
633 | |
634 » if(n+1 >= w) { | |
635 » » // just sign bit | |
636 » » goto longdiv; | |
637 » } | |
638 | |
639 » if(n < 0) | |
640 » » goto divbymul; | |
641 » switch(n) { | |
642 » case 0: | |
643 » » // divide by 1 | |
644 » » regalloc(&n1, nl->type, res); | |
645 » » cgen(nl, &n1); | |
646 » » if(op == OMOD) { | |
647 » » » gins(optoas(OXOR, nl->type), &n1, &n1); | |
648 » » } else | |
649 » » if(s) | |
650 » » » gins(optoas(OMINUS, nl->type), N, &n1); | |
651 » » gmove(&n1, res); | |
652 » » regfree(&n1); | |
653 » » return; | |
654 » case 1: | |
655 » » // divide by 2 | |
656 » » if(op == OMOD) { | |
657 » » » if(issigned[nl->type->etype]) | |
658 » » » » goto longmod; | |
659 » » » regalloc(&n1, nl->type, res); | |
660 » » » cgen(nl, &n1); | |
661 » » » nodconst(&n2, nl->type, 1); | |
662 » » » gins(optoas(OAND, nl->type), &n2, &n1); | |
663 » » » gmove(&n1, res); | |
664 » » » regfree(&n1); | |
665 » » » return; | |
666 » » } | |
667 » » regalloc(&n1, nl->type, res); | |
668 » » cgen(nl, &n1); | |
669 » » if(!issigned[nl->type->etype]) | |
670 » » » break; | |
671 | |
672 » » // develop -1 iff nl is negative | |
673 » » regalloc(&n2, nl->type, N); | |
674 » » gmove(&n1, &n2); | |
675 » » nodconst(&n3, nl->type, w-1); | |
676 » » gins(optoas(ORSH, nl->type), &n3, &n2); | |
677 » » gins(optoas(OSUB, nl->type), &n2, &n1); | |
678 » » regfree(&n2); | |
679 » » break; | |
680 » default: | |
681 » » if(op == OMOD) { | |
682 » » » if(issigned[nl->type->etype]) | |
683 » » » » goto longmod; | |
684 » » » regalloc(&n1, nl->type, res); | |
685 » » » cgen(nl, &n1); | |
686 » » » nodconst(&n2, nl->type, mpgetfix(nr->val.u.xval)-1); | |
687 » » » if(!smallintconst(&n2)) { | |
688 » » » » regalloc(&n3, nl->type, N); | |
689 » » » » gmove(&n2, &n3); | |
690 » » » » gins(optoas(OAND, nl->type), &n3, &n1); | |
691 » » » » regfree(&n3); | |
692 » » » } else | |
693 » » » » gins(optoas(OAND, nl->type), &n2, &n1); | |
694 » » » gmove(&n1, res); | |
695 » » » regfree(&n1); | |
696 » » » return; | |
697 » » } | |
698 » » regalloc(&n1, nl->type, res); | |
699 » » cgen(nl, &n1); | |
700 » » if(!issigned[nl->type->etype]) | |
701 » » » break; | |
702 | |
703 » » // develop (2^k)-1 iff nl is negative | |
704 » » regalloc(&n2, nl->type, N); | |
705 » » gmove(&n1, &n2); | |
706 » » nodconst(&n3, nl->type, w-1); | |
707 » » gins(optoas(ORSH, nl->type), &n3, &n2); | |
708 » » nodconst(&n3, nl->type, w-n); | |
709 » » gins(optoas(ORSH, tounsigned(nl->type)), &n3, &n2); | |
710 » » gins(optoas(OADD, nl->type), &n2, &n1); | |
711 » » regfree(&n2); | |
712 » » break; | |
713 » } | |
714 » nodconst(&n2, nl->type, n); | |
715 » gins(optoas(ORSH, nl->type), &n2, &n1); | |
716 » if(s) | |
717 » » gins(optoas(OMINUS, nl->type), N, &n1); | |
718 » gmove(&n1, res); | |
719 » regfree(&n1); | |
720 » return; | |
721 | |
722 divbymul: | |
723 // try to do division by multiply by (2^w)/d | 613 // try to do division by multiply by (2^w)/d |
724 // see hacker's delight chapter 10 | 614 // see hacker's delight chapter 10 |
725 switch(simtype[nl->type->etype]) { | 615 switch(simtype[nl->type->etype]) { |
726 default: | 616 default: |
727 goto longdiv; | 617 goto longdiv; |
728 | 618 |
729 case TUINT8: | |
730 case TUINT16: | |
731 case TUINT32: | |
732 case TUINT64: | 619 case TUINT64: |
733 m.w = w; | 620 m.w = w; |
734 m.ud = mpgetfix(nr->val.u.xval); | 621 m.ud = mpgetfix(nr->val.u.xval); |
735 umagic(&m); | 622 umagic(&m); |
736 if(m.bad) | 623 if(m.bad) |
737 break; | 624 break; |
738 if(op == OMOD) | 625 if(op == OMOD) |
739 goto longmod; | 626 goto longmod; |
740 | 627 |
741 » » regalloc(&n1, nl->type, N); | 628 » » cgenr(nl, &n1, N); |
742 » » cgen(nl, &n1);» » » » // num -> reg(n1) | |
743 | |
744 » » savex(D_AX, &ax, &oldax, res, nl->type); | |
745 » » savex(D_DX, &dx, &olddx, res, nl->type); | |
746 | |
747 nodconst(&n2, nl->type, m.um); | 629 nodconst(&n2, nl->type, m.um); |
748 » » gmove(&n2, &ax);» » » // const->ax | 630 » » regalloc(&n3, nl->type, res); |
749 | 631 » » cgen_hmul(&n1, &n2, &n3); |
750 » » gins(optoas(OHMUL, nl->type), &n1, N);» // imul reg | |
751 » » if(w == 8) { | |
752 » » » // fix up 8-bit multiply | |
753 » » » Node ah, dl; | |
754 » » » nodreg(&ah, types[TUINT8], D_AH); | |
755 » » » nodreg(&dl, types[TUINT8], D_DL); | |
756 » » » gins(AMOVB, &ah, &dl); | |
757 » » } | |
758 | 632 |
759 if(m.ua) { | 633 if(m.ua) { |
760 // need to add numerator accounting for overflow | 634 // need to add numerator accounting for overflow |
761 » » » gins(optoas(OADD, nl->type), &n1, &dx); | 635 » » » gins(optoas(OADD, nl->type), &n1, &n3); |
762 nodconst(&n2, nl->type, 1); | 636 nodconst(&n2, nl->type, 1); |
763 » » » gins(optoas(ORROTC, nl->type), &n2, &dx); | 637 » » » gins(optoas(ORROTC, nl->type), &n2, &n3); |
764 nodconst(&n2, nl->type, m.s-1); | 638 nodconst(&n2, nl->type, m.s-1); |
765 » » » gins(optoas(ORSH, nl->type), &n2, &dx); | 639 » » » gins(optoas(ORSH, nl->type), &n2, &n3); |
766 } else { | 640 } else { |
767 nodconst(&n2, nl->type, m.s); | 641 nodconst(&n2, nl->type, m.s); |
768 » » » gins(optoas(ORSH, nl->type), &n2, &dx);»// shift dx | 642 » » » gins(optoas(ORSH, nl->type), &n2, &n3);»// shift dx |
769 } | 643 } |
770 | 644 |
771 | 645 » » gmove(&n3, res); |
772 regfree(&n1); | 646 regfree(&n1); |
773 » » gmove(&dx, res); | 647 » » regfree(&n3); |
774 | |
775 » » restx(&ax, &oldax); | |
776 » » restx(&dx, &olddx); | |
777 return; | 648 return; |
778 | 649 |
779 case TINT8: | |
780 case TINT16: | |
781 case TINT32: | |
782 case TINT64: | 650 case TINT64: |
783 m.w = w; | 651 m.w = w; |
784 m.sd = mpgetfix(nr->val.u.xval); | 652 m.sd = mpgetfix(nr->val.u.xval); |
785 smagic(&m); | 653 smagic(&m); |
786 if(m.bad) | 654 if(m.bad) |
787 break; | 655 break; |
788 if(op == OMOD) | 656 if(op == OMOD) |
789 goto longmod; | 657 goto longmod; |
790 | 658 |
791 » » regalloc(&n1, nl->type, N); | 659 » » cgenr(nl, &n1, res); |
792 » » cgen(nl, &n1);» » » » // num -> reg(n1) | |
793 | |
794 » » savex(D_AX, &ax, &oldax, res, nl->type); | |
795 » » savex(D_DX, &dx, &olddx, res, nl->type); | |
796 | |
797 nodconst(&n2, nl->type, m.sm); | 660 nodconst(&n2, nl->type, m.sm); |
798 » » gmove(&n2, &ax);» » » // const->ax | 661 » » regalloc(&n3, nl->type, N); |
799 | 662 » » cgen_hmul(&n1, &n2, &n3); |
800 » » gins(optoas(OHMUL, nl->type), &n1, N);» // imul reg | |
801 » » if(w == 8) { | |
802 » » » // fix up 8-bit multiply | |
803 » » » Node ah, dl; | |
804 » » » nodreg(&ah, types[TUINT8], D_AH); | |
805 » » » nodreg(&dl, types[TUINT8], D_DL); | |
806 » » » gins(AMOVB, &ah, &dl); | |
807 » » } | |
808 | 663 |
809 if(m.sm < 0) { | 664 if(m.sm < 0) { |
810 // need to add numerator | 665 // need to add numerator |
811 » » » gins(optoas(OADD, nl->type), &n1, &dx); | 666 » » » gins(optoas(OADD, nl->type), &n1, &n3); |
812 } | 667 } |
813 | 668 |
814 nodconst(&n2, nl->type, m.s); | 669 nodconst(&n2, nl->type, m.s); |
815 » » gins(optoas(ORSH, nl->type), &n2, &dx);»// shift dx | 670 » » gins(optoas(ORSH, nl->type), &n2, &n3);»// shift n3 |
816 | 671 |
817 nodconst(&n2, nl->type, w-1); | 672 nodconst(&n2, nl->type, w-1); |
818 gins(optoas(ORSH, nl->type), &n2, &n1); // -1 iff num is neg | 673 gins(optoas(ORSH, nl->type), &n2, &n1); // -1 iff num is neg |
819 » » gins(optoas(OSUB, nl->type), &n1, &dx);»// added | 674 » » gins(optoas(OSUB, nl->type), &n1, &n3);»// added |
820 | 675 |
821 if(m.sd < 0) { | 676 if(m.sd < 0) { |
822 // this could probably be removed | 677 // this could probably be removed |
823 // by factoring it into the multiplier | 678 // by factoring it into the multiplier |
824 » » » gins(optoas(OMINUS, nl->type), N, &dx); | 679 » » » gins(optoas(OMINUS, nl->type), N, &n3); |
825 } | 680 } |
826 | 681 |
| 682 gmove(&n3, res); |
827 regfree(&n1); | 683 regfree(&n1); |
828 » » gmove(&dx, res); | 684 » » regfree(&n3); |
829 | |
830 » » restx(&ax, &oldax); | |
831 » » restx(&dx, &olddx); | |
832 return; | 685 return; |
833 } | 686 } |
834 goto longdiv; | 687 goto longdiv; |
835 | 688 |
836 longdiv: | 689 longdiv: |
837 // division and mod using (slow) hardware instruction | 690 // division and mod using (slow) hardware instruction |
838 dodiv(op, nl, nr, res); | 691 dodiv(op, nl, nr, res); |
839 return; | 692 return; |
840 | 693 |
841 longmod: | 694 longmod: |
(...skipping 16 matching lines...) Expand all Loading... |
858 regfree(&n3); | 711 regfree(&n3); |
859 } else | 712 } else |
860 gins(a, nr, &n2); | 713 gins(a, nr, &n2); |
861 gins(optoas(OSUB, nl->type), &n2, &n1); | 714 gins(optoas(OSUB, nl->type), &n2, &n1); |
862 gmove(&n1, res); | 715 gmove(&n1, res); |
863 regfree(&n1); | 716 regfree(&n1); |
864 regfree(&n2); | 717 regfree(&n2); |
865 } | 718 } |
866 | 719 |
867 /* | 720 /* |
| 721 * generate high multiply: |
| 722 * res = (nl*nr) >> width |
| 723 */ |
| 724 void |
| 725 cgen_hmul(Node *nl, Node *nr, Node *res) |
| 726 { |
| 727 Type *t; |
| 728 int a; |
| 729 Node n1, n2, ax, dx, *tmp; |
| 730 |
| 731 t = nl->type; |
| 732 a = optoas(OHMUL, t); |
| 733 if(nl->ullman < nr->ullman) { |
| 734 tmp = nl; |
| 735 nl = nr; |
| 736 nr = tmp; |
| 737 } |
| 738 cgenr(nl, &n1, res); |
| 739 cgenr(nr, &n2, N); |
| 740 nodreg(&ax, t, D_AX); |
| 741 gmove(&n1, &ax); |
| 742 gins(a, &n2, N); |
| 743 regfree(&n2); |
| 744 regfree(&n1); |
| 745 |
| 746 if(t->width == 1) { |
| 747 // byte multiply behaves differently. |
| 748 nodreg(&ax, t, D_AH); |
| 749 nodreg(&dx, t, D_DL); |
| 750 gmove(&ax, &dx); |
| 751 } |
| 752 nodreg(&dx, t, D_DX); |
| 753 gmove(&dx, res); |
| 754 } |
| 755 |
| 756 /* |
868 * generate shift according to op, one of: | 757 * generate shift according to op, one of: |
869 * res = nl << nr | 758 * res = nl << nr |
870 * res = nl >> nr | 759 * res = nl >> nr |
871 */ | 760 */ |
872 void | 761 void |
873 cgen_shift(int op, int bounded, Node *nl, Node *nr, Node *res) | 762 cgen_shift(int op, int bounded, Node *nl, Node *nr, Node *res) |
874 { | 763 { |
875 Node n1, n2, n3, n4, n5, cx, oldcx; | 764 Node n1, n2, n3, n4, n5, cx, oldcx; |
876 int a, rcx; | 765 int a, rcx; |
877 Prog *p1; | 766 Prog *p1; |
(...skipping 179 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1057 gins(ASTOSB, N, N); // STOB AL,*(DI)+ | 946 gins(ASTOSB, N, N); // STOB AL,*(DI)+ |
1058 } else | 947 } else |
1059 while(c > 0) { | 948 while(c > 0) { |
1060 gins(ASTOSB, N, N); // STOB AL,*(DI)+ | 949 gins(ASTOSB, N, N); // STOB AL,*(DI)+ |
1061 c--; | 950 c--; |
1062 } | 951 } |
1063 | 952 |
1064 restx(&n1, &oldn1); | 953 restx(&n1, &oldn1); |
1065 restx(&ax, &oldax); | 954 restx(&ax, &oldax); |
1066 } | 955 } |
OLD | NEW |