1// Copyright 2016 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
5package ssa
6
7import "cmd/internal/src"
8
9// trim removes blocks with no code in them.
10// These blocks were inserted to remove critical edges.
11func trim(f *Func) {
12	n := 0
13	for _, b := range f.Blocks {
14		if !trimmableBlock(b) {
15			f.Blocks[n] = b
16			n++
17			continue
18		}
19
20		bPos := b.Pos
21		bIsStmt := bPos.IsStmt() == src.PosIsStmt
22
23		// Splice b out of the graph. NOTE: `mergePhi` depends on the
24		// order, in which the predecessors edges are merged here.
25		p, i := b.Preds[0].b, b.Preds[0].i
26		s, j := b.Succs[0].b, b.Succs[0].i
27		ns := len(s.Preds)
28		p.Succs[i] = Edge{s, j}
29		s.Preds[j] = Edge{p, i}
30
31		for _, e := range b.Preds[1:] {
32			p, i := e.b, e.i
33			p.Succs[i] = Edge{s, len(s.Preds)}
34			s.Preds = append(s.Preds, Edge{p, i})
35		}
36
37		// Attempt to preserve a statement boundary
38		if bIsStmt {
39			sawStmt := false
40			for _, v := range s.Values {
41				if isPoorStatementOp(v.Op) {
42					continue
43				}
44				if v.Pos.SameFileAndLine(bPos) {
45					v.Pos = v.Pos.WithIsStmt()
46				}
47				sawStmt = true
48				break
49			}
50			if !sawStmt && s.Pos.SameFileAndLine(bPos) {
51				s.Pos = s.Pos.WithIsStmt()
52			}
53		}
54		// If `s` had more than one predecessor, update its phi-ops to
55		// account for the merge.
56		if ns > 1 {
57			for _, v := range s.Values {
58				if v.Op == OpPhi {
59					mergePhi(v, j, b)
60				}
61
62			}
63			// Remove the phi-ops from `b` if they were merged into the
64			// phi-ops of `s`.
65			k := 0
66			for _, v := range b.Values {
67				if v.Op == OpPhi {
68					if v.Uses == 0 {
69						v.resetArgs()
70						continue
71					}
72					// Pad the arguments of the remaining phi-ops so
73					// they match the new predecessor count of `s`.
74					// Since s did not have a Phi op corresponding to
75					// the phi op in b, the other edges coming into s
76					// must be loopback edges from s, so v is the right
77					// argument to v!
78					args := make([]*Value, len(v.Args))
79					copy(args, v.Args)
80					v.resetArgs()
81					for x := 0; x < j; x++ {
82						v.AddArg(v)
83					}
84					v.AddArg(args[0])
85					for x := j + 1; x < ns; x++ {
86						v.AddArg(v)
87					}
88					for _, a := range args[1:] {
89						v.AddArg(a)
90					}
91				}
92				b.Values[k] = v
93				k++
94			}
95			b.Values = b.Values[:k]
96		}
97
98		// Merge the blocks' values.
99		for _, v := range b.Values {
100			v.Block = s
101		}
102		k := len(b.Values)
103		m := len(s.Values)
104		for i := 0; i < k; i++ {
105			s.Values = append(s.Values, nil)
106		}
107		copy(s.Values[k:], s.Values[:m])
108		copy(s.Values, b.Values)
109	}
110	if n < len(f.Blocks) {
111		f.invalidateCFG()
112		tail := f.Blocks[n:]
113		for i := range tail {
114			tail[i] = nil
115		}
116		f.Blocks = f.Blocks[:n]
117	}
118}
119
120// emptyBlock reports whether the block does not contain actual
121// instructions
122func emptyBlock(b *Block) bool {
123	for _, v := range b.Values {
124		if v.Op != OpPhi {
125			return false
126		}
127	}
128	return true
129}
130
131// trimmableBlock reports whether the block can be trimmed from the CFG,
132// subject to the following criteria:
133//  - it should not be the first block
134//  - it should be BlockPlain
135//  - it should not loop back to itself
136//  - it either is the single predecessor of the successor block or
137//    contains no actual instructions
138func trimmableBlock(b *Block) bool {
139	if b.Kind != BlockPlain || b == b.Func.Entry {
140		return false
141	}
142	s := b.Succs[0].b
143	return s != b && (len(s.Preds) == 1 || emptyBlock(b))
144}
145
146// mergePhi adjusts the number of `v`s arguments to account for merge
147// of `b`, which was `i`th predecessor of the `v`s block.
148func mergePhi(v *Value, i int, b *Block) {
149	u := v.Args[i]
150	if u.Block == b {
151		if u.Op != OpPhi {
152			b.Func.Fatalf("value %s is not a phi operation", u.LongString())
153		}
154		// If the original block contained u = φ(u0, u1, ..., un) and
155		// the current phi is
156		//    v = φ(v0, v1, ..., u, ..., vk)
157		// then the merged phi is
158		//    v = φ(v0, v1, ..., u0, ..., vk, u1, ..., un)
159		v.SetArg(i, u.Args[0])
160		v.AddArgs(u.Args[1:]...)
161	} else {
162		// If the original block contained u = φ(u0, u1, ..., un) and
163		// the current phi is
164		//    v = φ(v0, v1, ...,  vi, ..., vk)
165		// i.e. it does not use a value from the predecessor block,
166		// then the merged phi is
167		//    v = φ(v0, v1, ..., vk, vi, vi, ...)
168		for j := 1; j < len(b.Preds); j++ {
169			v.AddArg(v.Args[i])
170		}
171	}
172}
173