diff options
Diffstat (limited to 'compiler/semparallel.nim')
| -rw-r--r-- | compiler/semparallel.nim | 247 |
1 files changed, 129 insertions, 118 deletions
diff --git a/compiler/semparallel.nim b/compiler/semparallel.nim index 2581f5728..23a8e6362 100644 --- a/compiler/semparallel.nim +++ b/compiler/semparallel.nim @@ -22,10 +22,11 @@ # - output slices need special logic (+) import - ast, astalgo, idents, lowerings, magicsys, guards, sempass2, msgs, - renderer, types -from trees import getMagic -from strutils import `%` + ast, astalgo, idents, lowerings, magicsys, guards, msgs, + renderer, types, modulegraphs, options, spawn, lineinfos + +from trees import getMagic, getRoot +from std/strutils import `%` discard """ @@ -73,28 +74,30 @@ type # the 'parallel' section currentSpawnId: int inLoop: int + graph: ModuleGraph -proc initAnalysisCtx(): AnalysisCtx = - result.locals = @[] - result.slices = @[] - result.args = @[] - result.guards = @[] +proc initAnalysisCtx(g: ModuleGraph): AnalysisCtx = + result = AnalysisCtx(locals: @[], + slices: @[], + args: @[], + graph: g) + result.guards.s = @[] + result.guards.g = g proc lookupSlot(c: AnalysisCtx; s: PSym): int = - for i in 0.. <c.locals.len: + for i in 0..<c.locals.len: if c.locals[i].v == s or c.locals[i].alias == s: return i return -1 proc getSlot(c: var AnalysisCtx; v: PSym): ptr MonotonicVar = let s = lookupSlot(c, v) if s >= 0: return addr(c.locals[s]) - let L = c.locals.len - c.locals.setLen(L+1) - c.locals[L].v = v - return addr(c.locals[L]) + c.locals.setLen(c.locals.len+1) + c.locals[^1].v = v + return addr(c.locals[^1]) proc gatherArgs(c: var AnalysisCtx; n: PNode) = - for i in 0.. <n.safeLen: + for i in 0..<n.safeLen: let root = getRoot n[i] if root != nil: block addRoot: @@ -117,23 +120,25 @@ proc checkLocal(c: AnalysisCtx; n: PNode) = if isLocal(n): let s = c.lookupSlot(n.sym) if s >= 0 and c.locals[s].stride != nil: - localError(n.info, "invalid usage of counter after increment") + localError(c.graph.config, n.info, "invalid usage of counter after increment") else: - for i in 0 .. <n.safeLen: checkLocal(c, n.sons[i]) + for i in 0..<n.safeLen: checkLocal(c, n[i]) template `?`(x): untyped = x.renderTree proc checkLe(c: AnalysisCtx; a, b: PNode) = case proveLe(c.guards, a, b) of impUnknown: - localError(a.info, "cannot prove: " & ?a & " <= " & ?b & " (bounds check)") + message(c.graph.config, a.info, warnStaticIndexCheck, + "cannot prove: " & ?a & " <= " & ?b) of impYes: discard of impNo: - localError(a.info, "can prove: " & ?a & " > " & ?b & " (bounds check)") + message(c.graph.config, a.info, warnStaticIndexCheck, + "can prove: " & ?a & " > " & ?b) proc checkBounds(c: AnalysisCtx; arr, idx: PNode) = - checkLe(c, arr.lowBound, idx) - checkLe(c, idx, arr.highBound) + checkLe(c, lowBound(c.graph.config, arr), idx) + checkLe(c, idx, highBound(c.graph.config, arr, c.graph.operators)) proc addLowerBoundAsFacts(c: var AnalysisCtx) = for v in c.locals: @@ -142,34 +147,34 @@ proc addLowerBoundAsFacts(c: var AnalysisCtx) = proc addSlice(c: var AnalysisCtx; n: PNode; x, le, ri: PNode) = checkLocal(c, n) - let le = le.canon - let ri = ri.canon + let le = le.canon(c.graph.operators) + let ri = ri.canon(c.graph.operators) # perform static bounds checking here; and not later! - let oldState = c.guards.len + let oldState = c.guards.s.len addLowerBoundAsFacts(c) c.checkBounds(x, le) c.checkBounds(x, ri) - c.guards.setLen(oldState) + c.guards.s.setLen(oldState) c.slices.add((x, le, ri, c.currentSpawnId, c.inLoop > 0)) -proc overlap(m: TModel; x,y,c,d: PNode) = +proc overlap(m: TModel; conf: ConfigRef; x,y,c,d: PNode) = # X..Y and C..D overlap iff (X <= D and C <= Y) case proveLe(m, c, y) of impUnknown: case proveLe(m, x, d) of impNo: discard of impUnknown, impYes: - localError(x.info, + message(conf, x.info, warnStaticIndexCheck, "cannot prove: $# > $#; required for ($#)..($#) disjoint from ($#)..($#)" % [?c, ?y, ?x, ?y, ?c, ?d]) of impYes: case proveLe(m, x, d) of impUnknown: - localError(x.info, + message(conf, x.info, warnStaticIndexCheck, "cannot prove: $# > $#; required for ($#)..($#) disjoint from ($#)..($#)" % [?x, ?d, ?x, ?y, ?c, ?d]) of impYes: - localError(x.info, "($#)..($#) not disjoint from ($#)..($#)" % + message(conf, x.info, warnStaticIndexCheck, "($#)..($#) not disjoint from ($#)..($#)" % [?c, ?y, ?x, ?y, ?c, ?d]) of impNo: discard of impNo: discard @@ -179,20 +184,23 @@ proc stride(c: AnalysisCtx; n: PNode): BiggestInt = let s = c.lookupSlot(n.sym) if s >= 0 and c.locals[s].stride != nil: result = c.locals[s].stride.intVal + else: + result = 0 else: - for i in 0 .. <n.safeLen: result += stride(c, n.sons[i]) + result = 0 + for i in 0..<n.safeLen: result += stride(c, n[i]) proc subStride(c: AnalysisCtx; n: PNode): PNode = # substitute with stride: if isLocal(n): let s = c.lookupSlot(n.sym) if s >= 0 and c.locals[s].stride != nil: - result = n +@ c.locals[s].stride.intVal + result = buildAdd(n, c.locals[s].stride.intVal, c.graph.operators) else: result = n elif n.safeLen > 0: result = shallowCopy(n) - for i in 0 .. <n.len: result.sons[i] = subStride(c, n.sons[i]) + for i in 0..<n.len: result[i] = subStride(c, n[i]) else: result = n @@ -203,7 +211,7 @@ proc checkSlicesAreDisjoint(c: var AnalysisCtx) = addLowerBoundAsFacts(c) # Every slice used in a loop needs to be disjoint with itself: for x,a,b,id,inLoop in items(c.slices): - if inLoop: overlap(c.guards, a,b, c.subStride(a), c.subStride(b)) + if inLoop: overlap(c.guards, c.graph.config, a,b, c.subStride(a), c.subStride(b)) # Another tricky example is: # while true: # spawn f(a[i]) @@ -212,8 +220,8 @@ proc checkSlicesAreDisjoint(c: var AnalysisCtx) = # # Or even worse: # while true: - # spawn f(a[i+1 .. i+3]) - # spawn f(a[i+4 .. i+5]) + # spawn f(a[i+1..i+3]) + # spawn f(a[i+4..i+5]) # inc i, 4 # Prove that i*k*stride + 3 != i*k'*stride + 5 # For the correct example this amounts to @@ -222,44 +230,42 @@ proc checkSlicesAreDisjoint(c: var AnalysisCtx) = # For now, we don't try to prove things like that at all, even though it'd # be feasible for many useful examples. Instead we attach the slice to # a spawn and if the attached spawns differ, we bail out: - for i in 0 .. high(c.slices): - for j in i+1 .. high(c.slices): + for i in 0..high(c.slices): + for j in i+1..high(c.slices): let x = c.slices[i] let y = c.slices[j] if x.spawnId != y.spawnId and guards.sameTree(x.x, y.x): if not x.inLoop or not y.inLoop: # XXX strictly speaking, 'or' is not correct here and it needs to # be 'and'. However this prevents too many obviously correct programs - # like f(a[0..x]); for i in x+1 .. a.high: f(a[i]) - overlap(c.guards, x.a, x.b, y.a, y.b) + # like f(a[0..x]); for i in x+1..a.high: f(a[i]) + overlap(c.guards, c.graph.config, x.a, x.b, y.a, y.b) elif (let k = simpleSlice(x.a, x.b); let m = simpleSlice(y.a, y.b); k >= 0 and m >= 0): # ah I cannot resist the temptation and add another sweet heuristic: # if both slices have the form (i+k)..(i+k) and (i+m)..(i+m) we # check they are disjoint and k < stride and m < stride: - overlap(c.guards, x.a, x.b, y.a, y.b) + overlap(c.guards, c.graph.config, x.a, x.b, y.a, y.b) let stride = min(c.stride(x.a), c.stride(y.a)) if k < stride and m < stride: discard else: - localError(x.x.info, "cannot prove ($#)..($#) disjoint from ($#)..($#)" % + localError(c.graph.config, x.x.info, "cannot prove ($#)..($#) disjoint from ($#)..($#)" % [?x.a, ?x.b, ?y.a, ?y.b]) else: - localError(x.x.info, "cannot prove ($#)..($#) disjoint from ($#)..($#)" % + localError(c.graph.config, x.x.info, "cannot prove ($#)..($#) disjoint from ($#)..($#)" % [?x.a, ?x.b, ?y.a, ?y.b]) proc analyse(c: var AnalysisCtx; n: PNode) proc analyseSons(c: var AnalysisCtx; n: PNode) = - for i in 0 .. <safeLen(n): analyse(c, n[i]) + for i in 0..<n.safeLen: analyse(c, n[i]) proc min(a, b: PNode): PNode = if a.isNil: result = b elif a.intVal < b.intVal: result = a else: result = b -proc fromSystem(op: PSym): bool = sfSystemModule in getModule(op).flags - template pushSpawnId(c, body) {.dirty.} = inc c.spawns let oldSpawnId = c.currentSpawnId @@ -291,36 +297,36 @@ proc analyseCall(c: var AnalysisCtx; n: PNode; op: PSym) = analyseSons(c, n) proc analyseCase(c: var AnalysisCtx; n: PNode) = - analyse(c, n.sons[0]) - let oldFacts = c.guards.len - for i in 1.. <n.len: - let branch = n.sons[i] - setLen(c.guards, oldFacts) + analyse(c, n[0]) + let oldFacts = c.guards.s.len + for i in 1..<n.len: + let branch = n[i] + setLen(c.guards.s, oldFacts) addCaseBranchFacts(c.guards, n, i) - for i in 0 .. <branch.len: - analyse(c, branch.sons[i]) - setLen(c.guards, oldFacts) + for i in 0..<branch.len: + analyse(c, branch[i]) + setLen(c.guards.s, oldFacts) proc analyseIf(c: var AnalysisCtx; n: PNode) = - analyse(c, n.sons[0].sons[0]) - let oldFacts = c.guards.len - addFact(c.guards, canon(n.sons[0].sons[0])) - - analyse(c, n.sons[0].sons[1]) - for i in 1.. <n.len: - let branch = n.sons[i] - setLen(c.guards, oldFacts) + analyse(c, n[0][0]) + let oldFacts = c.guards.s.len + addFact(c.guards, canon(n[0][0], c.graph.operators)) + + analyse(c, n[0][1]) + for i in 1..<n.len: + let branch = n[i] + setLen(c.guards.s, oldFacts) for j in 0..i-1: - addFactNeg(c.guards, canon(n.sons[j].sons[0])) + addFactNeg(c.guards, canon(n[j][0], c.graph.operators)) if branch.len > 1: - addFact(c.guards, canon(branch.sons[0])) - for i in 0 .. <branch.len: - analyse(c, branch.sons[i]) - setLen(c.guards, oldFacts) + addFact(c.guards, canon(branch[0], c.graph.operators)) + for i in 0..<branch.len: + analyse(c, branch[i]) + setLen(c.guards.s, oldFacts) proc analyse(c: var AnalysisCtx; n: PNode) = case n.kind - of nkAsgn, nkFastAsgn: + of nkAsgn, nkFastAsgn, nkSinkAsgn: let y = n[1].skipConv if n[0].isSingleAssignable and y.isLocal: let slot = c.getSlot(y.sym) @@ -345,10 +351,11 @@ proc analyse(c: var AnalysisCtx; n: PNode) = if n[0].kind == nkSym: analyseCall(c, n, n[0].sym) else: analyseSons(c, n) of nkBracketExpr: - c.addSlice(n, n[0], n[1], n[1]) + if n[0].typ != nil and skipTypes(n[0].typ, abstractVar).kind != tyTuple: + c.addSlice(n, n[0], n[1], n[1]) analyseSons(c, n) - of nkReturnStmt, nkRaiseStmt, nkTryStmt: - localError(n.info, "invalid control flow for 'parallel'") + of nkReturnStmt, nkRaiseStmt, nkTryStmt, nkHiddenTryStmt: + localError(c.graph.config, n.info, "invalid control flow for 'parallel'") # 'break' that leaves the 'parallel' section is not valid either # or maybe we should generate a 'try' XXX of nkVarSection, nkLetSection: @@ -360,45 +367,49 @@ proc analyse(c: var AnalysisCtx; n: PNode) = gatherArgs(c, value[1]) analyseSons(c, value[1]) if value.kind != nkEmpty: - for j in 0 .. it.len-3: + for j in 0..<it.len-2: if it[j].isLocal: let slot = c.getSlot(it[j].sym) if slot.lower.isNil: slot.lower = value - else: internalError(it.info, "slot already has a lower bound") + else: internalError(c.graph.config, it.info, "slot already has a lower bound") if not isSpawned: analyse(c, value) of nkCaseStmt: analyseCase(c, n) of nkWhen, nkIfStmt, nkIfExpr: analyseIf(c, n) of nkWhileStmt: - analyse(c, n.sons[0]) + analyse(c, n[0]) # 'while true' loop? inc c.inLoop - if isTrue(n.sons[0]): - analyseSons(c, n.sons[1]) + if isTrue(n[0]): + analyseSons(c, n[1]) else: # loop may never execute: let oldState = c.locals.len - let oldFacts = c.guards.len - addFact(c.guards, canon(n.sons[0])) - analyse(c, n.sons[1]) + let oldFacts = c.guards.s.len + addFact(c.guards, canon(n[0], c.graph.operators)) + analyse(c, n[1]) setLen(c.locals, oldState) - setLen(c.guards, oldFacts) + setLen(c.guards.s, oldFacts) # we know after the loop the negation holds: - if not hasSubnodeWith(n.sons[1], nkBreakStmt): - addFactNeg(c.guards, canon(n.sons[0])) + if not hasSubnodeWith(n[1], nkBreakStmt): + addFactNeg(c.guards, canon(n[0], c.graph.operators)) dec c.inLoop of nkTypeSection, nkProcDef, nkConverterDef, nkMethodDef, nkIteratorDef, - nkMacroDef, nkTemplateDef, nkConstSection, nkPragma, nkFuncDef: + nkMacroDef, nkTemplateDef, nkConstSection, nkPragma, nkFuncDef, + nkMixinStmt, nkBindStmt, nkExportStmt: discard else: analyseSons(c, n) -proc transformSlices(n: PNode): PNode = +proc transformSlices(g: ModuleGraph; idgen: IdGenerator; n: PNode): PNode = if n.kind in nkCallKinds and n[0].kind == nkSym: let op = n[0].sym if op.name.s == "[]" and op.fromSystem: result = copyNode(n) - let opSlice = newSymNode(createMagic("slice", mSlice)) - opSlice.typ = getSysType(tyInt) + var typ = newType(tyOpenArray, idgen, result.typ.owner) + typ.add result.typ.elementType + result.typ = typ + let opSlice = newSymNode(createMagic(g, idgen, "slice", mSlice)) + opSlice.typ = getSysType(g, n.info, tyInt) result.add opSlice result.add n[1] let slice = n[2].skipStmtList @@ -407,60 +418,60 @@ proc transformSlices(n: PNode): PNode = return result if n.safeLen > 0: result = shallowCopy(n) - for i in 0 .. < n.len: - result.sons[i] = transformSlices(n.sons[i]) + for i in 0..<n.len: + result[i] = transformSlices(g, idgen, n[i]) else: result = n -proc transformSpawn(owner: PSym; n, barrier: PNode): PNode -proc transformSpawnSons(owner: PSym; n, barrier: PNode): PNode = +proc transformSpawn(g: ModuleGraph; idgen: IdGenerator; owner: PSym; n, barrier: PNode): PNode +proc transformSpawnSons(g: ModuleGraph; idgen: IdGenerator; owner: PSym; n, barrier: PNode): PNode = result = shallowCopy(n) - for i in 0 .. < n.len: - result.sons[i] = transformSpawn(owner, n.sons[i], barrier) + for i in 0..<n.len: + result[i] = transformSpawn(g, idgen, owner, n[i], barrier) -proc transformSpawn(owner: PSym; n, barrier: PNode): PNode = +proc transformSpawn(g: ModuleGraph; idgen: IdGenerator; owner: PSym; n, barrier: PNode): PNode = case n.kind of nkVarSection, nkLetSection: result = nil for it in n: let b = it.lastSon if getMagic(b) == mSpawn: - if it.len != 3: localError(it.info, "invalid context for 'spawn'") - let m = transformSlices(b) + if it.len != 3: localError(g.config, it.info, "invalid context for 'spawn'") + let m = transformSlices(g, idgen, b) if result.isNil: result = newNodeI(nkStmtList, n.info) result.add n - let t = b[1][0].typ.sons[0] + let t = b[1][0].typ.returnType if spawnResult(t, true) == srByVar: - result.add wrapProcForSpawn(owner, m, b.typ, barrier, it[0]) - it.sons[it.len-1] = emptyNode + result.add wrapProcForSpawn(g, idgen, owner, m, b.typ, barrier, it[0]) + it[^1] = newNodeI(nkEmpty, it.info) else: - it.sons[it.len-1] = wrapProcForSpawn(owner, m, b.typ, barrier, nil) + it[^1] = wrapProcForSpawn(g, idgen, owner, m, b.typ, barrier, nil) if result.isNil: result = n - of nkAsgn, nkFastAsgn: + of nkAsgn, nkFastAsgn, nkSinkAsgn: let b = n[1] - if getMagic(b) == mSpawn and (let t = b[1][0].typ.sons[0]; + if getMagic(b) == mSpawn and (let t = b[1][0].typ.returnType; spawnResult(t, true) == srByVar): - let m = transformSlices(b) - return wrapProcForSpawn(owner, m, b.typ, barrier, n[0]) - result = transformSpawnSons(owner, n, barrier) + let m = transformSlices(g, idgen, b) + return wrapProcForSpawn(g, idgen, owner, m, b.typ, barrier, n[0]) + result = transformSpawnSons(g, idgen, owner, n, barrier) of nkCallKinds: if getMagic(n) == mSpawn: - result = transformSlices(n) - return wrapProcForSpawn(owner, result, n.typ, barrier, nil) - result = transformSpawnSons(owner, n, barrier) + result = transformSlices(g, idgen, n) + return wrapProcForSpawn(g, idgen, owner, result, n.typ, barrier, nil) + result = transformSpawnSons(g, idgen, owner, n, barrier) elif n.safeLen > 0: - result = transformSpawnSons(owner, n, barrier) + result = transformSpawnSons(g, idgen, owner, n, barrier) else: result = n proc checkArgs(a: var AnalysisCtx; n: PNode) = - discard "too implement" + discard "to implement" proc generateAliasChecks(a: AnalysisCtx; result: PNode) = - discard "too implement" + discard "to implement" -proc liftParallel*(owner: PSym; n: PNode): PNode = +proc liftParallel*(g: ModuleGraph; idgen: IdGenerator; owner: PSym; n: PNode): PNode = # this needs to be called after the 'for' loop elimination # first pass: @@ -469,25 +480,25 @@ proc liftParallel*(owner: PSym; n: PNode): PNode = # - detect used arguments #echo "PAR ", renderTree(n) - var a = initAnalysisCtx() + var a = initAnalysisCtx(g) let body = n.lastSon analyse(a, body) if a.spawns == 0: - localError(n.info, "'parallel' section without 'spawn'") + localError(g.config, n.info, "'parallel' section without 'spawn'") checkSlicesAreDisjoint(a) checkArgs(a, body) var varSection = newNodeI(nkVarSection, n.info) - var temp = newSym(skTemp, getIdent"barrier", owner, n.info) - temp.typ = magicsys.getCompilerProc("Barrier").typ + var temp = newSym(skTemp, getIdent(g.cache, "barrier"), idgen, owner, n.info) + temp.typ = magicsys.getCompilerProc(g, "Barrier").typ incl(temp.flags, sfFromGeneric) let tempNode = newSymNode(temp) varSection.addVar tempNode - let barrier = genAddrOf(tempNode) + let barrier = genAddrOf(tempNode, idgen) result = newNodeI(nkStmtList, n.info) generateAliasChecks(a, result) result.add varSection - result.add callCodegenProc("openBarrier", barrier) - result.add transformSpawn(owner, body, barrier) - result.add callCodegenProc("closeBarrier", barrier) + result.add callCodegenProc(g, "openBarrier", barrier.info, barrier) + result.add transformSpawn(g, idgen, owner, body, barrier) + result.add callCodegenProc(g, "closeBarrier", barrier.info, barrier) |