1#!/usr/bin/env python
2"""A ladder graph creation program.
3
4This is a python program that creates c source code that will generate
5CFGs that are ladder graphs.  Ladder graphs are generally the worst case
6for a lot of dominance related algorithms (Dominance frontiers, etc),
7and often generate N^2 or worse behavior.
8
9One good use of this program is to test whether your linear time algorithm is
10really behaving linearly.
11"""
12
13import argparse
14def 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
42if __name__ == '__main__':
43  main()
44