1
2
3
4
5 package ssa
6
7
8
9 import (
10 "bytes"
11 "fmt"
12 "go/ast"
13 "go/types"
14 "io"
15 "os"
16 "strings"
17
18 "golang.org/x/tools/internal/typeparams"
19 )
20
21
22
23 func (f *Function) objectOf(id *ast.Ident) types.Object {
24 if o := f.info.ObjectOf(id); o != nil {
25 return o
26 }
27 panic(fmt.Sprintf("no types.Object for ast.Ident %s @ %s",
28 id.Name, f.Prog.Fset.Position(id.Pos())))
29 }
30
31
32
33 func (f *Function) typeOf(e ast.Expr) types.Type {
34 if T := f.info.TypeOf(e); T != nil {
35 return f.typ(T)
36 }
37 panic(fmt.Sprintf("no type for %T @ %s", e, f.Prog.Fset.Position(e.Pos())))
38 }
39
40
41
42 func (f *Function) typ(T types.Type) types.Type {
43 return f.subst.typ(T)
44 }
45
46
47
48 func (f *Function) instanceType(id *ast.Ident) types.Type {
49 if t, ok := f.info.Instances[id]; ok {
50 return t.Type
51 }
52 return f.typeOf(id)
53 }
54
55
56
57 func (f *Function) selection(selector *ast.SelectorExpr) *selection {
58 sel := f.info.Selections[selector]
59 if sel == nil {
60 return nil
61 }
62
63 switch sel.Kind() {
64 case types.MethodExpr, types.MethodVal:
65 if recv := f.typ(sel.Recv()); recv != sel.Recv() {
66
67 pkg := f.declaredPackage().Pkg
68 obj, index, indirect := types.LookupFieldOrMethod(recv, true, pkg, sel.Obj().Name())
69
70
71 sig := obj.Type().(*types.Signature)
72 sig = changeRecv(sig, newVar(sig.Recv().Name(), recv))
73 if sel.Kind() == types.MethodExpr {
74 sig = recvAsFirstArg(sig)
75 }
76 return &selection{
77 kind: sel.Kind(),
78 recv: recv,
79 typ: sig,
80 obj: obj,
81 index: index,
82 indirect: indirect,
83 }
84 }
85 }
86 return toSelection(sel)
87 }
88
89
90
91
92 type targets struct {
93 tail *targets
94 _break *BasicBlock
95 _continue *BasicBlock
96 _fallthrough *BasicBlock
97 }
98
99
100
101
102 type lblock struct {
103 _goto *BasicBlock
104 _break *BasicBlock
105 _continue *BasicBlock
106 }
107
108
109
110
111 func (f *Function) labelledBlock(label *ast.Ident) *lblock {
112 obj := f.objectOf(label).(*types.Label)
113 lb := f.lblocks[obj]
114 if lb == nil {
115 lb = &lblock{_goto: f.newBasicBlock(label.Name)}
116 if f.lblocks == nil {
117 f.lblocks = make(map[*types.Label]*lblock)
118 }
119 f.lblocks[obj] = lb
120 }
121 return lb
122 }
123
124
125 func (f *Function) addParamVar(v *types.Var) *Parameter {
126 name := v.Name()
127 if name == "" {
128 name = fmt.Sprintf("arg%d", len(f.Params))
129 }
130 param := &Parameter{
131 name: name,
132 object: v,
133 typ: f.typ(v.Type()),
134 parent: f,
135 }
136 f.Params = append(f.Params, param)
137 return param
138 }
139
140
141
142
143 func (f *Function) addSpilledParam(obj *types.Var) {
144 param := f.addParamVar(obj)
145 spill := emitLocalVar(f, obj)
146 f.emit(&Store{Addr: spill, Val: param})
147 }
148
149
150
151 func (f *Function) startBody() {
152 f.currentBlock = f.newBasicBlock("entry")
153 f.vars = make(map[*types.Var]Value)
154 }
155
156
157
158
159
160
161
162
163
164 func (f *Function) createSyntacticParams(recv *ast.FieldList, functype *ast.FuncType) {
165
166 if recv != nil {
167 for _, field := range recv.List {
168 for _, n := range field.Names {
169 f.addSpilledParam(identVar(f, n))
170 }
171
172 if field.Names == nil {
173 f.addParamVar(f.Signature.Recv())
174 }
175 }
176 }
177
178
179 if functype.Params != nil {
180 n := len(f.Params)
181 for _, field := range functype.Params.List {
182 for _, n := range field.Names {
183 f.addSpilledParam(identVar(f, n))
184 }
185
186 if field.Names == nil {
187 f.addParamVar(f.Signature.Params().At(len(f.Params) - n))
188 }
189 }
190 }
191
192
193 if functype.Results != nil {
194 for _, field := range functype.Results.List {
195
196 for _, n := range field.Names {
197 namedResult := emitLocalVar(f, identVar(f, n))
198 f.namedResults = append(f.namedResults, namedResult)
199 }
200 }
201 }
202 }
203
204 type setNumable interface {
205 setNum(int)
206 }
207
208
209
210
211 func numberRegisters(f *Function) {
212 v := 0
213 for _, b := range f.Blocks {
214 for _, instr := range b.Instrs {
215 switch instr.(type) {
216 case Value:
217 instr.(setNumable).setNum(v)
218 v++
219 }
220 }
221 }
222 }
223
224
225
226
227 func buildReferrers(f *Function) {
228 var rands []*Value
229 for _, b := range f.Blocks {
230 for _, instr := range b.Instrs {
231 rands = instr.Operands(rands[:0])
232 for _, rand := range rands {
233 if r := *rand; r != nil {
234 if ref := r.Referrers(); ref != nil {
235 *ref = append(*ref, instr)
236 }
237 }
238 }
239 }
240 }
241 }
242
243
244
245
246 func (f *Function) finishBody() {
247 f.vars = nil
248 f.currentBlock = nil
249 f.lblocks = nil
250
251
252 j := 0
253 for _, l := range f.Locals {
254 if !l.Heap {
255 f.Locals[j] = l
256 j++
257 }
258 }
259
260 for i := j; i < len(f.Locals); i++ {
261 f.Locals[i] = nil
262 }
263 f.Locals = f.Locals[:j]
264
265 optimizeBlocks(f)
266
267 buildReferrers(f)
268
269 buildDomTree(f)
270
271 if f.Prog.mode&NaiveForm == 0 {
272
273
274
275 lift(f)
276 }
277
278
279 f.namedResults = nil
280 f.subst = nil
281
282 numberRegisters(f)
283 }
284
285
286
287 func (f *Function) done() {
288 assert(f.parent == nil, "done called on an anonymous function")
289
290 var visit func(*Function)
291 visit = func(f *Function) {
292 for _, anon := range f.AnonFuncs {
293 visit(anon)
294 }
295
296 f.build = nil
297
298 if f.Prog.mode&PrintFunctions != 0 {
299 printMu.Lock()
300 f.WriteTo(os.Stdout)
301 printMu.Unlock()
302 }
303
304 if f.Prog.mode&SanityCheckFunctions != 0 {
305 mustSanityCheck(f, nil)
306 }
307 }
308 visit(f)
309 }
310
311
312
313 func (f *Function) removeNilBlocks() {
314 j := 0
315 for _, b := range f.Blocks {
316 if b != nil {
317 b.Index = j
318 f.Blocks[j] = b
319 j++
320 }
321 }
322
323 for i := j; i < len(f.Blocks); i++ {
324 f.Blocks[i] = nil
325 }
326 f.Blocks = f.Blocks[:j]
327 }
328
329
330
331
332
333 func (pkg *Package) SetDebugMode(debug bool) {
334 pkg.debug = debug
335 }
336
337
338 func (f *Function) debugInfo() bool {
339
340 p := f.declaredPackage()
341 return p != nil && p.debug
342 }
343
344
345
346
347
348
349
350 func (f *Function) lookup(obj *types.Var, escaping bool) Value {
351 if v, ok := f.vars[obj]; ok {
352 if escaping {
353 switch v := v.(type) {
354 case *Alloc:
355 v.Heap = true
356 case *Phi:
357 for _, edge := range v.Edges {
358 if alloc, ok := edge.(*Alloc); ok {
359 alloc.Heap = true
360 }
361 }
362 }
363 }
364 return v
365 }
366
367
368
369 if f.parent == nil {
370 panic("no ssa.Value for " + obj.String())
371 }
372 outer := f.parent.lookup(obj, true)
373 v := &FreeVar{
374 name: obj.Name(),
375 typ: outer.Type(),
376 pos: outer.Pos(),
377 outer: outer,
378 parent: f,
379 }
380 f.vars[obj] = v
381 f.FreeVars = append(f.FreeVars, v)
382 return v
383 }
384
385
386 func (f *Function) emit(instr Instruction) Value {
387 return f.currentBlock.emit(instr)
388 }
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413 func (f *Function) RelString(from *types.Package) string {
414
415 if f.parent != nil {
416
417
418 parent := f.parent.RelString(from)
419 for i, anon := range f.parent.AnonFuncs {
420 if anon == f {
421 return fmt.Sprintf("%s$%d", parent, 1+i)
422 }
423 }
424
425 return f.name
426 }
427
428
429 if recv := f.Signature.Recv(); recv != nil {
430 return f.relMethod(from, recv.Type())
431 }
432
433
434 if f.method != nil {
435 return f.relMethod(from, f.method.recv)
436 }
437
438
439 if len(f.FreeVars) == 1 && strings.HasSuffix(f.name, "$bound") {
440 return f.relMethod(from, f.FreeVars[0].Type())
441 }
442
443
444
445 if p := f.relPkg(); p != nil && p != from {
446 return fmt.Sprintf("%s.%s", p.Path(), f.name)
447 }
448
449
450 return f.name
451 }
452
453 func (f *Function) relMethod(from *types.Package, recv types.Type) string {
454 return fmt.Sprintf("(%s).%s", relType(recv, from), f.name)
455 }
456
457
458 func writeSignature(buf *bytes.Buffer, from *types.Package, name string, sig *types.Signature) {
459 buf.WriteString("func ")
460 if recv := sig.Recv(); recv != nil {
461 buf.WriteString("(")
462 if name := recv.Name(); name != "" {
463 buf.WriteString(name)
464 buf.WriteString(" ")
465 }
466 types.WriteType(buf, recv.Type(), types.RelativeTo(from))
467 buf.WriteString(") ")
468 }
469 buf.WriteString(name)
470 types.WriteSignature(buf, sig, types.RelativeTo(from))
471 }
472
473
474
475 func (fn *Function) declaredPackage() *Package {
476 switch {
477 case fn.Pkg != nil:
478 return fn.Pkg
479 case fn.topLevelOrigin != nil:
480 return fn.topLevelOrigin.Pkg
481 case fn.parent != nil:
482 return fn.parent.declaredPackage()
483 default:
484 return nil
485 }
486 }
487
488
489 func (fn *Function) relPkg() *types.Package {
490 if p := fn.declaredPackage(); p != nil {
491 return p.Pkg
492 }
493 return nil
494 }
495
496 var _ io.WriterTo = (*Function)(nil)
497
498 func (f *Function) WriteTo(w io.Writer) (int64, error) {
499 var buf bytes.Buffer
500 WriteFunction(&buf, f)
501 n, err := w.Write(buf.Bytes())
502 return int64(n), err
503 }
504
505
506 func WriteFunction(buf *bytes.Buffer, f *Function) {
507 fmt.Fprintf(buf, "# Name: %s\n", f.String())
508 if f.Pkg != nil {
509 fmt.Fprintf(buf, "# Package: %s\n", f.Pkg.Pkg.Path())
510 }
511 if syn := f.Synthetic; syn != "" {
512 fmt.Fprintln(buf, "# Synthetic:", syn)
513 }
514 if pos := f.Pos(); pos.IsValid() {
515 fmt.Fprintf(buf, "# Location: %s\n", f.Prog.Fset.Position(pos))
516 }
517
518 if f.parent != nil {
519 fmt.Fprintf(buf, "# Parent: %s\n", f.parent.Name())
520 }
521
522 if f.Recover != nil {
523 fmt.Fprintf(buf, "# Recover: %s\n", f.Recover)
524 }
525
526 from := f.relPkg()
527
528 if f.FreeVars != nil {
529 buf.WriteString("# Free variables:\n")
530 for i, fv := range f.FreeVars {
531 fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, fv.Name(), relType(fv.Type(), from))
532 }
533 }
534
535 if len(f.Locals) > 0 {
536 buf.WriteString("# Locals:\n")
537 for i, l := range f.Locals {
538 fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, l.Name(), relType(typeparams.MustDeref(l.Type()), from))
539 }
540 }
541 writeSignature(buf, from, f.Name(), f.Signature)
542 buf.WriteString(":\n")
543
544 if f.Blocks == nil {
545 buf.WriteString("\t(external)\n")
546 }
547
548
549
550 const punchcard = 80
551 const tabwidth = 8
552 for _, b := range f.Blocks {
553 if b == nil {
554
555 fmt.Fprintf(buf, ".nil:\n")
556 continue
557 }
558 n, _ := fmt.Fprintf(buf, "%d:", b.Index)
559 bmsg := fmt.Sprintf("%s P:%d S:%d", b.Comment, len(b.Preds), len(b.Succs))
560 fmt.Fprintf(buf, "%*s%s\n", punchcard-1-n-len(bmsg), "", bmsg)
561
562 if false {
563 fmt.Fprintf(buf, "\t# CFG: %s --> %s --> %s\n", b.Preds, b, b.Succs)
564 }
565 for _, instr := range b.Instrs {
566 buf.WriteString("\t")
567 switch v := instr.(type) {
568 case Value:
569 l := punchcard - tabwidth
570
571 if name := v.Name(); name != "" {
572 n, _ := fmt.Fprintf(buf, "%s = ", name)
573 l -= n
574 }
575 n, _ := buf.WriteString(instr.String())
576 l -= n
577
578 if t := v.Type(); t != nil {
579 buf.WriteByte(' ')
580 ts := relType(t, from)
581 l -= len(ts) + len(" ")
582 if l > 0 {
583 fmt.Fprintf(buf, "%*s", l, "")
584 }
585 buf.WriteString(ts)
586 }
587 case nil:
588
589 buf.WriteString("<deleted>")
590 default:
591 buf.WriteString(instr.String())
592 }
593
594 if f.Prog.mode&LogSource != 0 {
595 if pos := instr.Pos(); pos.IsValid() {
596 fmt.Fprintf(buf, " L%d", f.Prog.Fset.Position(pos).Line)
597 }
598 }
599 buf.WriteString("\n")
600 }
601 }
602 fmt.Fprintf(buf, "\n")
603 }
604
605
606
607
608 func (f *Function) newBasicBlock(comment string) *BasicBlock {
609 b := &BasicBlock{
610 Index: len(f.Blocks),
611 Comment: comment,
612 parent: f,
613 }
614 b.Succs = b.succs2[:0]
615 f.Blocks = append(f.Blocks, b)
616 return b
617 }
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633 func (prog *Program) NewFunction(name string, sig *types.Signature, provenance string) *Function {
634 return &Function{Prog: prog, name: name, Signature: sig, Synthetic: provenance}
635 }
636
637
638
639 func (f *Function) Syntax() ast.Node { return f.syntax }
640
641
642 func identVar(fn *Function, id *ast.Ident) *types.Var {
643 return fn.info.Defs[id].(*types.Var)
644 }
645
View as plain text