LEFT | RIGHT |
| 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 } |
LEFT | RIGHT |