diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/ast.nim | 8 | ||||
| -rw-r--r-- | compiler/evaltempl.nim | 5 | ||||
| -rw-r--r-- | compiler/guards.nim | 136 | ||||
| -rw-r--r-- | compiler/lambdalifting.nim | 10 | ||||
| -rw-r--r-- | compiler/semparallel.nim | 33 | ||||
| -rw-r--r-- | compiler/sempass2.nim | 2 | ||||
| -rw-r--r-- | compiler/vmgen.nim | 7 |
7 files changed, 173 insertions, 28 deletions
diff --git a/compiler/ast.nim b/compiler/ast.nim index 08a991468..4001e896e 100644 --- a/compiler/ast.nim +++ b/compiler/ast.nim @@ -1588,6 +1588,14 @@ proc makeStmtList*(n: PNode): PNode = result = newNodeI(nkStmtList, n.info) result.add n +proc skipStmtList*(n: PNode): PNode = + if n.kind in {nkStmtList, nkStmtListExpr}: + for i in 0 .. n.len-2: + if n[i].kind notin {nkEmpty, nkCommentStmt}: return n + result = n.lastSon + else: + result = n + proc createMagic*(name: string, m: TMagic): PSym = result = newSym(skProc, getIdent(name), nil, unknownLineInfo()) result.magic = m diff --git a/compiler/evaltempl.nim b/compiler/evaltempl.nim index 58594a8b7..c33e5be86 100644 --- a/compiler/evaltempl.nim +++ b/compiler/evaltempl.nim @@ -62,7 +62,7 @@ proc evalTemplateArgs(n: PNode, s: PSym): PNode = # if the template has zero arguments, it can be called without ``()`` # `n` is then a nkSym or something similar var totalParams = case n.kind - of nkCall, nkInfix, nkPrefix, nkPostfix, nkCommand, nkCallStrLit: <n.len + of nkCall, nkInfix, nkPrefix, nkPostfix, nkCommand, nkCallStrLit: n.len-1 else: 0 var @@ -90,8 +90,7 @@ proc evalTemplateArgs(n: PNode, s: PSym): PNode = # not supplied by the user for i in givenRegularParams+1 .. expectedRegularParams: let default = s.typ.n.sons[i].sym.ast - internalAssert default != nil - if default.kind == nkEmpty: + if default.isNil or default.kind == nkEmpty: localError(n.info, errWrongNumberOfArguments) addSon(result, ast.emptyNode) else: diff --git a/compiler/guards.nim b/compiler/guards.nim index bc802ae33..5ad932e48 100644 --- a/compiler/guards.nim +++ b/compiler/guards.nim @@ -37,6 +37,7 @@ const someMod = {mModI} someMax = {mMaxI, mMaxF64} someMin = {mMinI, mMinF64} + someBinaryOp = someAdd+someSub+someMul+someMax+someMin proc isValue(n: PNode): bool = n.kind in {nkCharLit..nkNilLit} proc isLocation(n: PNode): bool = not n.isValue @@ -165,11 +166,21 @@ proc `|+|`(a, b: PNode): PNode = if a.kind in {nkCharLit..nkUInt64Lit}: result.intVal = a.intVal |+| b.intVal else: result.floatVal = a.floatVal + b.floatVal +proc `|-|`(a, b: PNode): PNode = + result = copyNode(a) + if a.kind in {nkCharLit..nkUInt64Lit}: result.intVal = a.intVal |-| b.intVal + else: result.floatVal = a.floatVal - b.floatVal + proc `|*|`(a, b: PNode): PNode = result = copyNode(a) if a.kind in {nkCharLit..nkUInt64Lit}: result.intVal = a.intVal |*| b.intVal else: result.floatVal = a.floatVal * b.floatVal +proc `|div|`(a, b: PNode): PNode = + result = copyNode(a) + if a.kind in {nkCharLit..nkUInt64Lit}: result.intVal = a.intVal div b.intVal + else: result.floatVal = a.floatVal / b.floatVal + proc negate(a, b, res: PNode): PNode = if b.kind in {nkCharLit..nkUInt64Lit} and b.intVal != low(BiggestInt): var b = copyNode(b) @@ -213,10 +224,16 @@ proc reassociation(n: PNode): PNode = if result[2].isValue and result[1].getMagic in someAdd and result[1][2].isValue: result = opAdd.buildCall(result[1][1], result[1][2] |+| result[2]) + if result[2].intVal == 0: + result = result[1] of someMul: if result[2].isValue and result[1].getMagic in someMul and result[1][2].isValue: - result = opAdd.buildCall(result[1][1], result[1][2] |*| result[2]) + result = opMul.buildCall(result[1][1], result[1][2] |*| result[2]) + if result[2].intVal == 1: + result = result[1] + elif result[2].intVal == 0: + result = zero() else: discard proc pred(n: PNode): PNode = @@ -234,7 +251,7 @@ proc canon*(n: PNode): PNode = result.sons[i] = canon(n.sons[i]) elif n.kind == nkSym and n.sym.kind == skLet and n.sym.ast.getMagic in (someEq + someAdd + someMul + someMin + - someMax + someHigh + {mUnaryLt} + someSub + someLen): + someMax + someHigh + {mUnaryLt} + someSub + someLen + someDiv): result = n.sym.ast.copyTree else: result = n @@ -248,7 +265,7 @@ proc canon*(n: PNode): PNode = # high == len+(-1) result = opAdd.buildCall(opLen.buildCall(result[1]), minusOne()) of mUnaryLt: - result = buildCall(opAdd, result[1], newIntNode(nkIntLit, -1)) + result = buildCall(opAdd, result[1], minusOne()) of someSub: # x - 4 --> x + (-4) result = negate(result[1], result[2], result) @@ -294,6 +311,16 @@ proc canon*(n: PNode): PNode = if plus != nil and not isLetLocation(x, true): result = buildCall(result[0].sym, plus, y[1]) else: discard + elif x.isValue and y.getMagic in someAdd and y[2].isValue: + # 0 <= a.len + 3 + # -3 <= a.len + result.sons[1] = x |-| y[2] + result.sons[2] = y[1] + elif x.isValue and y.getMagic in someSub and y[2].isValue: + # 0 <= a.len - 3 + # 3 <= a.len + result.sons[1] = x |+| y[2] + result.sons[2] = y[1] else: discard proc `+@`*(a: PNode; b: BiggestInt): PNode = @@ -313,6 +340,9 @@ proc usefulFact(n: PNode): PNode = if isLetLocation(n.sons[1], true) or isLetLocation(n.sons[2], true): # XXX algebraic simplifications! 'i-1 < a.len' --> 'i < a.len+1' result = n + elif n[1].getMagic in someLen or n[2].getMagic in someLen: + # XXX Rethink this whole idea of 'usefulFact' for semparallel + result = n of mIsNil: if isLetLocation(n.sons[1], false) or isVar(n.sons[1]): result = n @@ -366,8 +396,8 @@ proc usefulFact(n: PNode): PNode = type TModel* = seq[PNode] # the "knowledge base" -proc addFact*(m: var TModel, n: PNode) = - let n = usefulFact(n) +proc addFact*(m: var TModel, nn: PNode) = + let n = usefulFact(nn) if n != nil: m.add n proc addFactNeg*(m: var TModel, n: PNode) = @@ -697,10 +727,57 @@ proc simpleSlice*(a, b: PNode): BiggestInt = else: result = -1 + +template isMul(x): expr = x.getMagic in someMul +template isDiv(x): expr = x.getMagic in someDiv +template isAdd(x): expr = x.getMagic in someAdd +template isSub(x): expr = x.getMagic in someSub +template isVal(x): expr = x.kind in {nkCharLit..nkUInt64Lit} +template isIntVal(x, y): expr = x.intVal == y + +import macros + +macro `=~`(x: PNode, pat: untyped): bool = + proc m(x, pat, conds: NimNode) = + case pat.kind + of nnkInfix: + case $pat[0] + of "*": conds.add getAst(isMul(x)) + of "/": conds.add getAst(isDiv(x)) + of "+": conds.add getAst(isAdd(x)) + of "-": conds.add getAst(isSub(x)) + else: + error("invalid pattern") + m(newTree(nnkBracketExpr, x, newLit(1)), pat[1], conds) + m(newTree(nnkBracketExpr, x, newLit(2)), pat[2], conds) + of nnkPar: + if pat.len == 1: + m(x, pat[0], conds) + else: + error("invalid pattern") + of nnkIdent: + let c = newTree(nnkStmtListExpr, newLetStmt(pat, x)) + conds.add c + if ($pat)[^1] == 'c': c.add(getAst(isVal(pat))) + else: c.add bindSym"true" + of nnkIntLit: + conds.add(getAst(isIntVal(pat.intVal))) + else: + error("invalid pattern") + + var conds = newTree(nnkBracket) + m(x, pat, conds) + result = nestList(!"and", conds) + + +proc isMinusOne(n: PNode): bool = + n.kind in {nkCharLit..nkUInt64Lit} and n.intVal == -1 + proc pleViaModel(model: TModel; aa, bb: PNode): TImplication proc ple(m: TModel; a, b: PNode): TImplication = template `<=?`(a,b): expr = ple(m,a,b) == impYes + template `>=?`(a,b): expr = ple(m, nkIntLit.newIntNode(b), a) == impYes # 0 <= 3 if a.isValue and b.isValue: @@ -721,6 +798,7 @@ proc ple(m: TModel; a, b: PNode): TImplication = if a.intVal <= 0: return impYes # x <= y+c if 0 <= c and x <= y + # x <= y+(-c) if c <= 0 and y >= x if b.getMagic in someAdd and zero() <=? b[2] and a <=? b[1]: return impYes # x+c <= y if c <= 0 and x <= y @@ -730,10 +808,44 @@ proc ple(m: TModel; a, b: PNode): TImplication = if b.getMagic in someMul: if a <=? b[1] and one() <=? b[2] and zero() <=? b[1]: return impYes + + if a.getMagic in someMul and a[2].isValue and a[1].getMagic in someDiv and + a[1][2].isValue: + # simplify (x div 4) * 2 <= y to x div (c div d) <= y + if ple(m, buildCall(opDiv, a[1][1], `|div|`(a[1][2], a[2])), b) == impYes: + return impYes + + # x*3 + x == x*4. It follows that: + # x*3 + y <= x*4 if y <= x and 3 <= 4 + if a =~ x*dc + y and b =~ x2*ec: + if sameTree(x, x2): + let ec1 = opAdd.buildCall(ec, minusOne()) + if x >=? 1 and ec >=? 1 and dc >=? 1 and dc <=? ec1 and y <=? x: + return impYes + elif a =~ x*dc and b =~ x2*ec + y: + #echo "BUG cam ehrer e ", a, " <=? ", b + if sameTree(x, x2): + let ec1 = opAdd.buildCall(ec, minusOne()) + if x >=? 1 and ec >=? 1 and dc >=? 1 and dc <=? ec1 and y <=? zero(): + return impYes + + # x+c <= x+d if c <= d. Same for *, - etc. + if a.getMagic in someBinaryOp and a.getMagic == b.getMagic: + if sameTree(a[1], b[1]) and a[2] <=? b[2]: return impYes + elif sameTree(a[2], b[2]) and a[1] <=? b[1]: return impYes + # x div c <= y if 1 <= c and 0 <= y and x <= y: if a.getMagic in someDiv: if one() <=? a[2] and zero() <=? b and a[1] <=? b: return impYes + # x div c <= x div d if d <= c + if b.getMagic in someDiv: + if sameTree(a[1], b[1]) and b[2] <=? a[2]: return impYes + + # x div z <= x - 1 if z <= x + if a[2].isValue and b.getMagic in someAdd and b[2].isMinusOne: + if a[2] <=? a[1] and sameTree(a[1], b[1]): return impYes + # slightly subtle: # x <= max(y, z) iff x <= y or x <= z # note that 'x <= max(x, z)' is a special case of the above rule @@ -769,11 +881,19 @@ proc pleViaModelRec(m: var TModel; a, b: PNode): TImplication = for i in 0..m.high: let fact = m[i] if fact != nil and fact.getMagic in someLe: - # x <= y implies a <= b if a <= x and y <= b - let x = fact[1] - let y = fact[2] # mark as used: m[i] = nil + # i <= len-100 + # i <=? len-1 + # --> true if (len-100) <= (len-1) + let x = fact[1] + let y = fact[2] + if sameTree(x, a) and y.getMagic in someAdd and b.getMagic in someAdd and + sameTree(y[1], b[1]): + if ple(m, b[2], y[2]) == impYes: + return impYes + + # x <= y implies a <= b if a <= x and y <= b if ple(m, a, x) == impYes: if ple(m, y, b) == impYes: return impYes diff --git a/compiler/lambdalifting.nim b/compiler/lambdalifting.nim index c669fc745..cccc94756 100644 --- a/compiler/lambdalifting.nim +++ b/compiler/lambdalifting.nim @@ -859,11 +859,17 @@ proc transformOuterProc(o: POuterContext, n: PNode; it: TIter): PNode = return indirectAccess(newSymNode(it.closureParam), local, n.info) if local.kind == skClosureIterator: + # bug #3354; allow for + #iterator iter(): int {.closure.}= + # s.add(iter) + # yield 1 + + #if local == o.fn or local == it.fn: + # message(n.info, errRecursiveDependencyX, local.name.s) + # consider: [i1, i2, i1] Since we merged the iterator's closure # with the captured owning variables, we need to generate the # closure generation code again: - if local == o.fn or local == it.fn: - message(n.info, errRecursiveDependencyX, local.name.s) # XXX why doesn't this work? var closure = PEnv(idTableGet(o.lambdasToEnv, local)) if closure.isNil: diff --git a/compiler/semparallel.nim b/compiler/semparallel.nim index 36c63d038..b04ba4657 100644 --- a/compiler/semparallel.nim +++ b/compiler/semparallel.nim @@ -128,10 +128,10 @@ template `?`(x): expr = x.renderTree proc checkLe(c: AnalysisCtx; a, b: PNode) = case proveLe(c.guards, a, b) of impUnknown: - localError(a.info, "cannot prove: " & ?a & " <= " & ?b) + localError(a.info, "cannot prove: " & ?a & " <= " & ?b & " (bounds check)") of impYes: discard of impNo: - localError(a.info, "can prove: " & ?a & " > " & ?b) + localError(a.info, "can prove: " & ?a & " > " & ?b & " (bounds check)") proc checkBounds(c: AnalysisCtx; arr, idx: PNode) = checkLe(c, arr.lowBound, idx) @@ -156,19 +156,23 @@ proc addSlice(c: var AnalysisCtx; n: PNode; x, le, ri: PNode) = proc overlap(m: TModel; x,y,c,d: PNode) = # X..Y and C..D overlap iff (X <= D and C <= Y) - case proveLe(m, x, d) + case proveLe(m, c, y) of impUnknown: - localError(x.info, - "cannot prove: $# > $#; required for ($#)..($#) disjoint from ($#)..($#)" % - [?x, ?d, ?x, ?y, ?c, ?d]) + case proveLe(m, x, d) + of impNo: discard + of impUnknown, impYes: + localError(x.info, + "cannot prove: $# > $#; required for ($#)..($#) disjoint from ($#)..($#)" % + [?c, ?y, ?x, ?y, ?c, ?d]) of impYes: - case proveLe(m, c, y) + case proveLe(m, x, d) of impUnknown: localError(x.info, "cannot prove: $# > $#; required for ($#)..($#) disjoint from ($#)..($#)" % - [?c, ?y, ?x, ?y, ?c, ?d]) + [?x, ?d, ?x, ?y, ?c, ?d]) of impYes: - localError(x.info, "($#)..($#) not disjoint from ($#)..($#)" % [?x, ?y, ?c, ?d]) + localError(x.info, "($#)..($#) not disjoint from ($#)..($#)" % + [?c, ?y, ?x, ?y, ?c, ?d]) of impNo: discard of impNo: discard @@ -278,10 +282,12 @@ proc analyseCall(c: var AnalysisCtx; n: PNode; op: PSym) = slot.stride = min(slot.stride, incr) analyseSons(c, n) elif op.name.s == "[]" and op.fromSystem: - c.addSlice(n, n[1], n[2][1], n[2][2]) + let slice = n[2].skipStmtList + c.addSlice(n, n[1], slice[1], slice[2]) analyseSons(c, n) elif op.name.s == "[]=" and op.fromSystem: - c.addSlice(n, n[1], n[2][1], n[2][2]) + let slice = n[2].skipStmtList + c.addSlice(n, n[1], slice[1], slice[2]) analyseSons(c, n) else: analyseSons(c, n) @@ -395,8 +401,9 @@ proc transformSlices(n: PNode): PNode = result = copyNode(n) result.add opSlice.newSymNode result.add n[1] - result.add n[2][1] - result.add n[2][2] + let slice = n[2].skipStmtList + result.add slice[1] + result.add slice[2] return result if n.safeLen > 0: result = shallowCopy(n) diff --git a/compiler/sempass2.nim b/compiler/sempass2.nim index 272412b04..ef014963c 100644 --- a/compiler/sempass2.nim +++ b/compiler/sempass2.nim @@ -855,6 +855,8 @@ proc initEffects(effects: PNode; s: PSym; t: var TEffects) = newSeq(effects.sons, effectListLen) effects.sons[exceptionEffects] = newNodeI(nkArgList, s.info) effects.sons[tagEffects] = newNodeI(nkArgList, s.info) + effects.sons[usesEffects] = ast.emptyNode + effects.sons[writeEffects] = ast.emptyNode t.exc = effects.sons[exceptionEffects] t.tags = effects.sons[tagEffects] diff --git a/compiler/vmgen.nim b/compiler/vmgen.nim index 32982602b..95fa43b48 100644 --- a/compiler/vmgen.nim +++ b/compiler/vmgen.nim @@ -1377,10 +1377,13 @@ proc genCheckedObjAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) = genObjAccess(c, n.sons[0], dest, flags) proc genArrAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) = - if n.sons[0].typ.skipTypes(abstractVarRange-{tyTypeDesc}).kind in { - tyString, tyCString}: + let arrayType = n.sons[0].typ.skipTypes(abstractVarRange-{tyTypeDesc}).kind + if arrayType in {tyString, tyCString}: genArrAccess2(c, n, dest, opcLdStrIdx, {}) + elif arrayType == tyTypeDesc: + c.genTypeLit(n.typ, dest) else: + echo renderTree(n) genArrAccess2(c, n, dest, opcLdArr, flags) proc getNullValueAux(obj: PNode, result: PNode) = |