comp1 (Практикум 2)
Описание файла
Файл "comp1" внутри архива находится в следующих папках: Практикум 2, отчеты. PDF-файл из архива "Практикум 2", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
CFG + Dataflow analysesШрамов Георгий НиколаевичГраф потока управленияТекст данной программы разбивается на базовые блоки следующим образом:1После чего строится граф потока управления:Анализ достигающих определенийДля проведения анализа достигающих определений сперва необходимо вычислитьмножества gen и kill для каждого базового блока.
Результаты представлены в этой2таблице в том же виде, в котором они были в лекциях (если базового блока нет, то обамножества для него пустые):BB1genB{(wmax, B1), (wcur, B1), (hax, B1)}B2{(haxbuf, B2)}B3B4B5{(wmax, B3), (i, B3)}{(t17, B4), (t19, B4), (t20, B4),(t21, B4), (wcur, B4), (t23, B4)}{(haxbuf, B5)}B6{(haxbuf, B6)}killB{(wmax, B3), (wmax, B12), (wcur, B4),(hax, B12)}{(haxbuf, B5), (haxbuf, B6),(haxbuf, B11)}{(wmax, B1), (wmax, B12), (i, B7)}{(wcur, B1)}{(haxbuf, B2), (haxbuf, B6),(haxbuf, B11)}{(haxbuf, B2), (haxbuf, B5),(haxbuf, B11)}{(i, B3)}{}{(haxbuf, B2), (haxbuf, B5),(haxbuf, B6)}{(wmax, B1), (wmax, B3), (hax, B1)}B7 {(i, B7)}B10 {(t29, B10), (u, B10)}B11 {(haxbuf, B11)}B12 {(wmax, B12), (hax, B12)}Таблица 1: Множества gen и kill как в лекцияхОднако, в таком формате неудобно подавать данные на вход программе, поэтому втаблице 2 во множествах указываются номера строк с определением соответствующихпеременных. Кроме того, в таблицу добавлен столбец со множеством pred, в которомуказываны номера базовых блоков, из которых есть переход в текущий.
Именно втаком виде данные подаются на вход программе.Исходный текст программы находится в файле input.cpp, который приложен к этому отчету. В этой программе реализован алгоритм "Достигающие определения". Было проделано 11 итераций, в результате которых построено множество Input. Числасоответствуют номерам строк программы с объявлениями переменных, которые достижимы на входе в базовый блок.
Итог можно посмотреть в таблице 3.3BB1B2B3B4B5B6B7B8B9B10B11B12B13B14predB{entry}{13}{2}{8}{4}{4}{5, 6}{3, 7}{8}{2}{9, 10}{}{1, 12}{11, 13}genB{2, 3, 4}{7}{10, 11}{14, 15, 16, 17, 18, 19}{22}{25}{27}{}{}{33, 34}{36}{38, 39}{}{}killB{10, 38, 18, 39}{22, 25, 36}{2, 38, 27}{3}{7, 25, 36}{7, 22, 36}{11}{}{}{}{7, 22, 25}{2, 10, 4}{}{}Таблица 2: Множества prev, gen и kill для программыBB1B2B3B4B5B6B7B8B9B10B11B12B13B14ExitInput{}{2, 3, 4, 38, 39}{2, 3, 4, 7, 38, 39}{3, 4, 7, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 39}{4, 7, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 39}{4, 7, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 39}{4, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 39}{3, 4, 7, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 39}{3, 4, 7, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 39}{2, 3, 4, 7, 38, 39}{2, 3, 4, 7, 10, 11, 14, 15, 16, 17, 18, 19, 22, 25, 27, 33, 34, 38, 39}{}{2, 3, 4, 38, 39}{2, 3, 4, 10, 11, 14, 15, 16, 17, 18, 19, 27, 33, 34, 36, 38, 39}{2, 3, 4, 10, 11, 14, 15, 16, 17, 18, 19, 27, 33, 34, 36, 38, 39}Таблица 3: Множество Input4Анализ живых переменныхСначала нужно вычислить множества use и def .
Также в таблице есть столбец сомножеством succ, который строится аналогично множеству pred.BB1B2B3B4B5B6B7B8B9B10B11B12B13B14succB{13}{3, 10}{8}{5, 6}{7}{7}{8}{4, 9}{11}{11}{14}{13}{2, 14}{exit}useB{}{wcur, wmax}{wcur}{i, hax, haxbuf, wcur, w}{haxbuf}{haxbuf}{i}{i, n}{}{hax, w}{haxbuf}{wcur, hax}{hax, n}{wmax}defB{wmax, wcur, hax}{haxbuf}{wmax, i}{t17, t19, t20, t21, t23}{}{}{}{}{}{t29, u}{}{wmax}{}{}Таблица 4: Множества succ, use и defПрограмма представлена в исходном файле output.cpp, который приложен к отчету.В ней реализован алгоритм "Живые переменные".
Было произведено 10 итераций, врезультате чего сформировано множество Output. Результаты представлены в таблице5.5BEntryB1B2B3B4B5B6B7B8B9B10B11B12B13B14Output{n, w}{hax, n, w, wcur, wmax}{hax, haxbuf, n, w, wcur, wmax}{hax, haxbuf, i, n, w, wcur, wmax}{hax, haxbuf, i, n, w, wcur}{hax, haxbuf, i, n, w, wcur, wmax}{hax, haxbuf, i, n, w, wcur, wmax}{hax, haxbuf, i, n, w, wcur, wmax}{hax, haxbuf, i, n, w, wcur, wmax}{haxbuf, wmax}{haxbuf, wmax}{wmax}{hax, n, w, wcur, wmax}{hax, n, w, wcur, wmax}{}Таблица 5: Множество Output6.