1#include "jitpch.h"
2#ifdef _MSC_VER
3#pragma hdrstop
4#endif
5
6#include "treelifeupdater.h"
7
8template <bool ForCodeGen>
9TreeLifeUpdater<ForCodeGen>::TreeLifeUpdater(Compiler* compiler)
10 : compiler(compiler)
11 , newLife(VarSetOps::MakeEmpty(compiler))
12 , stackVarDeltaSet(VarSetOps::MakeEmpty(compiler))
13 , varDeltaSet(VarSetOps::MakeEmpty(compiler))
14 , gcTrkStkDeltaSet(VarSetOps::MakeEmpty(compiler))
15#ifdef DEBUG
16 , gcVarPtrSetNew(VarSetOps::MakeEmpty(compiler))
17 , epoch(compiler->GetCurLVEpoch())
18#endif // DEBUG
19{
20}
21
22//------------------------------------------------------------------------
23// UpdateLifeVar: Update live sets for a given tree.
24//
25// Arguments:
26// tree - the tree which affects liveness.
27//
28template <bool ForCodeGen>
29void TreeLifeUpdater<ForCodeGen>::UpdateLifeVar(GenTree* tree)
30{
31 GenTree* indirAddrLocal = compiler->fgIsIndirOfAddrOfLocal(tree);
32 assert(tree->OperIsNonPhiLocal() || indirAddrLocal != nullptr);
33
34 // Get the local var tree -- if "tree" is "Ldobj(addr(x))", or "ind(addr(x))" this is "x", else it's "tree".
35 GenTree* lclVarTree = indirAddrLocal;
36 if (lclVarTree == nullptr)
37 {
38 lclVarTree = tree;
39 }
40 unsigned int lclNum = lclVarTree->gtLclVarCommon.gtLclNum;
41 LclVarDsc* varDsc = compiler->lvaTable + lclNum;
42
43#ifdef DEBUG
44#if !defined(_TARGET_AMD64_)
45 // There are no addr nodes on ARM and we are experimenting with encountering vars in 'random' order.
46 // Struct fields are not traversed in a consistent order, so ignore them when
47 // verifying that we see the var nodes in execution order
48 if (ForCodeGen)
49 {
50 if (tree->OperIsIndir())
51 {
52 assert(indirAddrLocal != NULL);
53 }
54 else if (tree->gtNext != NULL && tree->gtNext->gtOper == GT_ADDR &&
55 ((tree->gtNext->gtNext == NULL || !tree->gtNext->gtNext->OperIsIndir())))
56 {
57 assert(tree->IsLocal()); // Can only take the address of a local.
58 // The ADDR might occur in a context where the address it contributes is eventually
59 // dereferenced, so we can't say that this is not a use or def.
60 }
61 }
62#endif // !_TARGET_AMD64_
63#endif // DEBUG
64
65 compiler->compCurLifeTree = tree;
66 VarSetOps::Assign(compiler, newLife, compiler->compCurLife);
67
68 // By codegen, a struct may not be TYP_STRUCT, so we have to
69 // check lvPromoted, for the case where the fields are being
70 // tracked.
71 if (!varDsc->lvTracked && !varDsc->lvPromoted)
72 {
73 return;
74 }
75
76 // if it's a partial definition then variable "x" must have had a previous, original, site to be born.
77 bool isBorn = ((tree->gtFlags & GTF_VAR_DEF) != 0 && (tree->gtFlags & GTF_VAR_USEASG) == 0);
78 bool isDying = ((tree->gtFlags & GTF_VAR_DEATH) != 0);
79 bool spill = ((tree->gtFlags & GTF_SPILL) != 0);
80
81 // Since all tracked vars are register candidates, but not all are in registers at all times,
82 // we maintain two separate sets of variables - the total set of variables that are either
83 // born or dying here, and the subset of those that are on the stack
84 VarSetOps::ClearD(compiler, stackVarDeltaSet);
85
86 if (isBorn || isDying)
87 {
88 VarSetOps::ClearD(compiler, varDeltaSet);
89
90 if (varDsc->lvTracked)
91 {
92 VarSetOps::AddElemD(compiler, varDeltaSet, varDsc->lvVarIndex);
93 if (ForCodeGen)
94 {
95 if (isBorn && varDsc->lvIsRegCandidate() && tree->gtHasReg())
96 {
97 compiler->codeGen->genUpdateVarReg(varDsc, tree);
98 }
99 if (varDsc->lvIsInReg() && tree->gtRegNum != REG_NA)
100 {
101 compiler->codeGen->genUpdateRegLife(varDsc, isBorn, isDying DEBUGARG(tree));
102 }
103 else
104 {
105 VarSetOps::AddElemD(compiler, stackVarDeltaSet, varDsc->lvVarIndex);
106 }
107 }
108 }
109 else if (varDsc->lvPromoted)
110 {
111 // If hasDeadTrackedFieldVars is true, then, for a LDOBJ(ADDR(<promoted struct local>)),
112 // *deadTrackedFieldVars indicates which tracked field vars are dying.
113 bool hasDeadTrackedFieldVars = false;
114
115 if (indirAddrLocal != nullptr && isDying)
116 {
117 assert(!isBorn); // GTF_VAR_DEATH only set for LDOBJ last use.
118 VARSET_TP* deadTrackedFieldVars = nullptr;
119 hasDeadTrackedFieldVars =
120 compiler->LookupPromotedStructDeathVars(indirAddrLocal, &deadTrackedFieldVars);
121 if (hasDeadTrackedFieldVars)
122 {
123 VarSetOps::Assign(compiler, varDeltaSet, *deadTrackedFieldVars);
124 }
125 }
126
127 for (unsigned i = varDsc->lvFieldLclStart; i < varDsc->lvFieldLclStart + varDsc->lvFieldCnt; ++i)
128 {
129 LclVarDsc* fldVarDsc = &(compiler->lvaTable[i]);
130 noway_assert(fldVarDsc->lvIsStructField);
131 if (fldVarDsc->lvTracked)
132 {
133 unsigned fldVarIndex = fldVarDsc->lvVarIndex;
134 noway_assert(fldVarIndex < compiler->lvaTrackedCount);
135 if (!hasDeadTrackedFieldVars)
136 {
137 VarSetOps::AddElemD(compiler, varDeltaSet, fldVarIndex);
138 if (ForCodeGen)
139 {
140 // We repeat this call here and below to avoid the VarSetOps::IsMember
141 // test in this, the common case, where we have no deadTrackedFieldVars.
142 if (fldVarDsc->lvIsInReg())
143 {
144 if (isBorn)
145 {
146 compiler->codeGen->genUpdateVarReg(fldVarDsc, tree);
147 }
148 compiler->codeGen->genUpdateRegLife(fldVarDsc, isBorn, isDying DEBUGARG(tree));
149 }
150 else
151 {
152 VarSetOps::AddElemD(compiler, stackVarDeltaSet, fldVarIndex);
153 }
154 }
155 }
156 else if (ForCodeGen && VarSetOps::IsMember(compiler, varDeltaSet, fldVarIndex))
157 {
158 if (compiler->lvaTable[i].lvIsInReg())
159 {
160 if (isBorn)
161 {
162 compiler->codeGen->genUpdateVarReg(fldVarDsc, tree);
163 }
164 compiler->codeGen->genUpdateRegLife(fldVarDsc, isBorn, isDying DEBUGARG(tree));
165 }
166 else
167 {
168 VarSetOps::AddElemD(compiler, stackVarDeltaSet, fldVarIndex);
169 }
170 }
171 }
172 }
173 }
174
175 // First, update the live set
176 if (isDying)
177 {
178 // We'd like to be able to assert the following, however if we are walking
179 // through a qmark/colon tree, we may encounter multiple last-use nodes.
180 // assert (VarSetOps::IsSubset(compiler, regVarDeltaSet, newLife));
181 VarSetOps::DiffD(compiler, newLife, varDeltaSet);
182 }
183 else
184 {
185 // This shouldn't be in newLife, unless this is debug code, in which
186 // case we keep vars live everywhere, OR the variable is address-exposed,
187 // OR this block is part of a try block, in which case it may be live at the handler
188 // Could add a check that, if it's in newLife, that it's also in
189 // fgGetHandlerLiveVars(compCurBB), but seems excessive
190 //
191 // For a dead store, it can be the case that we set both isBorn and isDying to true.
192 // (We don't eliminate dead stores under MinOpts, so we can't assume they're always
193 // eliminated.) If it's both, we handled it above.
194 VarSetOps::UnionD(compiler, newLife, varDeltaSet);
195 }
196 }
197
198 if (!VarSetOps::Equal(compiler, compiler->compCurLife, newLife))
199 {
200#ifdef DEBUG
201 if (compiler->verbose)
202 {
203 printf("\t\t\t\t\t\t\tLive vars: ");
204 dumpConvertedVarSet(compiler, compiler->compCurLife);
205 printf(" => ");
206 dumpConvertedVarSet(compiler, newLife);
207 printf("\n");
208 }
209#endif // DEBUG
210
211 VarSetOps::Assign(compiler, compiler->compCurLife, newLife);
212
213 if (ForCodeGen)
214 {
215 // Only add vars to the gcInfo.gcVarPtrSetCur if they are currently on stack, since the
216 // gcInfo.gcTrkStkPtrLcls
217 // includes all TRACKED vars that EVER live on the stack (i.e. are not always in a register).
218 VarSetOps::Assign(compiler, gcTrkStkDeltaSet, compiler->codeGen->gcInfo.gcTrkStkPtrLcls);
219 VarSetOps::IntersectionD(compiler, gcTrkStkDeltaSet, stackVarDeltaSet);
220 if (!VarSetOps::IsEmpty(compiler, gcTrkStkDeltaSet))
221 {
222#ifdef DEBUG
223 if (compiler->verbose)
224 {
225 printf("\t\t\t\t\t\t\tGCvars: ");
226 dumpConvertedVarSet(compiler, compiler->codeGen->gcInfo.gcVarPtrSetCur);
227 printf(" => ");
228 }
229#endif // DEBUG
230
231 if (isBorn)
232 {
233 VarSetOps::UnionD(compiler, compiler->codeGen->gcInfo.gcVarPtrSetCur, gcTrkStkDeltaSet);
234 }
235 else
236 {
237 VarSetOps::DiffD(compiler, compiler->codeGen->gcInfo.gcVarPtrSetCur, gcTrkStkDeltaSet);
238 }
239
240#ifdef DEBUG
241 if (compiler->verbose)
242 {
243 dumpConvertedVarSet(compiler, compiler->codeGen->gcInfo.gcVarPtrSetCur);
244 printf("\n");
245 }
246#endif // DEBUG
247 }
248
249 compiler->codeGen->siUpdate();
250 }
251 }
252
253 if (ForCodeGen && spill)
254 {
255 assert(!varDsc->lvPromoted);
256 compiler->codeGen->genSpillVar(tree);
257 if (VarSetOps::IsMember(compiler, compiler->codeGen->gcInfo.gcTrkStkPtrLcls, varDsc->lvVarIndex))
258 {
259 if (!VarSetOps::IsMember(compiler, compiler->codeGen->gcInfo.gcVarPtrSetCur, varDsc->lvVarIndex))
260 {
261 VarSetOps::AddElemD(compiler, compiler->codeGen->gcInfo.gcVarPtrSetCur, varDsc->lvVarIndex);
262#ifdef DEBUG
263 if (compiler->verbose)
264 {
265 printf("\t\t\t\t\t\t\tVar V%02u becoming live\n", varDsc - compiler->lvaTable);
266 }
267#endif // DEBUG
268 }
269 }
270 }
271}
272
273//------------------------------------------------------------------------
274// UpdateLife: Determine whether the tree affects liveness, and update liveness sets accordingly.
275//
276// Arguments:
277// tree - the tree which effect on liveness is processed.
278//
279template <bool ForCodeGen>
280void TreeLifeUpdater<ForCodeGen>::UpdateLife(GenTree* tree)
281{
282 assert(compiler->GetCurLVEpoch() == epoch);
283 // TODO-Cleanup: We shouldn't really be calling this more than once
284 if (tree == compiler->compCurLifeTree)
285 {
286 return;
287 }
288
289 if (!tree->OperIsNonPhiLocal() && compiler->fgIsIndirOfAddrOfLocal(tree) == nullptr)
290 {
291 return;
292 }
293
294 UpdateLifeVar(tree);
295}
296
297template class TreeLifeUpdater<true>;
298template class TreeLifeUpdater<false>;
299