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