1.6.1.1.1.1.4. Addition and minus
Then for other operation, back in int_const_binop.
int_const_binop (continue)
1239 case PLUS_EXPR:
1240 overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1241 break;
1242
1243 case MINUS_EXPR:
1244 neg_double (int2l, int2h, &low, &hi);
1245 add_double (int1l, int1h, low, hi, &low, &hi);
1246 overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1247 break;
1248
1249 case MULT_EXPR:
1250 overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1251 break;
1252
1253 case TRUNC_DIV_EXPR:
1254 case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1255 case EXACT_DIV_EXPR:
1256
1257 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1258 && ! TREE_CONSTANT_OVERFLOW (arg1)
1259 && ! TREE_CONSTANT_OVERFLOW (arg2)
1260 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1261 {
1262 if (code == CEIL_DIV_EXPR)
1263 int1l += int2l - 1;
1264
1265 low = int1l / int2l, hi = 0;
1266 break;
1267 }
1268
1269
add_double accepts two operands, in its parameters, l1 a006Ed h1 are the low and high part of the first operand, so are l2 and h2 for second operand.
261 int
262 add_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, in fold-const.c
263 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
264 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
265 {
266 unsigned HOST_WIDE_INT l;
267 HOST_WIDE_INT h;
268
269 l = l1 + l2;
270 h = h1 + h2 + (l < l1);
271
272 *lv = l;
273 *hv = h;
274 return OVERFLOW_SUM_SIGN (h1, h2, h);
275 }
Above, if the sum of the low parts is smaller, it means carrier is produced for the sum, takes it into the high part at line 270. For high part, such case means overflow. Overflow occurs if A and B have the same sign, but A and SUM differ in sign. Below macro detects overflow by this way.
136 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
neg_double is alittle tricky, it is because of the 2 complement reprensentation.
282 int
283 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, in fold-const.c
284 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
285 {
286 if (l1 == 0)
287 {
288 *lv = 0;
289 *hv = - h1;
290 return (*hv & h1) < 0;
291 }
292 else
293 {
294 *lv = -l1;
295 *hv = ~h1;
296 return 0;
297 }
298 }
1.6.1.1.1.1.5. Multiplication
While to implement effective and correct multiplication, it must carefully to deal with the problem of overflow as multiplication may double the size of operands.
307 int
308 mul_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, in fold-const.c
309 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
310 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
311 {
312 HOST_WIDE_INT arg1[4];
313 HOST_WIDE_INT arg2[4];
314 HOST_WIDE_INT prod[4 * 2];
315 unsigned HOST_WIDE_INT carry;
316 int i, j, k;
317 unsigned HOST_WIDE_INT toplow, neglow;
318 HOST_WIDE_INT tophigh, neghigh;
319
320 encode (arg1, l1, h1);
321 encode (arg2, l2, h2);
322
323 memset (prod, 0, sizeof prod);
324
325 for (i = 0; i < 4; i++)
326 {
327 carry = 0;
328 for (j = 0; j < 4; j++)
329 {
330 k = i + j;
331
332 carry += arg1[i] * arg2[j];
333
334 carry += prod[k];
335 prod[k] = LOWPART (carry);
336 carry = HIGHPART (carry);
337 }
338 prod[i + 4] = carry;
339 }
340
341 decode (prod, lv, hv);
342
343
345 decode (prod + 4, &toplow, &tophigh);
346 if (h1 < 0)
347 {
348 neg_double (l2, h2, &neglow, &neghigh);
349 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
350 }
351 if (h2 < 0)
352 {
353 neg_double (l1, h1, &neglow, &neghigh);
354 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
355 }
356 return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
357 }
To handle the problem of overflow, encode at line 320 and 321 will put the operands into the buffer of double size.
153 static void in fold-const.c
154 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
155 {
156 words[0] = LOWPART (low);
157 words[1] = HIGHPART (low);
158 words[2] = LOWPART (hi);
159 words[3] = HIGHPART (hi);
160 }
To see the operation in FOR loop at line 325 clearly, using following example to demonstrate the procedure. Assuming multiplication (decimal integer of size 2, and the result will be temperarily saved in buffer of size 4):
65 (then h1 = 6, l1 = 5)
X 23 (then h2 = 2, l2 = 3)
l1 * l2 (15)
+ carry (0)
+ prod[0+0] (0)
carry (1) ß 15 à prod[0+0] (5) (end of l1 * l2)
h1 * l2 (18)
+ carry (1)
+ prod[1+0] (0)
carry (1) ß19 à prod[1+0] (9) (end of h1 * l2, prod[0+2] = carry = 1)
l1 * h2 (10)
+ carry (0)
+ prod[0+1] (9)
carry (1) ß 19 à prod[0+1] (8) (end of l1 * h2)
h1 * h2 (12)
+ carry (1)
+ prod[1+1] (1)
carry (1) ß 14 à prod[1+1] (4) (end of h1 * h2, prod[1+2] = carry = 1)
lowpart = prod[0] + prod[1]*10 = 95
highpart = prod[2] + prod[3]*10 = 14;
result = 1495 (overflow for integer of size 2)
figure 1290 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1291 && ! TREE_CONSTANT_OVERFLOW (arg1)
1292 && ! TREE_CONSTANT_OVERFLOW (arg2)
1293 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1294 {
1295 if (code == CEIL_MOD_EXPR)
1296 int1l += int2l - 1;
1297 low = int1l % int2l, hi = 0;
1298 break;
1299 }
1300
1301
1302
1303 case ROUND_MOD_EXPR:
1304 overflow = div_and_round_double (code, uns,
1305 int1l, int1h, int2l, int2h,
1306 &garbagel, &garbageh, &low, &hi);
1307 break;
1308
1309 case MIN_EXPR:
1310 case MAX_EXPR:
1311 if (uns)
1312 low = (((unsigned HOST_WIDE_INT) int1h
1313 < (unsigned HOST_WIDE_INT) int2h)
1314 || (((unsigned HOST_WIDE_INT) int1h
1315 == (unsigned HOST_WIDE_INT) int2h)
1316 && int1l < int2l));
1317 else
1318 low = (int1h < int2h
1319 || (int1h == int2h && int1l < int2l));
1320
1321 if (low == (code == MIN_EXPR))
1322 low = int1l, hi = int1h;
1323 else
1324 low = int2l, hi = int2h;
1325 break;
1326
1327 default:
1328 abort ();
1329 }
The parameters of div_and_round_double are: code – code of operation, uns – the operation is unsigned or not, lnum_orig and hnum_orig – dividend, lden_orig and hden_orig – divisor, lquo and hquo – saved quotient, lrem and hrem – saved remainder.
540 int
541 div_and_round_double (enum tree_code code, int uns, in fold-const.c
542 unsigned HOST_WIDE_INT lnum_orig,
543 HOST_WIDE_INT hnum_orig,
544 unsigned HOST_WIDE_INT lden_orig,
545 HOST_WIDE_INT hden_orig,
546 unsigned HOST_WIDE_INT *lquo,
547 HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
548 HOST_WIDE_INT *hrem)
549 {
550 int quo_neg = 0;
551 HOST_WIDE_INT num[4 + 1];
552 HOST_WIDE_INT den[4], quo[4];
553 int i, j;
554 unsigned HOST_WIDE_INT work;
555 unsigned HOST_WIDE_INT carry = 0;
556 unsigned HOST_WIDE_INT lnum = lnum_orig;
557 HOST_WIDE_INT hnum = hnum_orig;
558 unsigned HOST_WIDE_INT lden = lden_orig;
559 HOST_WIDE_INT hden = hden_orig;
560 int overflow = 0;
561
562 if (hden == 0 && lden == 0)
563 overflow = 1, lden = 1;
564
565
566 if (!uns)
567 {
568 if (hnum < 0)
569 {
570 quo_neg = ~ quo_neg;
571
572 if (neg_double (lnum, hnum, &lnum, &hnum)
573 && ((HOST_WIDE_INT) lden & hden) == -1)
574 overflow = 1;
575 }
576 if (hden < 0)
577 {
578 quo_neg = ~ quo_neg;
579 neg_double (lden, hden, &lden, &hden);
580 }
581 }
582
583 if (hnum == 0 && hden == 0)
584 {
585 *hquo = *hrem = 0;
586
587 *lquo = lnum / lden;
588 goto finish_up;
589 }
590
591 if (hnum == 0)
592 {
593
594 *hquo = *lquo = 0;
595 *hrem = hnum;
596 *lrem = lnum;
597 goto finish_up;
598 }
599
600 memset (quo, 0, sizeof quo);
601
602 memset (num, 0, sizeof num);
603 memset (den, 0, sizeof den);
604
605 encode (num, lnum, hnum);
606 encode (den, lden, hden);
607
608
609 if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
610 {
611
612 for (i = 4 - 1; i >= 0; i--)
613 {
614 work = num[i] + carry * BASE;
615 quo[i] = work / lden;
616 carry = work % lden;
617 }
618 }
619 else
620 {
621
623 int num_hi_sig, den_hi_sig;
624 unsigned HOST_WIDE_INT quo_est, scale;
625
626
627 for (i = 4 - 1;; i--)
628 if (den[i] != 0)
629 {
630 den_hi_sig = i;
631 break;
632 }
633
634
636
637 scale = BASE / (den[den_hi_sig] + 1);
638 if (scale > 1)
639 {
640 carry = 0;
641 for (i = 0; i <= 4 - 1; i++)
642 {
643 work = (num[i] * scale) + carry;
644 num[i] = LOWPART (work);
645 carry = HIGHPART (work);
646 }
647
648 num[4] = carry;
649 carry = 0;
650 for (i = 0; i <= 4 - 1; i++)
651 {
652 work = (den[i] * scale) + carry;
653 den[i] = LOWPART (work);
654 carry = HIGHPART (work);
655 if (den[i] != 0) den_hi_sig = i;
656 }
657 }
Code sinppet begins from line 637 is interesting and important for the algorithm applied. It scales both divsor and divident so so to the most significant part of divisor is larger than Base/2. The reason to do that, consider following expressions:
abc * d and abc * (d+1), the later can be transformed to abc * d + abc, if a is larger than Base/2 (for our exmaple of decimal value, it is 5), the extra abc in the later expression will cause extra carry in the result, it can be distinguished with the former easily.
div_and_round_double (continue)
659 num_hi_sig = 4;
660
661
662 for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
663 {
664
667 unsigned HOST_WIDE_INT tmp;
668
669 num_hi_sig = i + den_hi_sig + 1;
670 work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
671 if (num[num_hi_sig] != den[den_hi_sig])
672 quo_est = work / den[den_hi_sig];
673 else
674 quo_est = BASE - 1;
675
676
677 tmp = work - quo_est * den[den_hi_sig];
678 if (tmp < BASE
679 && (den[den_hi_sig - 1] * quo_est
680 > (tmp * BASE + num[num_hi_sig - 2])))
681 quo_est--;
682
683
686
687 carry = 0;
688 for (j = 0; j <= den_hi_sig; j++)
689 {
690 work = quo_est * den[j] + carry;
691 carry = HIGHPART (work);
692 work = num[i + j] - LOWPART (work);
693 num[i + j] = LOWPART (work);
694 carry += HIGHPART (work) != 0;
695 }
696
697
699 if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
700 {
701 quo_est--;
702 carry = 0;
703 for (j = 0; j <= den_hi_sig; j++)
704 {
705 work = num[i + j] + den[j] + carry;
706 carry = HIGHPART (work);
707 num[i + j] = LOWPART (work);
708 }
709
710 num [num_hi_sig] += carry;
711 }
712
713
714 quo[i] = quo_est;
715 }
716 }
Integrating above code snippet, consider following example: 789 / 125 (note that base is 10 for the example).
After scaling, the expression transformed into: 3945 / 725, and we get following arrays:
num[4] = 0, num[3] = 3, num[2] = 9, num[1] = 4, num[0] = 5
den[3] = 0, den[2] = 7, den[1] = 2, den[0] = 5, den_hi_sig = 2.
For first loop at line 662, i = 4-2-1 = 2, the quotient will not contain more than 2 digits. For this loop, quo[1] = 0. For second loop, it works as following.
3945 (num[0])
carry ß 25 (725 *5)
0 à num[0]
3940
carryß10 (725 *5)
2 (carry)
2 à num[1]
3900
carryß35 (725 * 5)
1 (carry)
3 à num[2]
3000
3 (carry)
0 à num[3]
quot[0] = 5, quot[1] = 0
figure 722 if (quo_neg)
723 neg_double (*lquo, *hquo, lquo, hquo);
724
725
726 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
727 neg_double (*lrem, *hrem, lrem, hrem);
728 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
729
730 switch (code)
731 {
732 case TRUNC_DIV_EXPR:
733 case TRUNC_MOD_EXPR:
734 case EXACT_DIV_EXPR:
735 return overflow;
736
737 case FLOOR_DIV_EXPR:
738 case FLOOR_MOD_EXPR:
739 if (quo_neg && (*lrem != 0 || *hrem != 0))
740 {
741
742 add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1,
743 lquo, hquo);
744 }
745 else
746 return overflow;
747 break;
748
749 case CEIL_DIV_EXPR:
750 case CEIL_MOD_EXPR:
751 if (!quo_neg && (*lrem != 0 || *hrem != 0))
752 {
753 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
754 lquo, hquo);
755 }
756 else
757 return overflow;
758 break;
759
760 case ROUND_DIV_EXPR:
761 case ROUND_MOD_EXPR:
762 {
763 unsigned HOST_WIDE_INT labs_rem = *lrem;
764 HOST_WIDE_INT habs_rem = *hrem;
765 unsigned HOST_WIDE_INT labs_den = lden, ltwice;
766 HOST_WIDE_INT habs_den = hden, htwice;
767
768
769 if (*hrem < 0)
770 neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
771 if (hden < 0)
772 neg_double (lden, hden, &labs_den, &habs_den);
773
774
775 mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
776 labs_rem, habs_rem, <wice, &htwice);
777
778 if (((unsigned HOST_WIDE_INT) habs_den
779 < (unsigned HOST_WIDE_INT) htwice)
780 || (((unsigned HOST_WIDE_INT) habs_den
781 == (unsigned HOST_WIDE_INT) htwice)
782 && (labs_den < ltwice)))
783 {
784 if (*hquo < 0)
785
786 add_double (*lquo, *hquo,
787 (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
788 else
789
790 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
791 lquo, hquo);
792 }
793 else
794 return overflow;
795 }
796 break;
797
798 default:
799 abort ();
800 }
801
802
803 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
804 neg_double (*lrem, *hrem, lrem, hrem);
805 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
806 return overflow;
807 }
The rest of div_and_round_double adjusts the result according to the type of rounding.
![studio📍位址：15RegentStreetWoolloongabba,Brisbane,Queensland410[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)