thavlak_orc_stress.nim 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419
  1. discard """
  2. cmd: "nim c --gc:orc -d:useMalloc -d:nimStressOrc $file"
  3. valgrind: "leaks"
  4. output: "done"
  5. """
  6. import tables
  7. import sets
  8. import net
  9. type
  10. BasicBlock = object
  11. inEdges: seq[ref BasicBlock]
  12. outEdges: seq[ref BasicBlock]
  13. name: int
  14. proc newBasicBlock(name: int): ref BasicBlock =
  15. new(result)
  16. result.inEdges = newSeq[ref BasicBlock]()
  17. result.outEdges = newSeq[ref BasicBlock]()
  18. result.name = name
  19. proc hash(x: ref BasicBlock): int {.inline.} =
  20. result = x.name
  21. type
  22. BasicBlockEdge = object
  23. fr: ref BasicBlock
  24. to: ref BasicBlock
  25. Cfg = object
  26. basicBlockMap: Table[int, ref BasicBlock]
  27. edgeList: seq[BasicBlockEdge]
  28. startNode: ref BasicBlock
  29. proc newCfg(): Cfg =
  30. result = Cfg()
  31. result.basicBlockMap = initTable[int, ref BasicBlock]()
  32. result.edgeList = newSeq[BasicBlockEdge]()
  33. proc createNode(self: var Cfg, name: int): ref BasicBlock =
  34. #var node: ref BasicBlock
  35. result = self.basicBlockMap.getOrDefault(name)
  36. if result == nil:
  37. result = newBasicBlock(name)
  38. self.basicBlockMap.add name, result
  39. if self.startNode == nil:
  40. self.startNode = result
  41. proc addEdge(self: var Cfg, edge: BasicBlockEdge) =
  42. self.edgeList.add(edge)
  43. proc getNumNodes(self: Cfg): int =
  44. self.basicBlockMap.len
  45. proc newBasicBlockEdge(cfg: var Cfg, fromName: int, toName: int) =
  46. var newEdge = BasicBlockEdge()
  47. newEdge.fr = cfg.createNode(fromName)
  48. newEdge.to = cfg.createNode(toName)
  49. newEdge.fr.outEdges.add(newEdge.to)
  50. newEdge.to.inEdges.add(newEdge.fr)
  51. cfg.addEdge(newEdge)
  52. type
  53. SimpleLoop = object
  54. basicBlocks: seq[ref BasicBlock] # TODO: set here
  55. children: seq[ref SimpleLoop] # TODO: set here
  56. parent: ref SimpleLoop
  57. header: ref BasicBlock
  58. isRoot: bool
  59. isReducible: bool
  60. counter: int
  61. nestingLevel: int
  62. depthLevel: int
  63. proc newSimpleLoop(): ref SimpleLoop =
  64. new(result)
  65. result.basicBlocks = newSeq[ref BasicBlock]()
  66. result.children = newSeq[ref SimpleLoop]()
  67. result.parent = nil
  68. result.header = nil
  69. result.isRoot = false
  70. result.isReducible = true
  71. result.counter = 0
  72. result.nestingLevel = 0
  73. result.depthLevel = 0
  74. proc addNode(self: ref SimpleLoop, bb: ref BasicBlock) =
  75. self.basicBlocks.add bb
  76. proc addChildLoop(self: ref SimpleLoop, loop: ref SimpleLoop) =
  77. self.children.add loop
  78. proc setParent(self: ref SimpleLoop, parent: ref SimpleLoop) =
  79. self.parent = parent
  80. self.parent.addChildLoop(self)
  81. proc setHeader(self: ref SimpleLoop, bb: ref BasicBlock) =
  82. self.basicBlocks.add(bb)
  83. self.header = bb
  84. proc setNestingLevel(self: ref SimpleLoop, level: int) =
  85. self.nestingLevel = level
  86. if level == 0: self.isRoot = true
  87. var loop_counter: int = 0
  88. type
  89. Lsg = object
  90. loops: seq[ref SimpleLoop]
  91. root: ref SimpleLoop
  92. proc createNewLoop(self: var Lsg): ref SimpleLoop =
  93. var s = newSimpleLoop()
  94. loop_counter += 1
  95. s.counter = loop_counter
  96. s
  97. proc addLoop(self: var Lsg, l: ref SimpleLoop) =
  98. self.loops.add l
  99. proc newLsg(): Lsg =
  100. result = Lsg()
  101. result.loops = newSeq[ref SimpleLoop]()
  102. result.root = result.createNewLoop()
  103. result.root.setNestingLevel(0)
  104. result.addLoop(result.root)
  105. proc getNumLoops(self: Lsg): int =
  106. self.loops.len
  107. type
  108. UnionFindNode = object
  109. parent: ref UnionFindNode
  110. bb: ref BasicBlock
  111. l: ref SimpleLoop
  112. dfsNumber: int
  113. proc newUnionFindNode(): ref UnionFindNode =
  114. new(result)
  115. result.parent = nil
  116. result.bb = nil
  117. result.l = nil
  118. result.dfsNumber = 0
  119. proc initNode(self: ref UnionFindNode, bb: ref BasicBlock, dfsNumber: int) =
  120. self.parent = self
  121. self.bb = bb
  122. self.dfsNumber = dfsNumber
  123. proc findSet(self: ref UnionFindNode): ref UnionFindNode =
  124. var nodeList = newSeq[ref UnionFindNode]()
  125. var node = self
  126. while node != node.parent:
  127. var parent = node.parent
  128. if parent != parent.parent: nodeList.add node
  129. node = parent
  130. for iter in nodeList: iter.parent = node.parent
  131. node
  132. proc union(self: ref UnionFindNode, unionFindNode: ref UnionFindNode) =
  133. self.parent = unionFindNode
  134. const
  135. BB_NONHEADER = 1 # a regular BB
  136. BB_REDUCIBLE = 2 # reducible loop
  137. BB_SELF = 3 # single BB loop
  138. BB_IRREDUCIBLE = 4 # irreducible loop
  139. BB_DEAD = 5 # a dead BB
  140. # # Marker for uninitialized nodes.
  141. UNVISITED = -1
  142. # # Safeguard against pathologic algorithm behavior.
  143. MAXNONBACKPREDS = (32 * 1024)
  144. type
  145. HavlakLoopFinder = object
  146. cfg: Cfg
  147. lsg: Lsg
  148. proc newHavlakLoopFinder(cfg: sink Cfg, lsg: sink Lsg): HavlakLoopFinder =
  149. result = HavlakLoopFinder()
  150. result.cfg = cfg
  151. result.lsg = lsg
  152. proc isAncestor(w: int, v: int, last: seq[int]): bool =
  153. w <= v and v <= last[w]
  154. proc dfs(currentNode: ref BasicBlock, nodes: var seq[ref UnionFindNode], number: var Table[ref BasicBlock, int], last: var seq[int], current: int): int =
  155. nodes[current].initNode(currentNode, current)
  156. number[currentNode] = current
  157. var lastid = current
  158. for target in currentNode.outEdges:
  159. if number[target] == UNVISITED:
  160. lastid = dfs(target, nodes, number, last, lastid + 1)
  161. last[number[currentNode]] = lastid
  162. return lastid
  163. proc findLoops(self: var HavlakLoopFinder): int =
  164. var startNode = self.cfg.startNode
  165. if startNode == nil: return 0
  166. var size = self.cfg.getNumNodes
  167. var nonBackPreds = newSeq[HashSet[int]]()
  168. var backPreds = newSeq[seq[int]]()
  169. var number = initTable[ref BasicBlock, int]()
  170. var header = newSeq[int](size)
  171. var types = newSeq[int](size)
  172. var last = newSeq[int](size)
  173. var nodes = newSeq[ref UnionFindNode]()
  174. for i in 1..size:
  175. nonBackPreds.add initHashSet[int](1)
  176. backPreds.add newSeq[int]()
  177. nodes.add newUnionFindNode()
  178. # Step a:
  179. # - initialize all nodes as unvisited.
  180. # - depth-first traversal and numbering.
  181. # - unreached BB's are marked as dead.
  182. #
  183. for v in self.cfg.basicBlockMap.values: number[v] = UNVISITED
  184. discard dfs(startNode, nodes, number, last, 0)
  185. # Step b:
  186. # - iterate over all nodes.
  187. #
  188. # A backedge comes from a descendant in the DFS tree, and non-backedges
  189. # from non-descendants (following Tarjan).
  190. #
  191. # - check incoming edges 'v' and add them to either
  192. # - the list of backedges (backPreds) or
  193. # - the list of non-backedges (nonBackPreds)
  194. #
  195. for w in 0 ..< size:
  196. header[w] = 0
  197. types[w] = BB_NONHEADER
  198. var nodeW = nodes[w].bb
  199. if nodeW != nil:
  200. for nodeV in nodeW.inEdges:
  201. var v = number[nodeV]
  202. if v != UNVISITED:
  203. if isAncestor(w, v, last):
  204. backPreds[w].add v
  205. else:
  206. nonBackPreds[w].incl v
  207. else:
  208. types[w] = BB_DEAD
  209. # Start node is root of all other loops.
  210. header[0] = 0
  211. # Step c:
  212. #
  213. # The outer loop, unchanged from Tarjan. It does nothing except
  214. # for those nodes which are the destinations of backedges.
  215. # For a header node w, we chase backward from the sources of the
  216. # backedges adding nodes to the set P, representing the body of
  217. # the loop headed by w.
  218. #
  219. # By running through the nodes in reverse of the DFST preorder,
  220. # we ensure that inner loop headers will be processed before the
  221. # headers for surrounding loops.
  222. for w in countdown(size - 1, 0):
  223. # this is 'P' in Havlak's paper
  224. var nodePool = newSeq[ref UnionFindNode]()
  225. var nodeW = nodes[w].bb
  226. if nodeW != nil: # dead BB
  227. # Step d:
  228. for v in backPreds[w]:
  229. if v != w:
  230. nodePool.add nodes[v].findSet
  231. else:
  232. types[w] = BB_SELF
  233. # Copy nodePool to workList.
  234. #
  235. var workList = newSeq[ref UnionFindNode]()
  236. for x in nodePool: workList.add x
  237. if nodePool.len != 0: types[w] = BB_REDUCIBLE
  238. # work the list...
  239. #
  240. while workList.len > 0:
  241. var x = workList[0]
  242. workList.del(0)
  243. # Step e:
  244. #
  245. # Step e represents the main difference from Tarjan's method.
  246. # Chasing upwards from the sources of a node w's backedges. If
  247. # there is a node y' that is not a descendant of w, w is marked
  248. # the header of an irreducible loop, there is another entry
  249. # into this loop that avoids w.
  250. #
  251. # The algorithm has degenerated. Break and
  252. # return in this case.
  253. #
  254. var nonBackSize = nonBackPreds[x.dfsNumber].len
  255. if nonBackSize > MAXNONBACKPREDS: return 0
  256. for iter in nonBackPreds[x.dfsNumber]:
  257. var y = nodes[iter]
  258. var ydash = y.findSet
  259. if not isAncestor(w, ydash.dfsNumber, last):
  260. types[w] = BB_IRREDUCIBLE
  261. nonBackPreds[w].incl ydash.dfsNumber
  262. else:
  263. if ydash.dfsNumber != w and not nodePool.contains(ydash):
  264. workList.add ydash
  265. nodePool.add ydash
  266. # Collapse/Unionize nodes in a SCC to a single node
  267. # For every SCC found, create a loop descriptor and link it in.
  268. #
  269. if (nodePool.len > 0) or (types[w] == BB_SELF):
  270. var l = self.lsg.createNewLoop
  271. l.setHeader(nodeW)
  272. l.isReducible = types[w] != BB_IRREDUCIBLE
  273. # At this point, one can set attributes to the loop, such as:
  274. #
  275. # the bottom node:
  276. # iter = backPreds(w).begin();
  277. # loop bottom is: nodes(iter).node;
  278. #
  279. # the number of backedges:
  280. # backPreds(w).size()
  281. #
  282. # whether this loop is reducible:
  283. # types(w) != BB_IRREDUCIBLE
  284. #
  285. nodes[w].l = l
  286. for node in nodePool:
  287. # Add nodes to loop descriptor.
  288. header[node.dfsNumber] = w
  289. node.union(nodes[w])
  290. # Nested loops are not added, but linked together.
  291. var node_l = node.l
  292. if node_l != nil:
  293. node_l.setParent(l)
  294. else:
  295. l.addNode(node.bb)
  296. self.lsg.addLoop(l)
  297. result = self.lsg.getNumLoops
  298. type
  299. LoopTesterApp = object
  300. cfg: Cfg
  301. lsg: Lsg
  302. proc newLoopTesterApp(): LoopTesterApp =
  303. result = LoopTesterApp()
  304. result.cfg = newCfg()
  305. result.lsg = newLsg()
  306. proc buildDiamond(self: var LoopTesterApp, start: int): int =
  307. var bb0 = start
  308. newBasicBlockEdge(self.cfg, bb0, bb0 + 1)
  309. newBasicBlockEdge(self.cfg, bb0, bb0 + 2)
  310. newBasicBlockEdge(self.cfg, bb0 + 1, bb0 + 3)
  311. newBasicBlockEdge(self.cfg, bb0 + 2, bb0 + 3)
  312. result = bb0 + 3
  313. proc buildConnect(self: var LoopTesterApp, start1: int, end1: int) =
  314. newBasicBlockEdge(self.cfg, start1, end1)
  315. proc buildStraight(self: var LoopTesterApp, start: int, n: int): int =
  316. for i in 0..n-1:
  317. self.buildConnect(start + i, start + i + 1)
  318. result = start + n
  319. proc buildBaseLoop(self: var LoopTesterApp, from1: int): int =
  320. var header = self.buildStraight(from1, 1)
  321. var diamond1 = self.buildDiamond(header)
  322. var d11 = self.buildStraight(diamond1, 1)
  323. var diamond2 = self.buildDiamond(d11)
  324. var footer = self.buildStraight(diamond2, 1)
  325. self.buildConnect(diamond2, d11)
  326. self.buildConnect(diamond1, header)
  327. self.buildConnect(footer, from1)
  328. result = self.buildStraight(footer, 1)
  329. proc run(self: var LoopTesterApp) =
  330. discard self.cfg.createNode(0)
  331. discard self.buildBaseLoop(0)
  332. discard self.cfg.createNode(1)
  333. self.buildConnect(0, 2)
  334. for i in 1..8:
  335. # yes, it's 8 and it's correct.
  336. var h = newHavlakLoopFinder(self.cfg, newLsg())
  337. discard h.findLoops()
  338. echo "done"
  339. var l = newLoopTesterApp()
  340. l.run()