Skip to content

Liveness Analysis in Python IV

October 13, 2015

So I redid the parsing part which did not get prettier but at the same time i added a bunch of opcodes and successor analysis using branches. I applied it to the delay routine and the results look correct. The bumps before the passes list below is the dictionary of target line numbers for labels and the list of successors for statements.

Python Liveness analysis III
program to analyze:
{'L11': 12, 'L7': 14, 'L8': 8, '_delay': 1, 'L9': 10}
[[1], [2], [3], [4], [5], [6], [7], [12], [9], [10], [11], [12], [13], [14, 8], [14], [15], [16], [17], [18], []]
*********************
1 passes 6 changes
2 passes 8 changes
3 passes 11 changes
4 passes 9 changes
5 passes 6 changes
6 passes 4 changes
7 passes 1 changes
8 passes 0 changes
0  ['R12']
1 _delay:		;framesize=10 ['R12']
2 	pushf R6	;opt11 ['R12']
3 	pushl R7	;opt11 ['R12']
4 	reserve 4; save room for outgoing arguments ['R12']
5 	cpy2 R7,R12; function(2054) 1 ['R7']
6 	ldaD R6,1; reg:acon ['R6', 'R7']
7 	lbr L11 ['R6', 'R7']
8 L8: ['R6', 'R7']
9 	Ccall _oneMsBN; CALLI2(ar) ['R6', 'R7']
10 L9: ['R6', 'R7']
11 	incm R6,1 ['R6', 'R7']
12 L11: ['R6', 'R7']
13 	jneU2 R6,R7,L8; NE ['R6', 'R7']
14 L7: []
15 	release 4; release room for outgoing arguments []
16 	popr R7 []
17 	popr R6 []
18 	Cretn ['rp1p2', 'r15']

The code is pretty awful but it’s here for my records. I need to think about why it seems so nasty and whether I could improve it. Note that getting this to the point where it would be any use would mean hundreds of opcode definitions and a bunch of optimization rules that would just clutter it further. One way to go would be to pseudocode it in C++(which i dislike but i can code expressively in) and see whether that leads anywhere.

print "Python Liveness analysis III"
zeroops=["cretn"]
ignores=["equ","listing","include","db","reserve","release","ccall","seq",
         "pushf","pushm","pushl","pushr","ldi","smi","bnz"]
loads=["ldad","popr"]
incdecs=["Incr","incm","dec","decm"]
cjumps1=["jneu2"]
jumps=["lbr"]
copies=["cpy2"]
pgm=list();label=list();opcode=list();uses=list();sets=list();refs=list()
targets=dict() #branch targets
def loadpgm():
    fname=raw_input("program to analyze:")
    if fname=="":
        fname="livesamp"
    fname=fname+".asm"
    fhand=open(fname)
    for line in fhand:
        pgm.append(line.rstrip())
def parsepgm():
    for n in range(len(pgm)):
        src=pgm[n]
        label.append("");opcode.append("");uses.append([]);sets.append([]);refs.append([])
        if src.strip()=="":
            continue
        src=src.split(";")[0]
        if src.strip()=="":
            continue
        if src.find(":")>0:
            label[n]=src.split(":")[0]
            targets[label[n]]=n
            src=src.split(":")[1].strip()
            if src=="":
                continue
        #here we have a non-blank/comment unlableled line
        toks=src.split()
        opcode[n]=toks[0].strip().lower()
        if opcode[n] in zeroops or opcode[n] in ignores:
            continue
        ops=toks[1].split(',')
        if opcode[n] in copies:
            sets[n]=[ops[0]];uses[n]=[ops[1]]
        elif opcode[n] in incdecs:
            sets[n]=[ops[0]];uses[n]=[ops[0]]
        elif opcode[n] in cjumps1:
            uses[n]=[ops[0],ops[1]]
            refs[n]=[ops[2]]
        elif opcode[n] in jumps:
            refs[n]=[ops[0]]
        elif opcode[n] in loads:
            sets[n]=[ops[0]]
        else:
            print "ignoring",opcode[n]
        
loadpgm()
parsepgm()

livein=dict()
liveout=dict()
labels=dict()
successors=list()
print targets

for n in range(len(pgm)-1):
    if opcode[n] in cjumps1:
        successors.append([n+1,targets[refs[n][0]]])
    if opcode[n] in jumps:
        successors.append([targets[refs[n][0]]])
    else:
        successors.append([n+1])
successors.append([])
print successors
for n in range(len(pgm)):
    livein[n]=[]
    if opcode[n]=="cretn":
        liveout[n]=["rp1p2","r15"]
    else:
        liveout[n]=[]

print "*********************"
for k in range(1,100):
    changes=0
    for n in range(len(pgm)):
        for succ in successors[n]:
            for what in livein[succ]:
                if what not in liveout[n]:
                    liveout[n].append(what)
                    changes=changes+1
                    
    for n in range(len(pgm)):
        for what in uses[n]:
            if what not in livein[n]:
                livein[n].append(what)
                changes=changes+1

    for n in range(len(pgm)):
        for what in liveout[n]:
            if what not in sets[n] and what not in livein[n]:
                livein[n].append(what)
                changes=changes+1

    print k,"passes", changes,"changes"
    if changes==0:
        break
for n in range(len(pgm)):
    print n,pgm[n],liveout[n]
Advertisements

From → Uncategorized

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: