1 #!/usr/bin/env python 2 """A ladder graph creation program. 3 4 This is a python program that creates c source code that will generate 5 CFGs that are ladder graphs. Ladder graphs are generally the worst case 6 for a lot of dominance related algorithms (Dominance frontiers, etc), 7 and often generate N^2 or worse behavior. 8 9 One good use of this program is to test whether your linear time algorithm is 10 really behaving linearly. 11 """ 12 13 import argparse 14 def main(): 15 parser = argparse.ArgumentParser(description=__doc__) 16 parser.add_argument('rungs', type=int, 17 help="Number of ladder rungs. Must be a multiple of 2") 18 args = parser.parse_args() 19 if (args.rungs % 2) != 0: 20 print "Rungs must be a multiple of 2" 21 return 22 print "int ladder(int *foo, int *bar, int x) {" 23 rung1 = xrange(0, args.rungs, 2) 24 rung2 = xrange(1, args.rungs, 2) 25 for i in rung1: 26 print "rung1%d:" % i 27 print "*foo = x++;" 28 if i != rung1[-1]: 29 print "if (*bar) goto rung1%d;" % (i+2) 30 print "else goto rung2%d;" % (i+1) 31 else: 32 print "goto rung2%d;" % (i+1) 33 for i in rung2: 34 print "rung2%d:" % i 35 print "*foo = x++;" 36 if i != rung2[-1]: 37 print "goto rung2%d;" % (i+2) 38 else: 39 print "return *foo;" 40 print "}" 41 42 if __name__ == '__main__': 43 main() 44
