Аккордовые графы и программы форм SSA
Мой вопрос просто о том, почему каждая программа формы SSA по умолчанию представляет хордовый граф.
что я знаю о хордовом графе из Википедии
хордальный граф - это тот, в котором все циклы из четырех или более вершин имеют хорду, которая является ребром, которое не является частью цикла, но соединяет две вершины цикла
вот простой пример
Теперь было учебное пособие, которому я следовал, чтобы понять преимущества формы SSA, представляющей хордовый граф для регистрации распределения, было это изображение: 
вот первое, что я не могу понять, как этот граф хордовый граф, потому что автор сказал, что
следующая программа и соответствующий хордальный граф
Вот ссылка на полную лекцию: https://www.cs.cmu.edu/~rjsimmon/15411-f15/lec/03-regalloc.pdf
предыдущая программа не в форме SSA, я знаю, что после преобразования в форму SSA мы получаем этот график помех
Опять же, я не вижу, как это хордовый граф, например, как первый граф связан с любым из более поздних графов, как я могу получить преимущества оптимальности использования формы SSA при распределении регистров (из-за ее строгой природы и того, что каждое использование является доминирующим по своему определению и потому, что каждая переменная имеет одну природу определения формы SSA), и я видел примеры того, как это улучшает распределение регистров, но что я не понимаю, как программы SSA формируют (точнее пересечение SSA) графы) являются хордальными графами (я знаю, почему хордовые графы дают оптимальность в распределении регистров, потому что мы можем оптимально упорядочить вершины), и вот некоторые источники, которые я изучил:
https://homepages.dcc.ufmg.br/~fernando/publications/papers/APLAS05.pdf
https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/ementa/slides/SSABasedRA.pdf
Любая помощь приветствуется заранее.
0 ответов
Что касается программы, которую вы перечислили в разделе 6 конспекта лекции:
Я не понимаю, как этот график хордовый. Я понимаю, что программа не в форме SSA.
Вы правы, что оригинальная программа не в форме SSA. Вы также по праву смущены тем, почему его "хордовый граф" является хордовым: это не так. Авторы допустили небольшую ошибку. Там, где они написали "хордальный граф" со ссылкой на эту первую программу, они имели в виду написать "интерференционный граф".
Этот второй график, на который вы ссылаетесь, тривиален, потому что он не содержит циклов. Запомните определение хордального графа, который вы дали:
хордальный граф - это тот, в котором все циклы из четырех или более вершин имеют хорду, которая является ребром, которое не является частью цикла, но соединяет две вершины цикла
Если есть нулевые циклы, то в вакууме все эти циклы содержат аккорд.