کاهش قدرت
در ساخت کامپایلر ، کاهش قدرت یک روش بهینه سازی کامپایلر است که در آن عملیات های پر هزینه با عملیات معادل اما کم هزینه تر جایگزین می شوند. مثال برای کاهش قدرتی ضرب های "قوی" در داخل حلقه را به جمع های "ضعیف تر" تبدیل می کند – چیزی که غالباً در آدرس دهی آرایه اتفاق می افتد.
مثال هایی از کاهش قدرت عبارتند از:
بیشتر زمان اجرای برنامه به طور معمول در یک بخش کوچک از کد (به نام منطقه داغ ) سپری می شود ، و آن بخش از کد اغلب در داخل یک حلقه است که بارها و بارها اجرا می شود.
کامپایلر از روش هایی برای شناسایی حلقه ها و تشخیص ویژگی های مقادیر در آن حلقه ها استفاده می کند. برای کاهش قدرت ،به داده های زیر نیازمند است :
ثابت های حلقه(Loop invariants) در اصل درون یک حلقه ثابت هستند ، اما ممکن است مقدار آنها در خارج از حلقه تغییر کنند. متغیرهای القایی با مقادیر شناخته شده(خاصی) در حال تغییر هستند. شرایط نسبت به یک حلقه خاص است. هنگامی که حلقه ها تودرتو باشند ، یک متغیر القایی در یک حلقه بیرونی می تواند یک ثابت حلقه ای (Loop invariants) در یک حلقه داخلی باشد.
کاهش قدرت به دنبال عباراتی که شامل ثابت حلقه ای (Loop invariants)و متغیر القایی می گردد. برخی از این عبارات را می توان ساده سازی کرد. به عنوان مثال ، ضرب ثابت حلقه ای codice_1 و متغیر القایی codice_2  c = 7; for (i = 0; i < N; i++) c = 7; k = 0; for (i = 0; i < N; i++)
در زیر مثالی وجود دارد که تمام ضرب های داخل حلقه که از محاسبات آدرس دهی فهرست بندی آرایه (array indexing address calculations)به وجود آمده اند با روش کاهش قدرت ،بهینه سازد.
یک حلقه ساده را تصور کنید که یک آرایه را به یک ماتریس هویت(identity matrix) می نشاند .  for (i = 0; i < n; i++)
کامپایلر کد زیر را به عنوان گزاره زیر میبیند :  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 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 0410 G0001:
کامپایلر شروع به انجام بسیاری از بهینه سازی های دیگر خواهد کرد – نه تنها کاهش قدرت. عباراتی که ثابت (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 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 0410 G0001: 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 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 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 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 0410 G0001:
مقدار 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 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 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 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 0410 G0001: 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 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 0410 G0001:
علاوه بر این ، 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 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 0410 G0001:
اپراتور روش کاهش قدرت ،از ریاضیات برای جایگزینی عملیات ها یواش با عملیات های سریع استفاده میکند. مزایا به پردازنده (CPU) هدف و گاهی اوقات به کد های اطراف(که میتواند بر در دسترس بودن واحد های کاری درون پردازنده تاثیر داشته باشد) بستگی دارد.
متغیر القایی یا کاهش قدرت بازگشتی ، تابع برخی از متغیرهای در حال تغییر سیستماتیک را با یک محاسبه ساده تر با استفاده از مقادیر قبلی تابع جایگزین می کند. در یک زبان برنامه نویسی روندی() این عبارت برای یک عبارت شامل متغیر حلقه ای کاربرد دارد و در یک زبان اعلامی برای استدلال یک تابع بازگشتی اعمال می شود . مثلاً،