Портал освітньо-інформаційних послуг «Студентська консультація»

  
Телефон +3 8(066) 185-39-18
Телефон +3 8(093) 202-63-01
 (093) 202-63-01
 studscon@gmail.com
 facebook.com/studcons

<script>

  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){

  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),

  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)

  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

 

  ga('create', 'UA-53007750-1', 'auto');

  ga('send', 'pageview');

 

</script>

Методики перенацілюваної генерації коду для мікропроцесорних архітектур з нерегулярним довгим командним словом

Тип роботи: 
Автореферат
К-сть сторінок: 
32
Мова: 
Українська
Оцінка: 

підмножини класів міток. Визначається множина об’єктів-»типів» міток W, для wW поставлена у відповідність множина міток V (w) =Vi1Vi2…Vis, де VijV – деякий клас міток для будь-якого j.

Ієрархічна графова модель (ІГМ) є трійка (H, M, L), де H – ієрархічний граф, M – функція типу, яка приписує кожному елементу (вершині, ребру і фрагменту) h ієрархічного графа H його тип M (h) W, а L – функція міток, яка приписує кожному елементу h графа H його мітку – деякий елемент L (h) V (M (h)). Семантична частина графової моделі задається за допомогою системи перетворень графових моделей, що зберігають їх еквівалентність (еквівалентних перетворень).
Графова граматика складається з множини правил (графових продукцій), які можуть ітеративно застосовуватися до графа, роблячи звичайно його локальні перетворення. Графова продукція є четвіркою (L, R, E, C), де L і R – два графи, які називаються лівою та правою частинами продукції, E – деякий механізм вбудовування, C – умови застосування продукції. Продукція p застосовується до оброблюваного графа G наступним чином:
1) знаходимо входження лівої частини L в G (за виконання умови застосування C) ;
2) видаляємо частину графа G, визначену вказаним входженням L, для одержання контекстного (або залишкового) графа D;
3) вбудовуємо в D праву частину (копію) R за допомогою механізму вбудовування E і отримуємо виведений граф H.
Вершини ІГ функцією типу M (h) поділяються на два основних класи: 1) перетворювачі, які мають не більш однієї вихідної дуги та являють собою одну або декілька інструкцій присвоєння значення змінній або виклику підпрограми; 2) розрізнювачі, що мають більш одного можливого наступника по керуванню, але не змінюють стан пам’яті (окрім змінних-лічильників), являють собою умовний оператор, оператор вибору, циклічні конструкції. На рис. 1 показано приклад структури гіпотетичної підпрограми x1 та її ІГМ (білим кольором показано перетворювачі, чорним – розрізнювачі).
Рис. 1. Приклад ієрархічної графової моделі.
Кожний перетворювач являє собою ІГ Hb (Tb, Gb), де дерево вкладеності Tb є променем; граф Gb є незв’язаним та складається з множини ациклічних орграфів Defi, (дерев), які визначають присвоєння. Кожен орграф Defi зіставлений деякій вершині Tb. Граф Hb – відображення лінійної ділянки програми, до якої не входять умовні або безумовні переходи, – базового блоку (ББ).
Орграфи, які визначають присвоєння, позначаються за допомогою дужкового запису Def (Var, Exp), де Var – змінна, яка присвоюється, Exp – значення виразу, яке присвоюється, Exp=Opn (Exp1, …, Expn) |Vari|Consti, де Opn – n-арна операція, Vari – змінна, Consti – константа. Вводиться множина змінних програми VAR={vari} та множина констант CONST={consti}. Вводяться множина типів (як базових, так і композитних) TYPES={typei}. Для множин VAR та CONST вводиться функція t=Type (vari|consti), tTYPES, яка повертає тип змінної або константи.
Дерево вкладеності ІГ програми визначає зв’язки по керуванню.
За допомогою перетворювачів відображаються зв’язки за даними в базових блоках. Скалярний оператор Si виконується раніше скалярного Sj (позначається Si Sj), якщо оператор Si лексично передує Sj (i<j). Через OUT (Si) позначається множина екземплярів змінних, які модифікуються оператором Si, через IN (Si) – множина екземплярів змінних, які використовуються тим же оператором. Оператори Si та Sj знаходяться у потоковій залежності SiSj, якщо справедливі дві умови:
1) Si Sj;
2) OUT (Si) IN (Sj) .
Антизалежність між Si та Sj (позначається Si Sj) визначається аналогічно потоковій, але умова (2) має вигляд IN (Si) OUT (Sj) . Залежність за виходом між Si та Sj (позначається SiSj) визначається аналогічно потоковій, але з умовою (2) : OUT (Si) OUT (Sj) . На базі введених формалізмів розглядаються оптимізуючі продукції (оптимізації) для ББ і для глобальної оптимізації. При створенні ІГМ після локальних оптимізацій в графах ББ залишаються лише потокові залежності.
Розглядаються деякі описи оптимізуючих графових продукцій.
1. Поширення констант – посилання на змінну, яка дорівнює константі, замінюється на константу
L = di  diSi  SjDef (di, ConstK)  Sj Si, R = (ConstK).
2. Алгебраїчні спрощення, являють собою велику кількість продукцій типу
L = {'+', '-'} (vari, 0) ; R = (vari) ; для перетворення x+0x, x-0x.
3. Для видалення повторюваних виразів використовується наступний метод. Нехай існує L = Op (…, …), та Si, Sj, такі, що Si Si, LSi, LSj. Продукція вставляє новий оператор R=SR=Def (varTEMP, L), так що для будь-якого Sk Si виконується Sk SR і SR Si. Входження L в операторах Si і Sj заміняється на змінну varTEMP.
Усі розглянуті в роботі продукції для оптимізації ББ є машиннонезалежними.
Для застосування оптимізуючих продукцій у процесі глобальної оптимізації використовується аналіз потоку даних. Для ББ B вводиться функція передачі (ФП) FB (vari), де vari – будь-яка змінна, яка відображує значення змінної vari після виконання ББ. Результатом відображення є вираз у символьному вигляді – значення vari як функція від значень певних змінних перед початком виконання ББ.
Вводиться оператор композиції  над двома ФП FB1 (vari) та FB2 (vari), нова ФП FB1B2 (vari) =FB1 (vari) FB2 (vari) являє собою ФП – результат послідовного виконання базових блоків B1
Фото Капча