utils/create_ladder_graph.py

   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()