// Copyright 2018 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 ssa import ( "fmt" "os" "slices" ) // If true, check poset integrity after every mutation var debugPoset = false const uintSize = 32 << (^uint(0) >> 63) // 32 or 64 // bitset is a bit array for dense indexes. type bitset []uint func newBitset(n int) bitset { return make(bitset, (n+uintSize-1)/uintSize) } func (bs bitset) Reset() { for i := range bs { bs[i] = 0 } } func (bs bitset) Set(idx uint32) { bs[idx/uintSize] |= 1 << (idx % uintSize) } func (bs bitset) Clear(idx uint32) { bs[idx/uintSize] &^= 1 << (idx % uintSize) } func (bs bitset) Test(idx uint32) bool { return bs[idx/uintSize]&(1<<(idx%uintSize)) != 0 } type undoType uint8 const ( undoInvalid undoType = iota undoCheckpoint // a checkpoint to group undo passes undoSetChl // change back left child of undo.idx to undo.edge undoSetChr // change back right child of undo.idx to undo.edge undoNonEqual // forget that SSA value undo.ID is non-equal to undo.idx (another ID) undoNewNode // remove new node created for SSA value undo.ID undoAliasNode // unalias SSA value undo.ID so that it points back to node index undo.idx undoNewRoot // remove node undo.idx from root list undoChangeRoot // remove node undo.idx from root list, and put back undo.edge.Target instead undoMergeRoot // remove node undo.idx from root list, and put back its children instead ) // posetUndo represents an undo pass to be performed. // It's a union of fields that can be used to store information, // and typ is the discriminant, that specifies which kind // of operation must be performed. Not all fields are always used. type posetUndo struct { typ undoType idx uint32 ID ID edge posetEdge } const ( // Make poset handle values as unsigned numbers. // (TODO: remove?) posetFlagUnsigned = 1 << iota ) // A poset edge. The zero value is the null/empty edge. // Packs target node index (31 bits) and strict flag (1 bit). type posetEdge uint32 func newedge(t uint32, strict bool) posetEdge { s := uint32(0) if strict { s = 1 } return posetEdge(t<<1 | s) } func (e posetEdge) Target() uint32 { return uint32(e) >> 1 } func (e posetEdge) Strict() bool { return uint32(e)&1 != 0 } func (e posetEdge) String() string { s := fmt.Sprint(e.Target()) if e.Strict() { s += "*" } return s } // posetNode is a node of a DAG within the poset. type posetNode struct { l, r posetEdge } // poset is a union-find data structure that can represent a partially ordered set // of SSA values. Given a binary relation that creates a partial order (eg: '<'), // clients can record relations between SSA values using SetOrder, and later // check relations (in the transitive closure) with Ordered. For instance, // if SetOrder is called to record that A 0 { i := open[len(open)-1] open = open[:len(open)-1] // Don't visit the same node twice. Notice that all nodes // across non-strict paths are still visited at least once, so // a non-strict path can never obscure a strict path to the // same node. if !closed.Test(i) { closed.Set(i) l, r := po.children(i) if l != 0 { if l.Strict() { next = append(next, l.Target()) } else { open = append(open, l.Target()) } } if r != 0 { if r.Strict() { next = append(next, r.Target()) } else { open = append(open, r.Target()) } } } } open = next closed.Reset() } for len(open) > 0 { i := open[len(open)-1] open = open[:len(open)-1] if !closed.Test(i) { if f(i) { return true } closed.Set(i) l, r := po.children(i) if l != 0 { open = append(open, l.Target()) } if r != 0 { open = append(open, r.Target()) } } } return false } // Returns true if there is a path from i1 to i2. // If strict == true: if the function returns true, then i1 < i2. // If strict == false: if the function returns true, then i1 <= i2. // If the function returns false, no relation is known. func (po *poset) reaches(i1, i2 uint32, strict bool) bool { return po.dfs(i1, strict, func(n uint32) bool { return n == i2 }) } // findroot finds i's root, that is which DAG contains i. // Returns the root; if i is itself a root, it is returned. // Panic if i is not in any DAG. func (po *poset) findroot(i uint32) uint32 { // TODO(rasky): if needed, a way to speed up this search is // storing a bitset for each root using it as a mini bloom filter // of nodes present under that root. for _, r := range po.roots { if po.reaches(r, i, false) { return r } } panic("findroot didn't find any root") } // mergeroot merges two DAGs into one DAG by creating a new extra root func (po *poset) mergeroot(r1, r2 uint32) uint32 { r := po.newnode(nil) po.setchl(r, newedge(r1, false)) po.setchr(r, newedge(r2, false)) po.changeroot(r1, r) po.removeroot(r2) po.upush(undoMergeRoot, r, 0) return r } // collapsepath marks n1 and n2 as equal and collapses as equal all // nodes across all paths between n1 and n2. If a strict edge is // found, the function does not modify the DAG and returns false. // Complexity is O(n). func (po *poset) collapsepath(n1, n2 *Value) bool { i1, i2 := po.values[n1.ID], po.values[n2.ID] if po.reaches(i1, i2, true) { return false } // Find all the paths from i1 to i2 paths := po.findpaths(i1, i2) // Mark all nodes in all the paths as aliases of n1 // (excluding n1 itself) paths.Clear(i1) po.aliasnodes(n1, paths) return true } // findpaths is a recursive function that calculates all paths from cur to dst // and return them as a bitset (the index of a node is set in the bitset if // that node is on at least one path from cur to dst). // We do a DFS from cur (stopping going deep any time we reach dst, if ever), // and mark as part of the paths any node that has a children which is already // part of the path (or is dst itself). func (po *poset) findpaths(cur, dst uint32) bitset { seen := newBitset(int(po.lastidx + 1)) path := newBitset(int(po.lastidx + 1)) path.Set(dst) po.findpaths1(cur, dst, seen, path) return path } func (po *poset) findpaths1(cur, dst uint32, seen bitset, path bitset) { if cur == dst { return } seen.Set(cur) l, r := po.chl(cur), po.chr(cur) if !seen.Test(l) { po.findpaths1(l, dst, seen, path) } if !seen.Test(r) { po.findpaths1(r, dst, seen, path) } if path.Test(l) || path.Test(r) { path.Set(cur) } } // 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[i1]; ok && bs.Test(i2) { return true } return false } // 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) } 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 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 indices arrive. bs = newBitset(int(i1)) po.noneq[i1] = bs } else if bs.Test(i2) { // Already recorded return } bs.Set(i2) po.upushneq(i1, i2) } // CheckIntegrity verifies internal integrity of a poset. It is intended // for debugging purposes. func (po *poset) CheckIntegrity() { // Verify that each node appears in a single DAG seen := newBitset(int(po.lastidx + 1)) for _, r := range po.roots { if r == 0 { panic("empty root") } po.dfs(r, false, func(i uint32) bool { if seen.Test(i) { panic("duplicate node") } seen.Set(i) return false }) } // Verify that values contain the minimum set for id, idx := range po.values { if !seen.Test(idx) { panic(fmt.Errorf("spurious value [%d]=%d", id, idx)) } } // Verify that only existing nodes have non-zero children for i, n := range po.nodes { if n.l|n.r != 0 { if !seen.Test(uint32(i)) { panic(fmt.Errorf("children of unknown node %d->%v", i, n)) } if n.l.Target() == uint32(i) || n.r.Target() == uint32(i) { panic(fmt.Errorf("self-loop on node %d", i)) } } } } // CheckEmpty checks that a poset is completely empty. // It can be used for debugging purposes, as a poset is supposed to // be empty after it's fully rolled back through Undo. func (po *poset) CheckEmpty() error { if len(po.nodes) != 1 { return fmt.Errorf("non-empty nodes list: %v", po.nodes) } if len(po.values) != 0 { return fmt.Errorf("non-empty value map: %v", po.values) } if len(po.roots) != 0 { return fmt.Errorf("non-empty root list: %v", po.roots) } if len(po.undo) != 0 { return fmt.Errorf("non-empty undo list: %v", po.undo) } if po.lastidx != 0 { return fmt.Errorf("lastidx index is not zero: %v", po.lastidx) } for _, bs := range po.noneq { for _, x := range bs { if x != 0 { return fmt.Errorf("non-empty noneq map") } } } return nil } // DotDump dumps the poset in graphviz format to file fn, with the specified title. func (po *poset) DotDump(fn string, title string) error { f, err := os.Create(fn) if err != nil { return err } defer f.Close() // Create reverse index mapping (taking aliases into account) names := make(map[uint32]string) for id, i := range po.values { s := names[i] if s == "" { s = fmt.Sprintf("v%d", id) } else { s += fmt.Sprintf(", v%d", id) } names[i] = s } fmt.Fprintf(f, "digraph poset {\n") fmt.Fprintf(f, "\tedge [ fontsize=10 ]\n") for ridx, r := range po.roots { fmt.Fprintf(f, "\tsubgraph root%d {\n", ridx) po.dfs(r, false, func(i uint32) bool { fmt.Fprintf(f, "\t\tnode%d [label=<%s [%d]>]\n", i, names[i], i) chl, chr := po.children(i) for _, ch := range []posetEdge{chl, chr} { if ch != 0 { if ch.Strict() { fmt.Fprintf(f, "\t\tnode%d -> node%d [label=\" <\" color=\"red\"]\n", i, ch.Target()) } else { fmt.Fprintf(f, "\t\tnode%d -> node%d [label=\" <=\" color=\"green\"]\n", i, ch.Target()) } } } return false }) fmt.Fprintf(f, "\t}\n") } fmt.Fprintf(f, "\tlabelloc=\"t\"\n") fmt.Fprintf(f, "\tlabeldistance=\"3.0\"\n") fmt.Fprintf(f, "\tlabel=%q\n", title) fmt.Fprintf(f, "}\n") return nil } // Ordered reports whether n1 r i1 // i2 \ / // i2 // extra := po.newnode(nil) po.changeroot(r, extra) po.upush(undoChangeRoot, extra, newedge(r, false)) po.addchild(extra, r, false) po.addchild(extra, i1, false) po.addchild(i1, i2, strict) case f1 && f2: // If the nodes are aliased, fail only if we're setting a strict order // (that is, we cannot set n1 0 { pass := po.undo[len(po.undo)-1] po.undo = po.undo[:len(po.undo)-1] switch pass.typ { case undoCheckpoint: return case undoSetChl: po.setchl(pass.idx, pass.edge) case undoSetChr: po.setchr(pass.idx, pass.edge) case undoNonEqual: po.noneq[uint32(pass.ID)].Clear(pass.idx) case undoNewNode: if pass.idx != po.lastidx { panic("invalid newnode index") } if pass.ID != 0 { if po.values[pass.ID] != pass.idx { panic("invalid newnode undo pass") } delete(po.values, pass.ID) } po.setchl(pass.idx, 0) po.setchr(pass.idx, 0) po.nodes = po.nodes[:pass.idx] po.lastidx-- case undoAliasNode: ID, prev := pass.ID, pass.idx cur := po.values[ID] if prev == 0 { // Born as an alias, die as an alias delete(po.values, ID) } else { if cur == prev { panic("invalid aliasnode undo pass") } // Give it back previous value po.values[ID] = prev } case undoNewRoot: i := pass.idx l, r := po.children(i) if l|r != 0 { panic("non-empty root in undo newroot") } po.removeroot(i) case undoChangeRoot: i := pass.idx l, r := po.children(i) if l|r != 0 { panic("non-empty root in undo changeroot") } po.changeroot(i, pass.edge.Target()) case undoMergeRoot: i := pass.idx l, r := po.children(i) po.changeroot(i, l.Target()) po.roots = append(po.roots, r.Target()) default: panic(pass.typ) } } if debugPoset && po.CheckEmpty() != nil { panic("poset not empty at the end of undo") } }