1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
#
#
# The Nim Compiler
# (c) Copyright 2021 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## Dead code elimination (=DCE) for IC.
import std/[intsets, tables]
when defined(nimPreviewSlimSystem):
import std/assertions
import ".." / [ast, options, lineinfos, types]
import packed_ast, ic, bitabs
type
AliveSyms* = seq[IntSet]
AliveContext* = object ## Purpose is to fill the 'alive' field.
stack: seq[(int, TOptions, NodePos)] ## A stack for marking symbols as alive.
decoder: PackedDecoder ## We need a PackedDecoder for module ID address translations.
thisModule: int ## The module we're currently analysing for DCE.
alive: AliveSyms ## The final result of our computation.
options: TOptions
compilerProcs: Table[string, (int, int32)]
proc isExportedToC(c: var AliveContext; g: PackedModuleGraph; symId: int32): bool =
## "Exported to C" procs are special (these are marked with '.exportc') because these
## must not be optimized away!
let symPtr = unsafeAddr g[c.thisModule].fromDisk.syms[symId]
let flags = symPtr.flags
# due to a bug/limitation in the lambda lifting, unused inner procs
# are not transformed correctly; issue (#411). However, the whole purpose here
# is to eliminate unused procs. So there is no special logic required for this case.
if sfCompileTime notin flags:
if ({sfExportc, sfCompilerProc} * flags != {}) or
(symPtr.kind == skMethod):
result = true
else:
result = false
# XXX: This used to be a condition to:
# (sfExportc in prc.flags and lfExportLib in prc.loc.flags) or
if sfCompilerProc in flags:
c.compilerProcs[g[c.thisModule].fromDisk.strings[symPtr.name]] = (c.thisModule, symId)
else:
result = false
template isNotGeneric(n: NodePos): bool = ithSon(tree, n, genericParamsPos).kind == nkEmpty
proc followLater(c: var AliveContext; g: PackedModuleGraph; module: int; item: int32) =
## Marks a symbol 'item' as used and later in 'followNow' the symbol's body will
## be analysed.
if not c.alive[module].containsOrIncl(item):
var body = g[module].fromDisk.syms[item].ast
if body != emptyNodeId:
let opt = g[module].fromDisk.syms[item].options
if g[module].fromDisk.syms[item].kind in routineKinds:
body = NodeId ithSon(g[module].fromDisk.bodies, NodePos body, bodyPos)
c.stack.add((module, opt, NodePos(body)))
when false:
let nid = g[module].fromDisk.syms[item].name
if nid != LitId(0):
let name = g[module].fromDisk.strings[nid]
if name in ["nimFrame", "callDepthLimitReached"]:
echo "I was called! ", name, " body exists: ", body != emptyNodeId, " ", module, " ", item
proc requestCompilerProc(c: var AliveContext; g: PackedModuleGraph; name: string) =
let (module, item) = c.compilerProcs[name]
followLater(c, g, module, item)
proc loadTypeKind(t: PackedItemId; c: AliveContext; g: PackedModuleGraph; toSkip: set[TTypeKind]): TTypeKind =
template kind(t: ItemId): TTypeKind = g[t.module].fromDisk.types[t.item].kind
var t2 = translateId(t, g, c.thisModule, c.decoder.config)
result = t2.kind
while result in toSkip:
t2 = translateId(g[t2.module].fromDisk.types[t2.item].types[^1], g, t2.module, c.decoder.config)
result = t2.kind
proc rangeCheckAnalysis(c: var AliveContext; g: PackedModuleGraph; tree: PackedTree; n: NodePos) =
## Replicates the logic of `ccgexprs.genRangeChck`.
## XXX Refactor so that the duplicated logic is avoided. However, for now it's not clear
## the approach has enough merit.
var dest = loadTypeKind(n.typ, c, g, abstractVar)
if optRangeCheck notin c.options or dest in {tyUInt..tyUInt64}:
discard "no need to generate a check because it was disabled"
else:
let n0t = loadTypeKind(n.firstSon.typ, c, g, {})
if n0t in {tyUInt, tyUInt64}:
c.requestCompilerProc(g, "raiseRangeErrorNoArgs")
else:
let raiser =
case loadTypeKind(n.typ, c, g, abstractVarRange)
of tyUInt..tyUInt64, tyChar: "raiseRangeErrorU"
of tyFloat..tyFloat128: "raiseRangeErrorF"
else: "raiseRangeErrorI"
c.requestCompilerProc(g, raiser)
proc aliveCode(c: var AliveContext; g: PackedModuleGraph; tree: PackedTree; n: NodePos) =
## Marks the symbols we encounter when we traverse the AST at `tree[n]` as alive, unless
## it is purely in a declarative context (type section etc.).
case n.kind
of nkNone..pred(nkSym), succ(nkSym)..nkNilLit:
discard "ignore non-sym atoms"
of nkSym:
# This symbol is alive and everything its body references.
followLater(c, g, c.thisModule, tree[n].soperand)
of nkModuleRef:
let (n1, n2) = sons2(tree, n)
assert n1.kind == nkNone
assert n2.kind == nkNone
let m = n1.litId
let item = tree[n2].soperand
let otherModule = toFileIndexCached(c.decoder, g, c.thisModule, m).int
followLater(c, g, otherModule, item)
of nkMacroDef, nkTemplateDef, nkTypeSection, nkTypeOfExpr,
nkCommentStmt, nkIncludeStmt,
nkImportStmt, nkImportExceptStmt, nkExportStmt, nkExportExceptStmt,
nkFromStmt, nkStaticStmt:
discard
of nkVarSection, nkLetSection, nkConstSection:
# XXX ignore the defining local variable name?
for son in sonsReadonly(tree, n):
aliveCode(c, g, tree, son)
of nkChckRangeF, nkChckRange64, nkChckRange:
rangeCheckAnalysis(c, g, tree, n)
of nkProcDef, nkConverterDef, nkMethodDef, nkFuncDef, nkIteratorDef:
if n.firstSon.kind == nkSym and isNotGeneric(n):
let item = tree[n.firstSon].soperand
if isExportedToC(c, g, item):
# This symbol is alive and everything its body references.
followLater(c, g, c.thisModule, item)
else:
for son in sonsReadonly(tree, n):
aliveCode(c, g, tree, son)
proc followNow(c: var AliveContext; g: PackedModuleGraph) =
## Mark all entries in the stack. Marking can add more entries
## to the stack but eventually we have looked at every alive symbol.
while c.stack.len > 0:
let (modId, opt, ast) = c.stack.pop()
c.thisModule = modId
c.options = opt
aliveCode(c, g, g[modId].fromDisk.bodies, ast)
proc computeAliveSyms*(g: PackedModuleGraph; conf: ConfigRef): AliveSyms =
## Entry point for our DCE algorithm.
var c = AliveContext(stack: @[], decoder: PackedDecoder(config: conf),
thisModule: -1, alive: newSeq[IntSet](g.len),
options: conf.options)
for i in countdown(len(g)-1, 0):
if g[i].status != undefined:
c.thisModule = i
for p in allNodes(g[i].fromDisk.topLevel):
aliveCode(c, g, g[i].fromDisk.topLevel, p)
followNow(c, g)
result = move(c.alive)
proc isAlive*(a: AliveSyms; module: int, item: int32): bool =
## Backends use this to query if a symbol is `alive` which means
## we need to produce (C/C++/etc) code for it.
result = a[module].contains(item)
|
