如何从装配控制流图？ [英] How to generate a Control Flow Graph from Assembly?

问题描述

有关的背景下，我试图写从AVM2反编译器（ActionScript虚拟机2）字节code /组装到高层次的ActionScript 3 code。据我所知，这需要我来分析组装和生成由此产生的控制流图，以推断结构，如循环，条件分支（如果/其他）。

For context, I'm attempting to write a decompiler from AVM2 (ActionScript Virtual machine 2) bytecode/assembly to high-level ActionScript 3 code. As far as I am aware, this requires me to analyze the assembly and generate resulting Control Flow Graph from this, in order to deduce structures such as loops, and conditional branching (if/else).

由于一些汇编，如：

0         getlocal0         
1         pushscope         
2         findpropstrict    {, private, }::trace
4         pushstring        "one"
6         callproperty      {, private, }::trace (1)
9         pop               
10        pushbyte          5
12        pushbyte          3
14        ifngt             L1

18        findpropstrict    {, private, }::trace
20        pushstring        "two"
22        callproperty      {, private, }::trace (1)
25        pop               

L1: 
26        findpropstrict    {, private, }::trace
28        pushstring        "three"
30        callproperty      {, private, }::trace (1)
33        coerce_a          
34        setlocal1         
35        getlocal1         
36        returnvalue       
37        kill              1

什么是算法生成控制流图？

What is an algorithm to generate a Control Flow Graph?

推荐答案

我想通了这一点。基本上，保持标签（这在我的情况是指数来说明在一个数组）的列表。的标签之间说明每个列表是块（这是图中的顶点）。标签指令每个分支后，（这样分支是块的最后一条指令，这样你可以弄清楚什么样的边缘是。或者，您可以在分支类型边缘标记。），以及目标各分支。

I figured this out. Basically, keep a list of labels (which in my case are indices to instructions in an array). Each list of instructions between the labels are blocks (which are vertices in the graph). Label the instruction after each branch (so that the branch is the last instruction of the block, that way you can figure out what kind of edge it is. Alternatively, you could tag on the branch type to the edge.), and the target of each branch.

一旦你的标签，只是将它们分割成块。我通过标签分类的每个循环指标，如果最后一个块的最后一个指令是一个分支，从我把它添加边缘目标。如果没有，我从它添加一个边缘到当前块（如落空节点）。

Once you have the labels, just split them up into blocks. I loop through each sorted index in the labels and if the last block's last instruction was a branch, I add an edge from it to the target. If not, I add an edge from it to the current block (as a fall-through node).

这篇关于如何从装配控制流图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！