Skip to content

Navigation Menu

Sign in

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit fbdc01d

Browse filesBrowse files
n2on2o
committed
Added first version of a liveness analysis
1 parent f361901 commit fbdc01d
Copy full SHA for fbdc01d

31 files changed

+958
-324
lines changed

‎Block.java

Copy file name to clipboard
+71
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

Copy file name to clipboard
-401 Bytes
Binary file not shown.

‎GraphVisitor.java

Copy file name to clipboard
+121
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

Copy file name to clipboard
+137-10
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

Copy file name to clipboard
+24-27
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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.