Mercurial > hg > CbC > CbC_llvm

annotate utils/create_ladder_graph.py @ 171:66f3bfe93da9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 25 May 2020 11:07:02 +0900
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
171
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #!/usr/bin/env python
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 """A ladder graph creation program.
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 This is a python program that creates c source code that will generate
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 CFGs that are ladder graphs. Ladder graphs are generally the worst case
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 for a lot of dominance related algorithms (Dominance frontiers, etc),
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 and often generate N^2 or worse behavior.
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 One good use of this program is to test whether your linear time algorithm is
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 really behaving linearly.
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 """
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 from __future__ import print_function
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 import argparse
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 def main():
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 parser = argparse.ArgumentParser(description=__doc__)
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 parser.add_argument('rungs', type=int,
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 help="Number of ladder rungs. Must be a multiple of 2")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 args = parser.parse_args()
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 if (args.rungs % 2) != 0:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 print("Rungs must be a multiple of 2")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 return
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 print("int ladder(int *foo, int *bar, int x) {")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 rung1 = range(0, args.rungs, 2)
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 rung2 = range(1, args.rungs, 2)
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 for i in rung1:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 print("rung1%d:" % i)
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 print("*foo = x++;")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 if i != rung1[-1]:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 print("if (*bar) goto rung1%d;" % (i+2))
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 print("else goto rung2%d;" % (i+1))
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 else:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 print("goto rung2%d;" % (i+1))
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 for i in rung2:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 print("rung2%d:" % i)
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 print("*foo = x++;")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 if i != rung2[-1]:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 print("goto rung2%d;" % (i+2))
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 else:
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 print("return *foo;")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 print("}")
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 if __name__ == '__main__':
66f3bfe93da9 git version 2c4ca6832fa6b306ee6a7010bfb80a3f2596f824
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 main()