Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1153)

Delta Between Two Patch Sets: src/pkg/exp/ssa/func.go

Issue 7229074: code review 7229074: exp/ssa: build fully pruned SSA form. (Closed)
Left Patch Set: diff -r dd18b993ba95 https://go.googlecode.com/hg/ Created 11 years, 1 month ago
Right Patch Set: diff -r 734059df2768 https://code.google.com/p/go/ Created 11 years, 1 month ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « src/pkg/exp/ssa/dom.go ('k') | src/pkg/exp/ssa/lift.go » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
1 package ssa
2
3 // This file implements the Function and BasicBlock types.
4
5 import (
6 "fmt"
7 "go/ast"
8 "go/types"
9 "io"
10 "os"
11 )
12
13 // addEdge adds a control-flow graph edge from from to to.
14 func addEdge(from, to *BasicBlock) {
15 from.Succs = append(from.Succs, to)
1 to.Preds = append(to.Preds, from) 16 to.Preds = append(to.Preds, from)
17 }
18
19 // String returns a human-readable label of this block.
20 // It is not guaranteed unique within the function.
21 //
22 func (b *BasicBlock) String() string {
23 return fmt.Sprintf("%d.%s", b.Index, b.Comment)
2 } 24 }
3 25
4 // emit appends an instruction to the current basic block. 26 // emit appends an instruction to the current basic block.
5 // If the instruction defines a Value, it is returned. 27 // If the instruction defines a Value, it is returned.
6 // 28 //
29 func (b *BasicBlock) emit(i Instruction) Value {
30 i.SetBlock(b)
31 b.Instrs = append(b.Instrs, i)
32 v, _ := i.(Value)
33 return v
34 }
35
36 // predIndex returns the i such that b.Preds[i] == c or panics if
37 // there is none.
38 func (b *BasicBlock) predIndex(c *BasicBlock) int {
39 for i, pred := range b.Preds {
40 if pred == c {
41 return i
42 }
43 }
44 panic(fmt.Sprintf("no edge %s -> %s", c, b))
45 }
46
47 // hasPhi returns true if b.Instrs contains φ-nodes.
48 func (b *BasicBlock) hasPhi() bool {
49 _, ok := b.Instrs[0].(*Phi)
50 return ok
51 }
52
53 // phis returns the prefix of b.Instrs containing all the block's φ-nodes.
54 func (b *BasicBlock) phis() []Instruction {
55 for i, instr := range b.Instrs {
56 if _, ok := instr.(*Phi); !ok {
57 return b.Instrs[:i]
58 }
59 }
60 return nil // unreachable in well-formed blocks
61 }
62
63 // replacePred replaces all occurrences of p in b's predecessor list with q.
64 // Ordinarily there should be at most one.
65 //
66 func (b *BasicBlock) replacePred(p, q *BasicBlock) {
67 for i, pred := range b.Preds {
68 if pred == p {
69 b.Preds[i] = q
70 }
71 }
72 }
73
74 // replaceSucc replaces all occurrences of p in b's successor list with q.
75 // Ordinarily there should be at most one.
76 //
77 func (b *BasicBlock) replaceSucc(p, q *BasicBlock) {
78 for i, succ := range b.Succs {
79 if succ == p {
80 b.Succs[i] = q
81 }
82 }
83 }
84
85 // removePred removes all occurrences of p in b's
86 // predecessor list and φ-nodes.
87 // Ordinarily there should be at most one.
88 //
89 func (b *BasicBlock) removePred(p *BasicBlock) {
90 phis := b.phis()
91
92 // We must preserve edge order for φ-nodes.
93 j := 0
94 for i, pred := range b.Preds {
95 if pred != p {
96 b.Preds[j] = b.Preds[i]
97 // Strike out φ-edge too.
98 for _, instr := range phis {
99 phi := instr.(*Phi)
100 phi.Edges[j] = phi.Edges[i]
101 }
102 j++
103 }
104 }
105 // Nil out b.Preds[j:] and φ-edges[j:] to aid GC.
106 for i := j; i < len(b.Preds); i++ {
107 b.Preds[i] = nil
108 for _, instr := range phis {
109 instr.(*Phi).Edges[i] = nil
110 }
111 }
112 b.Preds = b.Preds[:j]
113 for _, instr := range phis {
114 phi := instr.(*Phi)
115 phi.Edges = phi.Edges[:j]
116 }
117 }
118
119 // Destinations associated with unlabelled for/switch/select stmts.
120 // We push/pop one of these as we enter/leave each construct and for
121 // each BranchStmt we scan for the innermost target of the right type.
122 //
123 type targets struct {
124 tail *targets // rest of stack
125 _break *BasicBlock
126 _continue *BasicBlock
127 _fallthrough *BasicBlock
128 }
129
130 // Destinations associated with a labelled block.
131 // We populate these as labels are encountered in forward gotos or
132 // labelled statements.
133 //
134 type lblock struct {
135 _goto *BasicBlock
136 _break *BasicBlock
137 _continue *BasicBlock
138 }
139
140 // funcSyntax holds the syntax tree for the function declaration and body.
141 type funcSyntax struct {
142 recvField *ast.FieldList
143 paramFields *ast.FieldList
144 resultFields *ast.FieldList
145 body *ast.BlockStmt
146 }
147
148 // labelledBlock returns the branch target associated with the
149 // specified label, creating it if needed.
150 //
151 func (f *Function) labelledBlock(label *ast.Ident) *lblock {
152 lb := f.lblocks[label.Obj]
153 if lb == nil {
154 lb = &lblock{_goto: f.newBasicBlock(label.Name)}
155 f.lblocks[label.Obj] = lb
156 }
157 return lb
158 }
159
160 // addParam adds a (non-escaping) parameter to f.Params of the
161 // specified name and type.
162 //
163 func (f *Function) addParam(name string, typ types.Type) *Parameter {
164 v := &Parameter{
165 Name_: name,
166 Type_: typ,
167 }
168 f.Params = append(f.Params, v)
169 return v
170 }
171
172 // addSpilledParam declares a parameter that is pre-spilled to the
173 // stack; the function body will load/store the spilled location.
174 // Subsequent lifting will eliminate spills where possible.
175 //
176 func (f *Function) addSpilledParam(obj types.Object) {
177 name := obj.GetName()
178 param := f.addParam(name, obj.GetType())
179 spill := &Alloc{
180 Name_: name + "~", // "~" means "spilled"
181 Type_: pointer(obj.GetType()),
182 }
183 f.objects[obj] = spill
184 f.Locals = append(f.Locals, spill)
185 f.emit(spill)
186 f.emit(&Store{Addr: spill, Val: param})
187 }
188
189 // start initializes the function prior to generating SSA code for its body.
190 // Precondition: f.Type() already set.
191 //
192 // If f.syntax != nil, f is a Go source function and idents must be a
193 // mapping from syntactic identifiers to their canonical type objects;
194 // Otherwise, idents is ignored and the usual set-up for Go source
195 // functions is skipped.
196 //
197 func (f *Function) start(idents map[*ast.Ident]types.Object) {
198 if f.Prog.mode&LogSource != 0 {
199 fmt.Fprintf(os.Stderr, "build function %s @ %s\n", f.FullName(), f.Prog.Files.Position(f.Pos))
200 }
201 f.currentBlock = f.newBasicBlock("entry")
202 f.objects = make(map[types.Object]Value) // needed for some synthetics, e.g. init
203 if f.syntax == nil {
204 return // synthetic function; no syntax tree
205 }
206 f.lblocks = make(map[*ast.Object]*lblock)
207
208 // Receiver (at most one inner iteration).
209 if f.syntax.recvField != nil {
210 for _, field := range f.syntax.recvField.List {
211 for _, n := range field.Names {
212 f.addSpilledParam(idents[n])
213 }
214 if field.Names == nil {
215 f.addParam(f.Signature.Recv.Name, f.Signature.Re cv.Type)
216 }
217 }
218 }
219
220 // Parameters.
221 if f.syntax.paramFields != nil {
222 for _, field := range f.syntax.paramFields.List {
223 for _, n := range field.Names {
224 f.addSpilledParam(idents[n])
225 }
226 }
227 }
228
229 // Results.
230 if f.syntax.resultFields != nil {
231 for _, field := range f.syntax.resultFields.List {
232 // Implicit "var" decl of locals for named results.
233 for _, n := range field.Names {
234 f.results = append(f.results, f.addNamedLocal(id ents[n]))
235 }
236 }
237 }
238 }
239
240 // numberRegisters assigns numbers to all SSA registers
241 // (value-defining Instructions) in f, to aid debugging.
242 // (Non-Instruction Values are named at construction.)
243 // NB: named Allocs retain their existing name.
244 // TODO(adonovan): when we have source position info,
245 // preserve names only for source locals.
246 //
247 func numberRegisters(f *Function) {
248 a, v := 0, 0
249 for _, b := range f.Blocks {
250 for _, instr := range b.Instrs {
251 switch instr := instr.(type) {
252 case *Alloc:
253 // Allocs may be named at birth.
254 if instr.Name_ == "" {
255 instr.Name_ = fmt.Sprintf("a%d", a)
256 a++
257 }
258 case Value:
259 instr.(interface {
260 setNum(int)
261 }).setNum(v)
262 v++
263 }
264 }
265 }
266 }
267
268 // finish() finalizes the function after SSA code generation of its body.
269 func (f *Function) finish() {
270 f.objects = nil
271 f.results = nil
272 f.currentBlock = nil
273 f.lblocks = nil
274 f.syntax = nil
275
276 // Remove any f.Locals that are now heap-allocated.
277 j := 0
278 for _, l := range f.Locals {
279 if !l.Heap {
280 f.Locals[j] = l
281 j++
282 }
283 }
284 // Nil out f.Locals[j:] to aid GC.
285 for i := j; i < len(f.Locals); i++ {
286 f.Locals[i] = nil
287 }
288 f.Locals = f.Locals[:j]
289
290 optimizeBlocks(f)
291
292 // Build immediate-use (referrers) graph.
293 var rands []*Value
294 for _, b := range f.Blocks {
295 for _, instr := range b.Instrs {
296 rands = instr.Operands(rands[:0]) // recycle storage
297 for _, rand := range rands {
298 if r := *rand; r != nil {
299 if ref := r.Referrers(); ref != nil {
300 *ref = append(*ref, instr)
301 }
302 }
303 }
304 }
305 }
306
307 if f.Prog.mode&NaiveForm == 0 {
308 // For debugging pre-state of lifting pass:
309 // numberRegisters(f)
310 // f.DumpTo(os.Stderr)
311
312 lift(f)
313 }
314
315 numberRegisters(f)
316
317 if f.Prog.mode&LogFunctions != 0 {
318 f.DumpTo(os.Stderr)
319 }
320
321 if f.Prog.mode&SanityCheckFunctions != 0 {
322 MustSanityCheck(f, nil)
323 }
324 if f.Prog.mode&LogSource != 0 {
325 fmt.Fprintf(os.Stderr, "build function %s done\n", f.FullName())
326 }
327 }
328
329 // removeNilBlocks eliminates nils from f.Blocks and updates each
330 // BasicBlock.Index. Use this after any pass that may delete blocks.
331 //
332 func (f *Function) removeNilBlocks() {
333 j := 0
334 for _, b := range f.Blocks {
335 if b != nil {
336 b.Index = j
337 f.Blocks[j] = b
338 j++
339 }
340 }
341 // Nil out f.Blocks[j:] to aid GC.
342 for i := j; i < len(f.Blocks); i++ {
343 f.Blocks[i] = nil
344 }
345 f.Blocks = f.Blocks[:j]
346 }
347
348 // addNamedLocal creates a local variable, adds it to function f and
349 // returns it. Its name and type are taken from obj. Subsequent
350 // calls to f.lookup(obj) will return the same local.
351 //
352 // Precondition: f.syntax != nil (i.e. a Go source function).
353 //
354 func (f *Function) addNamedLocal(obj types.Object) *Alloc {
355 l := f.addLocal(obj.GetType())
356 l.Name_ = obj.GetName()
357 f.objects[obj] = l
358 return l
359 }
360
361 // addLocal creates an anonymous local variable of type typ, adds it
362 // to function f and returns it.
363 //
364 func (f *Function) addLocal(typ types.Type) *Alloc {
365 v := &Alloc{Type_: pointer(typ)}
366 f.Locals = append(f.Locals, v)
367 f.emit(v)
368 return v
369 }
370
371 // lookup returns the address of the named variable identified by obj
372 // that is local to function f or one of its enclosing functions.
373 // If escaping, the reference comes from a potentially escaping pointer
374 // expression and the referent must be heap-allocated.
375 //
376 func (f *Function) lookup(obj types.Object, escaping bool) Value {
377 if v, ok := f.objects[obj]; ok {
378 if escaping {
379 // Walk up the chain of Captures.
380 x := v
381 for {
382 if c, ok := x.(*Capture); ok {
383 x = c.Outer
384 } else {
385 break
386 }
387 }
388 // By construction, all captures are ultimately Allocs i n the
389 // naive SSA form. Parameters are pre-spilled to the st ack.
390 x.(*Alloc).Heap = true
391 }
392 return v // function-local var (address)
393 }
394
395 // Definition must be in an enclosing function;
396 // plumb it through intervening closures.
397 if f.Enclosing == nil {
398 panic("no Value for type.Object " + obj.GetName())
399 }
400 v := &Capture{Outer: f.Enclosing.lookup(obj, true)} // escaping
401 f.objects[obj] = v
402 f.FreeVars = append(f.FreeVars, v)
403 return v
404 }
405
406 // emit emits the specified instruction to function f, updating the
407 // control-flow graph if required.
408 //
409 func (f *Function) emit(instr Instruction) Value {
410 return f.currentBlock.emit(instr)
411 }
412
413 // FullName returns the full name of this function, qualified by
414 // package name, receiver type, etc.
415 //
416 // The specific formatting rules are not guaranteed and may change.
417 //
418 // Examples:
419 // "math.IsNaN" // a package-level function
420 // "IsNaN" // intra-package reference to same
421 // "(*sync.WaitGroup).Add" // a declared method
422 // "(*exp/ssa.Ret).Block" // a bridge method
423 // "(ssa.Instruction).Block" // an interface method thunk
424 // "func@5.32" // an anonymous function
425 //
426 func (f *Function) FullName() string {
427 return f.fullName(nil)
428 }
429
430 // Like FullName, but if from==f.Pkg, suppress package qualification.
431 func (f *Function) fullName(from *Package) string {
432 // Anonymous?
433 if f.Enclosing != nil {
434 return f.Name_
435 }
436
437 recv := f.Signature.Recv
438
439 // Synthetic?
440 if f.Pkg == nil {
441 var recvType types.Type
442 if recv != nil {
443 recvType = recv.Type // bridge method
444 } else {
445 recvType = f.Params[0].Type() // interface method thunk
446 }
447 return fmt.Sprintf("(%s).%s", recvType, f.Name_)
448 }
449
450 // Declared method?
451 if recv != nil {
452 return fmt.Sprintf("(%s).%s", recv.Type, f.Name_)
453 }
454
455 // Package-level function.
456 // Prefix with package name for cross-package references only.
457 if from != f.Pkg {
458 return fmt.Sprintf("%s.%s", f.Pkg.ImportPath, f.Name_)
459 }
460 return f.Name_
461 }
462
463 // DumpTo prints to w a human readable "disassembly" of the SSA code of
464 // all basic blocks of function f.
465 //
466 func (f *Function) DumpTo(w io.Writer) {
467 fmt.Fprintf(w, "# Name: %s\n", f.FullName())
468 fmt.Fprintf(w, "# Declared at %s\n", f.Prog.Files.Position(f.Pos))
469
470 if f.Enclosing != nil {
471 fmt.Fprintf(w, "# Parent: %s\n", f.Enclosing.Name())
472 }
473
474 if f.FreeVars != nil {
475 io.WriteString(w, "# Free variables:\n")
476 for i, fv := range f.FreeVars {
477 fmt.Fprintf(w, "# % 3d:\t%s %s\n", i, fv.Name(), fv.Type ())
478 }
479 }
480
481 if len(f.Locals) > 0 {
482 io.WriteString(w, "# Locals:\n")
483 for i, l := range f.Locals {
484 fmt.Fprintf(w, "# % 3d:\t%s %s\n", i, l.Name(), indirect Type(l.Type()))
485 }
486 }
487
488 // Function Signature in declaration syntax; derived from types.Signatur e.String().
489 io.WriteString(w, "func ")
490 params := f.Params
491 if f.Signature.Recv != nil {
492 fmt.Fprintf(w, "(%s %s) ", params[0].Name(), params[0].Type())
493 params = params[1:]
494 }
495 io.WriteString(w, f.Name())
496 io.WriteString(w, "(")
497 for i, v := range params {
498 if i > 0 {
499 io.WriteString(w, ", ")
500 }
501 io.WriteString(w, v.Name())
502 io.WriteString(w, " ")
503 if f.Signature.IsVariadic && i == len(params)-1 {
504 io.WriteString(w, "...")
505 }
506 io.WriteString(w, v.Type().String())
507 }
508 io.WriteString(w, ")")
509 if res := f.Signature.Results; res != nil {
510 io.WriteString(w, " ")
511 var t types.Type
512 if len(res) == 1 && res[0].Name == "" {
513 t = res[0].Type
514 } else {
515 t = &types.Result{Values: res}
516 }
517 io.WriteString(w, t.String())
518 }
519 io.WriteString(w, ":\n")
520
521 if f.Blocks == nil {
522 io.WriteString(w, "\t(external)\n")
523 }
524
525 for _, b := range f.Blocks {
526 if b == nil {
527 // Corrupt CFG.
528 fmt.Fprintf(w, ".nil:\n")
529 continue
530 }
531 fmt.Fprintf(w, ".%s:\t\t\t\t\t\t\t P:%d S:%d\n", b, len(b. Preds), len(b.Succs))
532 if false { // CFG debugging
533 fmt.Fprintf(w, "\t# CFG: %s --> %s --> %s\n", blockNames (b.Preds), b, blockNames(b.Succs))
534 }
535 for _, instr := range b.Instrs {
536 io.WriteString(w, "\t")
537 switch v := instr.(type) {
538 case Value:
539 l := 80 // for old time's sake.
540 // Left-align the instruction.
541 if name := v.Name(); name != "" {
542 n, _ := fmt.Fprintf(w, "%s = ", name)
543 l -= n
544 }
545 n, _ := io.WriteString(w, instr.String())
546 l -= n
547 // Right-align the type.
548 if t := v.Type(); t != nil {
549 fmt.Fprintf(w, "%*s", l-9, t)
550 }
551 case nil:
552 // Be robust against bad transforms.
553 io.WriteString(w, "<deleted>")
554 default:
555 io.WriteString(w, instr.String())
556 }
557 io.WriteString(w, "\n")
558 }
559 }
560 fmt.Fprintf(w, "\n")
561 }
562
563 // newBasicBlock adds to f a new basic block and returns it. It does
564 // not automatically become the current block for subsequent calls to emit.
565 // comment is an optional string for more readable debugging output.
566 //
567 func (f *Function) newBasicBlock(comment string) *BasicBlock {
568 b := &BasicBlock{
569 Index: len(f.Blocks),
570 Comment: comment,
571 Func: f,
572 }
573 b.Succs = b.succs2[:0]
574 f.Blocks = append(f.Blocks, b)
575 return b
576 }
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b