Skip to content

Liveness Analysis With Bodgy Python

October 9, 2015

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.

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: