optimizer.nim 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291
  1. #
  2. #
  3. # The Nim Compiler
  4. # (c) Copyright 2020 Andreas Rumpf
  5. #
  6. # See the file "copying.txt", included in this
  7. # distribution, for details about the copyright.
  8. #
  9. ## Optimizer:
  10. ## - elide 'wasMoved(x); destroy(x)' pairs
  11. ## - recognize "all paths lead to 'wasMoved(x)'"
  12. import
  13. ast, renderer, idents, intsets
  14. from trees import exprStructuralEquivalent
  15. import std/strutils
  16. const
  17. nfMarkForDeletion = nfNone # faster than a lookup table
  18. type
  19. BasicBlock = object
  20. wasMovedLocs: seq[PNode]
  21. kind: TNodeKind
  22. hasReturn, hasBreak: bool
  23. label: PSym # can be nil
  24. parent: ptr BasicBlock
  25. Con = object
  26. somethingTodo: bool
  27. inFinally: int
  28. proc nestedBlock(parent: var BasicBlock; kind: TNodeKind): BasicBlock =
  29. BasicBlock(wasMovedLocs: @[], kind: kind, hasReturn: false, hasBreak: false,
  30. label: nil, parent: addr(parent))
  31. proc breakStmt(b: var BasicBlock; n: PNode) =
  32. var it = addr(b)
  33. while it != nil:
  34. it.wasMovedLocs.setLen 0
  35. it.hasBreak = true
  36. if n.kind == nkSym:
  37. if it.label == n.sym: break
  38. else:
  39. # unnamed break leaves the block is nkWhileStmt or the like:
  40. if it.kind in {nkWhileStmt, nkBlockStmt, nkBlockExpr}: break
  41. it = it.parent
  42. proc returnStmt(b: var BasicBlock) =
  43. b.hasReturn = true
  44. var it = addr(b)
  45. while it != nil:
  46. it.wasMovedLocs.setLen 0
  47. it = it.parent
  48. proc mergeBasicBlockInfo(parent: var BasicBlock; this: BasicBlock) {.inline.} =
  49. if this.hasReturn:
  50. parent.wasMovedLocs.setLen 0
  51. parent.hasReturn = true
  52. proc wasMovedTarget(matches: var IntSet; branch: seq[PNode]; moveTarget: PNode): bool =
  53. result = false
  54. for i in 0..<branch.len:
  55. if exprStructuralEquivalent(branch[i][1].skipAddr, moveTarget,
  56. strictSymEquality = true):
  57. result = true
  58. matches.incl i
  59. proc intersect(summary: var seq[PNode]; branch: seq[PNode]) =
  60. # keep all 'wasMoved(x)' calls in summary that are also in 'branch':
  61. var i = 0
  62. var matches = initIntSet()
  63. while i < summary.len:
  64. if wasMovedTarget(matches, branch, summary[i][1].skipAddr):
  65. inc i
  66. else:
  67. summary.del i
  68. for m in matches:
  69. summary.add branch[m]
  70. proc invalidateWasMoved(c: var BasicBlock; x: PNode) =
  71. var i = 0
  72. while i < c.wasMovedLocs.len:
  73. if exprStructuralEquivalent(c.wasMovedLocs[i][1].skipAddr, x,
  74. strictSymEquality = true):
  75. c.wasMovedLocs.del i
  76. else:
  77. inc i
  78. proc wasMovedDestroyPair(c: var Con; b: var BasicBlock; d: PNode) =
  79. var i = 0
  80. while i < b.wasMovedLocs.len:
  81. if exprStructuralEquivalent(b.wasMovedLocs[i][1].skipAddr, d[1].skipAddr,
  82. strictSymEquality = true):
  83. b.wasMovedLocs[i].flags.incl nfMarkForDeletion
  84. c.somethingTodo = true
  85. d.flags.incl nfMarkForDeletion
  86. b.wasMovedLocs.del i
  87. else:
  88. inc i
  89. proc analyse(c: var Con; b: var BasicBlock; n: PNode) =
  90. case n.kind
  91. of nkCallKinds:
  92. var special = false
  93. var reverse = false
  94. if n[0].kind == nkSym:
  95. let s = n[0].sym
  96. let name = s.name.s.normalize
  97. if s.magic == mWasMoved or name == "=wasmoved":
  98. b.wasMovedLocs.add n
  99. special = true
  100. elif name == "=destroy":
  101. if c.inFinally > 0 and (b.hasReturn or b.hasBreak):
  102. discard "cannot optimize away the destructor"
  103. else:
  104. c.wasMovedDestroyPair b, n
  105. special = true
  106. elif name == "=sink":
  107. reverse = true
  108. if not special:
  109. if not reverse:
  110. for i in 0 ..< n.len:
  111. analyse(c, b, n[i])
  112. else:
  113. #[ Test destructor/tmatrix.test3:
  114. Prevent this from being elided. We should probably
  115. find a better solution...
  116. `=sink`(b, -
  117. let blitTmp = b;
  118. wasMoved(b);
  119. blitTmp + a)
  120. `=destroy`(b)
  121. ]#
  122. for i in countdown(n.len-1, 0):
  123. analyse(c, b, n[i])
  124. if canRaise(n[0]): returnStmt(b)
  125. of nkSym:
  126. # any usage of the location before destruction implies we
  127. # cannot elide the 'wasMoved(x)':
  128. b.invalidateWasMoved n
  129. of nkNone..pred(nkSym), succ(nkSym)..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef,
  130. nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo,
  131. nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt,
  132. nkExportStmt, nkPragma, nkCommentStmt, nkBreakState,
  133. nkTypeOfExpr, nkMixinStmt, nkBindStmt:
  134. discard "do not follow the construct"
  135. of nkAsgn, nkFastAsgn, nkSinkAsgn:
  136. # reverse order, see remark for `=sink`:
  137. analyse(c, b, n[1])
  138. analyse(c, b, n[0])
  139. of nkIfStmt, nkIfExpr:
  140. let isExhaustive = n[^1].kind in {nkElse, nkElseExpr}
  141. var wasMovedSet: seq[PNode] = @[]
  142. for i in 0 ..< n.len:
  143. var branch = nestedBlock(b, n[i].kind)
  144. analyse(c, branch, n[i])
  145. mergeBasicBlockInfo(b, branch)
  146. if isExhaustive:
  147. if i == 0:
  148. wasMovedSet = move(branch.wasMovedLocs)
  149. else:
  150. wasMovedSet.intersect(branch.wasMovedLocs)
  151. for i in 0..<wasMovedSet.len:
  152. b.wasMovedLocs.add wasMovedSet[i]
  153. of nkCaseStmt:
  154. let isExhaustive = skipTypes(n[0].typ,
  155. abstractVarRange-{tyTypeDesc}).kind notin {tyFloat..tyFloat128, tyString, tyCstring} or
  156. n[^1].kind == nkElse
  157. analyse(c, b, n[0])
  158. var wasMovedSet: seq[PNode] = @[]
  159. for i in 1 ..< n.len:
  160. var branch = nestedBlock(b, n[i].kind)
  161. analyse(c, branch, n[i])
  162. mergeBasicBlockInfo(b, branch)
  163. if isExhaustive:
  164. if i == 1:
  165. wasMovedSet = move(branch.wasMovedLocs)
  166. else:
  167. wasMovedSet.intersect(branch.wasMovedLocs)
  168. for i in 0..<wasMovedSet.len:
  169. b.wasMovedLocs.add wasMovedSet[i]
  170. of nkTryStmt:
  171. for i in 0 ..< n.len:
  172. var tryBody = nestedBlock(b, nkTryStmt)
  173. analyse(c, tryBody, n[i])
  174. mergeBasicBlockInfo(b, tryBody)
  175. of nkWhileStmt:
  176. analyse(c, b, n[0])
  177. var loopBody = nestedBlock(b, nkWhileStmt)
  178. analyse(c, loopBody, n[1])
  179. mergeBasicBlockInfo(b, loopBody)
  180. of nkBlockStmt, nkBlockExpr:
  181. var blockBody = nestedBlock(b, n.kind)
  182. if n[0].kind == nkSym:
  183. blockBody.label = n[0].sym
  184. analyse(c, blockBody, n[1])
  185. mergeBasicBlockInfo(b, blockBody)
  186. of nkBreakStmt:
  187. breakStmt(b, n[0])
  188. of nkReturnStmt, nkRaiseStmt:
  189. for child in n: analyse(c, b, child)
  190. returnStmt(b)
  191. of nkFinally:
  192. inc c.inFinally
  193. for child in n: analyse(c, b, child)
  194. dec c.inFinally
  195. else:
  196. for child in n: analyse(c, b, child)
  197. proc opt(c: Con; n, parent: PNode; parentPos: int) =
  198. template recurse() =
  199. let x = shallowCopy(n)
  200. for i in 0 ..< n.len:
  201. opt(c, n[i], x, i)
  202. parent[parentPos] = x
  203. case n.kind
  204. of nkCallKinds:
  205. if nfMarkForDeletion in n.flags:
  206. parent[parentPos] = newNodeI(nkEmpty, n.info)
  207. else:
  208. recurse()
  209. of nkNone..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef,
  210. nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo,
  211. nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt,
  212. nkExportStmt, nkPragma, nkCommentStmt, nkBreakState, nkTypeOfExpr,
  213. nkMixinStmt, nkBindStmt:
  214. parent[parentPos] = n
  215. else:
  216. recurse()
  217. proc optimize*(n: PNode): PNode =
  218. # optimize away simple 'wasMoved(x); destroy(x)' pairs.
  219. #[ Unfortunately this optimization is only really safe when no exceptions
  220. are possible, see for example:
  221. proc main(inp: string; cond: bool) =
  222. if cond:
  223. try:
  224. var s = ["hi", inp & "more"]
  225. for i in 0..4:
  226. use s
  227. consume(s)
  228. wasMoved(s)
  229. finally:
  230. destroy(s)
  231. Now assume 'use' raises, then we shouldn't do the 'wasMoved(s)'
  232. ]#
  233. var c: Con
  234. var b: BasicBlock
  235. analyse(c, b, n)
  236. if c.somethingTodo:
  237. result = shallowCopy(n)
  238. for i in 0 ..< n.safeLen:
  239. opt(c, n[i], result, i)
  240. else:
  241. result = n