Skip to content

Liveness Analysis in Python III

October 13, 2015

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(";")[0]
    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[0]
        line=sline[1:]
    else:
        line=line.strip().split();
    if len(line)==0:
        return([label,opcode,op1,op2])
    opcode=line[0]
    if opcode not in zeroops:
        op1=line[1].strip().split(',')[0]
        if opcode not in oneops:
            op2=line[1].strip().split(',')[1]
    return [label,opcode,op1,op2]      
    
    
def opcode(which):
    opc=""
    opc=parse(n)[1]
    return opc
def op1(which):
    op1=""
    op1=parse(n)[2]
    return op1
def op2(which):
    op2=""
    op2=parse(n)[3]
    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
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: