Skip to content

Commit fbdc01d

Browse files
n2on2o
committed
Added first version of a liveness analysis
1 parent f361901 commit fbdc01d

31 files changed

+958
-324
lines changed

‎Block.java

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
import java.util.LinkedList;
2+
3+
public class Block {
4+
private String def;
5+
public LinkedList<String> use;
6+
private LinkedList<String> in = new LinkedList<String>();
7+
private LinkedList<String> out = new LinkedList<String>();
8+
private LinkedList<Block> successor = new LinkedList<Block>();
9+
private boolean hasSuccessor = false;
10+
11+
private boolean hasUse = false;
12+
protected int blockID;
13+
14+
public Block(String identifier, int blockID) { // for an assignment context
15+
this.blockID = blockID;
16+
this.def = identifier;
17+
}
18+
public Block(int blockID) {
19+
this.blockID = blockID;
20+
}
21+
22+
////////////////////////////////////////////////////////////////////////////////
23+
24+
public void addUse(String input) {
25+
if (!hasUse) {
26+
use = new LinkedList<String>();
27+
hasUse = true;
28+
}
29+
use.add(input);
30+
}
31+
public void addIn(String input) {
32+
in.add(input);
33+
}
34+
public void addOut(String input) {
35+
out.add(input);
36+
}
37+
public void addSuccessor(Block input) {
38+
hasSuccessor = true;
39+
successor.add(input);
40+
}
41+
42+
////////////////////////////////////////////////////////////////////////////////
43+
44+
public LinkedList<String> getUse() {
45+
return use;
46+
}
47+
public LinkedList<String> getIn() {
48+
return in;
49+
}
50+
public LinkedList<String> getOut() {
51+
return out;
52+
}
53+
public LinkedList<Block> getSuccessor() {
54+
return successor;
55+
}
56+
public String getDef() {
57+
return def;
58+
}
59+
public Block getSuccessor(int i) {
60+
return successor.get(i);
61+
}
62+
public boolean hasSuccessor() {
63+
return hasSuccessor;
64+
}
65+
public int getBlockID() {
66+
return blockID;
67+
}
68+
public boolean hasUse() {
69+
return hasUse;
70+
}
71+
}

‎CodeGeneratorException.class

-401 Bytes
Binary file not shown.

‎GraphVisitor.java

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
import analysis.DepthFirstAdapter;
2+
import node.*;
3+
4+
import java.util.HashMap;
5+
import java.util.LinkedList;
6+
7+
public class GraphVisitor extends DepthFirstAdapter{
8+
private LinkedList<Block> blocks = new LinkedList<Block>();
9+
private Block lastBlock;
10+
private Block currentBlock;
11+
private Block startBlock;
12+
private int blockID = 1;
13+
private HashMap<Integer, Integer> addSuccessors = new HashMap<Integer, Integer>();
14+
15+
private LinkedList<Integer> removeSuccessors = new LinkedList<Integer>();
16+
17+
/**
18+
* Define Def and Use in the current block
19+
*/
20+
@Override
21+
public void caseAAssignmentExpr(AAssignmentExpr node) {
22+
String identifier = node.getIdentifier().toString().toLowerCase().replaceAll(" ","");
23+
currentBlock = new Block(identifier, blockID++);
24+
node.getExpr().apply(this); // evaluate the expression
25+
setStartAndSuccessor();
26+
}
27+
/**
28+
* For writeln(). Nearly same as Assignment
29+
*/
30+
@Override
31+
public void caseAPrintExpr(APrintExpr node) {
32+
currentBlock = new Block(blockID++);
33+
node.getExpr().apply(this); // evaluate the expression
34+
setStartAndSuccessor();
35+
}
36+
/**
37+
* If then
38+
*/
39+
@Override
40+
public void caseAIfThenExpr(AIfThenExpr node) {
41+
int temp = blockID;
42+
currentBlock = new Block(blockID++);
43+
node.getLeft().apply(this); // evaluate the expression
44+
setStartAndSuccessor();
45+
node.getRight().apply(this);
46+
addSuccessors.put(temp, blockID);
47+
}
48+
/**
49+
* If then else
50+
*/
51+
@Override
52+
public void caseAIfThenElseExpr(AIfThenElseExpr node) {
53+
int thenPointer, flow; // flow = next step after ifthenelse
54+
int ifPointer = blockID;
55+
currentBlock = new Block(blockID++);
56+
node.getIf().apply(this); // evaluate the expression
57+
setStartAndSuccessor();
58+
node.getThen().apply(this);
59+
thenPointer = blockID-1; // last element of then
60+
addSuccessors.put(ifPointer, blockID);
61+
node.getElse().apply(this);
62+
flow = blockID;
63+
64+
// because of the normal algorithm according to setStartAndSuccessor() I need to remove the
65+
// first successor, because this one points to else, which is simply wrong at this point.
66+
blocks.get(thenPointer-1).getSuccessor().removeFirst();
67+
addSuccessors.put(thenPointer, flow); // Add normal program flow after the then block
68+
}
69+
/**
70+
* While
71+
*/
72+
@Override
73+
public void caseAWhileExpr(AWhileExpr node) {
74+
int temp = blockID;
75+
currentBlock = new Block(blockID++);
76+
node.getLeft().apply(this); // evaluate the expression
77+
setStartAndSuccessor();
78+
node.getRight().apply(this);
79+
addSuccessors.put(temp, blockID); // Add second successor for while loop
80+
addSuccessors.put(blockID - 1, temp);
81+
// blocks.get(blockID-2).getSuccessor().removeFirst();
82+
removeSuccessors.add(blockID-1); // Remove later the first successor
83+
}
84+
85+
private void setStartAndSuccessor() {
86+
if (lastBlock != null) // if it is the first block, do nothing
87+
lastBlock.addSuccessor(currentBlock);
88+
else
89+
startBlock = currentBlock;
90+
blocks.add(currentBlock); // Add currentBlock to the global list of blocks
91+
lastBlock = currentBlock;
92+
}
93+
/**
94+
* Add to the current visited block a new item to the Use list
95+
*/
96+
@Override
97+
public void caseAIdentifierExpr(AIdentifierExpr node) {
98+
String identifier = node.getIdentifier().toString().toLowerCase().replaceAll(" ","");
99+
if (currentBlock != null) {
100+
if (!currentBlock.hasUse()) {
101+
currentBlock.addUse(identifier);
102+
} else {
103+
if (!currentBlock.getUse().contains(identifier)) {
104+
currentBlock.addUse(identifier);
105+
}
106+
}
107+
}
108+
109+
}
110+
111+
/************************************************************************************************/
112+
public HashMap<Integer, Integer> getAddSuccessors() {
113+
return addSuccessors;
114+
}
115+
public LinkedList<Integer> getRemoveSuccessors() {
116+
return removeSuccessors;
117+
}
118+
public LinkedList<Block> getBlocks() {
119+
return blocks;
120+
}
121+
}

‎Liveness.java

Lines changed: 137 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,140 @@
1-
/**
2-
* Created with IntelliJ IDEA.
3-
* User: cmeter
4-
* Date: 10.01.13
5-
* Time: 19:53
6-
* To change this template use File | Settings | File Templates.
7-
*/
1+
import java.util.HashMap;
2+
import java.util.LinkedList;
3+
84
public class Liveness {
9-
String input;
10-
public Liveness(String input) {
11-
this.input = input;
5+
private GraphVisitor analysis;
6+
private LinkedList<Block> blocks;
7+
8+
public Liveness(GraphVisitor analysis) {
9+
this.analysis = analysis;
10+
this.blocks = analysis.getBlocks();
11+
addSuccessors();
12+
removeSuccessors();
13+
14+
startLiveness();
15+
debug();
16+
}
17+
18+
/**
19+
* Preparing all the missing and unneceassary successors for the liveness analysis
20+
*/
21+
private void addSuccessors() {
22+
// Add last successors to the blocks, which have been stored in a map
23+
HashMap<Integer, Integer> map = analysis.getAddSuccessors();
24+
int value;
25+
for (int key : map.keySet()) {
26+
value = map.get(key);
27+
if (value-1 < blocks.size()) { // protecting to run out of the index of blocks
28+
blocks.get(key-1).addSuccessor(blocks.get(value-1));
29+
}
30+
}
31+
}
32+
private void removeSuccessors() {
33+
for (Integer i : analysis.getRemoveSuccessors()) {
34+
blocks.get(i-1).getSuccessor().removeFirst();
35+
}
36+
}
37+
38+
/**
39+
* Print all information about the blocks
40+
*/
41+
private void debug() {
42+
System.out.println("# Evaluating Liveness...");
43+
44+
Block currentBlock;
45+
46+
for (int i = 0; i < blocks.size(); i++) {
47+
currentBlock = blocks.get(i);
48+
System.out.print("\t#" + currentBlock.getBlockID() + "\tDef: " + currentBlock.getDef() + "\t\tUse: " + currentBlock.getUse()+"\t\tSuccessor: ");
49+
for (Block block : currentBlock.getSuccessor()) {
50+
System.out.print(block.getBlockID() + " ");
51+
}
52+
System.out.print("\t\t IN: ");
53+
for (String element : currentBlock.getIn()) {
54+
System.out.print(element + " ");
55+
}
56+
System.out.print("\t\t OUT: ");
57+
for (String element : currentBlock.getOut()) {
58+
System.out.print(element+" ");
59+
}
60+
System.out.println();
61+
}
62+
}
63+
64+
/****************************************************************************************************/
65+
/**
66+
* Start liveness analysis
67+
*/
68+
private void startLiveness() {
69+
if (blocks.size() < Integer.MAX_VALUE) {
70+
Block currentBlock = blocks.getFirst();
71+
boolean changed = true;
72+
73+
calcFirstIteration(); // Copy use to in in all the blocks!
74+
LinkedList<String> diff;
75+
LinkedList<String> inSuccessor;
76+
boolean duplicate = false;
77+
78+
while (changed) {
79+
changed = false;
80+
for (int i = 0; i < blocks.size(); i++) {
81+
// Get IN
82+
diff = calcDiff(currentBlock);
83+
for (String element : diff) {
84+
for (String in : currentBlock.getIn()) {
85+
if (in.equals(element)) {
86+
duplicate = true;
87+
}
88+
}
89+
if (!duplicate) {
90+
currentBlock.addIn(element);
91+
changed = true;
92+
}
93+
}
94+
duplicate = false;
95+
// Get OUT
96+
inSuccessor = calcInOfSuccessor(currentBlock);
97+
for (String element : inSuccessor) {
98+
for (String out : currentBlock.getOut())
99+
if (out.equals(element)) {
100+
duplicate = true;
101+
}
102+
if (!duplicate) {
103+
currentBlock.addOut(element);
104+
changed = true;
105+
}
106+
}
107+
duplicate = false;
108+
currentBlock = blocks.get(i);
109+
}
110+
}
111+
}
112+
}
113+
private void calcFirstIteration() {
114+
for (Block block : blocks) {
115+
if (block.hasUse()) {
116+
for (String element : block.getUse()) {
117+
block.addIn(element);
118+
}
119+
}
120+
}
121+
}
122+
private LinkedList<String> calcDiff(Block currentBlock) {
123+
LinkedList<String> output = new LinkedList<String>();
124+
for (String out : currentBlock.getOut()) {
125+
if (!out.equals(currentBlock.getDef())) {
126+
output.add(out);
127+
}
128+
}
129+
return output;
130+
}
131+
private LinkedList<String> calcInOfSuccessor(Block currentBlock) {
132+
LinkedList<String> inSuccessor = new LinkedList<String>();
133+
for (Block successor : currentBlock.getSuccessor()) {
134+
for (String element : successor.getIn()) {
135+
inSuccessor.add(element);
136+
}
137+
}
138+
return inSuccessor;
12139
}
13140
}

‎Pascal.pas

Lines changed: 24 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,24 @@
1-
program parenthesis;
2-
var a,c,b : integer;
3-
begin
4-
a := 1;
5-
b := a;
6-
c := b+a;
7-
8-
while a < 10 do
9-
begin
10-
a := a+1;
11-
while b < 10 do
12-
b := b+1;
13-
begin
14-
while c < 10 do
15-
begin
16-
writeln(c);
17-
break;
18-
writeln(111111);
19-
end;
20-
break;
21-
writeln(222222);
22-
end;
23-
break;
24-
writeln(333333);
25-
end
26-
writeln(999999);
27-
end.
1+
Program IlovePriNum;
2+
Var i, n: Integer;
3+
Var prim: Boolean;
4+
Begin
5+
n := 42;
6+
i := 2;
7+
prim := true;
8+
while true do
9+
BEGIN
10+
if (n mod i)=0 then
11+
BEGIN
12+
writeln(i);
13+
prim := false;
14+
break;
15+
END else
16+
i := i + 1;
17+
if i=(n-1) then
18+
BEGIN
19+
prim := true;
20+
break;
21+
END;
22+
END;
23+
writeln(42)
24+
End.

0 commit comments

Comments
 (0)