| 1 | // Copyright 2021 The Go Authors. All rights reserved. |
|---|---|
| 2 | // Use of this source code is governed by a BSD-style |
| 3 | // license that can be found in the LICENSE file. |
| 4 | |
| 5 | package vta |
| 6 | |
| 7 | import ( |
| 8 | "go/token" |
| 9 | "go/types" |
| 10 | "reflect" |
| 11 | "sort" |
| 12 | "strings" |
| 13 | "testing" |
| 14 | "unsafe" |
| 15 | |
| 16 | "golang.org/x/tools/go/ssa" |
| 17 | |
| 18 | "golang.org/x/tools/go/types/typeutil" |
| 19 | ) |
| 20 | |
| 21 | // val is a test data structure for creating ssa.Value |
| 22 | // outside of the ssa package. Needed for manual creation |
| 23 | // of vta graph nodes in testing. |
| 24 | type val struct { |
| 25 | name string |
| 26 | typ types.Type |
| 27 | } |
| 28 | |
| 29 | func (v val) String() string { |
| 30 | return v.name |
| 31 | } |
| 32 | |
| 33 | func (v val) Name() string { |
| 34 | return v.name |
| 35 | } |
| 36 | |
| 37 | func (v val) Type() types.Type { |
| 38 | return v.typ |
| 39 | } |
| 40 | |
| 41 | func (v val) Parent() *ssa.Function { |
| 42 | return nil |
| 43 | } |
| 44 | |
| 45 | func (v val) Referrers() *[]ssa.Instruction { |
| 46 | return nil |
| 47 | } |
| 48 | |
| 49 | func (v val) Pos() token.Pos { |
| 50 | return token.NoPos |
| 51 | } |
| 52 | |
| 53 | // newLocal creates a new local node with ssa.Value |
| 54 | // named `name` and type `t`. |
| 55 | func newLocal(name string, t types.Type) local { |
| 56 | return local{val: val{name: name, typ: t}} |
| 57 | } |
| 58 | |
| 59 | // newNamedType creates a bogus type named `name`. |
| 60 | func newNamedType(name string) *types.Named { |
| 61 | return types.NewNamed(types.NewTypeName(token.NoPos, nil, name, nil), types.Universe.Lookup("int").Type(), nil) |
| 62 | } |
| 63 | |
| 64 | // sccString is a utility for stringifying `nodeToScc`. Every |
| 65 | // scc is represented as a string where string representation |
| 66 | // of scc nodes are sorted and concatenated using `;`. |
| 67 | func sccString(nodeToScc map[node]int) []string { |
| 68 | sccs := make(map[int][]node) |
| 69 | for n, id := range nodeToScc { |
| 70 | sccs[id] = append(sccs[id], n) |
| 71 | } |
| 72 | |
| 73 | var sccsStr []string |
| 74 | for _, scc := range sccs { |
| 75 | var nodesStr []string |
| 76 | for _, node := range scc { |
| 77 | nodesStr = append(nodesStr, node.String()) |
| 78 | } |
| 79 | sort.Strings(nodesStr) |
| 80 | sccsStr = append(sccsStr, strings.Join(nodesStr, ";")) |
| 81 | } |
| 82 | return sccsStr |
| 83 | } |
| 84 | |
| 85 | // nodeToTypeString is testing utility for stringifying results |
| 86 | // of type propagation: propTypeMap `pMap` is converted to a map |
| 87 | // from node strings to a string consisting of type stringifications |
| 88 | // concatenated with `;`. We stringify reachable type information |
| 89 | // that also has an accompanying function by the function name. |
| 90 | func nodeToTypeString(pMap propTypeMap) map[string]string { |
| 91 | // Convert propType to a string. If propType has |
| 92 | // an attached function, return the function name. |
| 93 | // Otherwise, return the type name. |
| 94 | propTypeString := func(p propType) string { |
| 95 | if p.f != nil { |
| 96 | return p.f.Name() |
| 97 | } |
| 98 | return p.typ.String() |
| 99 | } |
| 100 | |
| 101 | nodeToTypeStr := make(map[string]string) |
| 102 | for node := range pMap.nodeToScc { |
| 103 | var propStrings []string |
| 104 | for _, prop := range pMap.propTypes(node) { |
| 105 | propStrings = append(propStrings, propTypeString(prop)) |
| 106 | } |
| 107 | sort.Strings(propStrings) |
| 108 | nodeToTypeStr[node.String()] = strings.Join(propStrings, ";") |
| 109 | } |
| 110 | |
| 111 | return nodeToTypeStr |
| 112 | } |
| 113 | |
| 114 | // sccEqual compares two sets of SCC stringifications. |
| 115 | func sccEqual(sccs1 []string, sccs2 []string) bool { |
| 116 | if len(sccs1) != len(sccs2) { |
| 117 | return false |
| 118 | } |
| 119 | sort.Strings(sccs1) |
| 120 | sort.Strings(sccs2) |
| 121 | return reflect.DeepEqual(sccs1, sccs2) |
| 122 | } |
| 123 | |
| 124 | // isRevTopSorted checks if sccs of `g` are sorted in reverse |
| 125 | // topological order: |
| 126 | // |
| 127 | // for every edge x -> y in g, nodeToScc[x] > nodeToScc[y] |
| 128 | func isRevTopSorted(g vtaGraph, nodeToScc map[node]int) bool { |
| 129 | for n, succs := range g { |
| 130 | for s := range succs { |
| 131 | if nodeToScc[n] < nodeToScc[s] { |
| 132 | return false |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | return true |
| 137 | } |
| 138 | |
| 139 | // setName sets name of the function `f` to `name` |
| 140 | // using reflection since setting the name otherwise |
| 141 | // is only possible within the ssa package. |
| 142 | func setName(f *ssa.Function, name string) { |
| 143 | fi := reflect.ValueOf(f).Elem().FieldByName("name") |
| 144 | fi = reflect.NewAt(fi.Type(), unsafe.Pointer(fi.UnsafeAddr())).Elem() |
| 145 | fi.SetString(name) |
| 146 | } |
| 147 | |
| 148 | // testSuite produces a named set of graphs as follows, where |
| 149 | // parentheses contain node types and F nodes stand for function |
| 150 | // nodes whose content is function named F: |
| 151 | // |
| 152 | // no-cycles: |
| 153 | // t0 (A) -> t1 (B) -> t2 (C) |
| 154 | // |
| 155 | // trivial-cycle: |
| 156 | // <-------- <-------- |
| 157 | // | | | | |
| 158 | // t0 (A) -> t1 (B) -> |
| 159 | // |
| 160 | // circle-cycle: |
| 161 | // t0 (A) -> t1 (A) -> t2 (B) |
| 162 | // | | |
| 163 | // <-------------------- |
| 164 | // |
| 165 | // fully-connected: |
| 166 | // t0 (A) <-> t1 (B) |
| 167 | // \ / |
| 168 | // t2(C) |
| 169 | // |
| 170 | // subsumed-scc: |
| 171 | // t0 (A) -> t1 (B) -> t2(B) -> t3 (A) |
| 172 | // | | | | |
| 173 | // | <--------- | |
| 174 | // <----------------------------- |
| 175 | // |
| 176 | // more-realistic: |
| 177 | // <-------- |
| 178 | // | | |
| 179 | // t0 (A) --> |
| 180 | // ----------> |
| 181 | // | | |
| 182 | // t1 (A) -> t2 (B) -> F1 -> F2 -> F3 -> F4 |
| 183 | // | | | | |
| 184 | // <------- <------------ |
| 185 | func testSuite() map[string]vtaGraph { |
| 186 | a := newNamedType("A") |
| 187 | b := newNamedType("B") |
| 188 | c := newNamedType("C") |
| 189 | sig := types.NewSignature(nil, types.NewTuple(), types.NewTuple(), false) |
| 190 | |
| 191 | f1 := &ssa.Function{Signature: sig} |
| 192 | setName(f1, "F1") |
| 193 | f2 := &ssa.Function{Signature: sig} |
| 194 | setName(f2, "F2") |
| 195 | f3 := &ssa.Function{Signature: sig} |
| 196 | setName(f3, "F3") |
| 197 | f4 := &ssa.Function{Signature: sig} |
| 198 | setName(f4, "F4") |
| 199 | |
| 200 | graphs := make(map[string]vtaGraph) |
| 201 | graphs["no-cycles"] = map[node]map[node]bool{ |
| 202 | newLocal("t0", a): {newLocal("t1", b): true}, |
| 203 | newLocal("t1", b): {newLocal("t2", c): true}, |
| 204 | } |
| 205 | |
| 206 | graphs["trivial-cycle"] = map[node]map[node]bool{ |
| 207 | newLocal("t0", a): {newLocal("t0", a): true}, |
| 208 | newLocal("t1", b): {newLocal("t1", b): true}, |
| 209 | } |
| 210 | |
| 211 | graphs["circle-cycle"] = map[node]map[node]bool{ |
| 212 | newLocal("t0", a): {newLocal("t1", a): true}, |
| 213 | newLocal("t1", a): {newLocal("t2", b): true}, |
| 214 | newLocal("t2", b): {newLocal("t0", a): true}, |
| 215 | } |
| 216 | |
| 217 | graphs["fully-connected"] = map[node]map[node]bool{ |
| 218 | newLocal("t0", a): {newLocal("t1", b): true, newLocal("t2", c): true}, |
| 219 | newLocal("t1", b): {newLocal("t0", a): true, newLocal("t2", c): true}, |
| 220 | newLocal("t2", c): {newLocal("t0", a): true, newLocal("t1", b): true}, |
| 221 | } |
| 222 | |
| 223 | graphs["subsumed-scc"] = map[node]map[node]bool{ |
| 224 | newLocal("t0", a): {newLocal("t1", b): true}, |
| 225 | newLocal("t1", b): {newLocal("t2", b): true}, |
| 226 | newLocal("t2", b): {newLocal("t1", b): true, newLocal("t3", a): true}, |
| 227 | newLocal("t3", a): {newLocal("t0", a): true}, |
| 228 | } |
| 229 | |
| 230 | graphs["more-realistic"] = map[node]map[node]bool{ |
| 231 | newLocal("t0", a): {newLocal("t0", a): true}, |
| 232 | newLocal("t1", a): {newLocal("t2", b): true}, |
| 233 | newLocal("t2", b): {newLocal("t1", a): true, function{f1}: true}, |
| 234 | function{f1}: {function{f2}: true, function{f3}: true}, |
| 235 | function{f2}: {function{f3}: true}, |
| 236 | function{f3}: {function{f1}: true, function{f4}: true}, |
| 237 | } |
| 238 | |
| 239 | return graphs |
| 240 | } |
| 241 | |
| 242 | func TestSCC(t *testing.T) { |
| 243 | suite := testSuite() |
| 244 | for _, test := range []struct { |
| 245 | name string |
| 246 | graph vtaGraph |
| 247 | want []string |
| 248 | }{ |
| 249 | // No cycles results in three separate SCCs: {t0} {t1} {t2} |
| 250 | {name: "no-cycles", graph: suite["no-cycles"], want: []string{"Local(t0)", "Local(t1)", "Local(t2)"}}, |
| 251 | // The two trivial self-loop cycles results in: {t0} {t1} |
| 252 | {name: "trivial-cycle", graph: suite["trivial-cycle"], want: []string{"Local(t0)", "Local(t1)"}}, |
| 253 | // The circle cycle produce a single SCC: {t0, t1, t2} |
| 254 | {name: "circle-cycle", graph: suite["circle-cycle"], want: []string{"Local(t0);Local(t1);Local(t2)"}}, |
| 255 | // Similar holds for fully connected SCC: {t0, t1, t2} |
| 256 | {name: "fully-connected", graph: suite["fully-connected"], want: []string{"Local(t0);Local(t1);Local(t2)"}}, |
| 257 | // Subsumed SCC also has a single SCC: {t0, t1, t2, t3} |
| 258 | {name: "subsumed-scc", graph: suite["subsumed-scc"], want: []string{"Local(t0);Local(t1);Local(t2);Local(t3)"}}, |
| 259 | // The more realistic example has the following SCCs: {t0} {t1, t2} {F1, F2, F3} {F4} |
| 260 | {name: "more-realistic", graph: suite["more-realistic"], want: []string{"Local(t0)", "Local(t1);Local(t2)", "Function(F1);Function(F2);Function(F3)", "Function(F4)"}}, |
| 261 | } { |
| 262 | sccs, _ := scc(test.graph) |
| 263 | if got := sccString(sccs); !sccEqual(test.want, got) { |
| 264 | t.Errorf("want %v for graph %v; got %v", test.want, test.name, got) |
| 265 | } |
| 266 | if !isRevTopSorted(test.graph, sccs) { |
| 267 | t.Errorf("%v not topologically sorted", test.name) |
| 268 | } |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | func TestPropagation(t *testing.T) { |
| 273 | suite := testSuite() |
| 274 | var canon typeutil.Map |
| 275 | for _, test := range []struct { |
| 276 | name string |
| 277 | graph vtaGraph |
| 278 | want map[string]string |
| 279 | }{ |
| 280 | // No cycles graph pushes type information forward. |
| 281 | {name: "no-cycles", graph: suite["no-cycles"], |
| 282 | want: map[string]string{ |
| 283 | "Local(t0)": "A", |
| 284 | "Local(t1)": "A;B", |
| 285 | "Local(t2)": "A;B;C", |
| 286 | }, |
| 287 | }, |
| 288 | // No interesting type flow in trivial cycle graph. |
| 289 | {name: "trivial-cycle", graph: suite["trivial-cycle"], |
| 290 | want: map[string]string{ |
| 291 | "Local(t0)": "A", |
| 292 | "Local(t1)": "B", |
| 293 | }, |
| 294 | }, |
| 295 | // Circle cycle makes type A and B get propagated everywhere. |
| 296 | {name: "circle-cycle", graph: suite["circle-cycle"], |
| 297 | want: map[string]string{ |
| 298 | "Local(t0)": "A;B", |
| 299 | "Local(t1)": "A;B", |
| 300 | "Local(t2)": "A;B", |
| 301 | }, |
| 302 | }, |
| 303 | // Similarly for fully connected graph. |
| 304 | {name: "fully-connected", graph: suite["fully-connected"], |
| 305 | want: map[string]string{ |
| 306 | "Local(t0)": "A;B;C", |
| 307 | "Local(t1)": "A;B;C", |
| 308 | "Local(t2)": "A;B;C", |
| 309 | }, |
| 310 | }, |
| 311 | // The outer loop of subsumed-scc pushes A an B through the graph. |
| 312 | {name: "subsumed-scc", graph: suite["subsumed-scc"], |
| 313 | want: map[string]string{ |
| 314 | "Local(t0)": "A;B", |
| 315 | "Local(t1)": "A;B", |
| 316 | "Local(t2)": "A;B", |
| 317 | "Local(t3)": "A;B", |
| 318 | }, |
| 319 | }, |
| 320 | // More realistic graph has a more fine grained flow. |
| 321 | {name: "more-realistic", graph: suite["more-realistic"], |
| 322 | want: map[string]string{ |
| 323 | "Local(t0)": "A", |
| 324 | "Local(t1)": "A;B", |
| 325 | "Local(t2)": "A;B", |
| 326 | "Function(F1)": "A;B;F1;F2;F3", |
| 327 | "Function(F2)": "A;B;F1;F2;F3", |
| 328 | "Function(F3)": "A;B;F1;F2;F3", |
| 329 | "Function(F4)": "A;B;F1;F2;F3;F4", |
| 330 | }, |
| 331 | }, |
| 332 | } { |
| 333 | if got := nodeToTypeString(propagate(test.graph, &canon)); !reflect.DeepEqual(got, test.want) { |
| 334 | t.Errorf("want %v for graph %v; got %v", test.want, test.name, got) |
| 335 | } |
| 336 | } |
| 337 | } |
| 338 |
Members