1// Copyright 2023 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 ir
6
7import (
8	"cmd/compile/internal/base"
9)
10
11// A ReassignOracle efficiently answers queries about whether local
12// variables are reassigned. This helper works by looking for function
13// params and short variable declarations (e.g.
14// https://go.dev/ref/spec#Short_variable_declarations) that are
15// neither address taken nor subsequently re-assigned. It is intended
16// to operate much like "ir.StaticValue" and "ir.Reassigned", but in a
17// way that does just a single walk of the containing function (as
18// opposed to a new walk on every call).
19type ReassignOracle struct {
20	fn *Func
21	// maps candidate name to its defining assignment (or for
22	// for params, defining func).
23	singleDef map[*Name]Node
24}
25
26// Init initializes the oracle based on the IR in function fn, laying
27// the groundwork for future calls to the StaticValue and Reassigned
28// methods. If the fn's IR is subsequently modified, Init must be
29// called again.
30func (ro *ReassignOracle) Init(fn *Func) {
31	ro.fn = fn
32
33	// Collect candidate map. Start by adding function parameters
34	// explicitly.
35	ro.singleDef = make(map[*Name]Node)
36	sig := fn.Type()
37	numParams := sig.NumRecvs() + sig.NumParams()
38	for _, param := range fn.Dcl[:numParams] {
39		if IsBlank(param) {
40			continue
41		}
42		// For params, use func itself as defining node.
43		ro.singleDef[param] = fn
44	}
45
46	// Walk the function body to discover any locals assigned
47	// via ":=" syntax (e.g. "a := <expr>").
48	var findLocals func(n Node) bool
49	findLocals = func(n Node) bool {
50		if nn, ok := n.(*Name); ok {
51			if nn.Defn != nil && !nn.Addrtaken() && nn.Class == PAUTO {
52				ro.singleDef[nn] = nn.Defn
53			}
54		} else if nn, ok := n.(*ClosureExpr); ok {
55			Any(nn.Func, findLocals)
56		}
57		return false
58	}
59	Any(fn, findLocals)
60
61	outerName := func(x Node) *Name {
62		if x == nil {
63			return nil
64		}
65		n, ok := OuterValue(x).(*Name)
66		if ok {
67			return n.Canonical()
68		}
69		return nil
70	}
71
72	// pruneIfNeeded examines node nn appearing on the left hand side
73	// of assignment statement asn to see if it contains a reassignment
74	// to any nodes in our candidate map ro.singleDef; if a reassignment
75	// is found, the corresponding name is deleted from singleDef.
76	pruneIfNeeded := func(nn Node, asn Node) {
77		oname := outerName(nn)
78		if oname == nil {
79			return
80		}
81		defn, ok := ro.singleDef[oname]
82		if !ok {
83			return
84		}
85		// any assignment to a param invalidates the entry.
86		paramAssigned := oname.Class == PPARAM
87		// assignment to local ok iff assignment is its orig def.
88		localAssigned := (oname.Class == PAUTO && asn != defn)
89		if paramAssigned || localAssigned {
90			// We found an assignment to name N that doesn't
91			// correspond to its original definition; remove
92			// from candidates.
93			delete(ro.singleDef, oname)
94		}
95	}
96
97	// Prune away anything that looks assigned. This code modeled after
98	// similar code in ir.Reassigned; any changes there should be made
99	// here as well.
100	var do func(n Node) bool
101	do = func(n Node) bool {
102		switch n.Op() {
103		case OAS:
104			asn := n.(*AssignStmt)
105			pruneIfNeeded(asn.X, n)
106		case OAS2, OAS2FUNC, OAS2MAPR, OAS2DOTTYPE, OAS2RECV, OSELRECV2:
107			asn := n.(*AssignListStmt)
108			for _, p := range asn.Lhs {
109				pruneIfNeeded(p, n)
110			}
111		case OASOP:
112			asn := n.(*AssignOpStmt)
113			pruneIfNeeded(asn.X, n)
114		case ORANGE:
115			rs := n.(*RangeStmt)
116			pruneIfNeeded(rs.Key, n)
117			pruneIfNeeded(rs.Value, n)
118		case OCLOSURE:
119			n := n.(*ClosureExpr)
120			Any(n.Func, do)
121		}
122		return false
123	}
124	Any(fn, do)
125}
126
127// StaticValue method has the same semantics as the ir package function
128// of the same name; see comments on [StaticValue].
129func (ro *ReassignOracle) StaticValue(n Node) Node {
130	arg := n
131	for {
132		if n.Op() == OCONVNOP {
133			n = n.(*ConvExpr).X
134			continue
135		}
136
137		if n.Op() == OINLCALL {
138			n = n.(*InlinedCallExpr).SingleResult()
139			continue
140		}
141
142		n1 := ro.staticValue1(n)
143		if n1 == nil {
144			if consistencyCheckEnabled {
145				checkStaticValueResult(arg, n)
146			}
147			return n
148		}
149		n = n1
150	}
151}
152
153func (ro *ReassignOracle) staticValue1(nn Node) Node {
154	if nn.Op() != ONAME {
155		return nil
156	}
157	n := nn.(*Name).Canonical()
158	if n.Class != PAUTO {
159		return nil
160	}
161
162	defn := n.Defn
163	if defn == nil {
164		return nil
165	}
166
167	var rhs Node
168FindRHS:
169	switch defn.Op() {
170	case OAS:
171		defn := defn.(*AssignStmt)
172		rhs = defn.Y
173	case OAS2:
174		defn := defn.(*AssignListStmt)
175		for i, lhs := range defn.Lhs {
176			if lhs == n {
177				rhs = defn.Rhs[i]
178				break FindRHS
179			}
180		}
181		base.Fatalf("%v missing from LHS of %v", n, defn)
182	default:
183		return nil
184	}
185	if rhs == nil {
186		base.Fatalf("RHS is nil: %v", defn)
187	}
188
189	if _, ok := ro.singleDef[n]; !ok {
190		return nil
191	}
192
193	return rhs
194}
195
196// Reassigned method has the same semantics as the ir package function
197// of the same name; see comments on [Reassigned] for more info.
198func (ro *ReassignOracle) Reassigned(n *Name) bool {
199	_, ok := ro.singleDef[n]
200	result := !ok
201	if consistencyCheckEnabled {
202		checkReassignedResult(n, result)
203	}
204	return result
205}
206