شماره گذاری ارزش

شماره گذاری ارزش یک تکنیک برای تعیین زمان محاسبه دو محاسبه در یک برنامه و حذف یکی از آنها با معنی شناسی حفظ بهینه سازی است.

شماره گذاری جهانی ارزش 
شماره گذاری ارزش جهانی (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)

جستارهای وابسته 
Partial redundancy elimination
Optimizing compiler
Common subexpression elimination

منابع 

 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