From f073395b73e2e5926a7bb996094a3e49ebc1d4dc Mon Sep 17 00:00:00 2001 From: Michael Munday Date: Wed, 13 May 2020 16:46:16 +0100 Subject: [PATCH] cmd/compile: fix tuple selector bug in CSE pass When tuple generators and selectors are eliminated as part of the CSE pass we may end up with tuple selectors that are in different blocks to the tuple generators that they correspond to. This breaks the invariant that tuple generators and their corresponding selectors must be in the same block. Therefore after CSE this situation must be corrected. Unfortunately the fixup code did not take into account that selectors could be eliminated by CSE. It assumed that only the tuple generators could be eliminated. In some situations this meant that it got into a state where it was replacing references to selectors with references to dead selectors in the wrong block. To fix this we move the fixup code after the CSE rewrites have been applied. This removes any difficult-to-reason-about interactions with the CSE rewriter. Fixes #38916. Change-Id: I2211982dcdba399d03299f0a819945b3eb93b291 Reviewed-on: https://go-review.googlesource.com/c/go/+/233857 Run-TryBot: Michael Munday TryBot-Result: Gobot Gobot Reviewed-by: Keith Randall Reviewed-by: Cherry Zhang --- src/cmd/compile/internal/ssa/cse.go | 92 +++++++++++++++++------------ test/fixedbugs/issue38916.go | 14 +++++ 2 files changed, 69 insertions(+), 37 deletions(-) create mode 100644 test/fixedbugs/issue38916.go diff --git a/src/cmd/compile/internal/ssa/cse.go b/src/cmd/compile/internal/ssa/cse.go index 15dfe6d795..6bfd2960c1 100644 --- a/src/cmd/compile/internal/ssa/cse.go +++ b/src/cmd/compile/internal/ssa/cse.go @@ -190,43 +190,6 @@ func cse(f *Func) { } } - // if we rewrite a tuple generator to a new one in a different block, - // copy its selectors to the new generator's block, so tuple generator - // and selectors stay together. - // be careful not to copy same selectors more than once (issue 16741). - copiedSelects := make(map[ID][]*Value) - for _, b := range f.Blocks { - out: - for _, v := range b.Values { - // New values are created when selectors are copied to - // a new block. We can safely ignore those new values, - // since they have already been copied (issue 17918). - if int(v.ID) >= len(rewrite) || rewrite[v.ID] != nil { - continue - } - if v.Op != OpSelect0 && v.Op != OpSelect1 { - continue - } - if !v.Args[0].Type.IsTuple() { - f.Fatalf("arg of tuple selector %s is not a tuple: %s", v.String(), v.Args[0].LongString()) - } - t := rewrite[v.Args[0].ID] - if t != nil && t.Block != b { - // v.Args[0] is tuple generator, CSE'd into a different block as t, v is left behind - for _, c := range copiedSelects[t.ID] { - if v.Op == c.Op { - // an equivalent selector is already copied - rewrite[v.ID] = c - continue out - } - } - c := v.copyInto(t.Block) - rewrite[v.ID] = c - copiedSelects[t.ID] = append(copiedSelects[t.ID], c) - } - } - } - rewrites := int64(0) // Apply substitutions @@ -259,6 +222,61 @@ func cse(f *Func) { } } } + + // Fixup tuple selectors. + // + // If we have rewritten a tuple generator to a new one in a different + // block, copy its selectors to the new generator's block, so tuple + // generator and selectors stay together. + // + // Note: that there must be only one selector of each type per tuple + // generator. CSE may have left us with more than one so we de-duplicate + // them using a map. See issue 16741. + selectors := make(map[struct { + id ID + op Op + }]*Value) + for _, b := range f.Blocks { + for _, selector := range b.Values { + if selector.Op != OpSelect0 && selector.Op != OpSelect1 { + continue + } + + // Get the tuple generator to use as a key for de-duplication. + tuple := selector.Args[0] + if !tuple.Type.IsTuple() { + f.Fatalf("arg of tuple selector %s is not a tuple: %s", selector.String(), tuple.LongString()) + } + + // If there is a pre-existing selector in the target block then + // use that. Do this even if the selector is already in the + // target block to avoid duplicate tuple selectors. + key := struct { + id ID + op Op + }{tuple.ID, selector.Op} + if t := selectors[key]; t != nil { + if selector != t { + selector.copyOf(t) + } + continue + } + + // If the selector is in the wrong block copy it into the target + // block. + if selector.Block != tuple.Block { + t := selector.copyInto(tuple.Block) + selector.copyOf(t) + selectors[key] = t + continue + } + + // The selector is in the target block. Add it to the map so it + // cannot be duplicated. + selectors[key] = selector + } + } + if f.pass.stats > 0 { f.LogStat("CSE REWRITES", rewrites) } diff --git a/test/fixedbugs/issue38916.go b/test/fixedbugs/issue38916.go new file mode 100644 index 0000000000..fb2ee3459d --- /dev/null +++ b/test/fixedbugs/issue38916.go @@ -0,0 +1,14 @@ +// compile + +// Copyright 2020 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package p + +func f(b bool, c complex128) func(complex128) complex128 { + return func(p complex128) complex128 { + b = (p+1i == 0) && b + return (p + 2i) * (p + 3i - c) + } +} -- 2.50.0