# Liveness Analysis in Python IV

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]

## Trackbacks & Pingbacks