Skip to content

Huh – The Awkwardness of Aligns – Branch Optimization III

February 13, 2018

I redid the branch optimization code to eliminate recursion. The new version does a single pass over the program to locate all the labels and long branches, then starts back down the list of branches looking at their location vs their target. When it finds an unnecessary long branch it shortens it in the program text and runs over all the branches and labels further down the program subtracting one from their location. This gets rid of the recursion but does a LOT of looping through the lists – in one modest sized C program it does 170 fixup scans making 18000 branch fixups and 24000 label fixups. The code is easier to understand though. One major problem is that it doesn’t work! Because I don’t look at the actual code when i’m doing the fixups – just the list ob branches and labels – I’m not processing align statements which will have a different effect on the program counter when they get moved. The only thing I can think of to do is to treat the aligns like jumps – include them in the jump list and, when I come to one, give it the “length” required to do the alignment. I’m frankly not clear as to whether that will work!


UPDATE:
It does work although I don’t completely trust it. If it fails though, the worst that will happen is that i will get assembly errors – all i’m doing is changing long to short branches and if i’m wrong it will be obvious. The 50 line comparulator test program ran successfully with 175 of 210 long branches shortened. I looked at some of the others and they were genuinely not convertible – the code is fairly long and a switch statement generates a lot of branches. If It was important I could manipulate the C source to reduce branch spans – maybe more function calls.

The other interesting thing about this is that if this were routine I could get rid of at least some of the “align”s and use long branches knowing they would probably get optimized out.

The current version of the code is called branchalignear.py.

#18-02-10 linear two pass scan - no recursion
#18-02-13 trying to include aligns with jumps.
import sys
sys.path.append('/lcc42/examples/branchanal/')
from opdefsNW import *
from opfuncsNW import *
asminfile = open(sys.argv[1],'r')
asmdata = asminfile.read().expandtabs()
asmlines = asmdata.split('\n')
print len(asmlines), 'lines read'
jumpcount=0;aligncount=0
repcount=0
progsize=0
i=0
tln=0;pln=0;mln=0 #temp label numbers for $$,+ -
labeldefs={}
labelrefs=[]
def ireplace(old, new, text): #    Replace case insensitive
    index_l = text.lower().index(old.lower())
    return text[:index_l] + new + text[index_l + len(old):] 
def gotlabel(token):
	global tln,pln,mln
	label=token.split(':')[0]
	if label.startswith("$$"):
		label+=str(tln)
	elif label.startswith("+"): #check for temporary label
		label+=str(pln)
		pln+=1
	elif label.startswith("-"): #check for temporary label
		mln+=1
		label+=str(mln)
	else:
		tln+=1
	labeldefs[label]=progsize

def fmtlabel(label):
	global tln,pln,mln
	if label.startswith("$$"):
		label+=str(tln)
	elif label.startswith("+"): #check for temporary label
		label+=str(pln)
	elif label.startswith("-"): #check for temporary label
		label+=str(mln)
	return label

for line in asmlines:
	aline=line.split(";")[0] #get rid of any comment portion
	tokens=aline.split();
	if tokens:
		#print "%d %X %s" % (i+1,progsize,aline)
		if (not aline.startswith(' ')) or tokens[0].endswith(':'): #if it has a label
			gotlabel(tokens[0])
			tokens=tokens[1:]			#get rid of it
		if tokens:
			if tokens[0].lower() in jumpdefs:
				jumpcount+=1
				labelrefs.append([i,progsize,tokens[0].lower(),fmtlabel(tokens[1].split(",")[0])])
			elif tokens[0].lower()=="align":
				aligncount+=1
				labelrefs.append([i,progsize,tokens[0].lower(),tokens[1].split(",")[0],process(tokens,progsize)])
				#print "align ",i,progsize,tokens[0].lower(),tokens[1].split(",")[0],process(tokens,progsize)
			progsize+=process(tokens,progsize)

	i+=1;
print "pass 1 completed. ",len(labeldefs)," labels found. ",len(labelrefs)," jumps found."
#print labelrefs,labeldefs
adjb=0;adjl=0
repacount=0
i=0
for ref in labelrefs: # line index, location, branch op(or align), label referenced(or alignment)
	line=ref[0]; loc=ref[1]; brop=ref[2]; label=ref[3]
	adjamt=0
	if brop=="align":
		repacount+=1
		newsize=process([brop,label],loc)
		adjamt=newsize-ref[4]
		labelrefs[i][4]=newsize
		#print "*A*%4d %4x %s" %(line+1,loc,brop), label, ref[4],newsize, adjamt
	elif (loc+1)//256==labeldefs[label]//256:
		asmlines[line]=ireplace(brop,jumpreps[brop],asmlines[line])
		#print "%4d %4x %s %4x" %(line+1,loc,asmlines[line],labeldefs[label])
		repcount+=1
		adjamt=-1
	if not adjamt==0:
		for adjref in labelrefs: # line index, location, branch op, label referenced
			if adjref[0]>line: # for jumps further down the way
				if adjref[2]=="align":
					pass #print "A%d %x "%(adjref[0],adjref[1]),adjref[2],adjref[3],adjref[4]
				adjref[1]+=adjamt #get adjusted
				adjb+=1
		for k, labloc in labeldefs.iteritems():
			if labloc>loc:
				labeldefs[k] +=adjamt
				adjl+=1
	i+=1
#print labeldefs
#for k,labloc in labeldefs.iteritems():
#	print "%4x %s" % (labloc,k)
print repcount,"+",repacount," fixup cycles ",adjb," branch fixups ",adjl," label fixups"
asmoutfile=open(sys.argv[1].split('.')[0]+".basm",'w'); asmoutfile.truncate()
i=0
for line in asmlines:
	asmoutfile.write(line+'\n')
	i+=1
print i, 'lines written'
print "%d long jumps found, %d shortened" % (jumpcount,repcount)

Also for the record, when i run this of one of the selftest programs 00comparulator.c the 50 lines of C generate 6400 lines of assembly(it’s compilicated code and it uses the floating point library) including 210 long jumps of which 170 get optimized away. As noted above the 170 branch optimizations cause 20100 branch/align fixups and 25222 label fixups.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: