block.go raw

   1  // Copyright 2022 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 ssa
   6  
   7  import "fmt"
   8  
   9  // This file implements the BasicBlock type.
  10  
  11  // addEdge adds a control-flow graph edge from from to to.
  12  func addEdge(from, to *BasicBlock) {
  13  	from.Succs = append(from.Succs, to)
  14  	to.Preds = append(to.Preds, from)
  15  }
  16  
  17  // Parent returns the function that contains block b.
  18  func (b *BasicBlock) Parent() *Function { return b.parent }
  19  
  20  // String returns a human-readable label of this block.
  21  // It is not guaranteed unique within the function.
  22  func (b *BasicBlock) String() string {
  23  	return fmt.Sprintf("%d", b.Index)
  24  }
  25  
  26  // emit appends an instruction to the current basic block.
  27  // If the instruction defines a Value, it is returned.
  28  func (b *BasicBlock) emit(i Instruction) Value {
  29  	i.setBlock(b)
  30  	b.Instrs = append(b.Instrs, i)
  31  	v, _ := i.(Value)
  32  	return v
  33  }
  34  
  35  // predIndex returns the i such that b.Preds[i] == c or panics if
  36  // there is none.
  37  func (b *BasicBlock) predIndex(c *BasicBlock) int {
  38  	for i, pred := range b.Preds {
  39  		if pred == c {
  40  			return i
  41  		}
  42  	}
  43  	panic(fmt.Sprintf("no edge %s -> %s", c, b))
  44  }
  45  
  46  // hasPhi returns true if b.Instrs contains φ-nodes.
  47  func (b *BasicBlock) hasPhi() bool {
  48  	_, ok := b.Instrs[0].(*Phi)
  49  	return ok
  50  }
  51  
  52  // phis returns the prefix of b.Instrs containing all the block's φ-nodes.
  53  func (b *BasicBlock) phis() []Instruction {
  54  	for i, instr := range b.Instrs {
  55  		if _, ok := instr.(*Phi); !ok {
  56  			return b.Instrs[:i]
  57  		}
  58  	}
  59  	return nil // unreachable in well-formed blocks
  60  }
  61  
  62  // replacePred replaces all occurrences of p in b's predecessor list with q.
  63  // Ordinarily there should be at most one.
  64  func (b *BasicBlock) replacePred(p, q *BasicBlock) {
  65  	for i, pred := range b.Preds {
  66  		if pred == p {
  67  			b.Preds[i] = q
  68  		}
  69  	}
  70  }
  71  
  72  // replaceSucc replaces all occurrences of p in b's successor list with q.
  73  // Ordinarily there should be at most one.
  74  func (b *BasicBlock) replaceSucc(p, q *BasicBlock) {
  75  	for i, succ := range b.Succs {
  76  		if succ == p {
  77  			b.Succs[i] = q
  78  		}
  79  	}
  80  }
  81  
  82  // removePred removes all occurrences of p in b's
  83  // predecessor list and φ-nodes.
  84  // Ordinarily there should be at most one.
  85  func (b *BasicBlock) removePred(p *BasicBlock) {
  86  	phis := b.phis()
  87  
  88  	// We must preserve edge order for φ-nodes.
  89  	j := 0
  90  	for i, pred := range b.Preds {
  91  		if pred != p {
  92  			b.Preds[j] = b.Preds[i]
  93  			// Strike out φ-edge too.
  94  			for _, instr := range phis {
  95  				phi := instr.(*Phi)
  96  				phi.Edges[j] = phi.Edges[i]
  97  			}
  98  			j++
  99  		}
 100  	}
 101  	// Nil out b.Preds[j:] and φ-edges[j:] to aid GC.
 102  	for i := j; i < len(b.Preds); i++ {
 103  		b.Preds[i] = nil
 104  		for _, instr := range phis {
 105  			instr.(*Phi).Edges[i] = nil
 106  		}
 107  	}
 108  	b.Preds = b.Preds[:j]
 109  	for _, instr := range phis {
 110  		phi := instr.(*Phi)
 111  		phi.Edges = phi.Edges[:j]
 112  	}
 113  }
 114