| 1 |
// Copyright 2013 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 ir |
| 6 |
|
| 7 |
// This file implements the Function and BasicBlock types. |
| 8 |
|
| 9 |
import ( |
| 10 |
"bytes" |
| 11 |
"fmt" |
| 12 |
"go/ast" |
| 13 |
"go/format" |
| 14 |
"go/token" |
| 15 |
"go/types" |
| 16 |
"io" |
| 17 |
"os" |
| 18 |
"sort" |
| 19 |
"strings" |
| 20 |
|
| 21 |
"honnef.co/go/tools/go/types/typeutil" |
| 22 |
) |
| 23 |
|
| 24 |
// addEdge adds a control-flow graph edge from from to to. |
| 25 |
func addEdge(from, to *BasicBlock) { |
| 26 |
from.Succs = append(from.Succs, to) |
| 27 |
to.Preds = append(to.Preds, from) |
| 28 |
} |
| 29 |
|
| 30 |
// Control returns the last instruction in the block. |
| 31 |
func (b *BasicBlock) Control() Instruction { |
| 32 |
if len(b.Instrs) == 0 { |
| 33 |
return nil |
| 34 |
} |
| 35 |
return b.Instrs[len(b.Instrs)-1] |
| 36 |
} |
| 37 |
|
| 38 |
// SigmaFor returns the sigma node for v coming from pred. |
| 39 |
func (b *BasicBlock) SigmaFor(v Value, pred *BasicBlock) *Sigma { |
| 40 |
for _, instr := range b.Instrs { |
| 41 |
sigma, ok := instr.(*Sigma) |
| 42 |
if !ok { |
| 43 |
// no more sigmas |
| 44 |
return nil |
| 45 |
} |
| 46 |
if sigma.From == pred && sigma.X == v { |
| 47 |
return sigma |
| 48 |
} |
| 49 |
} |
| 50 |
return nil |
| 51 |
} |
| 52 |
|
| 53 |
// Parent returns the function that contains block b. |
| 54 |
func (b *BasicBlock) Parent() *Function { return b.parent } |
| 55 |
|
| 56 |
// String returns a human-readable label of this block. |
| 57 |
// It is not guaranteed unique within the function. |
| 58 |
func (b *BasicBlock) String() string { |
| 59 |
return fmt.Sprintf("%d", b.Index) |
| 60 |
} |
| 61 |
|
| 62 |
// emit appends an instruction to the current basic block. |
| 63 |
// If the instruction defines a Value, it is returned. |
| 64 |
func (b *BasicBlock) emit(i Instruction, source ast.Node) Value { |
| 65 |
i.setSource(source) |
| 66 |
i.setBlock(b) |
| 67 |
b.Instrs = append(b.Instrs, i) |
| 68 |
v, _ := i.(Value) |
| 69 |
return v |
| 70 |
} |
| 71 |
|
| 72 |
// predIndex returns the i such that b.Preds[i] == c or panics if |
| 73 |
// there is none. |
| 74 |
func (b *BasicBlock) predIndex(c *BasicBlock) int { |
| 75 |
for i, pred := range b.Preds { |
| 76 |
if pred == c { |
| 77 |
return i |
| 78 |
} |
| 79 |
} |
| 80 |
panic(fmt.Sprintf("no edge %s -> %s", c, b)) |
| 81 |
} |
| 82 |
|
| 83 |
// succIndex returns the i such that b.Succs[i] == c or -1 if there is none. |
| 84 |
func (b *BasicBlock) succIndex(c *BasicBlock) int { |
| 85 |
for i, succ := range b.Succs { |
| 86 |
if succ == c { |
| 87 |
return i |
| 88 |
} |
| 89 |
} |
| 90 |
return -1 |
| 91 |
} |
| 92 |
|
| 93 |
// hasPhi returns true if b.Instrs contains φ-nodes. |
| 94 |
func (b *BasicBlock) hasPhi() bool { |
| 95 |
_, ok := b.Instrs[0].(*Phi) |
| 96 |
return ok |
| 97 |
} |
| 98 |
|
| 99 |
func (b *BasicBlock) Phis() []Instruction { |
| 100 |
return b.phis() |
| 101 |
} |
| 102 |
|
| 103 |
// phis returns the prefix of b.Instrs containing all the block's φ-nodes. |
| 104 |
func (b *BasicBlock) phis() []Instruction { |
| 105 |
for i, instr := range b.Instrs { |
| 106 |
if _, ok := instr.(*Phi); !ok { |
| 107 |
return b.Instrs[:i] |
| 108 |
} |
| 109 |
} |
| 110 |
return nil // unreachable in well-formed blocks |
| 111 |
} |
| 112 |
|
| 113 |
// replacePred replaces all occurrences of p in b's predecessor list with q. |
| 114 |
// Ordinarily there should be at most one. |
| 115 |
func (b *BasicBlock) replacePred(p, q *BasicBlock) { |
| 116 |
for i, pred := range b.Preds { |
| 117 |
if pred == p { |
| 118 |
b.Preds[i] = q |
| 119 |
} |
| 120 |
} |
| 121 |
} |
| 122 |
|
| 123 |
// replaceSucc replaces all occurrences of p in b's successor list with q. |
| 124 |
// Ordinarily there should be at most one. |
| 125 |
func (b *BasicBlock) replaceSucc(p, q *BasicBlock) { |
| 126 |
for i, succ := range b.Succs { |
| 127 |
if succ == p { |
| 128 |
b.Succs[i] = q |
| 129 |
} |
| 130 |
} |
| 131 |
} |
| 132 |
|
| 133 |
// removePred removes all occurrences of p in b's |
| 134 |
// predecessor list and φ-nodes. |
| 135 |
// Ordinarily there should be at most one. |
| 136 |
func (b *BasicBlock) removePred(p *BasicBlock) { |
| 137 |
phis := b.phis() |
| 138 |
|
| 139 |
// We must preserve edge order for φ-nodes. |
| 140 |
j := 0 |
| 141 |
for i, pred := range b.Preds { |
| 142 |
if pred != p { |
| 143 |
b.Preds[j] = b.Preds[i] |
| 144 |
// Strike out φ-edge too. |
| 145 |
for _, instr := range phis { |
| 146 |
phi := instr.(*Phi) |
| 147 |
phi.Edges[j] = phi.Edges[i] |
| 148 |
} |
| 149 |
j++ |
| 150 |
} |
| 151 |
} |
| 152 |
// Nil out b.Preds[j:] and φ-edges[j:] to aid GC. |
| 153 |
for i := j; i < len(b.Preds); i++ { |
| 154 |
b.Preds[i] = nil |
| 155 |
for _, instr := range phis { |
| 156 |
instr.(*Phi).Edges[i] = nil |
| 157 |
} |
| 158 |
} |
| 159 |
b.Preds = b.Preds[:j] |
| 160 |
for _, instr := range phis { |
| 161 |
phi := instr.(*Phi) |
| 162 |
phi.Edges = phi.Edges[:j] |
| 163 |
} |
| 164 |
} |
| 165 |
|
| 166 |
// Destinations associated with unlabelled for/switch/select stmts. |
| 167 |
// We push/pop one of these as we enter/leave each construct and for |
| 168 |
// each BranchStmt we scan for the innermost target of the right type. |
| 169 |
type targets struct { |
| 170 |
tail *targets // rest of stack |
| 171 |
_break *BasicBlock |
| 172 |
_continue *BasicBlock |
| 173 |
_fallthrough *BasicBlock |
| 174 |
} |
| 175 |
|
| 176 |
// Destinations associated with a labelled block. |
| 177 |
// We populate these as labels are encountered in forward gotos or |
| 178 |
// labelled statements. |
| 179 |
// Forward gotos are resolved once it is known which statement they |
| 180 |
// are associated with inside the Function. |
| 181 |
type lblock struct { |
| 182 |
label *types.Label // Label targeted by the blocks. |
| 183 |
resolved bool // _goto block encountered (back jump or resolved fwd jump) |
| 184 |
_goto *BasicBlock |
| 185 |
_break *BasicBlock |
| 186 |
_continue *BasicBlock |
| 187 |
} |
| 188 |
|
| 189 |
// label returns the symbol denoted by a label identifier. |
| 190 |
// |
| 191 |
// label should be a non-blank identifier (label.Name != "_"). |
| 192 |
func (f *Function) label(label *ast.Ident) *types.Label { |
| 193 |
return f.Pkg.objectOf(label).(*types.Label) |
| 194 |
} |
| 195 |
|
| 196 |
// lblockOf returns the branch target associated with the |
| 197 |
// specified label, creating it if needed. |
| 198 |
func (f *Function) lblockOf(label *types.Label) *lblock { |
| 199 |
lb := f.lblocks[label] |
| 200 |
if lb == nil { |
| 201 |
lb = &lblock{ |
| 202 |
label: label, |
| 203 |
_goto: f.newBasicBlock(label.Name()), |
| 204 |
} |
| 205 |
if f.lblocks == nil { |
| 206 |
f.lblocks = make(map[*types.Label]*lblock) |
| 207 |
} |
| 208 |
f.lblocks[label] = lb |
| 209 |
} |
| 210 |
return lb |
| 211 |
} |
| 212 |
|
| 213 |
// labelledBlock searches f for the block of the specified label. |
| 214 |
// |
| 215 |
// If f is a yield function, it additionally searches ancestor Functions |
| 216 |
// corresponding to enclosing range-over-func statements within the |
| 217 |
// same source function, so the returned block may belong to a different Function. |
| 218 |
func labelledBlock(f *Function, label *types.Label, tok token.Token) *BasicBlock { |
| 219 |
if lb := f.lblocks[label]; lb != nil { |
| 220 |
var block *BasicBlock |
| 221 |
switch tok { |
| 222 |
case token.BREAK: |
| 223 |
block = lb._break |
| 224 |
case token.CONTINUE: |
| 225 |
block = lb._continue |
| 226 |
case token.GOTO: |
| 227 |
block = lb._goto |
| 228 |
} |
| 229 |
if block != nil { |
| 230 |
return block |
| 231 |
} |
| 232 |
} |
| 233 |
// Search ancestors if this is a yield function. |
| 234 |
if f.jump != nil { |
| 235 |
return labelledBlock(f.parent, label, tok) |
| 236 |
} |
| 237 |
return nil |
| 238 |
} |
| 239 |
|
| 240 |
// targetedBlock looks for the nearest block in f.targets |
| 241 |
// (and f's ancestors) that matches tok's type, and returns |
| 242 |
// the block and function it was found in. |
| 243 |
func targetedBlock(f *Function, tok token.Token) *BasicBlock { |
| 244 |
if f == nil { |
| 245 |
return nil |
| 246 |
} |
| 247 |
for t := f.targets; t != nil; t = t.tail { |
| 248 |
var block *BasicBlock |
| 249 |
switch tok { |
| 250 |
case token.BREAK: |
| 251 |
block = t._break |
| 252 |
case token.CONTINUE: |
| 253 |
block = t._continue |
| 254 |
case token.FALLTHROUGH: |
| 255 |
block = t._fallthrough |
| 256 |
} |
| 257 |
if block != nil { |
| 258 |
return block |
| 259 |
} |
| 260 |
} |
| 261 |
// Search f's ancestors (in case f is a yield function). |
| 262 |
return targetedBlock(f.parent, tok) |
| 263 |
} |
| 264 |
|
| 265 |
// addResultVar adds a result for a variable v to f.results and v to f.returnVars. |
| 266 |
func (f *Function) addResultVar(v *types.Var, source ast.Node) { |
| 267 |
name := v.Name() |
| 268 |
if name == "" { |
| 269 |
name = fmt.Sprintf("res.%d", len(f.results)) |
| 270 |
} |
| 271 |
result := emitLocalVar(f, v, source) |
| 272 |
result.comment = name |
| 273 |
f.results = append(f.results, result) |
| 274 |
f.returnVars = append(f.returnVars, v) |
| 275 |
} |
| 276 |
|
| 277 |
func (f *Function) addParamVar(v *types.Var, source ast.Node) *Parameter { |
| 278 |
name := v.Name() |
| 279 |
if name == "" { |
| 280 |
name = fmt.Sprintf("arg%d", len(f.Params)) |
| 281 |
} |
| 282 |
var b *BasicBlock |
| 283 |
if len(f.Blocks) > 0 { |
| 284 |
b = f.Blocks[0] |
| 285 |
} |
| 286 |
param := &Parameter{name: name} |
| 287 |
param.setBlock(b) |
| 288 |
param.setType(v.Type()) |
| 289 |
param.setSource(source) |
| 290 |
param.object = v |
| 291 |
f.Params = append(f.Params, param) |
| 292 |
if b != nil { |
| 293 |
f.Blocks[0].Instrs = append(f.Blocks[0].Instrs, param) |
| 294 |
} |
| 295 |
return param |
| 296 |
} |
| 297 |
|
| 298 |
// addSpilledParam declares a parameter that is pre-spilled to the |
| 299 |
// stack; the function body will load/store the spilled location. |
| 300 |
// Subsequent lifting will eliminate spills where possible. |
| 301 |
func (f *Function) addSpilledParam(obj *types.Var, source ast.Node) { |
| 302 |
param := f.addParamVar(obj, source) |
| 303 |
spill := emitLocalVar(f, obj, source) |
| 304 |
emitStore(f, spill, param, source) |
| 305 |
// f.emit(&Store{Addr: spill, Val: param}) |
| 306 |
} |
| 307 |
|
| 308 |
// startBody initializes the function prior to generating IR code for its body. |
| 309 |
// Precondition: f.Type() already set. |
| 310 |
func (f *Function) startBody() { |
| 311 |
entry := f.newBasicBlock("entry") |
| 312 |
f.currentBlock = entry |
| 313 |
f.vars = make(map[*types.Var]Value) // needed for some synthetics, e.g. init |
| 314 |
} |
| 315 |
|
| 316 |
func (f *Function) blockset(i int) *BlockSet { |
| 317 |
bs := &f.blocksets[i] |
| 318 |
if len(bs.values) != len(f.Blocks) { |
| 319 |
if cap(bs.values) >= len(f.Blocks) { |
| 320 |
bs.values = bs.values[:len(f.Blocks)] |
| 321 |
bs.Clear() |
| 322 |
} else { |
| 323 |
bs.values = make([]bool, len(f.Blocks)) |
| 324 |
} |
| 325 |
} else { |
| 326 |
bs.Clear() |
| 327 |
} |
| 328 |
return bs |
| 329 |
} |
| 330 |
|
| 331 |
func (f *Function) exitBlock() { |
| 332 |
old := f.currentBlock |
| 333 |
|
| 334 |
f.Exit = f.newBasicBlock("exit") |
| 335 |
f.currentBlock = f.Exit |
| 336 |
|
| 337 |
results := make([]Value, len(f.results)) |
| 338 |
// Run function calls deferred in this |
| 339 |
// function when explicitly returning from it. |
| 340 |
f.emit(new(RunDefers), nil) |
| 341 |
for i, r := range f.results { |
| 342 |
results[i] = emitLoad(f, r, nil) |
| 343 |
} |
| 344 |
|
| 345 |
f.emit(&Return{Results: results}, nil) |
| 346 |
f.currentBlock = old |
| 347 |
} |
| 348 |
|
| 349 |
// createSyntacticParams populates f.Params and generates code (spills |
| 350 |
// and named result locals) for all the parameters declared in the |
| 351 |
// syntax. In addition it populates the f.objects mapping. |
| 352 |
// |
| 353 |
// Preconditions: |
| 354 |
// f.startBody() was called. |
| 355 |
// Postcondition: |
| 356 |
// len(f.Params) == len(f.Signature.Params) + (f.Signature.Recv() ? 1 : 0) |
| 357 |
func (f *Function) createSyntacticParams(recv *ast.FieldList, functype *ast.FuncType) { |
| 358 |
// Receiver (at most one inner iteration). |
| 359 |
if recv != nil { |
| 360 |
for _, field := range recv.List { |
| 361 |
for _, n := range field.Names { |
| 362 |
f.addSpilledParam(identVar(f, n), n) |
| 363 |
} |
| 364 |
// Anonymous receiver? No need to spill. |
| 365 |
if field.Names == nil { |
| 366 |
f.addParamVar(f.Signature.Recv(), field) |
| 367 |
} |
| 368 |
} |
| 369 |
} |
| 370 |
|
| 371 |
// Parameters. |
| 372 |
if functype.Params != nil { |
| 373 |
n := len(f.Params) // 1 if has recv, 0 otherwise |
| 374 |
for _, field := range functype.Params.List { |
| 375 |
for _, n := range field.Names { |
| 376 |
f.addSpilledParam(identVar(f, n), n) |
| 377 |
} |
| 378 |
// Anonymous parameter? No need to spill. |
| 379 |
if field.Names == nil { |
| 380 |
f.addParamVar(f.Signature.Params().At(len(f.Params)-n), field) |
| 381 |
} |
| 382 |
} |
| 383 |
} |
| 384 |
|
| 385 |
// Results. |
| 386 |
if functype.Results != nil { |
| 387 |
for _, field := range functype.Results.List { |
| 388 |
// Implicit "var" decl of locals for named results. |
| 389 |
for _, n := range field.Names { |
| 390 |
v := identVar(f, n) |
| 391 |
f.addResultVar(v, n) |
| 392 |
} |
| 393 |
// Implicit "var" decl of local for an unnamed result. |
| 394 |
if field.Names == nil { |
| 395 |
v := f.Signature.Results().At(len(f.results)) |
| 396 |
f.addResultVar(v, field.Type) |
| 397 |
} |
| 398 |
} |
| 399 |
} |
| 400 |
} |
| 401 |
|
| 402 |
// createDeferStack initializes fn.deferstack to a local variable |
| 403 |
// initialized to a ssa:deferstack() call. |
| 404 |
func (fn *Function) createDeferStack() { |
| 405 |
// Each syntactic function makes a call to ssa:deferstack, |
| 406 |
// which is spilled to a local. Unused ones are later removed. |
| 407 |
fn.deferstack = newVar("defer$stack", tDeferStack) |
| 408 |
call := &Call{Call: CallCommon{Value: vDeferStack}} |
| 409 |
call.setType(tDeferStack) |
| 410 |
deferstack := fn.emit(call, nil) |
| 411 |
spill := emitLocalVar(fn, fn.deferstack, nil) |
| 412 |
emitStore(fn, spill, deferstack, nil) |
| 413 |
} |
| 414 |
|
| 415 |
func numberNodes(f *Function) { |
| 416 |
var base ID |
| 417 |
for _, b := range f.Blocks { |
| 418 |
for _, instr := range b.Instrs { |
| 419 |
if instr == nil { |
| 420 |
continue |
| 421 |
} |
| 422 |
base++ |
| 423 |
instr.setID(base) |
| 424 |
} |
| 425 |
} |
| 426 |
} |
| 427 |
|
| 428 |
func updateOperandsReferrers(instr Instruction, ops []*Value) { |
| 429 |
for _, op := range ops { |
| 430 |
if r := *op; r != nil { |
| 431 |
if refs := (*op).Referrers(); refs != nil { |
| 432 |
if len(*refs) == 0 { |
| 433 |
// per median, each value has two referrers, so we can avoid one call into growslice |
| 434 |
// |
| 435 |
// Note: we experimented with allocating |
| 436 |
// sequential scratch space, but we |
| 437 |
// couldn't find a value that gave better |
| 438 |
// performance than making many individual |
| 439 |
// allocations |
| 440 |
*refs = make([]Instruction, 1, 2) |
| 441 |
(*refs)[0] = instr |
| 442 |
} else { |
| 443 |
*refs = append(*refs, instr) |
| 444 |
} |
| 445 |
} |
| 446 |
} |
| 447 |
} |
| 448 |
} |
| 449 |
|
| 450 |
// buildReferrers populates the def/use information in all non-nil |
| 451 |
// Value.Referrers slice. |
| 452 |
// Precondition: all such slices are initially empty. |
| 453 |
func buildReferrers(f *Function) { |
| 454 |
var rands []*Value |
| 455 |
|
| 456 |
for _, b := range f.Blocks { |
| 457 |
for _, instr := range b.Instrs { |
| 458 |
rands = instr.Operands(rands[:0]) // recycle storage |
| 459 |
updateOperandsReferrers(instr, rands) |
| 460 |
} |
| 461 |
} |
| 462 |
|
| 463 |
for _, c := range f.consts { |
| 464 |
rands = c.c.Operands(rands[:0]) |
| 465 |
updateOperandsReferrers(c.c, rands) |
| 466 |
} |
| 467 |
} |
| 468 |
|
| 469 |
func (f *Function) emitConsts() { |
| 470 |
defer func() { |
| 471 |
f.consts = nil |
| 472 |
f.aggregateConsts = typeutil.Map[[]*AggregateConst]{} |
| 473 |
}() |
| 474 |
|
| 475 |
if len(f.Blocks) == 0 { |
| 476 |
return |
| 477 |
} |
| 478 |
|
| 479 |
// TODO(dh): our deduplication only works on booleans and |
| 480 |
// integers. other constants are represented as pointers to |
| 481 |
// things. |
| 482 |
head := make([]constValue, 0, len(f.consts)) |
| 483 |
for _, c := range f.consts { |
| 484 |
if len(*c.c.Referrers()) == 0 { |
| 485 |
// TODO(dh): killing a const may make other consts dead, too |
| 486 |
killInstruction(c.c) |
| 487 |
} else { |
| 488 |
head = append(head, c) |
| 489 |
} |
| 490 |
} |
| 491 |
sort.Slice(head, func(i, j int) bool { |
| 492 |
return head[i].idx < head[j].idx |
| 493 |
}) |
| 494 |
entry := f.Blocks[0] |
| 495 |
instrs := make([]Instruction, 0, len(entry.Instrs)+len(head)) |
| 496 |
for _, c := range head { |
| 497 |
instrs = append(instrs, c.c) |
| 498 |
} |
| 499 |
f.aggregateConsts.Iterate(func(key types.Type, value []*AggregateConst) { |
| 500 |
for _, c := range value { |
| 501 |
instrs = append(instrs, c) |
| 502 |
} |
| 503 |
}) |
| 504 |
|
| 505 |
instrs = append(instrs, entry.Instrs...) |
| 506 |
entry.Instrs = instrs |
| 507 |
} |
| 508 |
|
| 509 |
// buildFakeExits ensures that every block in the function is |
| 510 |
// reachable in reverse from the Exit block. This is required to build |
| 511 |
// a full post-dominator tree, and to ensure the exit block's |
| 512 |
// inclusion in the dominator tree. |
| 513 |
func buildFakeExits(fn *Function) { |
| 514 |
// Find back-edges via forward DFS |
| 515 |
fn.fakeExits = BlockSet{values: make([]bool, len(fn.Blocks))} |
| 516 |
seen := fn.blockset(0) |
| 517 |
backEdges := fn.blockset(1) |
| 518 |
|
| 519 |
var dfs func(b *BasicBlock) |
| 520 |
dfs = func(b *BasicBlock) { |
| 521 |
if !seen.Add(b) { |
| 522 |
backEdges.Add(b) |
| 523 |
return |
| 524 |
} |
| 525 |
for _, pred := range b.Succs { |
| 526 |
dfs(pred) |
| 527 |
} |
| 528 |
} |
| 529 |
dfs(fn.Blocks[0]) |
| 530 |
buildLoop: |
| 531 |
for { |
| 532 |
seen := fn.blockset(2) |
| 533 |
var dfs func(b *BasicBlock) |
| 534 |
dfs = func(b *BasicBlock) { |
| 535 |
if !seen.Add(b) { |
| 536 |
return |
| 537 |
} |
| 538 |
for _, pred := range b.Preds { |
| 539 |
dfs(pred) |
| 540 |
} |
| 541 |
if b == fn.Exit { |
| 542 |
for _, b := range fn.Blocks { |
| 543 |
if fn.fakeExits.Has(b) { |
| 544 |
dfs(b) |
| 545 |
} |
| 546 |
} |
| 547 |
} |
| 548 |
} |
| 549 |
dfs(fn.Exit) |
| 550 |
|
| 551 |
for _, b := range fn.Blocks { |
| 552 |
if !seen.Has(b) && backEdges.Has(b) { |
| 553 |
// Block b is not reachable from the exit block. Add a |
| 554 |
// fake jump from b to exit, then try again. Note that we |
| 555 |
// only add one fake edge at a time, as it may make |
| 556 |
// multiple blocks reachable. |
| 557 |
// |
| 558 |
// We only consider those blocks that have back edges. |
| 559 |
// Any unreachable block that doesn't have a back edge |
| 560 |
// must flow into a loop, which by definition has a |
| 561 |
// back edge. Thus, by looking for loops, we should |
| 562 |
// need fewer fake edges overall. |
| 563 |
fn.fakeExits.Add(b) |
| 564 |
continue buildLoop |
| 565 |
} |
| 566 |
} |
| 567 |
|
| 568 |
break |
| 569 |
} |
| 570 |
} |
| 571 |
|
| 572 |
// finishBody() finalizes the function after IR code generation of its body. |
| 573 |
func (f *Function) finishBody() { |
| 574 |
f.currentBlock = nil |
| 575 |
f.lblocks = nil |
| 576 |
|
| 577 |
// Remove from f.Locals any Allocs that escape to the heap. |
| 578 |
j := 0 |
| 579 |
for _, l := range f.Locals { |
| 580 |
if !l.Heap { |
| 581 |
f.Locals[j] = l |
| 582 |
j++ |
| 583 |
} |
| 584 |
} |
| 585 |
// Nil out f.Locals[j:] to aid GC. |
| 586 |
for i := j; i < len(f.Locals); i++ { |
| 587 |
f.Locals[i] = nil |
| 588 |
} |
| 589 |
f.Locals = f.Locals[:j] |
| 590 |
|
| 591 |
optimizeBlocks(f) |
| 592 |
buildFakeExits(f) |
| 593 |
buildReferrers(f) |
| 594 |
buildDomTree(f) |
| 595 |
buildPostDomTree(f) |
| 596 |
|
| 597 |
if f.Prog.mode&NaiveForm == 0 { |
| 598 |
for lift(f) { |
| 599 |
} |
| 600 |
if doSimplifyConstantCompositeValues { |
| 601 |
for simplifyConstantCompositeValues(f) { |
| 602 |
} |
| 603 |
} |
| 604 |
} |
| 605 |
|
| 606 |
// emit constants after lifting, because lifting may produce new constants, but before other variable splitting, |
| 607 |
// because it expects constants to have been deduplicated. |
| 608 |
f.emitConsts() |
| 609 |
|
| 610 |
if f.Prog.mode&SplitAfterNewInformation != 0 { |
| 611 |
splitOnNewInformation(f.Blocks[0], &StackMap{}) |
| 612 |
} |
| 613 |
|
| 614 |
// clear remaining builder state |
| 615 |
f.results = nil // (used by lifting) |
| 616 |
f.deferstack = nil // (used by lifting) |
| 617 |
f.vars = nil // (used by lifting) |
| 618 |
f.goversion = "" |
| 619 |
|
| 620 |
numberNodes(f) |
| 621 |
|
| 622 |
defer f.wr.Close() |
| 623 |
f.wr.WriteFunc("start", "start", f) |
| 624 |
|
| 625 |
if f.Prog.mode&PrintFunctions != 0 { |
| 626 |
printMu.Lock() |
| 627 |
f.WriteTo(os.Stdout) |
| 628 |
printMu.Unlock() |
| 629 |
} |
| 630 |
|
| 631 |
if f.Prog.mode&SanityCheckFunctions != 0 { |
| 632 |
mustSanityCheck(f, nil) |
| 633 |
} |
| 634 |
} |
| 635 |
|
| 636 |
func isUselessPhi(phi *Phi) (Value, bool) { |
| 637 |
var v0 Value |
| 638 |
for _, e := range phi.Edges { |
| 639 |
if e == phi { |
| 640 |
continue |
| 641 |
} |
| 642 |
if v0 == nil { |
| 643 |
v0 = e |
| 644 |
} |
| 645 |
if v0 != e { |
| 646 |
if v0, ok := v0.(*Const); ok { |
| 647 |
if e, ok := e.(*Const); ok { |
| 648 |
if v0.typ == e.typ && v0.Value == e.Value { |
| 649 |
continue |
| 650 |
} |
| 651 |
} |
| 652 |
} |
| 653 |
return nil, false |
| 654 |
} |
| 655 |
} |
| 656 |
return v0, true |
| 657 |
} |
| 658 |
|
| 659 |
func (f *Function) RemoveNilBlocks() { |
| 660 |
f.removeNilBlocks() |
| 661 |
} |
| 662 |
|
| 663 |
// removeNilBlocks eliminates nils from f.Blocks and updates each |
| 664 |
// BasicBlock.Index. Use this after any pass that may delete blocks. |
| 665 |
func (f *Function) removeNilBlocks() { |
| 666 |
j := 0 |
| 667 |
for _, b := range f.Blocks { |
| 668 |
if b != nil { |
| 669 |
b.Index = j |
| 670 |
f.Blocks[j] = b |
| 671 |
j++ |
| 672 |
} |
| 673 |
} |
| 674 |
// Nil out f.Blocks[j:] to aid GC. |
| 675 |
for i := j; i < len(f.Blocks); i++ { |
| 676 |
f.Blocks[i] = nil |
| 677 |
} |
| 678 |
f.Blocks = f.Blocks[:j] |
| 679 |
} |
| 680 |
|
| 681 |
// SetDebugMode sets the debug mode for package pkg. If true, all its |
| 682 |
// functions will include full debug info. This greatly increases the |
| 683 |
// size of the instruction stream, and causes Functions to depend upon |
| 684 |
// the ASTs, potentially keeping them live in memory for longer. |
| 685 |
func (pkg *Package) SetDebugMode(debug bool) { |
| 686 |
// TODO(adonovan): do we want ast.File granularity? |
| 687 |
pkg.debug = debug |
| 688 |
} |
| 689 |
|
| 690 |
// debugInfo reports whether debug info is wanted for this function. |
| 691 |
func (f *Function) debugInfo() bool { |
| 692 |
return f.Pkg != nil && f.Pkg.debug |
| 693 |
} |
| 694 |
|
| 695 |
// lookup returns the address of the named variable identified by obj |
| 696 |
// that is local to function f or one of its enclosing functions. |
| 697 |
// If escaping, the reference comes from a potentially escaping pointer |
| 698 |
// expression and the referent must be heap-allocated. |
| 699 |
// We assume the referent is a *Alloc or *Phi. |
| 700 |
// (The only Phis at this stage are those created directly by go1.22 "for" loops.) |
| 701 |
func (f *Function) lookup(obj *types.Var, escaping bool) Value { |
| 702 |
if v, ok := f.vars[obj]; ok { |
| 703 |
if escaping { |
| 704 |
switch v := v.(type) { |
| 705 |
case *Alloc: |
| 706 |
v.Heap = true |
| 707 |
case *Phi: |
| 708 |
for _, edge := range v.Edges { |
| 709 |
if alloc, ok := edge.(*Alloc); ok { |
| 710 |
alloc.Heap = true |
| 711 |
} |
| 712 |
} |
| 713 |
} |
| 714 |
} |
| 715 |
return v // function-local var (address) |
| 716 |
} |
| 717 |
|
| 718 |
// Definition must be in an enclosing function; |
| 719 |
// plumb it through intervening closures. |
| 720 |
if f.parent == nil { |
| 721 |
panic("no ir.Value for " + obj.String()) |
| 722 |
} |
| 723 |
outer := f.parent.lookup(obj, true) // escaping |
| 724 |
v := &FreeVar{ |
| 725 |
name: obj.Name(), |
| 726 |
typ: outer.Type(), |
| 727 |
outer: outer, |
| 728 |
parent: f, |
| 729 |
} |
| 730 |
f.vars[obj] = v |
| 731 |
f.FreeVars = append(f.FreeVars, v) |
| 732 |
return v |
| 733 |
} |
| 734 |
|
| 735 |
// emit emits the specified instruction to function f. |
| 736 |
func (f *Function) emit(instr Instruction, source ast.Node) Value { |
| 737 |
return f.currentBlock.emit(instr, source) |
| 738 |
} |
| 739 |
|
| 740 |
// RelString returns the full name of this function, qualified by |
| 741 |
// package name, receiver type, etc. |
| 742 |
// |
| 743 |
// The specific formatting rules are not guaranteed and may change. |
| 744 |
// |
| 745 |
// Examples: |
| 746 |
// |
| 747 |
// "math.IsNaN" // a package-level function |
| 748 |
// "(*bytes.Buffer).Bytes" // a declared method or a wrapper |
| 749 |
// "(*bytes.Buffer).Bytes$thunk" // thunk (func wrapping method; receiver is param 0) |
| 750 |
// "(*bytes.Buffer).Bytes$bound" // bound (func wrapping method; receiver supplied by closure) |
| 751 |
// "main.main$1" // an anonymous function in main |
| 752 |
// "main.init#1" // a declared init function |
| 753 |
// "main.init" // the synthesized package initializer |
| 754 |
// |
| 755 |
// When these functions are referred to from within the same package |
| 756 |
// (i.e. from == f.Pkg.Object), they are rendered without the package path. |
| 757 |
// For example: "IsNaN", "(*Buffer).Bytes", etc. |
| 758 |
// |
| 759 |
// All non-synthetic functions have distinct package-qualified names. |
| 760 |
// (But two methods may have the same name "(T).f" if one is a synthetic |
| 761 |
// wrapper promoting a non-exported method "f" from another package; in |
| 762 |
// that case, the strings are equal but the identifiers "f" are distinct.) |
| 763 |
func (f *Function) RelString(from *types.Package) string { |
| 764 |
// Anonymous? |
| 765 |
if f.parent != nil { |
| 766 |
// An anonymous function's Name() looks like "parentName$1", |
| 767 |
// but its String() should include the type/package/etc. |
| 768 |
parent := f.parent.RelString(from) |
| 769 |
for i, anon := range f.parent.AnonFuncs { |
| 770 |
if anon == f { |
| 771 |
return fmt.Sprintf("%s$%d", parent, 1+i) |
| 772 |
} |
| 773 |
} |
| 774 |
|
| 775 |
return f.name // should never happen |
| 776 |
} |
| 777 |
|
| 778 |
// Method (declared or wrapper)? |
| 779 |
if recv := f.Signature.Recv(); recv != nil { |
| 780 |
return f.relMethod(from, recv.Type()) |
| 781 |
} |
| 782 |
|
| 783 |
// Thunk? |
| 784 |
if f.method != nil { |
| 785 |
return f.relMethod(from, f.method.Recv()) |
| 786 |
} |
| 787 |
|
| 788 |
// Bound? |
| 789 |
if len(f.FreeVars) == 1 && strings.HasSuffix(f.name, "$bound") { |
| 790 |
return f.relMethod(from, f.FreeVars[0].Type()) |
| 791 |
} |
| 792 |
|
| 793 |
// Package-level function? |
| 794 |
// Prefix with package name for cross-package references only. |
| 795 |
if p := f.pkg(); p != nil && p != from { |
| 796 |
return fmt.Sprintf("%s.%s", p.Path(), f.name) |
| 797 |
} |
| 798 |
|
| 799 |
// Unknown. |
| 800 |
return f.name |
| 801 |
} |
| 802 |
|
| 803 |
func (f *Function) relMethod(from *types.Package, recv types.Type) string { |
| 804 |
return fmt.Sprintf("(%s).%s", relType(recv, from), f.name) |
| 805 |
} |
| 806 |
|
| 807 |
// writeSignature writes to buf the signature sig in declaration syntax. |
| 808 |
func writeSignature(buf *bytes.Buffer, from *types.Package, name string, sig *types.Signature) { |
| 809 |
buf.WriteString("func ") |
| 810 |
if recv := sig.Recv(); recv != nil { |
| 811 |
buf.WriteString("(") |
| 812 |
if name := recv.Name(); name != "" { |
| 813 |
buf.WriteString(name) |
| 814 |
buf.WriteString(" ") |
| 815 |
} |
| 816 |
types.WriteType(buf, recv.Type(), types.RelativeTo(from)) |
| 817 |
buf.WriteString(") ") |
| 818 |
} |
| 819 |
buf.WriteString(name) |
| 820 |
types.WriteSignature(buf, sig, types.RelativeTo(from)) |
| 821 |
} |
| 822 |
|
| 823 |
func (f *Function) pkg() *types.Package { |
| 824 |
if f.Pkg != nil { |
| 825 |
return f.Pkg.Pkg |
| 826 |
} |
| 827 |
return nil |
| 828 |
} |
| 829 |
|
| 830 |
var _ io.WriterTo = (*Function)(nil) // *Function implements io.Writer |
| 831 |
|
| 832 |
func (f *Function) WriteTo(w io.Writer) (int64, error) { |
| 833 |
var buf bytes.Buffer |
| 834 |
WriteFunction(&buf, f) |
| 835 |
n, err := w.Write(buf.Bytes()) |
| 836 |
return int64(n), err |
| 837 |
} |
| 838 |
|
| 839 |
// WriteFunction writes to buf a human-readable "disassembly" of f. |
| 840 |
func WriteFunction(buf *bytes.Buffer, f *Function) { |
| 841 |
fmt.Fprintf(buf, "# Name: %s\n", f.String()) |
| 842 |
if f.Pkg != nil { |
| 843 |
fmt.Fprintf(buf, "# Package: %s\n", f.Pkg.Pkg.Path()) |
| 844 |
} |
| 845 |
if syn := f.Synthetic; syn != 0 { |
| 846 |
fmt.Fprintln(buf, "# Synthetic:", syn) |
| 847 |
} |
| 848 |
if pos := f.Pos(); pos.IsValid() { |
| 849 |
fmt.Fprintf(buf, "# Location: %s\n", f.Prog.Fset.Position(pos)) |
| 850 |
} |
| 851 |
|
| 852 |
if f.parent != nil { |
| 853 |
fmt.Fprintf(buf, "# Parent: %s\n", f.parent.Name()) |
| 854 |
} |
| 855 |
|
| 856 |
from := f.pkg() |
| 857 |
|
| 858 |
if f.FreeVars != nil { |
| 859 |
buf.WriteString("# Free variables:\n") |
| 860 |
for i, fv := range f.FreeVars { |
| 861 |
fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, fv.Name(), relType(fv.Type(), from)) |
| 862 |
} |
| 863 |
} |
| 864 |
|
| 865 |
if len(f.Locals) > 0 { |
| 866 |
buf.WriteString("# Locals:\n") |
| 867 |
for i, l := range f.Locals { |
| 868 |
fmt.Fprintf(buf, "# % 3d:\t%s %s\n", i, l.Name(), relType(deref(l.Type()), from)) |
| 869 |
} |
| 870 |
} |
| 871 |
writeSignature(buf, from, f.Name(), f.Signature) |
| 872 |
buf.WriteString(":\n") |
| 873 |
|
| 874 |
if f.Blocks == nil { |
| 875 |
buf.WriteString("\t(external)\n") |
| 876 |
} |
| 877 |
|
| 878 |
for _, b := range f.Blocks { |
| 879 |
if b == nil { |
| 880 |
// Corrupt CFG. |
| 881 |
fmt.Fprintf(buf, ".nil:\n") |
| 882 |
continue |
| 883 |
} |
| 884 |
fmt.Fprintf(buf, "b%d:", b.Index) |
| 885 |
if len(b.Preds) > 0 { |
| 886 |
fmt.Fprint(buf, " ←") |
| 887 |
for _, pred := range b.Preds { |
| 888 |
fmt.Fprintf(buf, " b%d", pred.Index) |
| 889 |
} |
| 890 |
} |
| 891 |
if b.Comment != "" { |
| 892 |
fmt.Fprintf(buf, " # %s", b.Comment) |
| 893 |
} |
| 894 |
buf.WriteByte('\n') |
| 895 |
|
| 896 |
if false { // CFG debugging |
| 897 |
fmt.Fprintf(buf, "\t# CFG: %s --> %s --> %s\n", b.Preds, b, b.Succs) |
| 898 |
} |
| 899 |
|
| 900 |
buf2 := &bytes.Buffer{} |
| 901 |
for _, instr := range b.Instrs { |
| 902 |
buf.WriteString("\t") |
| 903 |
switch v := instr.(type) { |
| 904 |
case Value: |
| 905 |
// Left-align the instruction. |
| 906 |
if name := v.Name(); name != "" { |
| 907 |
fmt.Fprintf(buf, "%s = ", name) |
| 908 |
} |
| 909 |
buf.WriteString(instr.String()) |
| 910 |
case nil: |
| 911 |
// Be robust against bad transforms. |
| 912 |
buf.WriteString("<deleted>") |
| 913 |
default: |
| 914 |
buf.WriteString(instr.String()) |
| 915 |
} |
| 916 |
if instr != nil && instr.Comment() != "" { |
| 917 |
buf.WriteString(" # ") |
| 918 |
buf.WriteString(instr.Comment()) |
| 919 |
} |
| 920 |
buf.WriteString("\n") |
| 921 |
|
| 922 |
if f.Prog.mode&PrintSource != 0 { |
| 923 |
if s := instr.Source(); s != nil { |
| 924 |
buf2.Reset() |
| 925 |
format.Node(buf2, f.Prog.Fset, s) |
| 926 |
for { |
| 927 |
line, err := buf2.ReadString('\n') |
| 928 |
if len(line) == 0 { |
| 929 |
break |
| 930 |
} |
| 931 |
buf.WriteString("\t\t> ") |
| 932 |
buf.WriteString(line) |
| 933 |
if line[len(line)-1] != '\n' { |
| 934 |
buf.WriteString("\n") |
| 935 |
} |
| 936 |
if err != nil { |
| 937 |
break |
| 938 |
} |
| 939 |
} |
| 940 |
} |
| 941 |
} |
| 942 |
} |
| 943 |
buf.WriteString("\n") |
| 944 |
} |
| 945 |
} |
| 946 |
|
| 947 |
// newBasicBlock adds to f a new basic block and returns it. It does |
| 948 |
// not automatically become the current block for subsequent calls to emit. |
| 949 |
// comment is an optional string for more readable debugging output. |
| 950 |
func (f *Function) newBasicBlock(comment string) *BasicBlock { |
| 951 |
var instrs []Instruction |
| 952 |
if len(f.functionBody.scratchInstructions) > 0 { |
| 953 |
instrs = f.functionBody.scratchInstructions[0:0:avgInstructionsPerBlock] |
| 954 |
f.functionBody.scratchInstructions = f.functionBody.scratchInstructions[avgInstructionsPerBlock:] |
| 955 |
} else { |
| 956 |
instrs = make([]Instruction, 0, avgInstructionsPerBlock) |
| 957 |
} |
| 958 |
|
| 959 |
b := &BasicBlock{ |
| 960 |
Index: len(f.Blocks), |
| 961 |
Comment: comment, |
| 962 |
parent: f, |
| 963 |
Instrs: instrs, |
| 964 |
} |
| 965 |
b.Succs = b.succs2[:0] |
| 966 |
f.Blocks = append(f.Blocks, b) |
| 967 |
return b |
| 968 |
} |
| 969 |
|
| 970 |
// NewFunction returns a new synthetic Function instance belonging to |
| 971 |
// prog, with its name and signature fields set as specified. |
| 972 |
// |
| 973 |
// The caller is responsible for initializing the remaining fields of |
| 974 |
// the function object, e.g. Pkg, Params, Blocks. |
| 975 |
// |
| 976 |
// It is practically impossible for clients to construct well-formed |
| 977 |
// IR functions/packages/programs directly, so we assume this is the |
| 978 |
// job of the Builder alone. NewFunction exists to provide clients a |
| 979 |
// little flexibility. For example, analysis tools may wish to |
| 980 |
// construct fake Functions for the root of the callgraph, a fake |
| 981 |
// "reflect" package, etc. |
| 982 |
// |
| 983 |
// TODO(adonovan): think harder about the API here. |
| 984 |
func (prog *Program) NewFunction(name string, sig *types.Signature, provenance Synthetic) *Function { |
| 985 |
return &Function{Prog: prog, name: name, Signature: sig, Synthetic: provenance} |
| 986 |
} |
| 987 |
|
| 988 |
//lint:ignore U1000 we may make use of this for functions loaded from export data |
| 989 |
type extentNode [2]token.Pos |
| 990 |
|
| 991 |
func (n extentNode) Pos() token.Pos { return n[0] } |
| 992 |
func (n extentNode) End() token.Pos { return n[1] } |
| 993 |
|
| 994 |
func (f *Function) initHTML(name string) { |
| 995 |
if name == "" { |
| 996 |
return |
| 997 |
} |
| 998 |
if rel := f.RelString(nil); rel == name { |
| 999 |
f.wr = NewHTMLWriter("ir.html", rel, "") |
| 1000 |
} |
| 1001 |
} |
| 1002 |
|
| 1003 |
func killInstruction(instr Instruction) { |
| 1004 |
ops := instr.Operands(nil) |
| 1005 |
for _, op := range ops { |
| 1006 |
if refs := (*op).Referrers(); refs != nil { |
| 1007 |
*refs = removeInstr(*refs, instr) |
| 1008 |
} |
| 1009 |
} |
| 1010 |
} |
| 1011 |
|
| 1012 |
// identVar returns the variable defined by id. |
| 1013 |
func identVar(fn *Function, id *ast.Ident) *types.Var { |
| 1014 |
return fn.Pkg.info.Defs[id].(*types.Var) |
| 1015 |
} |
| 1016 |
|
| 1017 |
// unique returns a unique positive int within the source tree of f. |
| 1018 |
// The source tree of f includes all of f's ancestors by parent and all |
| 1019 |
// of the AnonFuncs contained within these. |
| 1020 |
func unique(f *Function) int64 { |
| 1021 |
f.uniq++ |
| 1022 |
return f.uniq |
| 1023 |
} |
| 1024 |
|
| 1025 |
// exit is a change of control flow going from a range-over-func |
| 1026 |
// yield function to an ancestor function caused by a break, continue, |
| 1027 |
// goto, or return statement. |
| 1028 |
// |
| 1029 |
// There are 3 types of exits: |
| 1030 |
// * return from the source function (from ReturnStmt), |
| 1031 |
// * jump to a block (from break and continue statements [labelled/unlabelled]), |
| 1032 |
// * go to a label (from goto statements). |
| 1033 |
// |
| 1034 |
// As the builder does one pass over the ast, it is unclear whether |
| 1035 |
// a forward goto statement will leave a range-over-func body. |
| 1036 |
// The function being exited to is unresolved until the end |
| 1037 |
// of building the range-over-func body. |
| 1038 |
type exit struct { |
| 1039 |
id int64 // unique value for exit within from and to |
| 1040 |
from *Function // the function the exit starts from |
| 1041 |
to *Function // the function being exited to (nil if unresolved) |
| 1042 |
source ast.Node |
| 1043 |
|
| 1044 |
block *BasicBlock // basic block within to being jumped to. |
| 1045 |
label *types.Label // forward label being jumped to via goto. |
| 1046 |
// block == nil && label == nil => return |
| 1047 |
} |
| 1048 |
|
| 1049 |
// storeVar emits to function f code to store a value v to a *types.Var x. |
| 1050 |
func storeVar(f *Function, x *types.Var, v Value, source ast.Node) { |
| 1051 |
emitStore(f, f.lookup(x, true), v, source) |
| 1052 |
} |
| 1053 |
|
| 1054 |
// labelExit creates a new exit to a yield fn to exit the function using a label. |
| 1055 |
func labelExit(fn *Function, label *types.Label, source ast.Node) *exit { |
| 1056 |
e := &exit{ |
| 1057 |
id: unique(fn), |
| 1058 |
from: fn, |
| 1059 |
to: nil, |
| 1060 |
source: source, |
| 1061 |
label: label, |
| 1062 |
} |
| 1063 |
fn.exits = append(fn.exits, e) |
| 1064 |
return e |
| 1065 |
} |
| 1066 |
|
| 1067 |
// blockExit creates a new exit to a yield fn that jumps to a basic block. |
| 1068 |
func blockExit(fn *Function, block *BasicBlock, source ast.Node) *exit { |
| 1069 |
e := &exit{ |
| 1070 |
id: unique(fn), |
| 1071 |
from: fn, |
| 1072 |
to: block.parent, |
| 1073 |
source: source, |
| 1074 |
block: block, |
| 1075 |
} |
| 1076 |
fn.exits = append(fn.exits, e) |
| 1077 |
return e |
| 1078 |
} |
| 1079 |
|
| 1080 |
// returnExit creates a new exit to a yield fn that returns to the source function. |
| 1081 |
func returnExit(fn *Function, source ast.Node) *exit { |
| 1082 |
e := &exit{ |
| 1083 |
id: unique(fn), |
| 1084 |
from: fn, |
| 1085 |
to: fn.sourceFn, |
| 1086 |
source: source, |
| 1087 |
} |
| 1088 |
fn.exits = append(fn.exits, e) |
| 1089 |
return e |
| 1090 |
} |