Liveness Analysis With Bodgy Python
I’ve always wanted to do liveness analysis as part of the optimization in LCC1802 – the 1802 C compiler. It would address sequences like
ldi4 rl10,1
cpy4 rp1p2,rl10
where the copy from RL10 to RP1P2 is a waste if RL10 is never used again i.e. it’s not “live” after the copy.
This is classic compiler stuff that i learned last year and i figured python would be good for parsing and manipulating the assembly language.
I had a go at it today(rainy day fun!) and the result is horrible but it works, sort of. It’s based around a python dictionary where they keys are in the form n-register-i/o where n is a line number(starting with 0), register is one of the cpu registers or pairs, and i/o is either “in” or “out”. So, in my limited example I have register pairs rl8, l10, and rp1p2. For a 5 statement program I end up with 30 dictionary entries like {“0-rp1p2-in”:False} indicating that on entry to statement 0 rp1p2 is not live.
I initialize all the entries to False EXCEPT for return statements where I set the entry for “n-rp1p2-out” to True because I know that that’s where the return value has to go.
There’s a list of successors for each statement which, in my play case, is just the next statement. Branches would be different and conditional branches would have two successors.
Having set that up, I go through the program repeatedly with a set of rules:
If statement n’s successor says a register is live-in then it’s live-out for statement n. If a register is used by a statement then it’s live-in, otherwise if it’s set by a statement it’s dead-in**. Finally, if a statement doesn’t ref a register then it’s in state is the same as its out state.
I keep going through the program until the dictionary doesn’t change.
I bodged this together and it’s hard to understand but it’s also a horrible abuse of dictionaries. For a small program it works ok but i need a better data structure.
The output of the program is, however, correct so maybe it’s something I can build on.
cpy4 rl10,rl8 fog of war cpy4 rp1p2,rl10 st4 pigs,rl10 cretn
0 cpy4 rl10,rl8 rl10 1 fog of war rl10 2 cpy4 rp1p2,rl10 rp1p2 rl10 3 st4 pigs,rl10 rp1p2 4 cretn rp1p2
print "Python Liveness analysis"
from copy import deepcopy
def uses(which,what):
# print "does:",pgm[which]," use ",what,"?"
# if pgm[which].strip()=="cretn":
# if what=="rp1p2":
# print "yes(indirectly)"
# return True
# else:
# print "no(not even indirectly)"
# return False
if pgm[which].endswith(what):
# print "yes!"
return True
else:
# print "no!"
return False
def sets(which,what):
# print "does:",pgm[which]," set ",what,"?"
toks=pgm[which].split()
opcode=toks[0].strip()
if opcode=="cpy4":
op1=toks[1].split(",")[0]
# print "op1 is:",op1
if op1==what:
# print "yes!"
return True
else:
# print "no!"
return False
else:
# print "no!"
return False
pgm=[" cpy4 rl10,rl8"," fog of war"," cpy4 rp1p2,rl10"," st4 pigs,rl10"," cretn"]
#pgm=[" cpy4 rl10,rl8"," cpy4 rp1p2,rl10"," cretn"]
regs=["rp1p2","rl8","rl10"]
live=dict()
oldlive=dict()
successors=list()
#for n in range(len(pgm)):
# print n,pgm[n]
for n in range(len(pgm)-1):
successors.append([n+1])
successors.append([])
for what in regs:
for n in range(len(pgm)):
for io in ["in","out"]:
live[str(n)+"-"+what+"-"+io]=False
if pgm[n].strip()=="cretn":
live[str(n)+"-"+"rp1p2"+"-"+"out"]=True
print live
print "*********************"
for k in range(5):
oldlive=deepcopy(live)
for n in range(len(pgm)):
for succ in successors[n]:
print "s(",n,succ,")=",
for what in regs:
if live[str(succ)+"-"+what+"-"+"in"]==True:
print what,"X",
live[str(n)+"-"+what+"-"+"out"]=True
print
# print live
for n in range(len(pgm)):
for what in regs:
if uses(n,what):
live[str(n)+"-"+what+"-"+"in"]=True
elif sets(n,what):
live[str(n)+"-"+what+"-"+"in"]=False
else:
live[str(n)+"-"+what+"-"+"in"]=live[str(n)+"-"+what+"-"+"out"]
# print live
# print oldlive
if cmp(live,oldlive)==0:
print k,"***no change"
break
else:
print k,"***change"
for n in range(len(pgm)):
print n,pgm[n],
for what in regs:
if live[str(n)+"-"+what+"-"+"out"]==True:
print what,
print
print
for livekey,livevalue in sorted(live.items()):
print livekey,"\t",livevalue
Python Liveness analysis
{'2-rp1p2-in': False, '4-rl8-out': False, '2-rl8-in': False, '1-rl8-in': False, '4-rl10-in': False, '2-rl10-out': False, '2-rl8-out': False, '0-rp1p2-out': False, '1-rl10-in': False, '3-rl8-out': False, '4-rp1p2-out': True, '1-rp1p2-out': False, '0-rl10-out': False, '0-rl8-out': False, '1-rl10-out': False, '2-rp1p2-out': False, '3-rl10-out': False, '0-rl10-in': False, '3-rl10-in': False, '2-rl10-in': False, '3-rp1p2-in': False, '0-rp1p2-in': False, '1-rp1p2-in': False, '3-rp1p2-out': False, '4-rl10-out': False, '1-rl8-out': False, '4-rp1p2-in': False, '3-rl8-in': False, '4-rl8-in': False, '0-rl8-in': False}
*********************
s( 0 1 )=
s( 1 2 )=
s( 2 3 )=
s( 3 4 )=
0 ***change
s( 0 1 )=
s( 1 2 )= rl10 X
s( 2 3 )= rl10 X
s( 3 4 )= rp1p2 X
1 ***change
s( 0 1 )= rl10 X
s( 1 2 )= rl10 X
s( 2 3 )= rp1p2 X rl10 X
s( 3 4 )= rp1p2 X
2 ***change
s( 0 1 )= rl10 X
s( 1 2 )= rl10 X
s( 2 3 )= rp1p2 X rl10 X
s( 3 4 )= rp1p2 X
3 ***no change
0 cpy4 rl10,rl8 rl10
1 fog of war rl10
2 cpy4 rp1p2,rl10 rp1p2 rl10
3 st4 pigs,rl10 rp1p2
4 cretn rp1p2
0-rl10-in False
0-rl10-out True
0-rl8-in True
0-rl8-out False
0-rp1p2-in False
0-rp1p2-out False
1-rl10-in True
1-rl10-out True
1-rl8-in False
1-rl8-out False
1-rp1p2-in False
1-rp1p2-out False
2-rl10-in True
2-rl10-out True
2-rl8-in False
2-rl8-out False
2-rp1p2-in False
2-rp1p2-out True
3-rl10-in True
3-rl10-out False
3-rl8-in False
3-rl8-out False
3-rp1p2-in True
3-rp1p2-out True
4-rl10-in False
4-rl10-out False
4-rl8-in False
4-rl8-out False
4-rp1p2-in True
4-rp1p2-out True
**note to self. There could be an issue where things are not supposed to go from live to dead but i’m not preventing that.
olduino 