C17 · анализ программ · зависимости памяти

PS-form Memory Dependence Analyzer

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

01

Проблема

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

02

Ограничения

Анализ должен быть консервативным, быстрым на больших диапазонах и проверяемым на малых областях.

03

Решение

Для аффинной разности адресов считаю пары итераций без полного перебора; модульные проверки и НОД доказывают часть случаев независимости, а неизвестные остаются maybe.

04

Результат

Точный подсчёт пар итераций в аффинных случаях и модульные/НОД-доказательства независимости; yes/no проверяются независимым оракулом и метаморфными тестами, неопределённость — maybe.

05

Как проверялось

Точный brute-force oracle на малых областях, метаморфная генерация, sanitizers и воспроизводимые WA/TL-примеры.

06

Моя ответственность

Алгоритм анализа, точный оракул, stress infrastructure и разбор контрпримеров.