From 90888ed97b5b3c0d104b2e9f28e5b74c1b0d07dd Mon Sep 17 00:00:00 2001 From: Giovanni Bajo Date: Sun, 13 Oct 2019 01:30:51 +0200 Subject: [PATCH] cmd/compile: in poset, change the way inequality is recorded Before this CL, inequality was recorded in a bit matrix using SSA IDs. This allowed to record inequality for SSA values that we didn't know any relation in the partial order of. Unfortunately, this also means that inequality is harder to use within the poset itself as there is not fast way to map from internal poset indices and SSA values. Since we will need to check for inequality in following CLs within code that lost track of SSA values, switch to use a bit matrix of poset indices instead. This requires always allocate a poset node (as a new root) for values that are first seen in a SetNonEqual call, but it doesn't sound like a big problem. The other solution (creating and maintaining a reverse map from poset indices to SSA values) seem more complicated and memory hungry. Change-Id: Ic917485abbe70aef7ad6fa98408e5430328b6cd9 Reviewed-on: https://go-review.googlesource.com/c/go/+/196782 Run-TryBot: Giovanni Bajo TryBot-Result: Gobot Gobot Reviewed-by: David Chase --- src/cmd/compile/internal/ssa/poset.go | 150 ++++++++++++++++---------- 1 file changed, 96 insertions(+), 54 deletions(-) diff --git a/src/cmd/compile/internal/ssa/poset.go b/src/cmd/compile/internal/ssa/poset.go index e4fa3a83e0..e3a5485d13 100644 --- a/src/cmd/compile/internal/ssa/poset.go +++ b/src/cmd/compile/internal/ssa/poset.go @@ -147,14 +147,14 @@ type posetNode struct { // J K // type poset struct { - lastidx uint32 // last generated dense index - flags uint8 // internal flags - values map[ID]uint32 // map SSA values to dense indexes - constants map[int64]uint32 // record SSA constants together with their value - nodes []posetNode // nodes (in all DAGs) - roots []uint32 // list of root nodes (forest) - noneq map[ID]bitset // non-equal relations - undo []posetUndo // undo chain + lastidx uint32 // last generated dense index + flags uint8 // internal flags + values map[ID]uint32 // map SSA values to dense indexes + constants map[int64]uint32 // record SSA constants together with their value + nodes []posetNode // nodes (in all DAGs) + roots []uint32 // list of root nodes (forest) + noneq map[uint32]bitset // non-equal relations + undo []posetUndo // undo chain } func newPoset() *poset { @@ -163,7 +163,7 @@ func newPoset() *poset { constants: make(map[int64]uint32, 8), nodes: make([]posetNode, 1, 16), roots: make([]uint32, 0, 4), - noneq: make(map[ID]bitset), + noneq: make(map[uint32]bitset), undo: make([]posetUndo, 0, 4), } } @@ -197,8 +197,8 @@ func (po *poset) upushnew(id ID, idx uint32) { } // upushneq pushes a new undo pass for a nonequal relation -func (po *poset) upushneq(id1 ID, id2 ID) { - po.undo = append(po.undo, posetUndo{typ: undoNonEqual, ID: id1, idx: uint32(id2)}) +func (po *poset) upushneq(idx1 uint32, idx2 uint32) { + po.undo = append(po.undo, posetUndo{typ: undoNonEqual, ID: ID(idx1), idx: idx2}) } // upushalias pushes a new undo pass for aliasing two nodes @@ -622,38 +622,61 @@ func (po *poset) collapsepath(n1, n2 *Value) bool { return true } -// Check whether it is recorded that id1!=id2 -func (po *poset) isnoneq(id1, id2 ID) bool { - if id1 < id2 { - id1, id2 = id2, id1 +// Check whether it is recorded that i1!=i2 +func (po *poset) isnoneq(i1, i2 uint32) bool { + if i1 == i2 { + return false + } + if i1 < i2 { + i1, i2 = i2, i1 } // Check if we recorded a non-equal relation before - if bs, ok := po.noneq[id1]; ok && bs.Test(uint32(id2)) { + if bs, ok := po.noneq[i1]; ok && bs.Test(i2) { return true } return false } -// Record that id1!=id2 -func (po *poset) setnoneq(id1, id2 ID) { - if id1 < id2 { - id1, id2 = id2, id1 +// Record that i1!=i2 +func (po *poset) setnoneq(n1, n2 *Value) { + i1, f1 := po.lookup(n1) + i2, f2 := po.lookup(n2) + + // If any of the nodes do not exist in the poset, allocate them. Since + // we don't know any relation (in the partial order) about them, they must + // become independent roots. + if !f1 { + i1 = po.newnode(n1) + po.roots = append(po.roots, i1) + po.upush(undoNewRoot, i1, 0) } - bs := po.noneq[id1] + if !f2 { + i2 = po.newnode(n2) + po.roots = append(po.roots, i2) + po.upush(undoNewRoot, i2, 0) + } + + if i1 == i2 { + panic("setnoneq on same node") + } + if i1 < i2 { + i1, i2 = i2, i1 + } + bs := po.noneq[i1] if bs == nil { // Given that we record non-equality relations using the - // higher ID as a key, the bitsize will never change size. + // higher index as a key, the bitsize will never change size. // TODO(rasky): if memory is a problem, consider allocating - // a small bitset and lazily grow it when higher IDs arrive. - bs = newBitset(int(id1)) - po.noneq[id1] = bs - } else if bs.Test(uint32(id2)) { + // a small bitset and lazily grow it when higher indices arrive. + bs = newBitset(int(i1)) + po.noneq[i1] = bs + } else if bs.Test(i2) { // Already recorded return } - bs.Set(uint32(id2)) - po.upushneq(id1, id2) + bs.Set(i2) + po.upushneq(i1, i2) } // CheckIntegrity verifies internal integrity of a poset. It is intended @@ -876,7 +899,17 @@ func (po *poset) NonEqual(n1, n2 *Value) bool { if n1.ID == n2.ID { panic("should not call NonEqual with n1==n2") } - if po.isnoneq(n1.ID, n2.ID) { + + // If we never saw the nodes before, we don't + // have a recorded non-equality. + i1, f1 := po.lookup(n1) + i2, f2 := po.lookup(n2) + if !f1 || !f2 { + return false + } + + // Check if we recored inequality + if po.isnoneq(i1, i2) { return true } @@ -892,12 +925,6 @@ func (po *poset) NonEqual(n1, n2 *Value) bool { // if this is a contradiction. // Implements SetOrder() and SetOrderOrEqual() func (po *poset) setOrder(n1, n2 *Value, strict bool) bool { - // If we are trying to record n1<=n2 but we learned that n1!=n2, - // record n1