[dev.ssa] cmd/compile: implement OSLICESTR

Add a new function and generic operation to handle
bounds checking for slices. Unlike the index
bounds checking the index can be equal to the upper
bound.

Do gc-friendly slicing that generates proper code for
0-length result slices.

This is a takeover of Alexandru's original change,
(https://go-review.googlesource.com/#/c/12764/)
submittable now that the decompose phase is in.

Change-Id: I17d164cf42ed7839f84ca949c6ad3289269c9160
Reviewed-on: https://go-review.googlesource.com/13903
Reviewed-by: David Chase <drchase@google.com>

2 files changed, 177 insertions, 1 deletions

diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go
index 676de23115..ce20e7bdfd 100644
--- a/src/cmd/compile/internal/gc/ssa.go
+++ b/src/cmd/compile/internal/gc/ssa.go
@@ -1465,6 +1465,71 @@ func (s *state) expr(n *Node) *ssa.Value {
 		a := s.expr(n.Left)
 		return s.newValue1(ssa.OpITab, n.Type, a)
 
+	case OSLICESTR:
+		// Evaluate the string once.
+		str := s.expr(n.Left)
+		ptr := s.newValue1(ssa.OpStringPtr, Ptrto(Types[TUINT8]), str)
+		len := s.newValue1(ssa.OpStringLen, Types[TINT], str)
+		zero := s.constInt(Types[TINT], 0)
+
+		// Evaluate the slice indexes.
+		var low, high *ssa.Value
+		if n.Right.Left == nil {
+			low = zero
+		} else {
+			low = s.expr(n.Right.Left)
+		}
+		if n.Right.Right == nil {
+			high = len
+		} else {
+			high = s.expr(n.Right.Right)
+		}
+
+		// Panic if slice indices are not in bounds.
+		s.sliceBoundsCheck(low, high)
+		s.sliceBoundsCheck(high, len)
+
+		// Generate the following code assuming that indexes are in bounds.
+		// The conditional is to make sure that we don't generate a string
+		// that points to the next object in memory.
+		// rlen = (SubPtr high low)
+		// p = ptr
+		// if rlen != 0 {
+		//    p = (AddPtr ptr low)
+		// }
+		// result = (StringMake p size)
+		rlen := s.newValue2(ssa.OpSubPtr, Types[TINT], high, low)
+
+		// Use n as the "variable" for p.
+		s.vars[n] = ptr
+
+		// Generate code to test the resulting slice length.
+		var cmp *ssa.Value
+		if s.config.IntSize == 8 {
+			cmp = s.newValue2(ssa.OpNeq64, Types[TBOOL], rlen, zero)
+		} else {
+			cmp = s.newValue2(ssa.OpNeq32, Types[TBOOL], rlen, zero)
+		}
+
+		b := s.endBlock()
+		b.Kind = ssa.BlockIf
+		b.Likely = ssa.BranchLikely
+		b.Control = cmp
+
+		// Generate code for non-zero length slice case.
+		nz := s.f.NewBlock(ssa.BlockPlain)
+		addEdge(b, nz)
+		s.startBlock(nz)
+		s.vars[n] = s.newValue2(ssa.OpAddPtr, Ptrto(Types[TUINT8]), ptr, low)
+		s.endBlock()
+
+		// All done.
+		merge := s.f.NewBlock(ssa.BlockPlain)
+		addEdge(b, merge)
+		addEdge(nz, merge)
+		s.startBlock(merge)
+		return s.newValue2(ssa.OpStringMake, Types[TSTRING], s.variable(n, Ptrto(Types[TUINT8])), rlen)
+
 	case OCALLFUNC, OCALLMETH:
 		left := n.Left
 		static := left.Op == ONAME && left.Class == PFUNC
@@ -1782,6 +1847,25 @@ func (s *state) boundsCheck(idx, len *ssa.Value) {
 
 	// bounds check
 	cmp := s.newValue2(ssa.OpIsInBounds, Types[TBOOL], idx, len)
+	s.check(cmp, ssa.OpPanicIndexCheck)
+}
+
+// sliceBoundsCheck generates slice bounds checking code.  Checks if 0 <= idx <= len, branches to exit if not.
+// Starts a new block on return.
+func (s *state) sliceBoundsCheck(idx, len *ssa.Value) {
+	if Debug['B'] != 0 {
+		return
+	}
+	// TODO: convert index to full width?
+	// TODO: if index is 64-bit and we're compiling to 32-bit, check that high 32 bits are zero.
+
+	// bounds check
+	cmp := s.newValue2(ssa.OpIsSliceInBounds, Types[TBOOL], idx, len)
+	s.check(cmp, ssa.OpPanicSliceCheck)
+}
+
+// If cmp (a bool) is true, panic using the given op.
+func (s *state) check(cmp *ssa.Value, panicOp ssa.Op) {
 	b := s.endBlock()
 	b.Kind = ssa.BlockIf
 	b.Control = cmp
@@ -1794,7 +1878,7 @@ func (s *state) boundsCheck(idx, len *ssa.Value) {
 	s.startBlock(bPanic)
 	// The panic check takes/returns memory to ensure that the right
 	// memory state is observed if the panic happens.
-	s.vars[&memvar] = s.newValue1(ssa.OpPanicIndexCheck, ssa.TypeMem, s.mem())
+	s.vars[&memvar] = s.newValue1(panicOp, ssa.TypeMem, s.mem())
 	s.endBlock()
 	s.startBlock(bNext)
 }
diff --git a/src/cmd/compile/internal/gc/testdata/string_ssa.go b/src/cmd/compile/internal/gc/testdata/string_ssa.go
new file mode 100644
index 0000000000..5987412933
--- /dev/null
+++ b/src/cmd/compile/internal/gc/testdata/string_ssa.go
@@ -0,0 +1,92 @@
+// string_ssa.go tests string operations.
+package main
+
+var failed = false
+
+func testStringSlice1_ssa(a string, i, j int) string {
+	switch { // prevent inlining
+	}
+	return a[i:]
+}
+
+func testStringSlice2_ssa(a string, i, j int) string {
+	switch { // prevent inlining
+	}
+	return a[:j]
+}
+
+func testStringSlice12_ssa(a string, i, j int) string {
+	switch { // prevent inlining
+	}
+	return a[i:j]
+}
+
+func testStringSlice() {
+	tests := [...]struct {
+		fn        func(string, int, int) string
+		s         string
+		low, high int
+		want      string
+	}{
+		// -1 means the value is not used.
+		{testStringSlice1_ssa, "foobar", 0, -1, "foobar"},
+		{testStringSlice1_ssa, "foobar", 3, -1, "bar"},
+		{testStringSlice1_ssa, "foobar", 6, -1, ""},
+		{testStringSlice2_ssa, "foobar", -1, 0, ""},
+		{testStringSlice2_ssa, "foobar", -1, 3, "foo"},
+		{testStringSlice2_ssa, "foobar", -1, 6, "foobar"},
+		{testStringSlice12_ssa, "foobar", 0, 6, "foobar"},
+		{testStringSlice12_ssa, "foobar", 0, 0, ""},
+		{testStringSlice12_ssa, "foobar", 6, 6, ""},
+		{testStringSlice12_ssa, "foobar", 1, 5, "ooba"},
+		{testStringSlice12_ssa, "foobar", 3, 3, ""},
+		{testStringSlice12_ssa, "", 0, 0, ""},
+	}
+
+	for i, t := range tests {
+		if got := t.fn(t.s, t.low, t.high); t.want != got {
+			println("#", i, " ", t.s, "[", t.low, ":", t.high, "] = ", got, " want ", t.want)
+			failed = true
+		}
+	}
+}
+
+type prefix struct {
+	prefix string
+}
+
+func (p *prefix) slice_ssa() {
+	p.prefix = p.prefix[:3]
+}
+
+func testStructSlice() {
+	switch {
+	}
+	p := &prefix{"prefix"}
+	p.slice_ssa()
+	if "pre" != p.prefix {
+		println("wrong field slice: wanted %s got %s", "pre", p.prefix)
+	}
+}
+
+func testStringSlicePanic() {
+	defer func() {
+		if r := recover(); r != nil {
+			println("paniced as expected")
+		}
+	}()
+
+	str := "foobar"
+	println("got ", testStringSlice12_ssa(str, 3, 9))
+	println("expected to panic, but didn't")
+	failed = true
+}
+
+func main() {
+	testStringSlice()
+	testStringSlicePanic()
+
+	if failed {
+		panic("failed")
+	}
+}