Анализ программ весна 2020 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
Строка 38: Строка 38:
 
=== Лекция 8 ===
 
=== Лекция 8 ===
  
Анализ указателей. '''[[Медиа:StaticAnalysis2020Lection8.pdf|Слайды]]'''
+
Анализ указателей. '''[[Медиа:StaticAnalysis2019Lection8.pdf|Слайды]]'''
  
 
=== Лекция 9 ===
 
=== Лекция 9 ===

Версия 11:04, 25 марта 2020

Преподаватели: Марат Ахин (akhin@kspt.icc.spbstu.ru), Михаил Беляев (belyaev@kspt.icc.spbstu.ru)

Ссылки на предыдущие прочтения:

Лекции

Лекция 1

Введение в предмет курса. Слайды

Лекция 2

Статический анализ на основе систем типов. Слайды

Лекция 3

Теория решеток. Слайды

Лекция 4

Потокочувствительные анализы. Слайды

Лекция 5

Интервальный анализ. Слайды

Лекция 6

Чувствительность к путям и анализ зависимостей. Слайды

Лекция 7

Межпроцедурность и статический анализ. Слайды

Лекция 8

Анализ указателей. Слайды

Лекция 9

Ограниченная проверка моделей. Слайды


Практика

Ссылка на репозиторий с TIP: https://github.com/vorpal-research/TIP

НЕ ВЫКЛАДЫВАЙТЕ РЕШЕНИЯ В ОТКРЫТЫЙ ДОСТУП --- это просьба от коллег из университета Орхуса, откуда взяли существенную часть этого курса. В частности, не выкладывайте решения в открытые репозитории на GitHub. Используйте сервисы закрытых репозиториев.

Задания "на подумать" следует делать в кросс-платформенном человеко-читаемом формате (.pdf, .md, .smth) и складывать в свой форк базового репозитория в папку с говорящим именем (docs, reports).

Задание к лекции 2

  1. Дописать реализацию класса TypeAnalysis в TIP. Подумайте, как будет работать анализ, если в программе есть рекурсивный тип.
    1. Для консистентного создания экземпляров типов из узлов дерева можно использовать TipType.ast2typevar
  2. Попробуйте добавить в описанную в лекции систему типов тип Bool, не меняя синтаксис языка. Перепишите правила так, чтобы они продолжали работать на основе имеющегося алгоритма унификации.
  3. (опционально) Реализуйте пункт 2 в рамках пункта 1.
  4. Попробуйте добавить в описанную в лекции систему типов тип массива (при этом меняется синтаксис, см. слайды). Перепишите правила и попробуйте протипизировать программу из лекции.

Задание к лекции 3

  1. Подумайте, выразим ли анализ типов в монотонном фреймворке? А наоборот?
  2. Допишите метод transfer в трейте IntraprocSignAnalysisFunctions здесь.
  3. Реализуйте класс PowersetLattice в файле GenericLattices.

Задание к лекции 4

  1. Рассмотрим плоскую решётку над типами {Bool,Int} из задания 1. Если реализовать для неё анализ, каким по предложенной классификации он будет? Попробуйте выписать правила вывода.
  2. Дореализуйте live variables analysis здесь.
  3. Реализуйте reaching definitions analysis в файле ReachingDefsAnalysis.scala рядом.

Задание к лекции 5

  1. Допустим, мы хотим реализовать оптимизирующий компилятор для языка TIP. Среди прочего, для работы ему требуется информация о размерах различных переменных: bool (1 bit), byte (8 bit signed), char (16 bit unsigned), int (32 bit signed), bigint (any integer), any (any other thing).
    • Предложите решетку для реализации анализа размера переменных
      • Нужно описать не только решетку для одного абстрактного значения, но и все другие решетки, требуемые для анализа целой программы
    • Опишите правила вычисления различных выражений
    • Придумайте нетривиальный пример программы на TIP для получившегося анализа и посмотрите, что для него получается
      • Для этого можно воспользоваться результатами пункта 3
  2. Допишите реализацию метода widen в IntervalAnalysisWorklistSolverWithWidening здесь.
  3. Реализуйте придуманный вами анализ размера переменных в файле VariableSizeAnalysis.scala рядом.

Задание к лекции 6

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

Задание к лекции 7

Не будет 🙌

Задание к лекции 8

Не будет 🙌

Задание к лекции 9

Не будет 🙌