10c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar#!/usr/bin/env python 20c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar"""A ladder graph creation program. 30c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar 40c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga NainarThis is a python program that creates c source code that will generate 50c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga NainarCFGs that are ladder graphs. Ladder graphs are generally the worst case 60c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainarfor a lot of dominance related algorithms (Dominance frontiers, etc), 70c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainarand often generate N^2 or worse behavior. 80c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar 90c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga NainarOne good use of this program is to test whether your linear time algorithm is 100c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainarreally behaving linearly. 110c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar""" 120c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar 130c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainarimport argparse 140c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainardef main(): 150c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar parser = argparse.ArgumentParser(description=__doc__) 160c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar parser.add_argument('rungs', type=int, 170c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar help="Number of ladder rungs. Must be a multiple of 2") 180c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar args = parser.parse_args() 190c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (args.rungs % 2) != 0: 200c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "Rungs must be a multiple of 2" 210c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar return 220c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "int ladder(int *foo, int *bar, int x) {" 230c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar rung1 = xrange(0, args.rungs, 2) 240c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar rung2 = xrange(1, args.rungs, 2) 250c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar for i in rung1: 260c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "rung1%d:" % i 270c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "*foo = x++;" 280c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if i != rung1[-1]: 290c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "if (*bar) goto rung1%d;" % (i+2) 300c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "else goto rung2%d;" % (i+1) 310c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar else: 320c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "goto rung2%d;" % (i+1) 330c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar for i in rung2: 340c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "rung2%d:" % i 350c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "*foo = x++;" 360c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if i != rung2[-1]: 370c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "goto rung2%d;" % (i+2) 380c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar else: 390c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "return *foo;" 400c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar print "}" 410c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar 420c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainarif __name__ == '__main__': 430c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar main() 44