Как найти все основные блоки, появляющиеся между двумя конкретными базовыми блоками на уровне IR LLVM?

Question

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

Например, предположим, что у нас есть два основных блока с именами A и B. Теперь я хочу знать, какие базовые блоки могут появиться после выполнения базового блока A и перед базовым блоком B.

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

Единственное, что я смог найти в LLVM, была эта функция в llvm/analysis/CFG.h:

/// Determine whether instruction 'To' is reachable from 'From', without passing
/// through any blocks in ExclusionSet, returning true if uncertain.
///
/// Determine whether there is a path from From to To within a single function.
/// Returns false only if we can prove that once 'From' has been executed then
/// 'To' can not be executed. Conservatively returns true.
///
/// This function is linear with respect to the number of blocks in the CFG,
/// walking down successors from From to reach To, with a fixed threshold.
/// Using DT or LI allows us to answer more quickly. LI reduces the cost of
/// an entire loop of any number of blocks to be the same as the cost of a
/// single block. DT reduces the cost by allowing the search to terminate when
/// we find a block that dominates the block containing 'To'. DT is most useful
/// on branchy code but not loops, and LI is most useful on code with loops but
/// does not help on branchy code outside loops.
bool isPotentiallyReachable(
     const Instruction *From, const Instruction *To,
     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
     const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);

Но проблема в том, что эта функция настолько консервативна, а ответы не являются точными. Я хочу знать определенные ответы.

Answer 1

Концепция, которую вы ищете, называется доминированием. Вам нужны блоки, в которых преобладает A, а в последующем - B. Для этого вы создаете или получаете DominatorTree и PostDominatorTree и смотрите на части деревьев, которые находятся ниже A и B. Вы можете получить один из менеджеров пропусков, если вы пишете пропуск.

Тем не менее, обратите внимание, что код LLVM является консервативным, потому что подобные вещи быстро усложняются. А как насчет блоков, которые выполняются после A (т. Е. Доминирует A), но которые возвращают или выдают исключение вместо перехода к B? Ты хочешь те? Что если есть бесконечный цикл? Те могут быть преднамеренными. Что, если исключение может быть выдано, и обработчик не доминирует B? Подобные вещи полны дел, о которых вы должны подумать.