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
13from __future__ import print_function
14
15import argparse
16def main():
17  parser = argparse.ArgumentParser(description=__doc__)
18  parser.add_argument('rungs', type=int,
19                      help="Number of ladder rungs. Must be a multiple of 2")
20  args = parser.parse_args()
21  if (args.rungs % 2) != 0:
22    print("Rungs must be a multiple of 2")
23    return
24  print("int ladder(int *foo, int *bar, int x) {")
25  rung1 = range(0, args.rungs, 2)
26  rung2 = range(1, args.rungs, 2)
27  for i in rung1:
28    print("rung1%d:" % i)
29    print("*foo = x++;")
30    if i != rung1[-1]:
31      print("if (*bar) goto rung1%d;" % (i+2))
32      print("else goto rung2%d;" % (i+1))
33    else:
34      print("goto rung2%d;" % (i+1))
35  for i in rung2:
36    print("rung2%d:" % i)
37    print("*foo = x++;")
38    if i != rung2[-1]:
39      print("goto rung2%d;" % (i+2))
40    else:
41      print("return *foo;")
42  print("}")
43
44if __name__ == '__main__':
45  main()
46