GitLab

While submitting CL 7371051 I accidentally reverted much of CL
7395052.  This change restores it.

R=gri
TBR=gri
CC=golang-dev
https://golang.org/cl/7364051

The correct semantics of named result parameters and deferred
procedures cannot be implemented with the existing Ret
instruction alone, since the required sequence is:
(1) evaluate return operands and parallel-assign them to
    named result parameters
(2) invoke deferred procedures
(3) load named result parameters to form result tuple.

We introduce a new 'rundefers' instruction that explicitly
invokes the deferred procedure calls, and we generate code
that follows the sequence above.

Most functions do not use deferred procedures but this cannot
be known in a single pass.  So, we add an optimisation to
eliminate redundant 'rundefers'; it is piggybacked on the
existing pass done for "lifting".

Added tests.

R=gri
CC=golang-dev
https://golang.org/cl/7411043

Details:
- move Builder.nTo1Vars into package => thread-safe.
- add BuildSerially builder mode flag to disable concurrency.
- add Builder.BuildAllPackages method.

Benchmark: BuildAllPackages for $GOROOT/test/append.go drops
to 83ms from 190ms (GOMAXPROCS=8).

R=gri
CC=golang-dev
https://golang.org/cl/7371051

Actually it already worked since the spec only requires that
the one immediately preceding a for/switch/... be usable as
the target of a break or continue statement.

Added a test.
Also: allocate Function.lblocks on first use.

R=gri
CC=golang-dev
https://golang.org/cl/7365058

The previous approach desugared the ast.SelectorExpr
to make implicit field selections explicit.  But:
1) it was clunky since it required allocating temporary
   syntax trees.
2) it was not thread-safe since it required poking
   types into the shared type map for the new ASTs.
3) the desugared syntax had no place to represent the
   package lexically enclosing each implicit field
   selection, so it was as if they all occurred in the
   same package as the explicit field selection.
   This meant unexported field names changed meaning.

This CL does what I should have done all along: just
generate the SSA instructions directly from the original
AST and the promoted field information.

Also:
- add logStack util for paired start/end log messages.
  Useful for debugging crashes.

R=gri
CC=golang-dev
https://golang.org/cl/7395052

We wrap the final '...' argument's type in types.Slice.
Added tests.

Also:
- Function.writeSignature: suppress slice '[]' when printing
  variadic arg '...'.
- Eliminate Package.ImportPath field; redundant
  w.r.t. Package.Types.Path.
- Use "TODO: (opt|fix)" notation more widely.
- Eliminate many redundant/stale TODOs.

R=gri
CC=golang-dev
https://golang.org/cl/7378057

By appending to the wrong (always empty) list, only the last
anonymous field was being considered for promotion.

Also:
- eliminated "function-local NamedTypes" TODO; nothing to do.
- fixed Function.DumpTo: printing of anon receivers was "( T)",
  now "(T)"; extracted writeSignature into own function.
- eliminated blockNames function;
  thanks to BasicBlock.String, "%s" of []*BasicBlock is fine.
- extracted buildReferrers into own function.

exp/ssa can now build its own transitive closure.

R=gri
CC=golang-dev
https://golang.org/cl/7384054

- append: nothing to do (nonsemantic change).
- delete: now performs correct conversion (+ test).
- emitCompare: nothing to do.
- emitArith (shifts): nothing to do (+ test).
- "banish untyped types": give up on that.
- real, imag: now do correct conversions.
- added comment to interp.go re zero-size values.

R=gri
CC=golang-dev
https://golang.org/cl/7391046

By avoiding the need for self-loops following calls to panic,
we reduce the number of basic blocks considerably.

R=gri
CC=golang-dev, iant
https://golang.org/cl/7403043

Overview: Function.finish() now invokes the "lifting" pass which replaces local allocs and loads and stores to such cells by SSA registers.  We use very standard machinery:

(1) we build the dominator tree for the function's control flow graph (CFG) using the "Simple" Lengauer-Tarjan algorithm.  (Very "simple" in fact: even simple path compression is not yet implemented.)

In sanity-checking mode, we cross check the dominator tree against an alternative implementation using a simple iterative dataflow algorithm.
This all lives in dom.go, along with some diagnostic printing routines.

(2) we build the dominance frontier for the entire CFG using the Cytron et al algorithm.  The DF is represented as a slice of slices, keyed by block index.  See buildDomFrontier() in lift.go.

(3) we determine for each Alloc whether it can be lifted: is it only subject to loads and stores?  If so, we traverse the iterated dominance frontier (IDF) creating φ-nodes; they are not prepended to the blocks yet.
See liftAlloc() in lift.go.

(4) we perform the SSA renaming algorithm from Cytron et al, replacing all loads to lifted Alloc cells by the value stored by the dominating store operation, and deleting the stores and allocs.  See rename() in lift.go.

(5) we eliminate unneeded φ-nodes, then concatenate the remaining ones with the non-deleted instructions of the block into a new slice.  We eliminate any lifted allocs from Function.Locals.

To ease reviewing, I have avoided almost all optimisations at this point, though there are many opportunities to explore.  These will be easier to understand as follow-up changes.

All the existing tests (pending CL 7313062) pass.  (Faster!)

Details:

"NaiveForm" BuilderMode flag suppresses all the new logic.
Exposed as 'ssadump -build=N'.

BasicBlock:
- add .Index field (b.Func[b.Index]==b), simplifying
  algorithms such as Kildall-style dataflow with bitvectors.
- rename the Name field to Comment to better reflect its
  reduced purpose.  It now has a String() method.
- 'dom' field holds dominator tree node; private for now.
- new predIndex method.
- hasPhi is now a method

dom.go:
- domTree: a new struct for a node in a dominator tree.
- buildDomTree builds the dominator tree using the simple
  variant Lengauer/Tarjan algorithm with Georgiadis'
  bucket optimizations.
- sanityCheckDomTree builds dominance relation using
  Kildall-style dataflow and ensures the same result is
  obtained.
- printDomTreeDot prints the CFG/DomTree in GraphViz format.

blockopt.go:
- perform a mark/sweep pass to eliminate unreachable
  cycles; the previous prune() opt would only eliminate
  trivially dead blocks.  (Needed for LT algo.)
- using .Index, fuseblocks can now delete fused blocks directly.
- delete prune().

sanity.go: more consistency checks:
- Phi with missing edge value
- local Alloc instructions must appear in Function.Locals.
- BasicBlock.Index, Func consistency
- CFG edges are all intraprocedural.
- detect nils in BasicBlock.Instrs.
- detect Function.Locals with Heap flag set.
- check fn.Blocks is nil if empty.

Also:
- Phi now has Comment field for debugging.
- Fixed bug in Select.Operands()
  (took address of temporary copy of field)
- new Literal constructor zeroLiteral().
- algorithms steal private fields Alloc.index,
  BasicBlock.gaps to avoid allocating maps.
- We print Function.Locals in DumpTo.
- added profiling support to ssadump.

R=iant, gri
CC=golang-dev
https://golang.org/cl/7229074

(Offsetof is a function of Alignof and Sizeof.)

- removed IntSize, PtrSize from Context (set Sizeof instead)
- GcImporter needs a Context now (it needs to have
  access to Sizeof/Alignof)
- removed exported Size field from Basic (use Sizeof)
- added Offset to Field
- added Alignment, Size to Struct

R=adonovan
CC=golang-dev
https://golang.org/cl/7357046

This avoids ambiguity and makes the diagnostics closer to
those issued by gc, but it is more verbose since it qualifies
intra-package references.

Without extra context---e.g. a 'from *Package' parameter to
Type.String()---we are forced to err on one side or the other.

Also, cosmetic changes to exp/ssa:
- Remove package-qualification workaround in Function.FullName.
- Always set go/types.Package.Path field to the import path,
  since we know the correct path at this point.
- In Function.DumpTo, show variadic '...' and result type info,
  and delete now-redundant "# Type: " line.

R=gri
CC=golang-dev
https://golang.org/cl/7325051

The lowering of ast.RangeStmt now has three distinct cases:

1) rangeIter for maps and strings; approximately:
    it = range x
    for {
      k, v, ok = next it
      if !ok { break }
      ...
    }
   The Range instruction and the interpreter's "iter"
   datatype are now restricted to these types.

2) rangeChan for channels; approximately:
    for {
      k, ok = <-x
      if !ok { break }
      ...
    }

3) rangeIndexed for slices, arrays, and *array; approximately:
    for k, l = 0, len(x); k < l; k++ {
      v = x[k]
      ...
    }

In all cases we now evaluate the side effects of the range expression
exactly once, per comments on http://code.google.com/p/go/issues/detail?id=4644.

However the exact spec wording is still being discussed in
https://golang.org/cl/7307083/.  Further (small)
changes may be required once the dust settles.

R=iant
CC=golang-dev
https://golang.org/cl/7303074

R=iant, gri, iant, rogpeppe
CC=golang-dev
https://golang.org/cl/7196053