کاهش قدرت

در ساخت کامپایلر ، کاهش قدرت یک روش بهینه سازی کامپایلر است که در آن عملیات های پر هزینه با عملیات معادل اما کم هزینه تر جایگزین می شوند. ^[۱] مثال برای کاهش قدرتی ضرب های "قوی" در داخل حلقه را به جمع های "ضعیف تر" تبدیل می کند – چیزی که غالباً در آدرس دهی آرایه اتفاق می افتد. (Cooper, Simpson & Vick 1995)

مثال هایی از کاهش قدرت عبارتند از:

جایگزینی ضرب در یک حلقه با یک جمع
جایگزینی توان در یک حلقه با ضرب

تجزیه و تحلیل کد[ویرایش]

بیشتر زمان اجرای برنامه به طور معمول در یک بخش کوچک از کد (به نام منطقه داغ ) سپری می شود ، و آن بخش از کد اغلب در داخل یک حلقه است که بارها و بارها اجرا می شود.

کامپایلر از روش هایی برای شناسایی حلقه ها و تشخیص ویژگی های مقادیر در آن حلقه ها استفاده می کند. برای کاهش قدرت ،به داده های زیر نیازمند است :

ثابت های حلقه(Loop invariants): مقادیری که در داخل حلقه تغییر نمی‌کنند.
متغیرهای القایی(induction variables): مقادیری که در داخل هر اجرای حلقه تغییر (مثل i در یک حلقه for) می کنند.

ثابت های حلقه(Loop invariants) در اصل درون یک حلقه ثابت هستند ، اما ممکن است مقدار آنها در خارج از حلقه تغییر کنند. متغیرهای القایی با مقادیر شناخته شده(خاصی) در حال تغییر هستند. شرایط نسبت به یک حلقه خاص است. هنگامی که حلقه ها تودرتو باشند ، یک متغیر القایی در یک حلقه بیرونی می تواند یک ثابت حلقه ای (Loop invariants) در یک حلقه داخلی باشد.

کاهش قدرت به دنبال عباراتی که شامل ثابت حلقه ای (Loop invariants)و متغیر القایی می گردد. برخی از این عبارات را می توان ساده سازی کرد. به عنوان مثال ، ضرب ثابت حلقه ای c و متغیر القایی i

c = 7;
for (i = 0; i < N; i++)
{
  y[i] = c * i;
}

می تواند با جمع های ضعیف تر پی در پی جایگزین شود

c = 7;
k = 0;
for (i = 0; i < N; i++)
{
  y[i] = k;
  k = k + c;
}

مثال روش کاهش قدرت[ویرایش]

در زیر مثالی وجود دارد که تمام ضرب های داخل حلقه که از محاسبات آدرس دهی فهرست بندی آرایه (array indexing address calculations)به وجود آمده اند با روش کاهش قدرت ،بهینه سازد.

یک حلقه ساده را تصور کنید که یک آرایه را به یک ماتریس هویت(identity matrix) می نشاند .

for (i = 0; i < n; i++)
{
  for (j = 0; j < n; j++)
  {
    A[i,j] = 0.0;
  }
  A[i,i] = 1.0;
}

کد واسطه[ویرایش]

کامپایلر کد زیر را به عنوان گزاره زیر میبیند :

0010 ; for (i = 0, i < n; i++)
0020  {
0030   r1 = #0            ; i = 0
0040 G0000:
0050   load r2, n           ; i < n
0060   cmp r1, r2
0070   bge G0001
0080
0090   ; for (j = 0; j < n; j++)
0100    {
0110      r3  = #0         ; j = 0
0120 G0002:
0130      load r4, n        ; j < n
0140      cmp r3, r4
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0180      load r7, n
0190      r8 = r1 * r7       ; calculate subscript i * n + j
0200      r9 = r8 + r3
0210      r10 = r9 * #8       ; calculate byte address
0220      fr3 = #0.0
0230      fstore fr3, A[r10]
0240
0250      r3 = r3 + #1       ; j++
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0300   load r12, n          ; calculate subscript i * n + i
0310   r13 = r1 * r12
0320   r14 = r13 + r1
0330   r15 = r14 * #8         ; calculate byte address
0340   fr4 = #1.0
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380   r1 = r1 + #1
0390   br G0000
0400  }
0410 G0001:

این کد آرایه 2 بعدی A را به عنوان یک آرایه 1 بعدی با ابعاد n * n تبدیل میکند ، به طوری که هر زمان که کد سطح بالا A [x ، y] را فرا میخواند ، از نظر داخلی(کامپایلر) A [(x * n) + y] برای هر مقدار معتبر x و y داده می شود.

بهینه سازی های دیگر[ویرایش]

کامپایلر شروع به انجام بسیاری از بهینه سازی های دیگر خواهد کرد – نه تنها کاهش قدرت. عباراتی که ثابت (invariant) در یک حلقه خارج از حلقه برافراشته(hoisted) هستند . ثابت ها را می توان در خارج از هر دو حلقه قرار داد - مانند ثبات های اعشاری fr3 و fr4. تشخیص اینکه برخی از متغیرها تغییر نمی‌کنند ، امکان ادغام ثبات ها را فراهم می آورد. n ثابت است ، بنابراین r2، r4، r7، r12 می توان آن ها را برافراشت و یا از بین برد. مقدار مشترک i * n در r8 و r13 (برافراشته)محاسبه می شود ، بنابراین آنها از بین می روند. درونی ترین حلقه (0120-0260) از 11 به 7 دستورالعمل میانی کاهش یافته است. تنها ضربی که در پایین ترین حلقه باقی مانده است ، ضرب 8 در خط 0210 است.

0010 ; for (i = 0, i < n; i++)
0020  {
0030   r1 = #0            ; i = 0
0050   load r2, n
0130 ;  load r4, n   killed; use r2
0180 ;  load r7, n   killed; use r2
0300 ;  load r12, n  killed; use r2
0220   fr3 = #0.0
0340   fr4 = #1.0
0040 G0000:
0060   cmp r1, r2           ; i < n
0070   bge G0001
0080
0190   r8 = r1 * r2         ; calculate subscript i * n
0310 ;  r13 = r1 * r2 killed; use r8  ; calculate subscript i * n
0090   ; for (j = 0; j < n; j++)
0100    {
0110      r3  = #0         ; j = 0
0120 G0002:
0140      cmp r3, r2        ; j < n
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0200      r9 = r8 + r3       ; calculate subscript i * n + j
0210      r10 = r9 * #8       ; calculate byte address
0230      fstore fr3, A[r10]
0240
0250      r3 = r3 + #1       ; j++
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0320   r14 = r8 + r1         ; calculate subscript i * n + i
0330   r15 = r14 * #8         ; calculate byte address
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380   r1 = r1 + #1
0390   br G0000
0400  }
0410 G0001:

برای بهینه سازی راه های بیشتری وجود دارد. ثبات r3 که متغیر اصلی است در درونی ترین حلقه (0140-0260) است. هر بار از طریق حلقه 1 عدد افزایش می یابد. ثبات r8 (که در درونی ترین حلقه ،ثابت (invariant )است) به r3 اضافه می شود. به جای استفاده از r3 ، کامپایلر می تواند r3 را از بین ببرد و از r9 استفاده کند. حلقه به جای اینکه توسط r3 = 0 تا n-1 کنترل شود ، می تواند توسط r9 = r8 + 0 تا r8 + n-1 کنترل شود. این عملیات چهار دستورالعمل را اضافه می کند و چهار دستورالعمل را از بین می برد ، اما اکنون یک دستورالعمل کمتر در داخل حلقه وجود دارد.

0110 ;    r3  = #0   killed    ; j = 0
0115      r9  = r8         ; new assignment
0117      r20 = r8 + r2      ; new limit
0120 G0002:
0140 ;    cmp r3, r2  killed    ; j < n
0145      cmp r9, r20        ; r8 + j < r8 + n = r20
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0200 ;    r9 = r8 + r3 killed    ; calculate subscript i * n + j
0210      r10 = r9 * #8       ; calculate byte address
0230      fstore fr3, A[r10]
0240
0250 ;    r3 = r3 + #1 killed    ; j++
0255      r9 = r9 + #1       ; new loop variable
0260      br G0002

اکنون r9 متغیر حلقه است ، ولی با ضرب 8 تعامل دارد. در اینجا ما می توانیم با روش کاهش قدرت بهینه سازی انجام دهیم. ضرب در 8 را می توان به جمع های پی در پی 8 کاهش داد. اکنون هیچ ضرب در داخل حلقه وجود ندارد.

0115      r9  = r8         ; new assignment
0117      r20 = r8 + r2      ; new limit
0118      r10 = r8 * #8      ; initial value of r10
0120 G0002:
0145      cmp r9, r20        ; r8 + j < r8 + n = r20
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0210 ;    r10 = r9 * #8  killed  ; calculate byte address
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0255      r9 = r9 + #1       ; loop variable
0260      br G0002

ثبات های r9 و r10 (= 8 * r9) هر دو دیگر مورد نیاز نیستند. r9 را می توان در داخل حلقه از بین برد. حلقه اکنون 5 دستورالعمل است.

0115 ;    r9  = r8     killed
0117      r20 = r8 + r2      ; limit
0118      r10 = r8 * #8      ; initial value of r10
0119      r22 = r20 * #8      ; new limit
0120 G0002:
0145 ;    cmp r9, r20    killed  ; r8 + j < r8 + n = r20
0147      cmp r10, r22       ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0255 ;    r9 = r9 + #1   killed  ; loop variable
0260      br G0002

حلقه بیرونی[ویرایش]

حال به کل کد نگاه میکنیم:

0010 ; for (i = 0, i < n; i++)
0020  {
0030   r1 = #0            ; i = 0
0050   load r2, n
0220   fr3 = #0.0
0340   fr4 = #1.0
0040 G0000:
0060   cmp r1, r2           ; i < n
0070   bge G0001
0080
0190   r8  = r1 * r2         ; calculate subscript i * n
0117   r20 = r8 + r2         ; limit
0118   r10 = r8 * #8         ; initial value of r10
0119   r22 = r20 * #8        ; new limit
0090   ; for (j = 0; j < n; j++)
0100    {
0120 G0002:
0147      cmp r10, r22       ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0320   r14 = r8 + r1         ; calculate subscript i * n + i
0330   r15 = r14 * #8         ; calculate byte address
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380   r1 = r1 + #1
0390   br G0000
0400  }
0410 G0001:

اکنون چهار ضرب در حلقه بیرونی وجود دارد که ثبات R1 را افزایش می دهند. ثبات r8 = r1*r2 در خط 0190 با روش کاهش قدرت میتواند قبل از ورود به حلقه (0055) و افزایشش توسط ثبات r2 در انتهای حلقه (0385) مقدار دهی شود .

مقدار r8 * 8 (با شماره 0118) می تواند با مقدار دهی اولیه آن (0056) با کاهش قدرت و افزودن 8 * r2 به آن هنگام افزایش r8 (0386) مقدار آن کاهش یابد.

ثبات r20 توسط متغیر ثابت R2 هر بار از طریق حلقه در 0117 خط افزایش می یابد. پس از افزایش ، در 8 ضرب می شود تا r22 در 0119 را بوجود آورد. این ضرب میتواند با روش کاهشی قدرتی با اضافه کردن 8 * r2در هر تکرار بار حلقه بهینه سازی شود.

0010 ; for (i = 0, i < n; i++)
0020  {
0030   r1 = #0            ; i = 0
0050   load r2, n
0220   fr3 = #0.0
0340   fr4 = #1.0
0055   r8 = r1 * r2         ; set initial value for r8
0056   r40 = r8 * #8         ; initial value for r8 * 8
0057   r30 = r2 * #8         ; increment for r40
0058   r20 = r8 + r2         ; copied from 0117
0058   r22 = r20 * #8         ; initial value of r22
0040 G0000:
0060   cmp r1, r2           ; i < n
0070   bge G0001
0080
0190 ; r8  = r1 * r2  killed    ; calculate subscript i * n
0117 ; r20 = r8 + r2  killed - dead code
0118   r10 = r40           ; strength reduced expression to r40
0119 ; r22 = r20 * #8  killed    ; strength reduced
0090   ; for (j = 0; j < n; j++)
0100    {
0120 G0002:
0147      cmp r10, r22       ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0320   r14 = r8 + r1         ; calculate subscript i * n + i
0330   r15 = r14 * #8         ; calculate byte address
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380   r1 = r1 + #1
0385   r8 = r8 + r2         ; strength reduce r8 = r1 * r2
0386   r40 = r40 + r30        ; strength reduce expression r8 * 8
0388   r22 = r22 + r30        ; strength reduce r22 = r20 * 8
0390   br G0000
0400  }
0410 G0001:

آخرین ضرب[ویرایش]

در آخر این دو حلقه ب که تنها با یک عمل ضرب (در 0330) در حلقه بیرونی و هیچ ضرب در حلقه درونی باقی می مانند.

0010 ; for (i = 0, i < n; i++)
0020  {
0030   r1 = #0            ; i = 0
0050   load r2, n
0220   fr3 = #0.0
0340   fr4 = #1.0
0055   r8 = r1 * r2         ; set initial value for r8
0056   r40 = r8 * #8         ; initial value for r8 * 8
0057   r30 = r2 * #8         ; increment for r40
0058   r20 = r8 + r2         ; copied from 0117
0058   r22 = r20 * #8         ; initial value of r22
0040 G0000:
0060   cmp r1, r2           ; i < n
0070   bge G0001
0080
0118   r10 = r40           ; strength reduced expression to r40
0090   ; for (j = 0; j < n; j++)
0100    {
0120 G0002:
0147      cmp r10, r22       ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0320   r14 = r8 + r1         ; calculate subscript i * n + i
0330   r15 = r14 * #8         ; calculate byte address
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380   r1 = r1 + #1
0385   r8 = r8 + r2         ; strength reduce r8 = r1 * r2
0386   r40 = r40 + r30        ; strength reduce expression r8 * 8
0388   r22 = r22 + r30        ; strength reduce r22 = r20 * 8
0390   br G0000
0400  }
0410 G0001:

در خط 0320 ، r14 مجموع r8 و r1 است ، و r8 و r1 در حلقه افزایش می یابد. ثبات r8 توسط r2 (= n) = افزایش میابد(bumped ) و r1 توسط 1 افزایش میابد . در نتیجه ، r14 در هر بار تکرار حلقه n + 1 افزایش می یابد. آخرین ضرب حلقه ، در خط 0330 می تواند با روش کاهش قدرتی با افزودن (r2 + 1) * 8 در هر تکرار حلقه بهینه شود .

0010 ; for (i = 0, i < n; i++)
0020  {
0030   r1 = #0            ; i = 0
0050   load r2, n
0220   fr3 = #0.0
0340   fr4 = #1.0
0055   r8 = r1 * r2         ; set initial value for r8
0056   r40 = r8 * #8         ; initial value for r8 * 8
0057   r30 = r2 * #8         ; increment for r40
0058   r20 = r8 + r2         ; copied from 0117
0058   r22 = r20 * #8         ; initial value of r22
005A   r14 = r8 + r1         ; copied from 0320
005B   r15 = r14 * #8         ; initial value of r15 (0330)
005C   r49 = r2 + #1
005D   r50 = r49 * #8         ; strength reduced increment
0040 G0000:
0060   cmp r1, r2           ; i < n
0070   bge G0001
0080
0118   r10 = r40           ; strength reduced expression to r40
0090   ; for (j = 0; j < n; j++)
0100    {
0120 G0002:
0147      cmp r10, r22       ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0320 ; r14 = r8 + r1   killed   ; dead code
0330 ; r15 = r14 * #8   killed   ; strength reduced
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380   r1 = r1 + #1
0385   r8 = r8 + r2         ; strength reduce r8 = r1 * r2
0386   r40 = r40 + r30        ; strength reduce expression r8 * 8
0388   r22 = r22 + r30        ; strength reduce r22 = r20 * 8
0389   r15 = r15 + r50        ; strength reduce r15 = r14 * 8
0390   br G0000
0400  }
0410 G0001:

هنوز کار های بیشتری برای انجام هست. تاشو ثابت(Constant folding) r1 = 0 را در مقدمه کد شناسایی میکند ، بنابراین چندین دستورالعمل تمیز می شوند(کاهش میابند). ثبات r8 در حلقه استفاده نمی‌شود ، بنابراین می تواند از بین برود علاوه بر این ، r1 فقط برای کنترل حلقه مورد استفاده قرار گرفته است ، پس r1 را می توان با یک متغیر القایی متفاوت مانند R40 جایگزین کرد. زیرا جایی که متغیر i از 0 تا n تغیر میکند ، ثبات r40 از 0 تا8 * n * n تغییر میکند .

0010 ; for (i = 0, i < n; i++)
0020  {
0030 ; r1 = #0            ; i = 0, becomes dead code
0050   load r2, n
0220   fr3 = #0.0
0340   fr4 = #1.0
0055 ; r8 = #0     killed     ; r8 no longer used
0056   r40 = #0            ; initial value for r8 * 8
0057   r30 = r2 * #8         ; increment for r40
0058 ; r20 = r2     killed     ; r8 = 0, becomes dead code
0058   r22 = r2 * #8         ; r20 = r2
005A ; r14 =    #0  killed     ; r8 = 0, becomes dead code
005B   r15 =    #0         ; r14 = 0
005C   r49 = r2 + #1
005D   r50 = r49 * #8         ; strength reduced increment
005D   r60 = r2 * r30         ; new limit for r40
0040 G0000:
0060 ; cmp r1, r2    killed     ; i < n; induction variable replaced
0065   cmp r40, r60          ; i * 8 * n < 8 * n * n
0070   bge G0001
0080
0118   r10 = r40           ; strength reduced expression to r40
0090   ; for (j = 0; j < n; j++)
0100    {
0120 G0002:
0147      cmp r10, r22       ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150      bge G0003
0160
0170      ; A[i,j] = 0.0;
0230      fstore fr3, A[r10]
0240
0245      r10 = r10 + #8      ; strength reduced multiply
0260      br G0002
0270    }
0280 G0003:
0290   ; A[i,i] = 1.0;
0350   fstore fr4, A[r15]
0360
0370   ;i++
0380 ; r1 = r1 + #1   killed    ; dead code (r40 controls loop)
0385 ; r8 = r8 + r2   killed    ; dead code
0386   r40 = r40 + r30        ; strength reduce expression r8 * 8
0388   r22 = r22 + r30        ; strength reduce r22 = r20 * 8
0389   r15 = r15 + r50        ; strength reduce r15 = r14 * 8
0390   br G0000
0400  }
0410 G0001:

سایر عملیات کاهش قدرت[ویرایش]

این ماده مورد اختلاف است. بعنوان بهینه سازی پیله و تکالیف دستورالعمل توصیف بهتر توضیف شده است.

اپراتور روش کاهش قدرت ،از ریاضیات برای جایگزینی عملیات ها یواش با عملیات های سریع استفاده میکند. مزایا به پردازنده (CPU) هدف و گاهی اوقات به کد های اطراف(که میتواند بر در دسترس بودن واحد های کاری درون پردازنده تاثیر داشته باشد) بستگی دارد.

جایگزینی تقسیم عدد یا ضرب با توان 2 با یک تغییر حسابی یا تغییر منطقی ^[۲]
جایگزینی ضرب عدد صحیح توسط ثابت با ترکیبی از شیفت ، اضافه یا تفریق
جایگزینی تقسیم عدد صحیح توسط ثابت با ضرب ، با بهره گیری از محدوده عدد صحیح دستگاه. ^[۳] این روش همچنین در صورتی کار می کند که تقسیم کننده یک عدد غیرصحیح به اندازه کافی بزرگتر از 1 باشد ، به عنوان مثال √2 یا π. ^[۴]

محاسبه اصلی	محاسبه جایگزینی
y = x / 8	y = x>> 3
y = x * 64	y = x <<6
y = x * 2	y = x <<1
y = x * 15	y = (x <<4) - x
y = x / 10 (جایی که x از نوع uint16_t است)	y = ((uint32_t) x * (uint32_t) 0xCCCD)>> 19)
y = x / π (جایی که x از نوع uint16_t است)	y = (((uint32_t) x * (uint32_t) 0x45F3)>> 16) + x)>> 2)

متغیر القایی (یتیم)[ویرایش]

متغیر القایی یا کاهش قدرت بازگشتی ، تابع برخی از متغیرهای در حال تغییر سیستماتیک را با یک محاسبه ساده تر با استفاده از مقادیر قبلی تابع جایگزین می کند. در یک زبان برنامه نویسی روندی(procedural) این عبارت برای یک عبارت شامل متغیر حلقه ای کاربرد دارد و در یک زبان اعلامی برای استدلال یک تابع بازگشتی اعمال می شود . مثلاً،

 f x = ... (3 ** x) ... (f (x + 1)) ...

تبدیل می شود

 f x = f' x 1
 where
  f' x z = ... z ... (f' (x + 1) (3 * z)) ...

در اینجا عملکرد بازگشتی تغییر یافته f پارامتر دوم z = 3 ** x را در اختیار شما قرار می دهد و اجازه می دهد محاسبات گران قیمت (3 * x) با ارزانتر (3 * z) جایگزین شود.

همچنین میتوانید نگاهی به موضوعت زیر بیندازید[ویرایش]

یادآوری
ارزیابی جزئی
ریشه مربع معکوس سریع

نوشته ها[ویرایش]

↑ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2.
↑ In languages such as C and Java, integer division has round-towards-zero semantics, whereas a bit-shift always rounds down, requiring special treatment for negative numbers.
↑ Granlund, Torbjörn; Peter L. Montgomery. "Division by Invariant Integers Using Multiplication" (PDF).
↑ Jones, Nigel. "Division of integers by constants".

منابع[ویرایش]

Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986), Compilers: Principles, Techniques, and Tools (2nd ed.), ISBN 978-0-201-10088-4
Allen, Francis E.; Cocke, John; Kennedy, Ken (1981), "Reduction of Operator Strength", in Munchnik, Steven S.; Jones, Neil D. (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, ISBN 978-0-13-729681-1
Cocke, John; Kennedy, Ken (November 1977), "An algorithm for reduction of operator strength", Communications of the ACM, 20 (11), doi:10.1145/359863.359888
Cooper, Keith; Simpson, Taylor; Vick, Christopher (October 1995), Operator Strength Reduction (PDF), Rice University, retrieved April 22, 2010

[MuchnickAssociates1997-1] Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2.

[2] In languages such as C and Java, integer division has round-towards-zero semantics, whereas a bit-shift always rounds down, requiring special treatment for negative numbers.

[3] Granlund, Torbjörn; Peter L. Montgomery. "Division by Invariant Integers Using Multiplication" (PDF).

[4] Jones, Nigel. "Division of integers by constants".

[۱]

[۲]

[۳]

[۴]