автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Программные методы повышения производительности архитектуры picoJava-II

ВВЕДЕНИЕ.

1. АНАЛИЗ ВОПРОСОВ ЭФФЕКТИВНОСТИ ЯЗЫКА JAVA.

1.1 Основные способы реализации виртуальной Java-машины.

1.2 Устройство виртуальной Java-машины.

1.2.1 KoHifenifiin.

1.2.2 Формат Java-juicicca.

1.2.3 Набор команд JVM.

1.3 Архитектура picoJava-II.

1.3.1 Основные особенности.

1.3.2 Расширенный набор команд.

1.4 Постановка задачи.

1.5 Выводы.

2. ОПТИМИЗАЦИЯ РАЗМЕРА JAVA-КЛАССОВ.

2.1 Анализ традиционных подходов к оптимизации размера Java-классов.

2.2 Алгоритмы построения компактного константного пула класса.

2.2.1 Удаление неиспользуемых записей в константном пуле.

2.2.2 Пере использование записей в константном пуле.

2.3 Выводы.

3. СТАТИЧЕСКИЕ АЛГОРИТМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ БАЙТ-КОДА

3.1 Промежуточное представление байт-кода.

3.2 Адаптация традиционных алгоритмов для оптимизации байт-кода.

3.2.1 Свертка константных выражений.

3.2.2 Распространение констант.

3.2.3 Арифметические упрощения.

3.2.4 Инлайнинг.

3.2.5 Удаление мертвого и недостижимого кода.

3.2.6 Распространение копирований.

3.2.7 Сбор общих подвыражений.

3.2.8 Вынос инварианта из цикла.

3.2.9 Перераспределение локальных переменных.

3.3 Оптимизация обработки массивов с использованием расширенного набора команд picoJava-II.

3.4 Генерация байт-кода из промежуточного представления.

3.5 Выводы.

4. ДИНАМИЧЕСКИЕ АЛГОРИТМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ БАЙТ-КОДА.

4.1 Оптимизация вызова методов через класс-интерфейс.

4.2 Оптимизация вызова коротких невиртуальных методов.

4.3 ВЫВОДЫ.

Актуальность темы. Язык программирования Java, получивший широкое распространение в последние годы, обладает рядом достоинств, среди которых обычно выделяют платформенную независимость Java-программ [14]. Однако, как это часто бывает, достижения в чем-то одном приводят к проигрышу в другом. В случае Java наибольшей критике подвергается низкая производительность программ, написанных на этом языке, что является следствием изначально интерпретационного стиля их исполнения: платформенная независимость достигается путем интерпретации на конкретной архитектуре промежуточного представления, называемого байт-кодом.

В ходе развития языка была предложена технология динамической перекомпиляции байт-кода под конкретную исполняющую архитектуру, что позволило в несколько раз повысить производительность Java-nporpaMM. Эта технология получила название JIT-компиляции (Just-In-Time).

Однако JIT-компиляция не может использоваться во всей области применения Java. В последние годы разработчики бытовой техники все чаще создают устройства, имеющие выход в Internet. Например, уже не редкость мобильные телефоны, обладающие этим свойством. Такие устройства получили название встроенных (embedded). Но подключение к Internet вряд ли может считаться полноценным без поддержки Java. К сожалению, из-за резкого увеличения потребления памяти, ЛТ-технология не может быть применена для встроенных устройств, поскольку они зачастую не обладают достаточными ресурсами.

Альтернативой идее ЛТ-компиляции на рынке встроенных устройств стала идея микропроцессора, который мог бы аппаратно исполнять байт-код Java. Первой попыткой реализации этой идеи стала архитектура picoJava-II, разработанная фирмой Sun Microsystems в 1999 году. В 2000 году на основе этой архитектуры фирмой Fujitsu был разработан и запущен в серийное производство микропроцессор МВ86799 [44]. Испытания микропроцессора MB86799 показали, что при одинаковой тактовой частоте производительность архитектуры picoJava-II в 15 раз превышает производительность традиционных архитектур, использующих ЛТ-технологию.

Однако при дальнейшем анализе архитектуры picoJava-II и самого байт-кода становится ясно, что остается много возможностей дальнейшего повышения производительности picoJava-II программным путем. Частично эти возможности связаны с качеством самого исполняемого байт-кода, получаемого стандартным Java-компилятором. Другие возможности обусловлены архитектурными особенностями picoJava-II, пригодными для оптимального исполнения байт-кода. В связи с этим становятся актуальными работы, связанные с разработкой механизмов, использующих аппаратные особенности архитектуры picoJava-II для исполнения байт-кода оптимальным образом.

Целью диссертационной работы является анализ проблем, связанных с достижением наибольшей производительности Java-платформ, и практическое решение этих проблем применительно к архитектуре picoJava-II. Исходя из поставленной цели, в работе решаются следующие задачи:

• исследование возможностей увеличения производительности байт-кода Java;

• адаптация существующих алгоритмов оптимизации байт-кода к требованиям архитектуры picoJava-II;

• разработка новых алгоритмов, использующих для оптимизации байт-кода аппаратные возможности picoJava-II, в том числе динамически на этапе исполнения;

• оценка предлагаемых способов оптимизации при их реализации в составе оптимизирующего бинарного компилятора для архитектуры picoJava-II.

Предмет исследования составляют различные аспекты разработки средств программного повышения производительности для архитектуры picoJava-II:

• конкретные решения, принятые разработчиками архитектуры picoJava-II;

• методы оптимизации и их адаптация для получения оптимального байт-кода;

• методы поддержки исполнения оптимального байт-кода;

• конечная производительность байт-кода.

Методы исследования заимствованы из областей системного программирования, технологии компиляции и теории графов. Эффективность байт-кода и конечная производительность оценивалась путем замера времени исполнения пакета тестовых программ на потактовой модели архитектуры picoJava-II.

Научная новизна работы заключается в адаптации известных и разработке новых алгоритмов для решения задач повышения производительности архитектуры picoJava-II, имеющей ряд аппаратных особенностей:

• адаптирован к задаче оптимизации байт-кода для архитектуры picoJava-II целый ряд известных ранее классических алгоритмов оптимизации;

• разработан и реализован не исследовавшийся ранее алгоритм уменьшения размера Java классов с помощью переиспользования символьной информации;

• разработан и реализован новый алгоритм использования операции прямого чтения памяти вместо более медленной операции чтения элемента массива;

• разработаны и реализованы два оригинальных механизма поддержки времени исполнения, а именно: ускорение вызова методов через класс-интерфейс и встраивание "на лету" кода коротких методов по месту их вызова.

Практическая ценность результатов работы состоит в том, что на основе оценки производительности оптимизированного байт-кода подтверждена полезность программного подхода к повышению производительности архитектуры picoJava-II. Реализованы бинарный оптимизирующий компилятор и средства поддержки исполнения оптимального байт-кода для picoJava-II. Архитектурно-независимый характер части оптимизаций позволяет сделать вывод о том, что программный ресурс повышения производительности будет присутствовать и в будущих микропроцессорах, аппаратно исполняющих байт-код Java. Кроме того, некоторые представленные оптимизационные механизмы могут быть полезны и для традиционных архитектур, использующих JIT-технологию.

Основные практические результаты, выносимые на защиту.

1) Алгоритмы оптимизации размера байт-кода:

• удаление неиспользуемых записей в константном пуле;

• переиспользование записей в константном пуле.

2) Алгоритмы повышения производительности байт-кода на основе статического анализа:

• свертка константных выражений;

• распространение констант;

• арифметические упрощения;

• инлайнинг;

• удаление мертвого и недостижимого кода;

• распространение копирований;

• сбор общих подвыражений;

• вынос инварианта из цикла;

• перераспределение локальных переменных;

• обработка массивов с использованием инструкций из расширенного набора команд picoJava-II.

3) Алгоритмы динамической поддержки исполнения оптимального байт-кода:

• оптимизация вызова методов через класс-интерфейс;

• оптимизация вызова коротких невиртуальных методов.

Все разработанные алгоритмы реализованы в составе оптимизирующего бинарного компилятора для архитектуры picoJava-II. Оптимизирующий бинарный компилятор и средства поддержки времени исполнения прошли этап опытной эксплуатации в фирмах Sun Microsystems, ЗАО "МЦСТ", а также были опробованы сотрудниками фирмы Fujitsu и дали хорошие результаты.

В дальнейшем возможно использование результатов работы в составе математического обеспечения для любого микропроцессора, имеющего архитектуру picoJava-II (например, для микропроцессора МВ86799, разработанного фирмой Fujitsu).

Публикации.

По теме диссертации опубликованы 6 работ:

• статья "Эффективность языка Java в рамках архитектуры picoJava-II: оптимизация байт-кода" (журнал "Информационные технологии и вычислительные системы", №1, 2001) [2];

• статья "Оптимизация вызова методов через класс-интерфейс в реализации языка Java" (сборник "Высокопроизводительные вычислительные системы и микропроцессоры", №3, 2002) [3];

• статья "Оптимизация размера байт-кода языка Java" (журнал "Компьютеры в учебном процессе", №9, 2002) [10];

• тезисы доклада "Методы ускорения исполнения Java-nporpaMM: оптимизация байт-кода" на XLI научной конференции МФТИ (Москва, МФТИ, ноябрь 1998) [8];

• тезисы доклада "Программное моделирование архитектур как способ анализа их производительности" на XLII научной конференции МФТИ (Москва, МФТИ, ноябрь 1999) [11];

• тезисы доклада "Оптимизация вызова методов через класс-интерфейс в реализации языка Java" на XLIV научной конференции МФТИ, посвященной 50-летию создания МФТИ (Москва, МФТИ, ноябрь 2001) [9].

Апробация.

Результаты работы докладывались и обсуждались на XLI, XLII и XLIV научных конференциях Московского Физико-Технического Института, а также семинарах ЗАО "МЦСТ".

Краткое содержание работы.

В главе 1 дается краткий обзор проблем, связанных с эффективностью языка Java. Рассматриваются основные варианты реализации виртуальной Java-машины (JVM, Java Virtual Machine). Анализируются область применения и потенциальная эффективность каждого варианта.

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

В разделе 1.2 описываются основные особенности устройства виртуальной Java-машины, существенные для дальнейшего изложения. Подробно характеризуются формат Java-класса и набор команд JVM.

В разделе 1.3 анализируется основные архитектурные особенности picoJava-II. Отдельно рассматривается расширенный набор команд, использование которого позволяет увеличить производительность байт-кода.

По результатам проведенного анализа делается вывод о том, что в архитектуре picoJava-II присутствует возможность повышения производительности программным путем.

В главе 2 анализируются возможности оптимизации размера байт-кода Java. Размер байт-кода является его важной характеристикой, поскольку оказывает прямое влияние на скорость передачи Java-nporpaMM по сети. Встроенные устройства на основе архитектуры picoJava-II не имеют жестких дисков, осуществляя все взаимодействие с внешним миром исключительно с помощью сетевых соединений. Таким образом, размер байт-кода становится одним из ключевых факторов обеспечения производительности систем, построенных на основе этой архитектуры.

На основе анализа размера составных частей классов из тестового пакета JavaSpec 98 [47] делается вывод о том, что компонентом класса, занимающим подавляющую часть в общем объеме, является константный пул.

Кратко описываются традиционные подходы к оптимизации размера Java-классов на основе обфускации (сокращения размера символьных имен). Предлагаются два подхода к уменьшению размера константного пула за счет более компактного расположения его записей. Первый способ связан с удалением неиспользуемых записей, которые при некоторых обстоятельствах могут появиться в константном пуле класса. Второй способ позволяет переиспользовать одни и те же записи в разных целях, в результате чего некоторые из записей могут стать неиспользуемыми и быть удалены.

В конце главы приводятся результаты применения предлагаемых алгоритмов для оптимизации размера байт-кода программ из тестового пакета JavaSpec 98. Из полученных результатов видно, что объем классов уменьшается в среднем на 20%.

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

Подробно рассматриваются способы адаптации традиционных алгоритмов для оптимизации байт-кода, а именно:

• свертка константных выражений;

• распространение констант;

• арифметические упрощения;

• инлайнинг;

• удаление мертвого и недостижимого кода;

• распространение копирований;

• сбор общих подвыражений;

• вынос инварианта из цикла;

• перераспределение локальных переменных.

Для ускорения обработки массивов можно использовать архитектурные особенности picoJava-II. Доступ к массивам организован в виртуальной Java-машине с помощью специальных команд, одним из свойств которых является возбуждение исключительной ситуации в случае выхода за границы массива. Эта проверка требует дополнительного времени при исполнении команды. Однако часто при регулярной обработке массивов из структуры цикла бывает ясно, что подобная проверка является излишней. В этом случае можно добиться дополнительной экономии, используя команды прямого доступа в память из расширенного набора команд picoJava-II.

После проведения оптимизационных преобразований необходимо преобразовать промежуточное представление в байт-код. В разделе 3.4 предлагается генератор байт-кода из используемого промежуточного представления.

В конце главы приводятся результаты применения рассматриваемых алгоритмов на программах тестовых пакетов CaffeineMark 3.0 [46] и JavaSpec 98 [47], адаптированных для программного симулятора архитектуры picoJava-II. Для программ, мало использующих классы из стандартной библиотеки, получено существенное сокращение времени исполнения - в среднем на 25%. Для программ, активно использующих стандартную библиотеку языка, сокращение времени исполнения не столь заметно и составляет около 2-3%.

В главе 4 предлагаются способы динамической поддержки исполнения оптимального байт-кода на архитектуре picoJava-II: Поздняя линковка, принятая в Java, позволяет от запуска к запуску менять реализации отдельных классов при сохранении их интерфейса. Поэтому межклассовые оптимизации байт-кода на основе статического анализа могут оказаться некорректными. Однако некоторые межклассовые оптимизации могут быть осуществлены на основе динамического анализа поведения программы.

Одним из слабых мест архитектуры picoJava-II является вызов метода через класс-интерфейс (команда invokeinterfacequick из набора команд JVM). Эта команда реализована в виде программного прерывания, которое в среднем исполняется более 600 тактов. При некоторых динамически определяемых условиях ее можно заменить другими командами JVM, исполнение которых требует существенно меньшего времени.

Технология написания программ на объектно-ориентированных языках, к которым относится и Java, поощряет сокрытие членов-данных объекта и доступ к ним с помощью методов типа "getx ()". Поскольку инлайнинг между классами может быть некорректным, такой подход к написанию программ, хотя и позволяет писать менее подверженный ошибкам код, наносит ущерб производительности. В разделе 4.2 предлагается способ динамического инлайнинга методов типа "getx ()".

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

В Заключении приводятся основные результаты диссертационной работы. Делаются выводы об эффективности разработанных алгоритмов. Даются рекомендации по применению тех или иных оптимизационных алгоритмов и их месте в составе математического обеспечения для архитектуры picoJava-II.

В Приложении дана методика проведения замеров на потактовой модели архитектуры picoJava-II.

4.3 Выводы

1. Поздняя линковка, принятая в языке Java, препятствует проведению межклассовых оптимизаций. В большинстве случаев такие оптимизации могут быть реализованы только через полную переоптимизацию всех классов при загрузке в JVM каждого нового класса.

2. Некоторые простые межклассовые оптимизации могут быть реализованы в местах вызова методов в случаях, когда вызываемый метод определяется однозначно. Динамический анализ количества реализаций методов позволяет увеличить число таких мест за счет методов, являющихся виртуальными лишь формально.

3. Оптимизация вызова метода через класс-интерфейс позволяет в случаях, когда метод имеет единственную реализацию, использовать вместо команды вызова метода через класс-интерфейс более быструю команду вызова невиртуального метода. На программах, активно использующих вызов методов через класс-интерфейс, оптимизация может дать существенное уменьшение времени исполнения (до пяти раз на реальных приложениях).

4. Оптимизация вызова коротких невиртуальных методов позволяет в большинстве случаев производить встраивание кода методов типа "getXO" и "putXO" по месту вызова. На некоторых программах тестового пакета JavaSpec 98 оптимизация дает существенное уменьшение времени исполнения теста (до 40%).

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

Заключение

Диссертационная работа посвящена вопросам, связанным с повышением производительности архитектуры picoJava-II программным путем. Исследованы проблемы, имеющие отношение к получению оптимального байт-кода и разработке методов динамической поддержки его исполнения. Поставленные задачи решены практически в виде реализации бинарного оптимизирующего компилятора байт-кода для архитектуры picoJava-II и средств поддержки исполнения оптимального байт-кода. В ходе решения поставленных задач были достигнуты следующие результаты:

1. Проведен анализ проблем, касающихся эффективности языка Java. Рассмотрены основные варианты реализации виртуальной Java-машины, их область применения и потенциальная эффективность. Результатом анализа является вывод о перспективности на рынке встроенных устройств варианта реализации JVM в виде микропроцессора, аппаратно исполняющего байт-код, в том числе на основе одной из современных архитектурных платформ - picoJava-II.

2. Для решения задачи повышения производительности архитектуры picoJava-II предложены три основные стратегии:

• оптимизация размера Java-классов;

• повышение эффективности байт-кода на основе статического анализа;

• повышение эффективности байт-кода с использованием средств динамической поддержки.

3. В рамках решения задачи оптимизации размера Java-KnaccoB проведен анализ размера составных частей 1а\га-классов. На основе этого анализа сделан вывод о том, что подавляющую часть размера байт-кода классов занимает константный пул. Предложены два алгоритма построения компактного константного пула, а именно:

• удаление неиспользуемых записей в константном пуле;

• переиспользование записей в константном пуле.

Реализация предложенных алгоритмов построения компактного константного пула в составе бинарного оптимизатора байт-кода показала, что их применение совместно с традиционными подходами к уменьшению размера Java-KnaccoB позволяет сократить объем классов в среднем на 20%, что приблизительно на 10% лучше, чем применение только традиционных способов.

4. Java-компиляторы обычно не оптимизируют байт-код, откладывая оптимизации до стадии работы JIT-компиляторов, вследствие чего появляется возможность оптимизации байт-кода для архитектуры picoJava-II на основе статического анализа. При этом могут быть применены как традиционные оптимизирующие алгоритмы, так и специальные алгоритмы, учитывающие архитектурные особенности picoJava-II. Адаптация к специфике байт-кода целого ряда классических алгоритмов оптимизации и реализация специального алгоритма, ускоряющего за счет использования особенностей архитектуры регулярную обработку массивов, показали, что статическая оптимизация байт-кода для архитектуры picoJava-II позволяет получить сокращение времени исполнения на 2-3% для программ, активно использующих стандартную библиотеку языка. Для программ, мало использующих классы из стандартной библиотеки, сокращение времени исполнения может быть гораздо более существенным и достигать 25% и более.

5. Поздняя линковка, принятая в Java, препятствует проведению межклассовых оптимизаций, однако некоторые простые межклассовые оптимизации могут быть реализованы на основе динамического анализа поведения программы. Предложено два способа такой оптимизации с использованием динамического анализа количества реализаций методов, а именно:

• оптимизация вызова методов через класс-интерфейс;

• оптимизация вызова коротких невиртуальных методов.

Реализация предлагаемых способов оптимизации для архитектуры picoJava-II показала, что их эффективность сильно зависит от структуры оптимизируемой программы. Предложенные методы оптимизации наиболее эффективны для программ, использующих разделение интерфейса/реализации методов и сокрытие членов-данных. Таким образом, они позволяют разработчикам программного обеспечения использовать эти современные методы разработки программ, не заботясь о производительности получающегося кода. На отдельных тестовых программах, для которых критической является операция вызова метода, было получено уменьшение времени исполнения до пяти раз.

Опытная эксплуатация бинарного статического оптимизатора и средств динамической поддержки показала, что все разработанные алгоритмы могут быть использованы в составе математического обеспечения, поставляемого для микропроцессоров, имеющих архитектуру picoJava-II. Алгоритмы уменьшения размера Java-KnaccoB и адаптированные к байт-коду традиционные алгоритмы оптимизации на основе статического анализа имеют платформенно-независимый характер и могут использоваться в любом микропроцессоре, аппаратно исполняющем байт-код Java. Кроме того, для любого такого микропроцессора могут быть реализованы средства динамической поддержки, использующие те же идеи, что и в случае picoJava-II.

Работа над исследованием и реализацией статических методов оптимизации байт-кода, предлагаемых в третьей главе, осуществлялась в рамках проекта ВСО (Byte Code Optimizer), проводившегося совместно фирмами ЗАО "МЦСТ" и Sun Microsystems в 1997/1998 годах. Автором было разработано большинство алгоритмов, использованных в проекте, и выполнено около 30% работ, связанных с реализацией этих алгоритмов в составе статического бинарного оптимизатора байт-кода.

В заключение мне бы хотелось поблагодарить всех людей, принимавших участие в проекте ВСО. Я выражаю глубокую признательность сотруднику фирмы Sun Microsystems, руководителю проекта бинарной оптимизации Яну Цивлину за проявленное понимание и предоставленную возможность работать над диссертацией. Отдельно хочу поблагодарить начальника отдела ЗАО "МЦСТ", к.т.н. А.Д.Доброва и проф. В.В.Шилова, помогавших мне в течение всего времени написания этой работы, и без которых она была бы невозможна.

1. А.Ахо, Р.Сети, Д.Ульман. Компиляторы. Принципы, технологии, инструменты - М.: Вильяме. 2001.

2. В.Ю.Волконский, А.Д.Добров, С.А.Лунев. Эффективность языка Java в рамках архитектуры picoJava-II: оптимизация байт-кода // Информационные технологии и вычислительные системы. №1, 2001, стр. 61-71.

3. А.Д.Добров, С.А. Лунев. Оптимизация вызова методов через класс-интерфейс в реализации языка Java // Высокопроизводительные вычислительные системы и микропроцессоры. № 3, 2002.

4. В.А.Евстигнеев. Применение теории графов в программировании М.: Наука. 1985.

5. В.А.Евстигнеев, В.Н.Касьянов. Теория графов. Алгоритмы обработки деревьев -Новосибирск: Наука. 1994.

6. А.П.Ершов. Введение в теоретическое программирование М.: Наука. 1977.

7. В.Н.Касьянов. Оптимизирующие преобразования программ М.: Наука. 1988.

8. С.А.Лунев. Методы ускорения исполнения Java-nporpaMM: оптимизация байт-кода //Тезисы докладов XLI научной конференции МФТИ. Москва. МФТИ. Ноябрь 1998, стр. 30.

9. С.А.Лунев. Оптимизация вызова методов через класс-интерфейс в реализации языка Java // Тезисы докладов XLIV научной конференции МФТИ, посвященной 50-летию МФТИ. Москва. МФТИ. Ноябрь 2001, стр. 44.

10. С.А.Лунев. Оптимизация размера байт-кода языка Java // Компьютеры в учебном процессе. №9, 2002, стр. 47-54.

11. С.А.Лунев, В.К.Беляев. Программное моделирование архитектур как способ анализа их производительности // Тезисы докладов XLII научной конференции МФТИ. Москва. МФТИ. Ноябрь 1999.

12. Э.Майника. Алгоритмы оптимизации на сетях и графах М.: Мир. 1981.

13. М.И.Нечепуренко, В.К.Попков, С.М.Майнагашев и др. Алгоритмы и программы решения задач на графах и сетях Новосибирск: Наука. 1990.

14. П.Нотон. Java. Справочное руководство М.: Бином. 1996.

15. B.Alpern, M.N.Wegman, F.K.Zadeck. Detecting equality of values in programs // ACM POPL. Jan 1998.

16. A.W.Appel. Modern compiler implementation in Java // Cambridge University Press. 1988.

17. D.F.Bacon, S.L.Graham, O.J.Sharp. Compiler transformations for high-performance computing // ACM Computing Surveys. Dec 1994, pp. 345-420.

18. P.Briggs, K.D.Cooper, L.T.Simpson. Value numbering // Software: Practice and Experience. June 1997, pp. 701-724.

19. P.Briggs, K.D.Cooper, L.Torczon. Improvements to graph coloring register allocation // ACM TOPLAS. May 1994, pp. 428-455.

20. Z.Budimlic, K.Kennedy. Optimizing Java: theory and practice // Software: Practice and Experience. June 1997, pp. 445-463.

21. Z.Budimlic, K.Kennedy. Static interprocedural optimizations in Java // Tech. Rep. CRPC-TR98746. Rice University. 1998.

22. M.G.Burke, et al. The Jalapeno dynamic optimizing compiler for Java // ACM Java Grande Conference. San Francisco, California. June 1999.

23. G.J.Chaitin. Register allocation and spilling via graph coloring // ACM SIGPLAN. June 1982, pp. 98-105.

24. M.Cierniak, W.Li. Optimizing Java bytecodes // Software: Practice and Experience. June 1997, pp. 427-444.

25. C.Cifuentes, J.K.Gough. Decompilation of binary programs // Software: Practice and Experience. July 1995, pp. 811-829.

26. C.Collberg, C.Thomborson, D.Low. A taxonomy of obfuscating transformations // Tech. Rep. 148. University of Auckland. July 1997.

27. C.Collberg, C.Thomborson, D.Low. Manufacturing cheap, resilient, and stealthy opaque constructs // ACM POPL. Jan 1998.

28. D.Detlefs, O.Agesen. Mining of virtual methods // ECOOP Proceedings. Lisbon, Portugal. 1999, pp. 258-278.

29. J.Ferrante, K.J.Ottenstein, J.D.Warren. The program dependence graph and its use in optimization // ACM TOPLAS. July 1987, pp. 319-349.

30. J.R.Gosler. Software protection: myth or reality? // CRYPTO Advances in Cryptology. Aug 1985, pp. 140-157.

31. J.Gosling, B.Joy, G.Steele, G.Bracha. The Java language specification, Second Edition -2000.

32. J.Henessy. Program optimization and exception handling // ACM SIGPLAN. Jan 1981, pp. 200-206.

33. U.Holzle, D.Ungar. Optimizing dynamically-dispatched calls with run-time type feedback // ACM SIGPLAN. June 1994, pp. 326-336.

34. T.Lengauer, R.E.Tarjan. A fast algorithm for finding dominators in a flowgraph // ACM TOPLAS. July 1979, pp. 121-141.

35. T.Lindholm, F.Yellin. The Java virtual machine specification, Second Edition 1999.

36. S.P.Midkiff, J.E.Moreira, M.Snir. Optimizing bounds checking in Java programs // IBM Systems Journal. Aug 1998, pp. 409-453.

37. S.Muchnick. Compiler design and implementation Morgan Kaufmann Publishers. San Francisco, California. 1997.

38. M.N.Wegman, F.K.Zadeck. Constant propagation with conditional branches // ACM TOPLAS. Apr 1991, pp. 181-210.

39. File system safe UCS transformation format. ISO/IEC 10646.

40. IEEE standard for binary floating-point arithmetic. ANSI/IEEE Std. 754-1985.

41. Рис. 1. Доля различных частей в общем объеме Java-классов. Стр. 30. Рис. 2. Результаты применения алгоритмов оптимизации размера Java-югассов. Стр. 39.

42. Рис. 3. Общая схема статического оптимизатора байт-кода. Стр. 41.

43. Рис. 4. Пример графа потока данных для линейного участка. Стр. 45.

44. Рис. 5. Пример применения свертки константных выражений. Стр. 46.

45. Рис. 6. Пример применения распространения констант. Стр. 47.

46. Рис. 7. Пример применения арифметического упрощения. Стр. 49.

47. Рис. 8. Пример использования команды iinc для сложения локальнойпеременной с константой. Стр. 50. Рис. 9. Пример модификации графа управления при проведении инлайнинга. Стр. 51.

48. Рис. 10. Модификация графа потока данных первого линейного участка метода ml. Стр. 52.

49. Рис. 11. Модификация графа потока данных линейного участка из метода т2. Стр. 52.

50. Рис. 12. Пример удаления мертвого кода. Стр. 53.

51. Рис. 13. Пример применения распространения копирований для стековой машины. Стр. 55.

52. Рис. 14. Пример сбора общих подвыражений в пределах линейного участка. Стр. 56.

53. Рис. 15. Пример сбора общих подвыражений между линейными участками. Стр. 57.

54. Рис. 16. Пример графа взаимодействия локальных переменных. Стр. 60.

55. Рис. 22. Результаты статической оптимизации программ тестового пакета

56. CaffeineMark 3.0. Стр. 69. Рис. 23. Результаты статической оптимизации программ тестового пакета JavaSpec 98. Стр. 70.