شماره گذاری ارزش
این نوشتار نیازمند پیوند میانزبانی است. در صورت وجود، با توجه به خودآموز ترجمه، میانویکی مناسب را به نوشتار بیفزایید. |
این مقاله نیازمند بررسی توسط یک متخصص است. لطفاً پارامتر دلیل یا بحث در این الگو را برای مشخصکردن مشکل مقاله استفاده کنید. (دسامبر ۲۰۱۹) |
برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (دسامبر ۲۰۱۹) |
این مقاله نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
این مقاله شامل فهرستی از منابع، کتب مرتبط یا پیوندهای بیرونی است، اما بهدلیل فقدان یادکردهای درونخطی، منابع آن همچنان مبهم هستند. (دسامبر ۲۰۱۹) |
شماره گذاری ارزش یک تکنیک برای تعیین زمان محاسبه دو محاسبه در یک برنامه و حذف یکی از آنها با معنی شناسی حفظ بهینه سازی است.
شماره گذاری جهانی ارزش
ویرایششماره گذاری ارزش جهانی (GVN) یک بهینه سازی کامپایلر است که بر اساس نمایندگی واسطه فرم تکلیف استاتیک تک (SSA) است. بعضی اوقات به از بین بردن کدهای اضافی که حذف زیر بیان (CSE) کمک نمی‌کند ، کمک می کند. با این حال ، در همان زمان ، CSE ممکن است کدی را حذف کند که GVN آن را ندارد ، بنابراین هر دو اغلب در کامپایلرهای مدرن یافت می شوند. شماره گذاری ارزش جهانی با شماره گذاری محلی ارزش متمایز است به این دلیل که نقشه های شماره ارزش در مرزهای بلوک اصلی نیز نگهداری می شوند و از الگوریتم های مختلفی برای محاسبه نگاشت ها استفاده می شود.
شماره گذاری ارزش جهانی با اختصاص یک مقدار به متغیرها و عبارات کار می کند. همان مقدار ارزش به آن متغیرها و عبارات اختصاص داده شده معادل اختصاص داده می شود. به عنوان مثال ، در کد زیر:
w := 3
x := 3
y := x + 4
z := w + 4
یک روال خوب GVN عدد یکسانی را به w و x و همان عدد مقدار را به y و z اختصاص می دهد. به عنوان مثال ، نقشه پایین یک نقشه برداری با ارزش بهینه برای این بلوک تشکیل می دهد. با استفاده از این اطلاعات ، قطعه کد قبلی ممکن است با خیال راحت به کد زیر تبدیل شود:
w := 3
x := w
y := w + 4
z := y
بسته به کد زیر این قطعه ، انتشار کپی ممکن است تکالیف x و z را حذف کند. دلیل این که GVN گاهی اوقات قوی تر از CSE است از این واقعیت ناشی می شود که CSE با اصطلاحات واژگان یکسان منطبق است در حالی که GVN سعی در تعیین یک هم ارزی اساسی دارد. به عنوان مثال ، در کد:
a := c × d
e := c
f := e × d
بدون انتشار نسخه ، CSE اعتبار مورد نظر به f را از بین نمی‌برد ، اما حتی یک الگوریتم GVN ضعیف نیز باید این افزونگی را کشف و از بین ببرد.
فرم SSA برای انجام GVN لازم است به طوری که نگاشت اشتباه {نام ارزش → نام متغیر} ایجاد نمی‌شوند.
شماره گذاری محلی
ویرایششماره گذاری محلی (LVN) یک بهینه سازی کامپایلر است که هدف آن پیدا کردن چندین نمونه از عبارات معادل (یعنی عباراتی که همان نتیجه را دارند) را پیدا کرده و آنها را با اولین بار جایگزین می کند. LVN یک بهینه سازی محلی است ، به این معنی که برخلاف شماره گذاری جهانی ، در یک زمان واحد در یک بلوک اساسی عمل می کند.
شماره گذاری با ارزش محلی با اختصاص یک شماره منحصر به فرد به هر عملیات و به یاد آوردن این انجمن ها کار می کند. دستورالعمل های بعدی مورد بررسی قرار گرفته و در صورتی که دستورالعمل یکسان قبلاً ثبت شده باشد جایگزین نتیجه دستورالعمل قبلی می شود. مثلاً:
a ← 4 a is tagged as #1
b ← 5 b is tagged as #2
c ← a + b c (#1 + #2) is tagged as #3
d ← 5 d is tagged as #2, the same as b
e ← a + d e, being '#1 + #2' is tagged as #3
با اختصاص شماره به دستورالعمل های مقایسه نسخه های تکراری به مقایسه عدد صحیحی ساده تبدیل می شود. در این مثال خاص "c" و "e" به همان تعداد (شماره 3) اختصاص داده می شوند ، بنابراین به کامپایلر سیگنال می دهند که هر گونه ارجاع به e ممکن است به سادگی با c جایگزین شود.
مشکلات و الحاقات
ویرایشیک اجرای ساده ممکن است سعی کند با استفاده مستقیم از نامهای متغیر به جای اعداد ، بهینه سازی را انجام دهد. با این حال ، این رویکرد زمانی کار نمی‌کند که مقادیر متغیرها تغییر کنند. شبه کد را در نظر بگیرید:
a ← 1 a is tagged as #1
b ← 2 b is tagged as #2
c ← a + b c is tagged as #3
b ← 3
d ← a + b d is incorrectly tagged as #3
در این سناریو "d" نادرست عدد 3 را اختصاص می دهد زیرا آرگومان ها با "c" مطابقت دارند. با این حال ، این نادرست است زیرا "b" مقدار را از 2 به 3 تغییر داده و نتیجه واقعی را متفاوت می کند. یک پیاده سازی ساده همچنین ممکن است قادر به گرفتن همه عبارات معادل آن نباشد ، حتی در مواردی که فقط با ترتیب عملگرهای خود متفاوت باشند. در مثال زیر "a" و "b" می توانند به همین تعداد اختصاص داده شوند:
a ← 1 + 2
b ← 2 + 1
این مسئله به راحتی یا با اختصاص یک عدد به هر دو مورد قابل حل است (یعنی "a + b" و "b + a" هر دو با یک شماره ثبت می شوند) یا با مرتب کردن عملوندها قبل از بررسی معادل ها. بهینه سازهای شماره گذاری محلی نیز ممکن است از هویت ریاضی آگاه باشند. با فرض "a" یک عدد صحیح است که به همه عبارات زیر می توان مقدار یکسان داد:
b ← a + 0
c ← a * 1
d ← min(a, MAX_INT)
e ← max(a, a)
f ← a & 0xFF..FF (assuming '&' denotes the bitwise operation)
جستارهای وابسته
ویرایشمنابع
ویرایش- Cooper, Keith D.; Torczon, Linda.http://booksite.elsevier.com/9780120884780/Graduate_Lecture_Slides/Core_Lectures/03PrinciplesI.ppt. elsevier. Retrieved 15 May 2017.
- ^ Cooper, Keith D.; Torczon, Linda. https://www.clear.rice.edu/comp412/Lectures/L34LVN.pdf[پیوند مرده] (PDF). Rice University. Retrieved 15 May 2017