2006. Межпроцедурная нумерация значений, страница 4

Размерпрограммы – это сумма размеров всех её процедур. Представим, что в какой-то моментпринимается решение, подставлять ли процедуру P2 в процедуру P1. Чем размер P2больше, тем меньше шансов состояться у данной инлайн-подстановки.При таком подходе считаем, что после подстановки P2 в P1 sizeof(P1)=sizeof(P1)+sizeof(P2). Однако это не всегда так.

Если в P1 и P2 есть эквивалентные операции, топосле инлайна избыточные операции можно будет удалить. Значит, используя результаты межпроцедурной нумерации значений, можно показать, что после инлайна размерsizeof(P1)=sizeof(P1)+sizeof(P2)–num_of_common_op.На рис. 8 слева от жирной черты показан исходный код, справа – код после применения одного шага инлайн-подстановки. Алгоритм инлайна, не учитывающий результатыанализа нумерации значений, отказывался подставлять остальные вызовы g(). Алгоритм,использующий результаты анализа, понял, что увеличения кода больше не произойдёт, иподставил все вызовы g().тел./факс: (095) 917-24-70- 13 -a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------Рис. 8.

Один шаг инлайн-подстановки.Анализ “Межпроцедурная нумерация значений” позволяет более точно оценить увеличение кода процедуры, в которую производится инлайн-подстановка. Это приведёт ктому, что будет происходить больше инлайн-подстановок и будет получен более эффективный код. При этом размер программы будет оставаться в заданных пределах.5. НЕКОТОРЫЕ ТРУДНОСТИ МЕЖПРОЦЕДУРНОГО ОБХОДА ПРОГРАММ,НАПИСАННЫХ НА ЯЗЫКЕ СИ5.1. Нелокальные переходыВ языке Си имеется средство, позволяющее совершать нелокальные переходы из процедуры в процедуру, минуя операции CALL. Таким средством является пара вызововsetjmp и longjmp.

Вызов setjmp приводит к запоминанию стека вызовов и указатель натекущую команду в структуру jmp_buf. Если затем эту структуру подать вызову longjmp,то произойдёт восстановление стека, и передача управления в точку, где находитсяsetjmp. При этом управление может быть передано в другую процедуру.Вызовы setjmp и longjmp нарушают идеологию межпроцедурного обхода, представленного в данной работе, поэтому приходится производить для них специальную обработку. В процессе обхода процедуры, когда встречается вызов setjmp, запоминаем в специальном стеке процедуру и узел управляющего графа.Обработка вызовов longjmp происходит по следующему алгоритму:EvalLongJump(){proc = GetElemFromTheBottom( setjumps_stack);objs = GetObjsThatAreUsedInProc( proc);for ( obj = each object used in procedure proc){foreach element in setjmp stack{Получаем номер значения объекта obj, которое было записано в объектк моменту, когда был вызов setjmp, и сливаем с тем номером, которыйв объекте сейчас.

Записываем полученный таким образом номер значенияв узел, в котором был вызов setjmpтел./факс: (095) 917-24-70- 14 -a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------}return;}5.2. Обработчики сигналовПредставленный в работе межпроцедурный обход не может быть применён к программам, которые используют обработчики сигналов. Так как сигналы, как реакция навнешние события, могут поступать в произвольный момент функции обработчики могутбыть вызваны асинхронно относительно выполнения программы.

В теле такой функцииможет быть использование и запись в любые глобалы, чтение из памяти и запись в память. Программы, содержащие обработчики асинхронных сигналов, вообще говоря, непригодны для статического анализа.Поэтому, когда в ходе межпроцедурного обхода встречается вызов функции signal,анализ прекращается и считается, что для программы нет результатов анализа.6.

ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫЦелью эксперимента было, во-первых, увидеть сами результаты анализа “межпроцедурная нумерация значений”, проводимого для реальных задач, а, во-вторых, пронаблюдать эффект, достигаемый применением этих результатов для инлайн-подстановок. Эксперимент проводился в контексте работы оптимизирующего компилятора проекта Эльбрус-3М [2, 3] на задачах пакета Spec95.Табл. 1.Результаты анализа для задач пакета Spec95Тест129.compress130.li134.perlВызывающая процедураВызываемая процедураmainmainmainplistreadoneisnumbermainMainMaincompare_bufferfill_text_bufferspec_select_actionReadonePnameStrlenSprintfMyfatalInstrЧисло операций в вызываемойпроцедуре(N1)1291781451051652751743157135Число общих операций (N2)Процент общих операций(N2/N1*100%)17119811142919916201366810810111015В табл.

1 показаны несколько случаев вызовов процедур и полученные для этих процедур результаты анализа. Число общих операций здесь – это число таких операций ввызывающей процедуре, которые имеют эквивалентные им операции в вызываемой процедуре. Анализ показал, что в отдельных случаях значительная часть операций в вызываемой процедуре имеет эквивалентные им операции в вызывающей процедуре. Очевидно, в таких случаях применять инлайн-подстановку выгодно.В табл. 2 сведены показатели, демонстрирующие эффект, производимый применением результатов анализа для инлайн-подстановок. Эффект заключается как в уменьшенииполучаемого на выходе компилятора исполняемого кода, так и в улучшении времени истел./факс: (095) 917-24-70- 15 -a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------полнения исполняемого кода.

Размер исполняемого кода измерялся в байтах, время исполнения – в тактах архитектуры Эльбрус-3М.Табл. 2.Эффект от применения результатов анализа для инлайн-подстановокТест124.m88ksim129.compress130.li134.perl147.vortexУменьшение размера исполняемого файла(size_before/size_after)1,0091,0151,0061,0041,008Уменьшение времени исполнения(time_before/time_after)1,0011,0001,0021,0021,002Результаты эксперимента показывают, что основное улучшение при использованиирезультатов анализа получено как уменьшение размера исполняемого кода при почти неизменившемся времени исполнения. Такой явление объясняется более эффективной работой пары оптимизаций: {инлайн-подстановка – удаление избыточных вычислений}при использовании результатов анализа.7.

ЗАКЛЮЧЕНИЕАнализ “Межпроцедурная нумерация значений” является обобщением известного механизма “Нумерация значений” и выведением последнего на качественно новый межпроцедурный уровень.В статье рассмотрена модификация алгоритма, предложенного в [4], для проведенияанализа нумерация значений внутри одной процедуры. Затем предложены основныепринципы для проведения межпроцедурного анализа нумерация значений, опираясь навнутрипроцедурный анализ.

Показаны некоторые проблемы, возникающие при межпроцедурном обходе, и пути их решений. Указаны области применения результатов анализадля проведения оптимизаций.В настоящее время механизм межпроцедурного анализа и применение результатованализа для инлайн-подстановок процедур реализованы авторами статьи полностью вязыковом оптимизирующем компиляторе ecf_opt, компании Эльбрус [2, 3].ЛИТЕРАТУРА1.

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ulman. Compilers: Principles, Techniques andTools. Addison-Wesley Reading, 1986.2. ЗАО МЦСТ. Официальный сайт http://www.mcst.ru.3. Diefendorf K. The Russians Are Coming: Supercomputer Maker Elbrus Seeks to Joinx86/IA-64 Melee // Microprocessor Report, vol 11, № 2, February 15, 1999. P. 1-7.4. Simpson, Loren Taylor. Value-Driven Redundancy Elimination.

Ph.D. Thesis, Rice University, Houston, Texas, 1996.5. Wilson, Robert Paul. Efficient, Context-Sensitive Pointer Analysis For C Programs.Ph.D. Thesis, Stanford University, 1997.тел./факс: (095) 917-24-70- 16 -a88@narod.ru; http://a88.narod.ru.