Liveness Analysis in Python III
So I tried my new liveness analysis data structure and it’s much more satisfactory. The main loop of the program is much more believable:
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
The first “for” loop says that for statement n, the live registers on leaving the statement are the ones that are live entering any of its successors.
The second loop says that if a statement uses a register, the register is live on entry.
The third loop says that if a statement does not set a register then anything live after the statement is live before it.
obviously I could trivially combine those passes but i don’t think it matters much and i think there’s a more sophisticated combination approach that will occur to me sooner or later.
The reason for the last three lines in each block are that i need to track whether anything is changing in each pass so i can quit when i’m done. In my five statement toy program it takes 6 passes through the program for it to stop changing.
Python Liveness analysis II ********************* 1 passes 5 changes 2 passes 7 changes 3 passes 4 changes 4 passes 2 changes 5 passes 2 changes 6 passes 0 changes 0 cpy4 rl10,rl8 ['rl10', 'r15'] 1 ;fog of war ['rl10', 'r15'] 2 cpy4 rp1p2,rl10 ['rl10', 'rp1p2', 'r15'] 3 st4 pigs,rl10 ['rp1p2', 'r15'] 4 cretn ['rp1p2', 'r15']
A more serious problem is that parsing the assembly lines turned way uglier than i thought. It’s not just that the parse code itself is bad, it’s that i execute it about a million times for each pass. I think I need to do this once when i read the file and, instead of a function uses(n) that returns a list of registers used in statement n I would create a list uses indexed by n that would have the registers from the start.
zeroops=["cretn"] oneops=["ld2z"] twoops=["cpy2","cpy4","st2","st4"] def parse(n):# parse an assembly line into [label,opcode,op1,op2] line=pgm[n] label="" op1="" op2="" if line=="": return["","","",""] #line is null line=line.split(";") if line.strip()=="": return["","","",""] #line is blank or only a comment if not line.startswith(" ") or line.startswith("\t"): sline=line.strip().split(":") if len(sline)<2: #oops no : print "label error in line",n,pgm[n] quit() label=sline line=sline[1:] else: line=line.strip().split(); if len(line)==0: return([label,opcode,op1,op2]) opcode=line if opcode not in zeroops: op1=line.strip().split(',') if opcode not in oneops: op2=line.strip().split(',') return [label,opcode,op1,op2] def opcode(which): opc="" opc=parse(n) return opc def op1(which): op1="" op1=parse(n) return op1 def op2(which): op2="" op2=parse(n) return op2 def uses(which): usees= if opcode(which) in ["cpy4","st4"]: usees=[op2(which)] return usees def sets(which): setees= if opcode(which) in ["cpy4"]: setees=[op1(which)] return setees