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