[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>
diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go
index 676de23..ce20e7b 100644
--- a/src/cmd/compile/internal/gc/ssa.go
+++ b/src/cmd/compile/internal/gc/ssa.go
@@ -1465,6 +1465,71 @@
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 @@
// 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 @@
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 0000000..5987412
--- /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")
+ }
+}
diff --git a/src/cmd/compile/internal/ssa/gen/AMD64.rules b/src/cmd/compile/internal/ssa/gen/AMD64.rules
index ff89a7e..f0b9288 100644
--- a/src/cmd/compile/internal/ssa/gen/AMD64.rules
+++ b/src/cmd/compile/internal/ssa/gen/AMD64.rules
@@ -19,6 +19,7 @@
(Add64F x y) -> (ADDSD x y)
(Sub64 x y) -> (SUBQ x y)
+(SubPtr x y) -> (SUBQ x y)
(Sub32 x y) -> (SUBL x y)
(Sub16 x y) -> (SUBW x y)
(Sub8 x y) -> (SUBB x y)
@@ -279,6 +280,7 @@
// checks
(IsNonNil p) -> (SETNE (TESTQ <TypeFlags> p p))
(IsInBounds idx len) -> (SETB (CMPQ <TypeFlags> idx len))
+(IsSliceInBounds idx len) -> (SETBE (CMPQ <TypeFlags> idx len))
(PanicNilCheck ptr mem) -> (LoweredPanicNilCheck ptr mem)
(PanicIndexCheck mem) -> (LoweredPanicIndexCheck mem)
diff --git a/src/cmd/compile/internal/ssa/gen/genericOps.go b/src/cmd/compile/internal/ssa/gen/genericOps.go
index a0040d3..66bb659 100644
--- a/src/cmd/compile/internal/ssa/gen/genericOps.go
+++ b/src/cmd/compile/internal/ssa/gen/genericOps.go
@@ -21,9 +21,11 @@
{name: "Sub16"},
{name: "Sub32"},
{name: "Sub64"},
+ {name: "SubPtr"},
{name: "Sub32F"},
{name: "Sub64F"},
// TODO: Sub64C, Sub128C
+ // TODO: Sub32F, Sub64F, Sub64C, Sub128C
{name: "Mul8"}, // arg0 * arg1
{name: "Mul16"},
@@ -311,8 +313,9 @@
{name: "Cvt64Fto32F"},
// Automatically inserted safety checks
- {name: "IsNonNil"}, // arg0 != nil
- {name: "IsInBounds"}, // 0 <= arg0 < arg1
+ {name: "IsNonNil"}, // arg0 != nil
+ {name: "IsInBounds"}, // 0 <= arg0 < arg1
+ {name: "IsSliceInBounds"}, // 0 <= arg0 <= arg1
// Pseudo-ops
{name: "PanicNilCheck"}, // trigger a dereference fault; arg0=nil ptr, arg1=mem, returns mem
diff --git a/src/cmd/compile/internal/ssa/opGen.go b/src/cmd/compile/internal/ssa/opGen.go
index 4eccb46..8d99d57 100644
--- a/src/cmd/compile/internal/ssa/opGen.go
+++ b/src/cmd/compile/internal/ssa/opGen.go
@@ -274,6 +274,7 @@
OpSub16
OpSub32
OpSub64
+ OpSubPtr
OpSub32F
OpSub64F
OpMul8
@@ -491,6 +492,7 @@
OpCvt64Fto32F
OpIsNonNil
OpIsInBounds
+ OpIsSliceInBounds
OpPanicNilCheck
OpPanicIndexCheck
OpPanicSliceCheck
@@ -2335,6 +2337,7 @@
inputs: []inputInfo{
{0, 65535}, // .AX .CX .DX .BX .SP .BP .SI .DI .R8 .R9 .R10 .R11 .R12 .R13 .R14 .R15
},
+ clobbers: 8589934592, // .FLAGS
outputs: []regMask{
65519, // .AX .CX .DX .BX .BP .SI .DI .R8 .R9 .R10 .R11 .R12 .R13 .R14 .R15
},
@@ -2631,7 +2634,6 @@
inputs: []inputInfo{
{0, 65535}, // .AX .CX .DX .BX .SP .BP .SI .DI .R8 .R9 .R10 .R11 .R12 .R13 .R14 .R15
},
- clobbers: 8589934592, // .FLAGS
outputs: []regMask{
65519, // .AX .CX .DX .BX .BP .SI .DI .R8 .R9 .R10 .R11 .R12 .R13 .R14 .R15
},
@@ -3107,6 +3109,10 @@
generic: true,
},
{
+ name: "SubPtr",
+ generic: true,
+ },
+ {
name: "Sub32F",
generic: true,
},
@@ -3975,6 +3981,10 @@
generic: true,
},
{
+ name: "IsSliceInBounds",
+ generic: true,
+ },
+ {
name: "PanicNilCheck",
generic: true,
},
diff --git a/src/cmd/compile/internal/ssa/rewriteAMD64.go b/src/cmd/compile/internal/ssa/rewriteAMD64.go
index dc6dce9..c0213d8 100644
--- a/src/cmd/compile/internal/ssa/rewriteAMD64.go
+++ b/src/cmd/compile/internal/ssa/rewriteAMD64.go
@@ -2791,6 +2791,27 @@
goto endff508c3726edfb573abc6128c177e76c
endff508c3726edfb573abc6128c177e76c:
;
+ case OpIsSliceInBounds:
+ // match: (IsSliceInBounds idx len)
+ // cond:
+ // result: (SETBE (CMPQ <TypeFlags> idx len))
+ {
+ idx := v.Args[0]
+ len := v.Args[1]
+ v.Op = OpAMD64SETBE
+ v.AuxInt = 0
+ v.Aux = nil
+ v.resetArgs()
+ v0 := b.NewValue0(v.Line, OpAMD64CMPQ, TypeInvalid)
+ v0.Type = TypeFlags
+ v0.AddArg(idx)
+ v0.AddArg(len)
+ v.AddArg(v0)
+ return true
+ }
+ goto end41f8211150e3a4ef36a1b5168013f96f
+ end41f8211150e3a4ef36a1b5168013f96f:
+ ;
case OpLeq16:
// match: (Leq16 x y)
// cond:
@@ -9579,6 +9600,24 @@
goto end7d33bf9bdfa505f96b930563eca7955f
end7d33bf9bdfa505f96b930563eca7955f:
;
+ case OpSubPtr:
+ // match: (SubPtr x y)
+ // cond:
+ // result: (SUBQ x y)
+ {
+ x := v.Args[0]
+ y := v.Args[1]
+ v.Op = OpAMD64SUBQ
+ v.AuxInt = 0
+ v.Aux = nil
+ v.resetArgs()
+ v.AddArg(x)
+ v.AddArg(y)
+ return true
+ }
+ goto end748f63f755afe0b97a8f3cf7e4d9cbfe
+ end748f63f755afe0b97a8f3cf7e4d9cbfe:
+ ;
case OpTrunc16to8:
// match: (Trunc16to8 x)
// cond:
