Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- software:deep:dev:crosscompiler:cfg [2014-01-04 17:59] – Externe Bearbeitung 127.0.0.1
+++ software:deep:dev:crosscompiler:cfg [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Control Flow Graph ======
-The Control Flow Graph is an intermediate form where the instructions and the control flow are shown as a directed graph. It enables certain optimizations. For each method of a class an own CFG is built. Nodes in such a CFG represent a sequence of instructions with no branches. Further, there must be no branch target within a node. Branches in a method are represented by directed edges which connect the nodes. Each node has n predecessors and m successors as well as an index to the address of the first and the last Bytecode instruktion of this node.
-[{{ .:cfgnode.png?150&direct  | // Structure of a CFGNode //}}]
-In order to build the CFG of a method, unconditional and conditional jumps or branches have to be found.
-===== Implementation =====
-At the beginning the whole code of a method is a single node. Now the first branch is searched. This could be instructions such as //if_xx//, //goto//, //goto_w//, //tableswitch// and //lookupswitch//. Calls to methods do not change the flow of the program and don't give edges. The same is true for subroutines with //jsr// and //ret//.
-For searching this branch instructions all Bytecode instructions are stored in a lookup table together with attributes. These attributes indicate for example whether they are branch instructions. Special care has to be taken for instructions whithout a fixed length, among them are //wide//, //tableswitch// and //lookupswitch//.
-As soon as a branch instruction is found the node is split. The node which contains the branch target must be split as well.
-==== Splitting a Node After the Branch Instruction ====
-  * Split and link, new node is successor of the actual node. Important: Only link if conditional branch (//if_xx//). If unconditional branch -> no linking.
-  * If branch instruction is last instruction of a node -> no splitting.
-==== Splitting a Node Before the Branch Target ====
-  * Split and link, new node is successor of the actual node. Important: If the last instruction of the actual node is of type //return// or //goto// -> no linking.
-  * If branch target is first instruction of a node -> no splitting.
-  * Additionally, the node with the original branch instruction must be linked with the branch target node.
-  * If target instruction is //goto//: That means the target node of the branch consists of an unconditional branch. We can therefore omit this node and directly enter the node, which is the target of this unconditional branch, as a successor of the actual node.
-===== Loop Headers =====
-As a next step, all nodes are traversed and the loop headers marked. This information is later needed for the SSA. \\
-Starting from the root nodeNode the graph is recursively traversed. Each node with the flag //visited// already set must be a loop header. Also //nofBackwardBranches// will be incremented.
-===== Dead Code Elimination =====
-If a node has a single //goto// instruction, this node can be eliminated. //switch// statements often lead to such nodes. For this the branch, which leads to this special node, must be corrected in way that its target directly points to the node with the target of the //goto//. Important: The original Bytecode is not changed in any way. In there the target address of a switch table still contain the dead nodes. Later on we no longer parse the Bytecode and determine addresses but simply follow the successors of a node. The successors must be entered in the same order as the original branch targets in the Bytecode. For this purpose it's also important to list successors with the same target node multiple times if necessary. To find dead nodes, the flag //visited//, which was already used for the loop headers, can be reused.
-===== Predecessors =====
-For all nodes its predecessor can be added. For the case that several successors of a node point to the same target node only one predecessor must be entered.
-===== Dominator =====
-Finally the dominator of each node has to be determined. The resulting structure is called dominator tree and is a n-fold tree, since every node has exactly one reference to another node (its dominator).
-[{{ .:dominator.png?250&direct  | // Example of a CFG (left) and its dominator tree (right)//}}]
-Special care must be given to the case where the root node already has one or more predecessors.

Infoportal

Infoportal

Unterschiede

Infoportal

Infoportal

Unterschiede

Seiten-Werkzeuge