EvilZone
Community => General discussion => Topic started by: TheWormKill on September 14, 2014, 05:42:22 PM
-
Hi guys,
for a project I am working on I need to recognize loops in a CFG (a Control Flow Graph), see
http://en.wikipedia.org/wiki/Control_flow_graph (http://en.wikipedia.org/wiki/Control_flow_graph) for details. Since modern compilers like to do weird shit with the code,
a back-edge, more specifically speaking the jump back to the loop-condition isn't just a jump to lower memory-addresses, since at least some versions of GCC compile normal for- or while-loops as a do-while-loop with a jump from the loop-pre-header to the condition at the "end" of the loop. If you look at the disassembly in IDA using the graph view, you won't notice any significant difference, but this makes back-edge detection a bit more complex. After some research, I figured out that a backedge is an edge that is leading the control-flow from a node n to a node m, so that m dominates n. (see http://en.wikipedia.org/wiki/Dominator_%28graph_theory%29 (http://en.wikipedia.org/wiki/Dominator_%28graph_theory%29)) The only problem I have is to implement an algorithm that computes the dominators for each node in the graph. This article http://www.cs.rice.edu/~keith/Embed/dom.pdf (http://www.cs.rice.edu/~keith/Embed/dom.pdf) describes the process quite good, it's just that I can't get which datatypes the described variables have, at least it looks like the algorithm only computes one dominator for each node. Thus my question: can anyone help me understand it?
Sidenote: I'm not really sure this post belongs here, I just didn't find any suitable category, feel free to move it.
greets, TheWormKill
-
I am sorry for double-posting, but to raise awareness, as this *might* help someone having a similar goal, I do it anyway.
I solved the problem using a different approach:
1. Calculate all ways from start-node to target,saving them
2. Iterate through these ways, that are represented as lists:
2.1 if the assumed dominator d is in every path/way, it is, in fact, a dominator.
First I thought that it's not efective enough, but that seems to be negligible.
If someone wants to see code, feel free to ask.