1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#include "jitpch.h"
6#ifdef _MSC_VER
7#pragma hdrstop
8#endif
9
10#include "sideeffects.h"
11
12LclVarSet::LclVarSet() : m_bitVector(nullptr), m_hasAnyLcl(false), m_hasBitVector(false)
13{
14}
15
16//------------------------------------------------------------------------
17// LclVarSet::Add:
18// Adds the given lclNum to the LclVarSet.
19//
20// Arguments:
21// compiler - The compiler context
22// lclNum - The lclNum to add.
23//
24void LclVarSet::Add(Compiler* compiler, unsigned lclNum)
25{
26 if (!m_hasAnyLcl)
27 {
28 m_lclNum = lclNum;
29 m_hasAnyLcl = true;
30 }
31 else
32 {
33 if (!m_hasBitVector)
34 {
35 unsigned singleLclNum = m_lclNum;
36 m_bitVector = hashBv::Create(compiler);
37 m_bitVector->setBit(singleLclNum);
38 m_hasBitVector = true;
39 }
40
41 m_bitVector->setBit(lclNum);
42 }
43}
44
45//------------------------------------------------------------------------
46// LclVarSet::Intersects:
47// Returns true if this LclVarSet intersects with the given LclVarSet.
48//
49// Arguments:
50// other - The other lclVarSet.
51//
52bool LclVarSet::Intersects(const LclVarSet& other) const
53{
54 // If neither set has ever contained anything, the sets do not intersect.
55 if (!m_hasAnyLcl || !other.m_hasAnyLcl)
56 {
57 return false;
58 }
59
60 // If this set is not represented by a bit vector, see if the single lclNum is contained in the other set.
61 if (!m_hasBitVector)
62 {
63 if (!other.m_hasBitVector)
64 {
65 return m_lclNum == other.m_lclNum;
66 }
67
68 return other.m_bitVector->testBit(m_lclNum);
69 }
70
71 // If this set is represented by a bit vector but the other set is not, see if the single lclNum in the other
72 // set is contained in this set.
73 if (!other.m_hasBitVector)
74 {
75 return m_bitVector->testBit(other.m_lclNum);
76 }
77
78 // Both sets are represented by bit vectors. Check to see if they intersect.
79 return m_bitVector->Intersects(other.m_bitVector);
80}
81
82//------------------------------------------------------------------------
83// LclVarSet::Contains:
84// Returns true if this LclVarSet contains the given lclNum.
85//
86// Arguments:
87// lclNum - The lclNum in question.
88//
89bool LclVarSet::Contains(unsigned lclNum) const
90{
91 // If this set has never contained anything, it does not contain the lclNum.
92 if (!m_hasAnyLcl)
93 {
94 return false;
95 }
96
97 // If this set is not represented by a bit vector, see if its single lclNum is the same as the given lclNum.
98 if (!m_hasBitVector)
99 {
100 return m_lclNum == lclNum;
101 }
102
103 // This set is represented by a bit vector. See if the bit vector contains the given lclNum.
104 return m_bitVector->testBit(lclNum);
105}
106
107//------------------------------------------------------------------------
108// LclVarSet::Clear:
109// Clears the contents of this LclVarSet.
110//
111void LclVarSet::Clear()
112{
113 if (m_hasBitVector)
114 {
115 assert(m_hasAnyLcl);
116 m_bitVector->ZeroAll();
117 }
118 else if (m_hasAnyLcl)
119 {
120 m_hasAnyLcl = false;
121 }
122}
123
124AliasSet::AliasSet()
125 : m_lclVarReads(), m_lclVarWrites(), m_readsAddressableLocation(false), m_writesAddressableLocation(false)
126{
127}
128
129//------------------------------------------------------------------------
130// AliasSet::NodeInfo::NodeInfo:
131// Computes the alias info for a given node. Note that this does not
132// include the set of lclVar accesses for a node unless the node is
133// itself a lclVar access (e.g. a GT_LCL_VAR, GT_STORE_LCL_VAR, etc.).
134//
135// Arguments:
136// compiler - The compiler context.
137// node - The node in question.
138//
139AliasSet::NodeInfo::NodeInfo(Compiler* compiler, GenTree* node)
140 : m_compiler(compiler), m_node(node), m_flags(0), m_lclNum(0)
141{
142 if (node->IsCall())
143 {
144 // Calls are treated as reads and writes of addressable locations unless they are known to be pure.
145 if (node->AsCall()->IsPure(compiler))
146 {
147 m_flags = ALIAS_NONE;
148 return;
149 }
150
151 m_flags = ALIAS_READS_ADDRESSABLE_LOCATION | ALIAS_WRITES_ADDRESSABLE_LOCATION;
152 return;
153 }
154 else if (node->OperIsAtomicOp())
155 {
156 // Atomic operations both read and write addressable locations.
157 m_flags = ALIAS_READS_ADDRESSABLE_LOCATION | ALIAS_WRITES_ADDRESSABLE_LOCATION;
158 return;
159 }
160
161 // Is the operation a write? If so, set `node` to the location that is being written to.
162 bool isWrite = false;
163 if (node->OperIs(GT_ASG))
164 {
165 isWrite = true;
166 node = node->gtGetOp1();
167 }
168 else if (node->OperIsStore())
169 {
170 isWrite = true;
171 }
172
173 // `node` is the location being accessed. Determine whether or not it is a memory or local variable access, and if
174 // it is the latter, get the number of the lclVar.
175 bool isMemoryAccess = false;
176 bool isLclVarAccess = false;
177 unsigned lclNum = 0;
178 if (node->OperIsIndir())
179 {
180 // If the indirection targets a lclVar, we can be more precise with regards to aliasing by treating the
181 // indirection as a lclVar access.
182 GenTree* address = node->AsIndir()->Addr();
183 if (address->OperIsLocalAddr())
184 {
185 isLclVarAccess = true;
186 lclNum = address->AsLclVarCommon()->GetLclNum();
187 }
188 else
189 {
190 isMemoryAccess = true;
191 }
192 }
193 else if (node->OperIsImplicitIndir())
194 {
195 isMemoryAccess = true;
196 }
197 else if (node->OperIsLocal())
198 {
199 isLclVarAccess = true;
200 lclNum = node->AsLclVarCommon()->GetLclNum();
201 }
202 else
203 {
204 // This is neither a memory nor a local var access.
205 m_flags = ALIAS_NONE;
206 return;
207 }
208
209 assert(isMemoryAccess || isLclVarAccess);
210
211 // Now that we've determined whether or not this access is a read or a write and whether the accessed location is
212 // memory or a lclVar, determine whther or not the location is addressable and udpate the alias set.
213 const bool isAddressableLocation = isMemoryAccess || compiler->lvaTable[lclNum].lvAddrExposed;
214
215 if (!isWrite)
216 {
217 if (isAddressableLocation)
218 {
219 m_flags |= ALIAS_READS_ADDRESSABLE_LOCATION;
220 }
221
222 if (isLclVarAccess)
223 {
224 m_flags |= ALIAS_READS_LCL_VAR;
225 m_lclNum = lclNum;
226 }
227 }
228 else
229 {
230 if (isAddressableLocation)
231 {
232 m_flags |= ALIAS_WRITES_ADDRESSABLE_LOCATION;
233 }
234
235 if (isLclVarAccess)
236 {
237 m_flags |= ALIAS_WRITES_LCL_VAR;
238 m_lclNum = lclNum;
239 }
240 }
241}
242
243//------------------------------------------------------------------------
244// AliasSet::AddNode:
245// Adds the given node's accesses to this AliasSet.
246//
247// Arguments:
248// compiler - The compiler context.
249// node - The node to add to the set.
250//
251void AliasSet::AddNode(Compiler* compiler, GenTree* node)
252{
253 // First, add all lclVar uses associated with the node to the set. This is necessary because the lclVar reads occur
254 // at the position of the user, not at the position of the GenTreeLclVar node.
255 node->VisitOperands([compiler, this](GenTree* operand) -> GenTree::VisitResult {
256 if (operand->OperIsLocalRead())
257 {
258 const unsigned lclNum = operand->AsLclVarCommon()->GetLclNum();
259 if (compiler->lvaTable[lclNum].lvAddrExposed)
260 {
261 m_readsAddressableLocation = true;
262 }
263
264 m_lclVarReads.Add(compiler, lclNum);
265 }
266 if (!operand->IsArgPlaceHolderNode() && operand->isContained())
267 {
268 AddNode(compiler, operand);
269 }
270 return GenTree::VisitResult::Continue;
271 });
272
273 NodeInfo nodeInfo(compiler, node);
274 if (nodeInfo.ReadsAddressableLocation())
275 {
276 m_readsAddressableLocation = true;
277 }
278 if (nodeInfo.WritesAddressableLocation())
279 {
280 m_writesAddressableLocation = true;
281 }
282 if (nodeInfo.IsLclVarRead())
283 {
284 m_lclVarReads.Add(compiler, nodeInfo.LclNum());
285 }
286 if (nodeInfo.IsLclVarWrite())
287 {
288 m_lclVarWrites.Add(compiler, nodeInfo.LclNum());
289 }
290}
291
292//------------------------------------------------------------------------
293// AliasSet::InterferesWith:
294// Returns true if the reads and writes in this alias set interfere
295// with the given alias set.
296//
297// Two alias sets interfere under any of the following conditions:
298// - Both sets write to any addressable location (e.g. the heap,
299// address-exposed locals)
300// - One set reads any addressable location and the other set writes
301// any addressable location
302// - Both sets write to the same lclVar
303// - One set writes to a lclVar that is read by the other set
304//
305// Arguments:
306// other - The other alias set.
307//
308bool AliasSet::InterferesWith(const AliasSet& other) const
309{
310 // If both sets write any addressable location, the sets interfere.
311 if (m_writesAddressableLocation && other.m_writesAddressableLocation)
312 {
313 return true;
314 }
315
316 // If one set writes any addressable location and the other reads any addressable location, the sets interfere.
317 if ((m_readsAddressableLocation && other.m_writesAddressableLocation) ||
318 (m_writesAddressableLocation && other.m_readsAddressableLocation))
319 {
320 return true;
321 }
322
323 // If the set of lclVars written by this alias set intersects with the set of lclVars accessed by the other alias
324 // set, the alias sets interfere.
325 if (m_lclVarWrites.Intersects(other.m_lclVarReads) || m_lclVarWrites.Intersects(other.m_lclVarWrites))
326 {
327 return true;
328 }
329
330 // If the set of lclVars read by this alias set intersects with the set of lclVars written by the other alias set,
331 // the alias sets interfere. Otherwise, the alias sets do not interfere.
332 return m_lclVarReads.Intersects(other.m_lclVarWrites);
333}
334
335//------------------------------------------------------------------------
336// AliasSet::InterferesWith:
337// Returns true if the reads and writes in this alias set interfere
338// with those for the given node.
339//
340// An alias set interferes with a given node iff it interferes with the
341// alias set for that node.
342//
343// Arguments:
344// other - The info for the node in question.
345//
346bool AliasSet::InterferesWith(const NodeInfo& other) const
347{
348 // First check whether or not this set interferes with the lclVar uses associated with the given node.
349 if (m_writesAddressableLocation || !m_lclVarWrites.IsEmpty())
350 {
351 Compiler* compiler = other.TheCompiler();
352 for (GenTree* operand : other.Node()->Operands())
353 {
354 if (operand->OperIsLocalRead())
355 {
356 // If this set writes any addressable location and the node uses an address-exposed lclVar,
357 // the set interferes with the node.
358 const unsigned lclNum = operand->AsLclVarCommon()->GetLclNum();
359 if (compiler->lvaTable[lclNum].lvAddrExposed && m_writesAddressableLocation)
360 {
361 return true;
362 }
363
364 // If this set writes to a lclVar used by the node, the set interferes with the node.
365 if (m_lclVarWrites.Contains(lclNum))
366 {
367 return true;
368 }
369 }
370 }
371 }
372
373 // If the node and the set both write to any addressable location, they interfere.
374 if (m_writesAddressableLocation && other.WritesAddressableLocation())
375 {
376 return true;
377 }
378
379 // If the node or the set writes any addressable location and the other reads any addressable location,
380 // they interfere.
381 if ((m_readsAddressableLocation && other.WritesAddressableLocation()) ||
382 (m_writesAddressableLocation && other.ReadsAddressableLocation()))
383 {
384 return true;
385 }
386
387 // If the set writes a local var accessed by the node, they interfere.
388 if ((other.IsLclVarRead() || other.IsLclVarWrite()) && m_lclVarWrites.Contains(other.LclNum()))
389 {
390 return true;
391 }
392
393 // If the set reads a local var written by the node, they interfere.
394 return other.IsLclVarWrite() && m_lclVarReads.Contains(other.LclNum());
395}
396
397//------------------------------------------------------------------------
398// AliasSet::Clear:
399// Clears the current alias set.
400//
401void AliasSet::Clear()
402{
403 m_readsAddressableLocation = false;
404 m_writesAddressableLocation = false;
405
406 m_lclVarReads.Clear();
407 m_lclVarWrites.Clear();
408}
409
410SideEffectSet::SideEffectSet() : m_sideEffectFlags(0), m_aliasSet()
411{
412}
413
414//------------------------------------------------------------------------
415// SideEffectSet::SideEffectSet:
416// Constructs a side effect set initialized using the given node.
417// Equivalent to the following;
418//
419// SideEffectSet sideEffectSet;
420// sideEffectSet.AddNode(compiler, node);
421//
422// Arguments:
423// compiler - The compiler context.
424// node - The node to use for initialization.
425//
426SideEffectSet::SideEffectSet(Compiler* compiler, GenTree* node) : m_sideEffectFlags(0), m_aliasSet()
427{
428 AddNode(compiler, node);
429}
430
431//------------------------------------------------------------------------
432// SideEffectSet::AddNode:
433// Adds the given node's accesses to this SideEffectSet.
434//
435// Arguments:
436// compiler - The compiler context.
437// node - The node to add to the set.
438//
439void SideEffectSet::AddNode(Compiler* compiler, GenTree* node)
440{
441 m_sideEffectFlags |= (node->gtFlags & GTF_ALL_EFFECT);
442 m_aliasSet.AddNode(compiler, node);
443}
444
445//------------------------------------------------------------------------
446// SideEffectSet::InterferesWith:
447// Returns true if the side effects in this set interfere with the
448// given side effect flags and alias information.
449//
450// Two side effect sets interfere under any of the following
451// conditions:
452// - If the analysis is strict, and:
453// - Either set contains a compiler barrier, or
454// - Both sets produce an exception
455// - Whether or not the analysis is strict:
456// - One set produces an exception and the other set contains a
457// write
458// - One set's reads and writes interfere with the other set's
459// reads and writes
460//
461// Arguments:
462// otherSideEffectFlags - The side effect flags for the other side
463// effect set.
464// otherAliasInfo - The alias information for the other side effect
465// set.
466// strict - True if the analysis should be strict as described above.
467//
468template <typename TOtherAliasInfo>
469bool SideEffectSet::InterferesWith(unsigned otherSideEffectFlags,
470 const TOtherAliasInfo& otherAliasInfo,
471 bool strict) const
472{
473 const bool thisProducesException = (m_sideEffectFlags & GTF_EXCEPT) != 0;
474 const bool otherProducesException = (otherSideEffectFlags & GTF_EXCEPT) != 0;
475
476 if (strict)
477 {
478 // If either set contains a compiler barrier, the sets interfere.
479 if (((m_sideEffectFlags | otherSideEffectFlags) & GTF_ORDER_SIDEEFF) != 0)
480 {
481 return true;
482 }
483
484 // If both sets produce an exception, the sets interfere.
485 if (thisProducesException && otherProducesException)
486 {
487 return true;
488 }
489 }
490
491 // If one set produces an exception and the other set writes to any location, the sets interfere.
492 if ((thisProducesException && otherAliasInfo.WritesAnyLocation()) ||
493 (otherProducesException && m_aliasSet.WritesAnyLocation()))
494 {
495 return true;
496 }
497
498 // At this point, the only interference between the sets will arise from their alias sets.
499 return m_aliasSet.InterferesWith(otherAliasInfo);
500}
501
502//------------------------------------------------------------------------
503// SideEffectSet::InterferesWith:
504// Returns true if the side effects in this set interfere with the side
505// effects in the given side effect set.
506//
507// Two side effect sets interfere under any of the following
508// conditions:
509// - If the analysis is strict, and:
510// - Either set contains a compiler barrier, or
511// - Both sets produce an exception
512// - Whether or not the analysis is strict:
513// - One set produces an exception and the other set contains a
514// write
515// - One set's reads and writes interfere with the other set's
516// reads and writes
517//
518// Arguments:
519// other - The other side effect set.
520// strict - True if the analysis should be strict as described above.
521//
522bool SideEffectSet::InterferesWith(const SideEffectSet& other, bool strict) const
523{
524 return InterferesWith(other.m_sideEffectFlags, other.m_aliasSet, strict);
525}
526
527//------------------------------------------------------------------------
528// SideEffectSet::InterferesWith:
529// Returns true if the side effects in this set interfere with the side
530// effects for the given node.
531//
532// A side effect set interferes with a given node iff it interferes
533// with the side effect set of the node.
534//
535// Arguments:
536// compiler - The compiler context.
537// node - The node in question.
538// strict - True if the analysis should be strict as described above.
539//
540bool SideEffectSet::InterferesWith(Compiler* compiler, GenTree* node, bool strict) const
541{
542 return InterferesWith((node->gtFlags & GTF_ALL_EFFECT), AliasSet::NodeInfo(compiler, node), strict);
543}
544
545//------------------------------------------------------------------------
546// SideEffectSet::Clear:
547// Clears the current side effect set.
548//
549void SideEffectSet::Clear()
550{
551 m_sideEffectFlags = 0;
552 m_aliasSet.Clear();
553}
554