Clang Control Flow Graph?

Hi,
Just a quick question: Are the CFGBlock IDs strictly assigned in the depth-first order? I was trying to traverse the CFG but terminators like for loops “trap” me into an infinite loop; the successors have a path back to the predecessor of some blocks. My thinking was that if the block ids were assigned in a specific order, I may be able to use them as a way to avoid running into infinite loops (and stack overflows).

Thanks!
-Masoug

Hi, Masoug. No, I don’t think it’s safe to make that assumption, even if it’s true today. You’ll have to use a visited set; llvm::SmallPtrSet should be able to handle it quite well.

Best,
Jordan

Thanks for the reply! I’ll just check the block terminator type then.

-Masoug

What about goto? I don’t think you’re going to be able to get out of a proper visited set.

Good point. But the code I’m parsing never have goto statements.

I’m not actually trying to perform an exhaustive search through the CFG, I’m just starting at some block and walking up through the predecessors until I hit the ENTRY block. With the depth-first iterator, it seems to me that I should first assign special numbers to each block that follows the depth-first order and then have the walker walk up the CFG and avoid predecessors whose depth-first number is less than the current block’s depth-first number (seems a bit inefficient, unless I can reassign block ids which I’m guessing is not safe?). Do you have any suggestions for alternatives?

Unless you actually need the depth-first numbers, that’s functionally equivalent to just keeping a visited set. Again, SmallPtrSet will do you well.

Jordan