Comments 8
Меня сильно смущает, что сначала цикл определяется как максимальный по включению подграф, а затем в разделе про вложенные циклы говорится, что вложенный cycle ({3, 4}) - loop, хотя и не максимален по включению. Я, к своему стыду, в университете теорию компиляторов прогуливал, но мне как-то не верится, что в столь формализованной теории есть такие факапы в базовых определениях.
Циклом называется максимальный по включению сильно связный подграф, в котором одна из его вершин доминирует над всеми остальными.
Факапа нет, прочитайте определение ещё раз. Подграф максимальный при условии, что он всё ещё доминируется одной из его вершин. Если мы берём вершину 3, то максимальный по включению сильно связный подграф, который ей доминируется -- это {3, 4}.
Возможно, мне стоит как-то это переформулировать, чтобы было ясно, что свойство максимальности по включению вторично по отношению к свойству доминирования.
Как же получить non-loop cycle? Единственный известный мне способ этого добиться -- воспользоваться оператором
goto.
Кажется, можно ещё через switch сделать, как в Duff's device. Хотя от goto это не очень сильно отличается.
Почему в CFG для while у вас есть ребро 6 → 7?
Вы правы, это ошибка, спасибо! Сейчас переделаю.
Или смысл в том, что в do-while в блок внутри
} while (...)нельзя попасть мимо блока перед закрывающей фигурной скобкой, и компилятор сливает оба эти блока?
Практической разницы между тем, чтобы иметь 2 разных блока, между которыми единственное ребро, или один блок -- нет, компилятор при первой же возможности склеит их в один. Наверное, для чистоты можно было бы нарисовать два, я об этом как-то не думал.
Набор взаимно рекурсивных функций?
Можете объяснить, откуда там вообще цикл и non-loop в частности? Мне на ум приходят только какие-то вариации на уровне хвостовой рекурсии, которая после инлайнинга действительно порождает цикл, но обычный.
Поговорим об оптимизирующих компиляторах. Сказ четвёртый: Циклы