1

Given an LLVM Control-flow graph, how to get or traverse all possible paths between two nodes using LLVM?

LLVM CFG Example

As an example, from the graph above, between node %23 and node %30, I want to get these two paths: [[%23, %26, %30], [%23, %30]].

I have researched that LLVM has these two iterators for simple graph traversal:

However, the iterator just traversing in the depth-first and breadth-first manner (both are just walking from %23, %26 and then go directly to %30) and not having a direct feature to enumerate the paths between the node.

I have tried to combine the DFS/BFS with BasicBlock successors/predecessors iterator to enumerate paths from branch block, but I haven't got any intended results after some messy attempts.

I have also checked these two similar questions, unfortunately, there is still no suggestion for the solution there:

I am just wondering if there is already an API in LLVM that can handle this or any hints on which API combination that I can explore to get the intended result.

Jon Kartago Lamida
  • 827
  • 1
  • 7
  • 12
  • That's not an enumerable set; a loop can cause the set to be infinite. You'll have to think about how to handle or avoid that case. Once you've modified your thinking to handle the potentially infinite number of paths, I suspect that one of th two iterators you've found can help you achieve your goal. – arnt Jul 03 '21 at 12:21
  • Yes, that is true the loop makes this graph cyclic. I am thinking on find strongly connected components to handle the cyclic nature of the loop combined with tracking visited nodes. – Jon Kartago Lamida Jul 03 '21 at 12:58
  • One way to perhaps do what you want to do is to get dominator and postdominator trees for the function, get the tree of blocks dominated by A, get the set of blocks that postdominate B, then do a depth-first walk over A's tree. Whenever you find B, you do your A-to-B processing. When you instead find a block in B's set of postdominators, you stop walking that subtree of the A tree. This will not find *all* paths, but perhaps it will let you do the processing that is the (unmentioned) goal of your question. – arnt Jul 05 '21 at 14:10

0 Answers0