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#include "smallhash.h"
7#include "sideeffects.h"
8
9#ifdef _MSC_VER
10#pragma hdrstop
11#endif
12
13LIR::Use::Use() : m_range(nullptr), m_edge(nullptr), m_user(nullptr)
14{
15}
16
17LIR::Use::Use(const Use& other)
18{
19 *this = other;
20}
21
22//------------------------------------------------------------------------
23// LIR::Use::Use: Constructs a use <-> def edge given the range that
24// contains the use and the def, the use -> def edge, and
25// the user.
26//
27// Arguments:
28// range - The range that contains the use and the def.
29// edge - The use -> def edge.
30// user - The node that uses the def.
31//
32// Return Value:
33//
34LIR::Use::Use(Range& range, GenTree** edge, GenTree* user) : m_range(&range), m_edge(edge), m_user(user)
35{
36 AssertIsValid();
37}
38
39LIR::Use& LIR::Use::operator=(const Use& other)
40{
41 m_range = other.m_range;
42 m_user = other.m_user;
43 m_edge = other.IsDummyUse() ? &m_user : other.m_edge;
44
45 assert(IsDummyUse() == other.IsDummyUse());
46 return *this;
47}
48
49LIR::Use& LIR::Use::operator=(Use&& other)
50{
51 *this = other;
52 return *this;
53}
54
55//------------------------------------------------------------------------
56// LIR::Use::GetDummyUse: Returns a dummy use for a node.
57//
58// This method is provided as a convenience to allow transforms to work
59// uniformly over Use values. It allows the creation of a Use given a node
60// that is not used.
61//
62// Arguments:
63// range - The range that contains the node.
64// node - The node for which to create a dummy use.
65//
66// Return Value:
67//
68LIR::Use LIR::Use::GetDummyUse(Range& range, GenTree* node)
69{
70 assert(node != nullptr);
71
72 Use dummyUse;
73 dummyUse.m_range = &range;
74 dummyUse.m_user = node;
75 dummyUse.m_edge = &dummyUse.m_user;
76
77 assert(dummyUse.IsInitialized());
78 return dummyUse;
79}
80
81//------------------------------------------------------------------------
82// LIR::Use::IsDummyUse: Indicates whether or not a use is a dummy use.
83//
84// This method must be called before attempting to call the User() method
85// below: for dummy uses, the user is the same node as the def.
86//
87// Return Value: true if this use is a dummy use; false otherwise.
88//
89bool LIR::Use::IsDummyUse() const
90{
91 return m_edge == &m_user;
92}
93
94//------------------------------------------------------------------------
95// LIR::Use::Def: Returns the node that produces the def for this use.
96//
97GenTree* LIR::Use::Def() const
98{
99 assert(IsInitialized());
100
101 return *m_edge;
102}
103
104//------------------------------------------------------------------------
105// LIR::Use::User: Returns the node that uses the def for this use.
106///
107GenTree* LIR::Use::User() const
108{
109 assert(IsInitialized());
110 assert(!IsDummyUse());
111
112 return m_user;
113}
114
115//------------------------------------------------------------------------
116// LIR::Use::IsInitialized: Returns true if the use is minimally valid; false otherwise.
117//
118bool LIR::Use::IsInitialized() const
119{
120 return (m_range != nullptr) && (m_user != nullptr) && (m_edge != nullptr);
121}
122
123//------------------------------------------------------------------------
124// LIR::Use::AssertIsValid: DEBUG function to assert on many validity conditions.
125//
126void LIR::Use::AssertIsValid() const
127{
128 assert(IsInitialized());
129 assert(m_range->Contains(m_user));
130 assert(Def() != nullptr);
131
132 GenTree** useEdge = nullptr;
133 assert(m_user->TryGetUse(Def(), &useEdge));
134 assert(useEdge == m_edge);
135}
136
137//------------------------------------------------------------------------
138// LIR::Use::ReplaceWith: Changes the use to point to a new value.
139//
140// For example, given the following LIR:
141//
142// t15 = lclVar int arg1
143// t16 = lclVar int arg1
144//
145// /--* t15 int
146// +--* t16 int
147// t17 = * == int
148//
149// /--* t17 int
150// * jmpTrue void
151//
152// If we wanted to replace the use of t17 with a use of the constant "1", we
153// might do the following (where `opEq` is a `Use` value that represents the
154// use of t17):
155//
156// GenTree* constantOne = compiler->gtNewIconNode(1);
157// range.InsertAfter(opEq.Def(), constantOne);
158// opEq.ReplaceWith(compiler, constantOne);
159//
160// Which would produce something like the following LIR:
161//
162// t15 = lclVar int arg1
163// t16 = lclVar int arg1
164//
165// /--* t15 int
166// +--* t16 int
167// t17 = * == int
168//
169// t18 = const int 1
170//
171// /--* t18 int
172// * jmpTrue void
173//
174// Eliminating the now-dead compare and its operands using `LIR::Range::Remove`
175// would then give us:
176//
177// t18 = const int 1
178//
179// /--* t18 int
180// * jmpTrue void
181//
182// Arguments:
183// compiler - The Compiler context.
184// replacement - The replacement node.
185//
186void LIR::Use::ReplaceWith(Compiler* compiler, GenTree* replacement)
187{
188 assert(IsInitialized());
189 assert(compiler != nullptr);
190 assert(replacement != nullptr);
191 assert(IsDummyUse() || m_range->Contains(m_user));
192 assert(m_range->Contains(replacement));
193
194 if (!IsDummyUse())
195 {
196 m_user->ReplaceOperand(m_edge, replacement);
197 }
198 else
199 {
200 *m_edge = replacement;
201 }
202}
203
204//------------------------------------------------------------------------
205// LIR::Use::ReplaceWithLclVar: Assigns the def for this use to a local
206// var and points the use to a use of that
207// local var. If no local number is provided,
208// creates a new local var.
209//
210// For example, given the following IR:
211//
212// t15 = lclVar int arg1
213// t16 = lclVar int arg1
214//
215// /--* t15 int
216// +--* t16 int
217// t17 = * == int
218//
219// /--* t17 int
220// * jmpTrue void
221//
222// If we wanted to replace the use of t17 with a use of a new local var
223// that holds the value represented by t17, we might do the following
224// (where `opEq` is a `Use` value that represents the use of t17):
225//
226// opEq.ReplaceUseWithLclVar(compiler, block->getBBWeight(compiler));
227//
228// This would produce the following LIR:
229//
230// t15 = lclVar int arg1
231// t16 = lclVar int arg1
232//
233// /--* t15 int
234// +--* t16 int
235// t17 = * == int
236//
237// /--* t17 int
238// * st.lclVar int tmp0
239//
240// t18 = lclVar int tmp0
241//
242// /--* t18 int
243// * jmpTrue void
244//
245// Arguments:
246// compiler - The Compiler context.
247// blockWeight - The weight of the basic block that contains the use.
248// lclNum - The local to use for temporary storage. If BAD_VAR_NUM (the
249// default) is provided, this method will create and use a new
250// local var.
251//
252// Return Value: The number of the local var used for temporary storage.
253//
254unsigned LIR::Use::ReplaceWithLclVar(Compiler* compiler, unsigned blockWeight, unsigned lclNum)
255{
256 assert(IsInitialized());
257 assert(compiler != nullptr);
258 assert(m_range->Contains(m_user));
259 assert(m_range->Contains(*m_edge));
260
261 GenTree* const node = *m_edge;
262
263 if (lclNum == BAD_VAR_NUM)
264 {
265 lclNum = compiler->lvaGrabTemp(true DEBUGARG("ReplaceWithLclVar is creating a new local variable"));
266 }
267
268 GenTreeLclVar* const store = compiler->gtNewTempAssign(lclNum, node)->AsLclVar();
269 assert(store != nullptr);
270 assert(store->gtOp1 == node);
271
272 GenTree* const load =
273 new (compiler, GT_LCL_VAR) GenTreeLclVar(store->TypeGet(), store->AsLclVarCommon()->GetLclNum(), BAD_IL_OFFSET);
274
275 m_range->InsertAfter(node, store, load);
276
277 ReplaceWith(compiler, load);
278
279 JITDUMP("ReplaceWithLclVar created store :\n");
280 DISPNODE(store);
281
282 return lclNum;
283}
284
285LIR::ReadOnlyRange::ReadOnlyRange() : m_firstNode(nullptr), m_lastNode(nullptr)
286{
287}
288
289LIR::ReadOnlyRange::ReadOnlyRange(ReadOnlyRange&& other) : m_firstNode(other.m_firstNode), m_lastNode(other.m_lastNode)
290{
291#ifdef DEBUG
292 other.m_firstNode = nullptr;
293 other.m_lastNode = nullptr;
294#endif
295}
296
297//------------------------------------------------------------------------
298// LIR::ReadOnlyRange::ReadOnlyRange:
299// Creates a `ReadOnlyRange` value given the first and last node in
300// the range.
301//
302// Arguments:
303// firstNode - The first node in the range.
304// lastNode - The last node in the range.
305//
306LIR::ReadOnlyRange::ReadOnlyRange(GenTree* firstNode, GenTree* lastNode) : m_firstNode(firstNode), m_lastNode(lastNode)
307{
308 assert((m_firstNode == nullptr) == (m_lastNode == nullptr));
309 assert((m_firstNode == m_lastNode) || (Contains(m_lastNode)));
310}
311
312//------------------------------------------------------------------------
313// LIR::ReadOnlyRange::FirstNode: Returns the first node in the range.
314//
315GenTree* LIR::ReadOnlyRange::FirstNode() const
316{
317 return m_firstNode;
318}
319
320//------------------------------------------------------------------------
321// LIR::ReadOnlyRange::LastNode: Returns the last node in the range.
322//
323GenTree* LIR::ReadOnlyRange::LastNode() const
324{
325 return m_lastNode;
326}
327
328//------------------------------------------------------------------------
329// LIR::ReadOnlyRange::IsEmpty: Returns true if the range is empty; false
330// otherwise.
331//
332bool LIR::ReadOnlyRange::IsEmpty() const
333{
334 assert((m_firstNode == nullptr) == (m_lastNode == nullptr));
335 return m_firstNode == nullptr;
336}
337
338//------------------------------------------------------------------------
339// LIR::ReadOnlyRange::begin: Returns an iterator positioned at the first
340// node in the range.
341//
342LIR::ReadOnlyRange::Iterator LIR::ReadOnlyRange::begin() const
343{
344 return Iterator(m_firstNode);
345}
346
347//------------------------------------------------------------------------
348// LIR::ReadOnlyRange::end: Returns an iterator positioned after the last
349// node in the range.
350//
351LIR::ReadOnlyRange::Iterator LIR::ReadOnlyRange::end() const
352{
353 return Iterator(m_lastNode == nullptr ? nullptr : m_lastNode->gtNext);
354}
355
356//------------------------------------------------------------------------
357// LIR::ReadOnlyRange::rbegin: Returns an iterator positioned at the last
358// node in the range.
359//
360LIR::ReadOnlyRange::ReverseIterator LIR::ReadOnlyRange::rbegin() const
361{
362 return ReverseIterator(m_lastNode);
363}
364
365//------------------------------------------------------------------------
366// LIR::ReadOnlyRange::rend: Returns an iterator positioned before the first
367// node in the range.
368//
369LIR::ReadOnlyRange::ReverseIterator LIR::ReadOnlyRange::rend() const
370{
371 return ReverseIterator(m_firstNode == nullptr ? nullptr : m_firstNode->gtPrev);
372}
373
374#ifdef DEBUG
375
376//------------------------------------------------------------------------
377// LIR::ReadOnlyRange::Contains: Indicates whether or not this range
378// contains a given node.
379//
380// Arguments:
381// node - The node to find.
382//
383// Return Value: True if this range contains the given node; false
384// otherwise.
385//
386bool LIR::ReadOnlyRange::Contains(GenTree* node) const
387{
388 assert(node != nullptr);
389
390 // TODO-LIR: derive this from the # of nodes in the function as well as
391 // the debug level. Checking small functions is pretty cheap; checking
392 // large functions is not.
393 if (JitConfig.JitExpensiveDebugCheckLevel() < 2)
394 {
395 return true;
396 }
397
398 for (GenTree* n : *this)
399 {
400 if (n == node)
401 {
402 return true;
403 }
404 }
405
406 return false;
407}
408
409#endif
410
411LIR::Range::Range() : ReadOnlyRange()
412{
413}
414
415LIR::Range::Range(Range&& other) : ReadOnlyRange(std::move(other))
416{
417}
418
419//------------------------------------------------------------------------
420// LIR::Range::Range: Creates a `Range` value given the first and last
421// node in the range.
422//
423// Arguments:
424// firstNode - The first node in the range.
425// lastNode - The last node in the range.
426//
427LIR::Range::Range(GenTree* firstNode, GenTree* lastNode) : ReadOnlyRange(firstNode, lastNode)
428{
429}
430
431//------------------------------------------------------------------------
432// LIR::Range::LastPhiNode: Returns the last phi node in the range or
433// `nullptr` if no phis exist.
434//
435GenTree* LIR::Range::LastPhiNode() const
436{
437 GenTree* lastPhiNode = nullptr;
438 for (GenTree* node : *this)
439 {
440 if (!node->IsPhiNode())
441 {
442 break;
443 }
444
445 lastPhiNode = node;
446 }
447
448 return lastPhiNode;
449}
450
451//------------------------------------------------------------------------
452// LIR::Range::FirstNonPhiNode: Returns the first non-phi node in the
453// range or `nullptr` if no non-phi nodes
454// exist.
455//
456GenTree* LIR::Range::FirstNonPhiNode() const
457{
458 for (GenTree* node : *this)
459 {
460 if (!node->IsPhiNode())
461 {
462 return node;
463 }
464 }
465
466 return nullptr;
467}
468
469//------------------------------------------------------------------------
470// LIR::Range::FirstNonPhiOrCatchArgNode: Returns the first node after all
471// phi or catch arg nodes in this
472// range.
473//
474GenTree* LIR::Range::FirstNonPhiOrCatchArgNode() const
475{
476 for (GenTree* node : NonPhiNodes())
477 {
478 if (node->OperGet() == GT_CATCH_ARG)
479 {
480 continue;
481 }
482 else if ((node->OperGet() == GT_STORE_LCL_VAR) && (node->gtGetOp1()->OperGet() == GT_CATCH_ARG))
483 {
484 continue;
485 }
486
487 return node;
488 }
489
490 return nullptr;
491}
492
493//------------------------------------------------------------------------
494// LIR::Range::PhiNodes: Returns the range of phi nodes inside this range.
495//
496LIR::ReadOnlyRange LIR::Range::PhiNodes() const
497{
498 GenTree* lastPhiNode = LastPhiNode();
499 if (lastPhiNode == nullptr)
500 {
501 return ReadOnlyRange();
502 }
503
504 return ReadOnlyRange(m_firstNode, lastPhiNode);
505}
506
507//------------------------------------------------------------------------
508// LIR::Range::PhiNodes: Returns the range of non-phi nodes inside this
509// range.
510//
511LIR::ReadOnlyRange LIR::Range::NonPhiNodes() const
512{
513 GenTree* firstNonPhiNode = FirstNonPhiNode();
514 if (firstNonPhiNode == nullptr)
515 {
516 return ReadOnlyRange();
517 }
518
519 return ReadOnlyRange(firstNonPhiNode, m_lastNode);
520}
521
522//------------------------------------------------------------------------
523// LIR::Range::InsertBefore: Inserts a node before another node in this range.
524//
525// Arguments:
526// insertionPoint - The node before which `node` will be inserted. If non-null, must be part
527// of this range. If null, insert at the end of the range.
528// node - The node to insert. Must not be part of any range.
529//
530void LIR::Range::InsertBefore(GenTree* insertionPoint, GenTree* node)
531{
532 assert(node != nullptr);
533 assert(node->gtPrev == nullptr);
534 assert(node->gtNext == nullptr);
535
536 FinishInsertBefore(insertionPoint, node, node);
537}
538
539//------------------------------------------------------------------------
540// LIR::Range::InsertBefore: Inserts 2 nodes before another node in this range.
541//
542// Arguments:
543// insertionPoint - The node before which the nodes will be inserted. If non-null, must be part
544// of this range. If null, insert at the end of the range.
545// node1 - The first node to insert. Must not be part of any range.
546// node2 - The second node to insert. Must not be part of any range.
547//
548// Notes:
549// Resulting order:
550// previous insertionPoint->gtPrev <-> node1 <-> node2 <-> insertionPoint
551//
552void LIR::Range::InsertBefore(GenTree* insertionPoint, GenTree* node1, GenTree* node2)
553{
554 assert(node1 != nullptr);
555 assert(node2 != nullptr);
556
557 assert(node1->gtNext == nullptr);
558 assert(node1->gtPrev == nullptr);
559 assert(node2->gtNext == nullptr);
560 assert(node2->gtPrev == nullptr);
561
562 node1->gtNext = node2;
563 node2->gtPrev = node1;
564
565 FinishInsertBefore(insertionPoint, node1, node2);
566}
567
568//------------------------------------------------------------------------
569// LIR::Range::InsertBefore: Inserts 3 nodes before another node in this range.
570//
571// Arguments:
572// insertionPoint - The node before which the nodes will be inserted. If non-null, must be part
573// of this range. If null, insert at the end of the range.
574// node1 - The first node to insert. Must not be part of any range.
575// node2 - The second node to insert. Must not be part of any range.
576// node3 - The third node to insert. Must not be part of any range.
577//
578// Notes:
579// Resulting order:
580// previous insertionPoint->gtPrev <-> node1 <-> node2 <-> node3 <-> insertionPoint
581//
582void LIR::Range::InsertBefore(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3)
583{
584 assert(node1 != nullptr);
585 assert(node2 != nullptr);
586 assert(node3 != nullptr);
587
588 assert(node1->gtNext == nullptr);
589 assert(node1->gtPrev == nullptr);
590 assert(node2->gtNext == nullptr);
591 assert(node2->gtPrev == nullptr);
592 assert(node3->gtNext == nullptr);
593 assert(node3->gtPrev == nullptr);
594
595 node1->gtNext = node2;
596
597 node2->gtPrev = node1;
598 node2->gtNext = node3;
599
600 node3->gtPrev = node2;
601
602 FinishInsertBefore(insertionPoint, node1, node3);
603}
604
605//------------------------------------------------------------------------
606// LIR::Range::InsertBefore: Inserts 4 nodes before another node in this range.
607//
608// Arguments:
609// insertionPoint - The node before which the nodes will be inserted. If non-null, must be part
610// of this range. If null, insert at the end of the range.
611// node1 - The first node to insert. Must not be part of any range.
612// node2 - The second node to insert. Must not be part of any range.
613// node3 - The third node to insert. Must not be part of any range.
614// node4 - The fourth node to insert. Must not be part of any range.
615//
616// Notes:
617// Resulting order:
618// previous insertionPoint->gtPrev <-> node1 <-> node2 <-> node3 <-> node4 <-> insertionPoint
619//
620void LIR::Range::InsertBefore(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3, GenTree* node4)
621{
622 assert(node1 != nullptr);
623 assert(node2 != nullptr);
624 assert(node3 != nullptr);
625 assert(node4 != nullptr);
626
627 assert(node1->gtNext == nullptr);
628 assert(node1->gtPrev == nullptr);
629 assert(node2->gtNext == nullptr);
630 assert(node2->gtPrev == nullptr);
631 assert(node3->gtNext == nullptr);
632 assert(node3->gtPrev == nullptr);
633 assert(node4->gtNext == nullptr);
634 assert(node4->gtPrev == nullptr);
635
636 node1->gtNext = node2;
637
638 node2->gtPrev = node1;
639 node2->gtNext = node3;
640
641 node3->gtPrev = node2;
642 node3->gtNext = node4;
643
644 node4->gtPrev = node3;
645
646 FinishInsertBefore(insertionPoint, node1, node4);
647}
648
649//------------------------------------------------------------------------
650// LIR::Range::FinishInsertBefore: Helper function to finalize InsertBefore processing: link the
651// range to insertionPoint. gtNext/gtPrev links between first and last are already set.
652//
653// Arguments:
654// insertionPoint - The node before which the nodes will be inserted. If non-null, must be part
655// of this range. If null, indicates to insert at the end of the range.
656// first - The first node of the range to insert.
657// last - The last node of the range to insert.
658//
659// Notes:
660// Resulting order:
661// previous insertionPoint->gtPrev <-> first <-> ... <-> last <-> insertionPoint
662//
663void LIR::Range::FinishInsertBefore(GenTree* insertionPoint, GenTree* first, GenTree* last)
664{
665 assert(first != nullptr);
666 assert(last != nullptr);
667 assert(first->gtPrev == nullptr);
668 assert(last->gtNext == nullptr);
669
670 if (insertionPoint == nullptr)
671 {
672 if (m_firstNode == nullptr)
673 {
674 m_firstNode = first;
675 }
676 else
677 {
678 assert(m_lastNode != nullptr);
679 assert(m_lastNode->gtNext == nullptr);
680 m_lastNode->gtNext = first;
681 first->gtPrev = m_lastNode;
682 }
683 m_lastNode = last;
684 }
685 else
686 {
687 assert(Contains(insertionPoint));
688
689 first->gtPrev = insertionPoint->gtPrev;
690 if (first->gtPrev == nullptr)
691 {
692 assert(insertionPoint == m_firstNode);
693 m_firstNode = first;
694 }
695 else
696 {
697 first->gtPrev->gtNext = first;
698 }
699
700 last->gtNext = insertionPoint;
701 insertionPoint->gtPrev = last;
702 }
703}
704
705//------------------------------------------------------------------------
706// LIR::Range::InsertAfter: Inserts a node after another node in this range.
707//
708// Arguments:
709// insertionPoint - The node after which `node` will be inserted. If non-null, must be part
710// of this range. If null, insert at the beginning of the range.
711// node - The node to insert. Must not be part of any range.
712//
713// Notes:
714// Resulting order:
715// insertionPoint <-> node <-> previous insertionPoint->gtNext
716//
717void LIR::Range::InsertAfter(GenTree* insertionPoint, GenTree* node)
718{
719 assert(node != nullptr);
720
721 assert(node->gtNext == nullptr);
722 assert(node->gtPrev == nullptr);
723
724 FinishInsertAfter(insertionPoint, node, node);
725}
726
727//------------------------------------------------------------------------
728// LIR::Range::InsertAfter: Inserts 2 nodes after another node in this range.
729//
730// Arguments:
731// insertionPoint - The node after which the nodes will be inserted. If non-null, must be part
732// of this range. If null, insert at the beginning of the range.
733// node1 - The first node to insert. Must not be part of any range.
734// node2 - The second node to insert. Must not be part of any range. Inserted after node1.
735//
736// Notes:
737// Resulting order:
738// insertionPoint <-> node1 <-> node2 <-> previous insertionPoint->gtNext
739//
740void LIR::Range::InsertAfter(GenTree* insertionPoint, GenTree* node1, GenTree* node2)
741{
742 assert(node1 != nullptr);
743 assert(node2 != nullptr);
744
745 assert(node1->gtNext == nullptr);
746 assert(node1->gtPrev == nullptr);
747 assert(node2->gtNext == nullptr);
748 assert(node2->gtPrev == nullptr);
749
750 node1->gtNext = node2;
751 node2->gtPrev = node1;
752
753 FinishInsertAfter(insertionPoint, node1, node2);
754}
755
756//------------------------------------------------------------------------
757// LIR::Range::InsertAfter: Inserts 3 nodes after another node in this range.
758//
759// Arguments:
760// insertionPoint - The node after which the nodes will be inserted. If non-null, must be part
761// of this range. If null, insert at the beginning of the range.
762// node1 - The first node to insert. Must not be part of any range.
763// node2 - The second node to insert. Must not be part of any range. Inserted after node1.
764// node3 - The third node to insert. Must not be part of any range. Inserted after node2.
765//
766// Notes:
767// Resulting order:
768// insertionPoint <-> node1 <-> node2 <-> node3 <-> previous insertionPoint->gtNext
769//
770void LIR::Range::InsertAfter(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3)
771{
772 assert(node1 != nullptr);
773 assert(node2 != nullptr);
774 assert(node3 != nullptr);
775
776 assert(node1->gtNext == nullptr);
777 assert(node1->gtPrev == nullptr);
778 assert(node2->gtNext == nullptr);
779 assert(node2->gtPrev == nullptr);
780 assert(node3->gtNext == nullptr);
781 assert(node3->gtPrev == nullptr);
782
783 node1->gtNext = node2;
784
785 node2->gtPrev = node1;
786 node2->gtNext = node3;
787
788 node3->gtPrev = node2;
789
790 FinishInsertAfter(insertionPoint, node1, node3);
791}
792
793//------------------------------------------------------------------------
794// LIR::Range::InsertAfter: Inserts 4 nodes after another node in this range.
795//
796// Arguments:
797// insertionPoint - The node after which the nodes will be inserted. If non-null, must be part
798// of this range. If null, insert at the beginning of the range.
799// node1 - The first node to insert. Must not be part of any range.
800// node2 - The second node to insert. Must not be part of any range. Inserted after node1.
801// node3 - The third node to insert. Must not be part of any range. Inserted after node2.
802// node4 - The fourth node to insert. Must not be part of any range. Inserted after node3.
803//
804// Notes:
805// Resulting order:
806// insertionPoint <-> node1 <-> node2 <-> node3 <-> node4 <-> previous insertionPoint->gtNext
807//
808void LIR::Range::InsertAfter(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3, GenTree* node4)
809{
810 assert(node1 != nullptr);
811 assert(node2 != nullptr);
812 assert(node3 != nullptr);
813 assert(node4 != nullptr);
814
815 assert(node1->gtNext == nullptr);
816 assert(node1->gtPrev == nullptr);
817 assert(node2->gtNext == nullptr);
818 assert(node2->gtPrev == nullptr);
819 assert(node3->gtNext == nullptr);
820 assert(node3->gtPrev == nullptr);
821 assert(node4->gtNext == nullptr);
822 assert(node4->gtPrev == nullptr);
823
824 node1->gtNext = node2;
825
826 node2->gtPrev = node1;
827 node2->gtNext = node3;
828
829 node3->gtPrev = node2;
830 node3->gtNext = node4;
831
832 node4->gtPrev = node3;
833
834 FinishInsertAfter(insertionPoint, node1, node4);
835}
836
837//------------------------------------------------------------------------
838// LIR::Range::FinishInsertAfter: Helper function to finalize InsertAfter processing: link the
839// range to insertionPoint. gtNext/gtPrev links between first and last are already set.
840//
841// Arguments:
842// insertionPoint - The node after which the nodes will be inserted. If non-null, must be part
843// of this range. If null, insert at the beginning of the range.
844// first - The first node of the range to insert.
845// last - The last node of the range to insert.
846//
847// Notes:
848// Resulting order:
849// insertionPoint <-> first <-> ... <-> last <-> previous insertionPoint->gtNext
850//
851void LIR::Range::FinishInsertAfter(GenTree* insertionPoint, GenTree* first, GenTree* last)
852{
853 assert(first != nullptr);
854 assert(last != nullptr);
855 assert(first->gtPrev == nullptr);
856 assert(last->gtNext == nullptr);
857
858 if (insertionPoint == nullptr)
859 {
860 if (m_lastNode == nullptr)
861 {
862 m_lastNode = last;
863 }
864 else
865 {
866 assert(m_firstNode != nullptr);
867 assert(m_firstNode->gtPrev == nullptr);
868 m_firstNode->gtPrev = last;
869 last->gtNext = m_firstNode;
870 }
871 m_firstNode = first;
872 }
873 else
874 {
875 assert(Contains(insertionPoint));
876
877 last->gtNext = insertionPoint->gtNext;
878 if (last->gtNext == nullptr)
879 {
880 assert(insertionPoint == m_lastNode);
881 m_lastNode = last;
882 }
883 else
884 {
885 last->gtNext->gtPrev = last;
886 }
887
888 first->gtPrev = insertionPoint;
889 insertionPoint->gtNext = first;
890 }
891}
892
893//------------------------------------------------------------------------
894// LIR::Range::InsertBefore: Inserts a range before another node in `this` range.
895//
896// Arguments:
897// insertionPoint - The node before which the nodes will be inserted. If non-null, must be part
898// of this range. If null, insert at the end of the range.
899// range - The range to splice in.
900//
901void LIR::Range::InsertBefore(GenTree* insertionPoint, Range&& range)
902{
903 assert(!range.IsEmpty());
904 FinishInsertBefore(insertionPoint, range.m_firstNode, range.m_lastNode);
905}
906
907//------------------------------------------------------------------------
908// LIR::Range::InsertAfter: Inserts a range after another node in `this` range.
909//
910// Arguments:
911// insertionPoint - The node after which the nodes will be inserted. If non-null, must be part
912// of this range. If null, insert at the beginning of the range.
913// range - The range to splice in.
914//
915void LIR::Range::InsertAfter(GenTree* insertionPoint, Range&& range)
916{
917 assert(!range.IsEmpty());
918 FinishInsertAfter(insertionPoint, range.m_firstNode, range.m_lastNode);
919}
920
921//------------------------------------------------------------------------
922// LIR::Range::InsertAtBeginning: Inserts a node at the beginning of this range.
923//
924// Arguments:
925// node - The node to insert. Must not be part of any range.
926//
927void LIR::Range::InsertAtBeginning(GenTree* node)
928{
929 InsertBefore(m_firstNode, node);
930}
931
932//------------------------------------------------------------------------
933// LIR::Range::InsertAtEnd: Inserts a node at the end of this range.
934//
935// Arguments:
936// node - The node to insert. Must not be part of any range.
937//
938void LIR::Range::InsertAtEnd(GenTree* node)
939{
940 InsertAfter(m_lastNode, node);
941}
942
943//------------------------------------------------------------------------
944// LIR::Range::InsertAtBeginning: Inserts a range at the beginning of `this` range.
945//
946// Arguments:
947// range - The range to splice in.
948//
949void LIR::Range::InsertAtBeginning(Range&& range)
950{
951 InsertBefore(m_firstNode, std::move(range));
952}
953
954//------------------------------------------------------------------------
955// LIR::Range::InsertAtEnd: Inserts a range at the end of `this` range.
956//
957// Arguments:
958// range - The range to splice in.
959//
960void LIR::Range::InsertAtEnd(Range&& range)
961{
962 InsertAfter(m_lastNode, std::move(range));
963}
964
965//------------------------------------------------------------------------
966// LIR::Range::Remove: Removes a node from this range.
967//
968// Arguments:
969// node - The node to remove. Must be part of this range.
970// markOperandsUnused - If true, marks the node's operands as unused.
971//
972void LIR::Range::Remove(GenTree* node, bool markOperandsUnused)
973{
974 assert(node != nullptr);
975 assert(Contains(node));
976
977 if (markOperandsUnused)
978 {
979 node->VisitOperands([](GenTree* operand) -> GenTree::VisitResult {
980 // The operand of JTRUE does not produce a value (just sets the flags).
981 if (operand->IsValue())
982 {
983 operand->SetUnusedValue();
984 }
985 return GenTree::VisitResult::Continue;
986 });
987 }
988
989 GenTree* prev = node->gtPrev;
990 GenTree* next = node->gtNext;
991
992 if (prev != nullptr)
993 {
994 prev->gtNext = next;
995 }
996 else
997 {
998 assert(node == m_firstNode);
999 m_firstNode = next;
1000 }
1001
1002 if (next != nullptr)
1003 {
1004 next->gtPrev = prev;
1005 }
1006 else
1007 {
1008 assert(node == m_lastNode);
1009 m_lastNode = prev;
1010 }
1011
1012 node->gtPrev = nullptr;
1013 node->gtNext = nullptr;
1014}
1015
1016//------------------------------------------------------------------------
1017// LIR::Range::Remove: Removes a subrange from this range.
1018//
1019// Both the start and the end of the subrange must be part of this range.
1020//
1021// Arguments:
1022// firstNode - The first node in the subrange.
1023// lastNode - The last node in the subrange.
1024//
1025// Returns:
1026// A mutable range containing the removed nodes.
1027//
1028LIR::Range LIR::Range::Remove(GenTree* firstNode, GenTree* lastNode)
1029{
1030 assert(firstNode != nullptr);
1031 assert(lastNode != nullptr);
1032 assert(Contains(firstNode));
1033 assert((firstNode == lastNode) || firstNode->Precedes(lastNode));
1034
1035 GenTree* prev = firstNode->gtPrev;
1036 GenTree* next = lastNode->gtNext;
1037
1038 if (prev != nullptr)
1039 {
1040 prev->gtNext = next;
1041 }
1042 else
1043 {
1044 assert(firstNode == m_firstNode);
1045 m_firstNode = next;
1046 }
1047
1048 if (next != nullptr)
1049 {
1050 next->gtPrev = prev;
1051 }
1052 else
1053 {
1054 assert(lastNode == m_lastNode);
1055 m_lastNode = prev;
1056 }
1057
1058 firstNode->gtPrev = nullptr;
1059 lastNode->gtNext = nullptr;
1060
1061 return Range(firstNode, lastNode);
1062}
1063
1064//------------------------------------------------------------------------
1065// LIR::Range::Remove: Removes a subrange from this range.
1066//
1067// Arguments:
1068// range - The subrange to remove. Must be part of this range.
1069//
1070// Returns:
1071// A mutable range containing the removed nodes.
1072//
1073LIR::Range LIR::Range::Remove(ReadOnlyRange&& range)
1074{
1075 return Remove(range.m_firstNode, range.m_lastNode);
1076}
1077
1078//------------------------------------------------------------------------
1079// LIR::Range::Delete: Deletes a node from this range.
1080//
1081// Note that the deleted node must not be used after this function has
1082// been called.
1083//
1084// Arguments:
1085// node - The node to delete. Must be part of this range.
1086// block - The block that contains the node, if any. May be null.
1087// compiler - The compiler context. May be null if block is null.
1088//
1089void LIR::Range::Delete(Compiler* compiler, BasicBlock* block, GenTree* node)
1090{
1091 assert(node != nullptr);
1092 assert((block == nullptr) == (compiler == nullptr));
1093
1094 Remove(node);
1095 DEBUG_DESTROY_NODE(node);
1096}
1097
1098//------------------------------------------------------------------------
1099// LIR::Range::Delete: Deletes a subrange from this range.
1100//
1101// Both the start and the end of the subrange must be part of this range.
1102// Note that the deleted nodes must not be used after this function has
1103// been called.
1104//
1105// Arguments:
1106// firstNode - The first node in the subrange.
1107// lastNode - The last node in the subrange.
1108// block - The block that contains the subrange, if any. May be null.
1109// compiler - The compiler context. May be null if block is null.
1110//
1111void LIR::Range::Delete(Compiler* compiler, BasicBlock* block, GenTree* firstNode, GenTree* lastNode)
1112{
1113 assert(firstNode != nullptr);
1114 assert(lastNode != nullptr);
1115 assert((block == nullptr) == (compiler == nullptr));
1116
1117 Remove(firstNode, lastNode);
1118
1119 assert(lastNode->gtNext == nullptr);
1120
1121#ifdef DEBUG
1122 // We can't do this in the loop above because it causes `IsPhiNode` to return a false negative
1123 // for `GT_STORE_LCL_VAR` nodes that participate in phi definitions.
1124 for (GenTree* node = firstNode; node != nullptr; node = node->gtNext)
1125 {
1126 DEBUG_DESTROY_NODE(node);
1127 }
1128#endif
1129}
1130
1131//------------------------------------------------------------------------
1132// LIR::Range::Delete: Deletes a subrange from this range.
1133//
1134// Both the start and the end of the subrange must be part of this range.
1135// Note that the deleted nodes must not be used after this function has
1136// been called.
1137//
1138// Arguments:
1139// range - The subrange to delete.
1140// block - The block that contains the subrange, if any. May be null.
1141// compiler - The compiler context. May be null if block is null.
1142//
1143void LIR::Range::Delete(Compiler* compiler, BasicBlock* block, ReadOnlyRange&& range)
1144{
1145 Delete(compiler, block, range.m_firstNode, range.m_lastNode);
1146}
1147
1148//------------------------------------------------------------------------
1149// LIR::Range::TryGetUse: Try to find the use for a given node.
1150//
1151// Arguments:
1152// node - The node for which to find the corresponding use.
1153// use (out) - The use of the corresponding node, if any. Invalid if
1154// this method returns false.
1155//
1156// Return Value: Returns true if a use was found; false otherwise.
1157//
1158bool LIR::Range::TryGetUse(GenTree* node, Use* use)
1159{
1160 assert(node != nullptr);
1161 assert(use != nullptr);
1162 assert(Contains(node));
1163
1164 // Don't bother looking for uses of nodes that are not values.
1165 // If the node is the last node, we won't find a use (and we would
1166 // end up creating an illegal range if we tried).
1167 if (node->IsValue() && !node->IsUnusedValue() && (node != LastNode()))
1168 {
1169 for (GenTree* n : ReadOnlyRange(node->gtNext, m_lastNode))
1170 {
1171 GenTree** edge;
1172 if (n->TryGetUse(node, &edge))
1173 {
1174 *use = Use(*this, edge, n);
1175 return true;
1176 }
1177 }
1178 }
1179
1180 *use = Use();
1181 return false;
1182}
1183
1184//------------------------------------------------------------------------
1185// LIR::Range::GetTreeRange: Computes the subrange that includes all nodes
1186// in the dataflow trees rooted at a particular
1187// set of nodes.
1188//
1189// This method logically uses the following algorithm to compute the
1190// range:
1191//
1192// worklist = { set }
1193// firstNode = start
1194// isClosed = true
1195//
1196// while not worklist.isEmpty:
1197// if not worklist.contains(firstNode):
1198// isClosed = false
1199// else:
1200// for operand in firstNode:
1201// worklist.add(operand)
1202//
1203// worklist.remove(firstNode)
1204//
1205// firstNode = firstNode.previousNode
1206//
1207// return firstNode
1208//
1209// Instead of using a set for the worklist, the implementation uses the
1210// `LIR::Mark` bit of the `GenTree::LIRFlags` field to track whether or
1211// not a node is in the worklist.
1212//
1213// Note also that this algorithm depends LIR nodes being SDSU, SDSU defs
1214// and uses occurring in the same block, and correct dataflow (i.e. defs
1215// occurring before uses).
1216//
1217// Arguments:
1218// root - The root of the dataflow tree.
1219// isClosed - An output parameter that is set to true if the returned
1220// range contains only nodes in the dataflow tree and false
1221// otherwise.
1222//
1223// Returns:
1224// The computed subrange.
1225//
1226LIR::ReadOnlyRange LIR::Range::GetMarkedRange(unsigned markCount,
1227 GenTree* start,
1228 bool* isClosed,
1229 unsigned* sideEffects) const
1230{
1231 assert(markCount != 0);
1232 assert(start != nullptr);
1233 assert(isClosed != nullptr);
1234 assert(sideEffects != nullptr);
1235
1236 bool sawUnmarkedNode = false;
1237 unsigned sideEffectsInRange = 0;
1238
1239 GenTree* firstNode = start;
1240 GenTree* lastNode = nullptr;
1241 for (;;)
1242 {
1243 if ((firstNode->gtLIRFlags & LIR::Flags::Mark) != 0)
1244 {
1245 if (lastNode == nullptr)
1246 {
1247 lastNode = firstNode;
1248 }
1249
1250 // Mark the node's operands
1251 firstNode->VisitOperands([&markCount](GenTree* operand) -> GenTree::VisitResult {
1252 // Do not mark nodes that do not appear in the execution order
1253 if (operand->OperGet() == GT_ARGPLACE)
1254 {
1255 return GenTree::VisitResult::Continue;
1256 }
1257
1258 operand->gtLIRFlags |= LIR::Flags::Mark;
1259 markCount++;
1260 return GenTree::VisitResult::Continue;
1261 });
1262
1263 // Unmark the the node and update `firstNode`
1264 firstNode->gtLIRFlags &= ~LIR::Flags::Mark;
1265 markCount--;
1266 }
1267 else if (lastNode != nullptr)
1268 {
1269 sawUnmarkedNode = true;
1270 }
1271
1272 if (lastNode != nullptr)
1273 {
1274 sideEffectsInRange |= (firstNode->gtFlags & GTF_ALL_EFFECT);
1275 }
1276
1277 if (markCount == 0)
1278 {
1279 break;
1280 }
1281
1282 firstNode = firstNode->gtPrev;
1283
1284 // This assert will fail if the dataflow that feeds the root node
1285 // is incorrect in that it crosses a block boundary or if it involves
1286 // a use that occurs before its corresponding def.
1287 assert(firstNode != nullptr);
1288 }
1289
1290 assert(lastNode != nullptr);
1291
1292 *isClosed = !sawUnmarkedNode;
1293 *sideEffects = sideEffectsInRange;
1294 return ReadOnlyRange(firstNode, lastNode);
1295}
1296
1297//------------------------------------------------------------------------
1298// LIR::Range::GetTreeRange: Computes the subrange that includes all nodes
1299// in the dataflow tree rooted at a particular
1300// node.
1301//
1302// Arguments:
1303// root - The root of the dataflow tree.
1304// isClosed - An output parameter that is set to true if the returned
1305// range contains only nodes in the dataflow tree and false
1306// otherwise.
1307//
1308// Returns:
1309// The computed subrange.
1310LIR::ReadOnlyRange LIR::Range::GetTreeRange(GenTree* root, bool* isClosed) const
1311{
1312 unsigned unused;
1313 return GetTreeRange(root, isClosed, &unused);
1314}
1315
1316//------------------------------------------------------------------------
1317// LIR::Range::GetTreeRange: Computes the subrange that includes all nodes
1318// in the dataflow tree rooted at a particular
1319// node.
1320//
1321// Arguments:
1322// root - The root of the dataflow tree.
1323// isClosed - An output parameter that is set to true if the returned
1324// range contains only nodes in the dataflow tree and false
1325// otherwise.
1326// sideEffects - An output parameter that summarizes the side effects
1327// contained in the returned range.
1328//
1329// Returns:
1330// The computed subrange.
1331LIR::ReadOnlyRange LIR::Range::GetTreeRange(GenTree* root, bool* isClosed, unsigned* sideEffects) const
1332{
1333 assert(root != nullptr);
1334
1335 // Mark the root of the tree
1336 const unsigned markCount = 1;
1337 root->gtLIRFlags |= LIR::Flags::Mark;
1338
1339 return GetMarkedRange(markCount, root, isClosed, sideEffects);
1340}
1341
1342//------------------------------------------------------------------------
1343// LIR::Range::GetTreeRange: Computes the subrange that includes all nodes
1344// in the dataflow trees rooted by the operands
1345// to a particular node.
1346//
1347// Arguments:
1348// root - The root of the dataflow tree.
1349// isClosed - An output parameter that is set to true if the returned
1350// range contains only nodes in the dataflow tree and false
1351// otherwise.
1352// sideEffects - An output parameter that summarizes the side effects
1353// contained in the returned range.
1354//
1355// Returns:
1356// The computed subrange.
1357//
1358LIR::ReadOnlyRange LIR::Range::GetRangeOfOperandTrees(GenTree* root, bool* isClosed, unsigned* sideEffects) const
1359{
1360 assert(root != nullptr);
1361 assert(isClosed != nullptr);
1362 assert(sideEffects != nullptr);
1363
1364 // Mark the root node's operands
1365 unsigned markCount = 0;
1366 root->VisitOperands([&markCount](GenTree* operand) -> GenTree::VisitResult {
1367 operand->gtLIRFlags |= LIR::Flags::Mark;
1368 markCount++;
1369 return GenTree::VisitResult::Continue;
1370 });
1371
1372 if (markCount == 0)
1373 {
1374 *isClosed = true;
1375 *sideEffects = 0;
1376 return ReadOnlyRange();
1377 }
1378
1379 return GetMarkedRange(markCount, root, isClosed, sideEffects);
1380}
1381
1382#ifdef DEBUG
1383
1384//------------------------------------------------------------------------
1385// CheckLclVarSemanticsHelper checks lclVar semantics.
1386//
1387// Specifically, ensure that an unaliasable lclVar is not redefined between the
1388// point at which a use appears in linear order and the point at which it is used by its user.
1389// This ensures that it is always safe to treat a lclVar use as happening at the user (rather than at
1390// the lclVar node).
1391class CheckLclVarSemanticsHelper
1392{
1393public:
1394 //------------------------------------------------------------------------
1395 // CheckLclVarSemanticsHelper constructor: Init arguments for the helper.
1396 //
1397 // This needs unusedDefs because unused lclVar reads may otherwise appear as outstanding reads
1398 // and produce false indications that a write to a lclVar occurs while outstanding reads of that lclVar
1399 // exist.
1400 //
1401 // Arguments:
1402 // compiler - A compiler context.
1403 // range - a range to do the check.
1404 // unusedDefs - map of defs that do no have users.
1405 //
1406 CheckLclVarSemanticsHelper(Compiler* compiler,
1407 const LIR::Range* range,
1408 SmallHashTable<GenTree*, bool, 32U>& unusedDefs)
1409 : compiler(compiler), range(range), unusedDefs(unusedDefs), unusedLclVarReads(compiler->getAllocator())
1410 {
1411 }
1412
1413 //------------------------------------------------------------------------
1414 // Check: do the check.
1415 // Return Value:
1416 // 'true' if the Local variables semantics for the specified range is legal.
1417 bool Check()
1418 {
1419 for (GenTree* node : *range)
1420 {
1421 if (!node->isContained()) // a contained node reads operands in the parent.
1422 {
1423 UseNodeOperands(node);
1424 }
1425
1426 AliasSet::NodeInfo nodeInfo(compiler, node);
1427 if (nodeInfo.IsLclVarRead() && !unusedDefs.Contains(node))
1428 {
1429 int count = 0;
1430 unusedLclVarReads.TryGetValue(nodeInfo.LclNum(), &count);
1431 unusedLclVarReads.AddOrUpdate(nodeInfo.LclNum(), count + 1);
1432 }
1433
1434 // If this node is a lclVar write, it must be to a lclVar that does not have an outstanding read.
1435 assert(!nodeInfo.IsLclVarWrite() || !unusedLclVarReads.Contains(nodeInfo.LclNum()));
1436 }
1437
1438 return true;
1439 }
1440
1441private:
1442 //------------------------------------------------------------------------
1443 // UseNodeOperands: mark the node's operands as used.
1444 //
1445 // Arguments:
1446 // node - the node to use operands from.
1447 void UseNodeOperands(GenTree* node)
1448 {
1449 for (GenTree* operand : node->Operands())
1450 {
1451 if (!operand->IsLIR())
1452 {
1453 // ARGPLACE nodes are not represented in the LIR sequence. Ignore them.
1454 assert(operand->OperIs(GT_ARGPLACE));
1455 continue;
1456 }
1457 if (operand->isContained())
1458 {
1459 UseNodeOperands(operand);
1460 }
1461 AliasSet::NodeInfo operandInfo(compiler, operand);
1462 if (operandInfo.IsLclVarRead())
1463 {
1464 int count;
1465 const bool removed = unusedLclVarReads.TryRemove(operandInfo.LclNum(), &count);
1466 assert(removed);
1467
1468 if (count > 1)
1469 {
1470 unusedLclVarReads.AddOrUpdate(operandInfo.LclNum(), count - 1);
1471 }
1472 }
1473 }
1474 }
1475
1476private:
1477 Compiler* compiler;
1478 const LIR::Range* range;
1479 SmallHashTable<GenTree*, bool, 32U>& unusedDefs;
1480 SmallHashTable<int, int, 32U> unusedLclVarReads;
1481};
1482
1483//------------------------------------------------------------------------
1484// LIR::Range::CheckLIR: Performs a set of correctness checks on the LIR
1485// contained in this range.
1486//
1487// This method checks the following properties:
1488// - Defs are singly-used
1489// - Uses follow defs
1490// - Uses are correctly linked into the block
1491// - Nodes that do not produce values are not used
1492// - Only LIR nodes are present in the block
1493// - If any phi nodes are present in the range, they precede all other
1494// nodes
1495//
1496// The first four properties are verified by walking the range's LIR in execution order,
1497// inserting defs into a set as they are visited, and removing them as they are used. The
1498// different cases are distinguished only when an error is detected.
1499//
1500// Arguments:
1501// compiler - A compiler context.
1502//
1503// Return Value:
1504// 'true' if the LIR for the specified range is legal.
1505//
1506bool LIR::Range::CheckLIR(Compiler* compiler, bool checkUnusedValues) const
1507{
1508 if (IsEmpty())
1509 {
1510 // Nothing more to check.
1511 return true;
1512 }
1513
1514 // Check the gtNext/gtPrev links: (1) ensure there are no circularities, (2) ensure the gtPrev list is
1515 // precisely the inverse of the gtNext list.
1516 //
1517 // To detect circularity, use the "tortoise and hare" 2-pointer algorithm.
1518
1519 GenTree* slowNode = FirstNode();
1520 assert(slowNode != nullptr); // because it's a non-empty range
1521 GenTree* fastNode1 = nullptr;
1522 GenTree* fastNode2 = slowNode;
1523 GenTree* prevSlowNode = nullptr;
1524 while (((fastNode1 = fastNode2->gtNext) != nullptr) && ((fastNode2 = fastNode1->gtNext) != nullptr))
1525 {
1526 if ((slowNode == fastNode1) || (slowNode == fastNode2))
1527 {
1528 assert(!"gtNext nodes have a circularity!");
1529 }
1530 assert(slowNode->gtPrev == prevSlowNode);
1531 prevSlowNode = slowNode;
1532 slowNode = slowNode->gtNext;
1533 assert(slowNode != nullptr); // the fastNodes would have gone null first.
1534 }
1535 // If we get here, the list had no circularities, so either fastNode1 or fastNode2 must be nullptr.
1536 assert((fastNode1 == nullptr) || (fastNode2 == nullptr));
1537
1538 // Need to check the rest of the gtPrev links.
1539 while (slowNode != nullptr)
1540 {
1541 assert(slowNode->gtPrev == prevSlowNode);
1542 prevSlowNode = slowNode;
1543 slowNode = slowNode->gtNext;
1544 }
1545
1546 SmallHashTable<GenTree*, bool, 32> unusedDefs(compiler->getAllocator());
1547
1548 bool pastPhis = false;
1549 GenTree* prev = nullptr;
1550 for (Iterator node = begin(), end = this->end(); node != end; prev = *node, ++node)
1551 {
1552 // Verify that the node is allowed in LIR.
1553 assert(node->IsLIR());
1554
1555 // Some nodes should never be marked unused, as they must be contained in the backend.
1556 // These may be marked as unused during dead code elimination traversal, but they *must* be subsequently
1557 // removed.
1558 assert(!node->IsUnusedValue() || !node->OperIs(GT_FIELD_LIST, GT_LIST, GT_INIT_VAL));
1559
1560 // Verify that the REVERSE_OPS flag is not set. NOTE: if we ever decide to reuse the bit assigned to
1561 // GTF_REVERSE_OPS for an LIR-only flag we will need to move this check to the points at which we
1562 // insert nodes into an LIR range.
1563 assert((node->gtFlags & GTF_REVERSE_OPS) == 0);
1564
1565 // TODO: validate catch arg stores
1566
1567 // Check that all phi nodes (if any) occur at the start of the range.
1568 if ((node->OperGet() == GT_PHI_ARG) || (node->OperGet() == GT_PHI) || node->IsPhiDefn())
1569 {
1570 assert(!pastPhis);
1571 }
1572 else
1573 {
1574 pastPhis = true;
1575 }
1576
1577 for (GenTree** useEdge : node->UseEdges())
1578 {
1579 GenTree* def = *useEdge;
1580
1581 assert(!(checkUnusedValues && def->IsUnusedValue()) && "operands should never be marked as unused values");
1582
1583 if (!def->IsValue())
1584 {
1585 // Stack arguments do not produce a value, but they are considered children of the call.
1586 // It may be useful to remove these from being call operands, but that may also impact
1587 // other code that relies on being able to reach all the operands from a call node.
1588 // The GT_NOP case is because sometimes we eliminate stack argument stores as dead, but
1589 // instead of removing them we replace with a NOP.
1590 // ARGPLACE nodes are not represented in the LIR sequence. Ignore them.
1591 // The argument of a JTRUE doesn't produce a value (just sets a flag).
1592 assert(((node->OperGet() == GT_CALL) &&
1593 (def->OperIsStore() || def->OperIs(GT_PUTARG_STK, GT_NOP, GT_ARGPLACE))) ||
1594 ((node->OperGet() == GT_JTRUE) && (def->TypeGet() == TYP_VOID) &&
1595 ((def->gtFlags & GTF_SET_FLAGS) != 0)));
1596 continue;
1597 }
1598
1599 bool v;
1600 bool foundDef = unusedDefs.TryRemove(def, &v);
1601 if (!foundDef)
1602 {
1603 // First, scan backwards and look for a preceding use.
1604 for (GenTree* prev = *node; prev != nullptr; prev = prev->gtPrev)
1605 {
1606 // TODO: dump the users and the def
1607 GenTree** earlierUseEdge;
1608 bool foundEarlierUse = prev->TryGetUse(def, &earlierUseEdge) && earlierUseEdge != useEdge;
1609 assert(!foundEarlierUse && "found multiply-used LIR node");
1610 }
1611
1612 // The def did not precede the use. Check to see if it exists in the block at all.
1613 for (GenTree* next = node->gtNext; next != nullptr; next = next->gtNext)
1614 {
1615 // TODO: dump the user and the def
1616 assert(next != def && "found def after use");
1617 }
1618
1619 // The def might not be a node that produces a value.
1620 assert(def->IsValue() && "found use of a node that does not produce a value");
1621
1622 // By this point, the only possibility is that the def is not threaded into the LIR sequence.
1623 assert(false && "found use of a node that is not in the LIR sequence");
1624 }
1625 }
1626
1627 if (node->IsValue())
1628 {
1629 bool added = unusedDefs.AddOrUpdate(*node, true);
1630 assert(added);
1631 }
1632 }
1633
1634 assert(prev == m_lastNode);
1635
1636 // At this point the unusedDefs map should contain only unused values.
1637 if (checkUnusedValues)
1638 {
1639 for (auto kvp : unusedDefs)
1640 {
1641 GenTree* node = kvp.Key();
1642 assert(node->IsUnusedValue() && "found an unmarked unused value");
1643 assert(!node->isContained() && "a contained node should have a user");
1644 }
1645 }
1646
1647 CheckLclVarSemanticsHelper checkLclVarSemanticsHelper(compiler, this, unusedDefs);
1648 assert(checkLclVarSemanticsHelper.Check());
1649
1650 return true;
1651}
1652
1653#endif // DEBUG
1654
1655//------------------------------------------------------------------------
1656// LIR::AsRange: Returns an LIR view of the given basic block.
1657//
1658LIR::Range& LIR::AsRange(BasicBlock* block)
1659{
1660 return *static_cast<Range*>(block);
1661}
1662
1663//------------------------------------------------------------------------
1664// LIR::EmptyRange: Constructs and returns an empty range.
1665//
1666// static
1667LIR::Range LIR::EmptyRange()
1668{
1669 return Range(nullptr, nullptr);
1670}
1671
1672//------------------------------------------------------------------------
1673// LIR::SeqTree:
1674// Given a newly created, unsequenced HIR tree, set the evaluation
1675// order (call gtSetEvalOrder) and sequence the tree (set gtNext/gtPrev
1676// pointers by calling fgSetTreeSeq), and return a Range representing
1677// the list of nodes. It is expected this will later be spliced into
1678// an LIR range.
1679//
1680// Arguments:
1681// compiler - The Compiler context.
1682// tree - The tree to sequence.
1683//
1684// Return Value: The newly constructed range.
1685//
1686// static
1687LIR::Range LIR::SeqTree(Compiler* compiler, GenTree* tree)
1688{
1689 // TODO-LIR: it would be great to assert that the tree has not already been
1690 // threaded into an order, but I'm not sure that will be practical at this
1691 // point.
1692
1693 compiler->gtSetEvalOrder(tree);
1694 return Range(compiler->fgSetTreeSeq(tree, nullptr, true), tree);
1695}
1696
1697//------------------------------------------------------------------------
1698// LIR::InsertBeforeTerminator:
1699// Insert an LIR range before the terminating instruction in the given
1700// basic block. If the basic block has no terminating instruction (i.e.
1701// it has a jump kind that is not `BBJ_RETURN`, `BBJ_COND`, or
1702// `BBJ_SWITCH`), the range is inserted at the end of the block.
1703//
1704// Arguments:
1705// block - The block in which to insert the range.
1706// range - The range to insert.
1707//
1708void LIR::InsertBeforeTerminator(BasicBlock* block, LIR::Range&& range)
1709{
1710 LIR::Range& blockRange = LIR::AsRange(block);
1711
1712 GenTree* insertionPoint = nullptr;
1713 if ((block->bbJumpKind == BBJ_COND) || (block->bbJumpKind == BBJ_SWITCH) || (block->bbJumpKind == BBJ_RETURN))
1714 {
1715 insertionPoint = blockRange.LastNode();
1716 assert(insertionPoint != nullptr);
1717
1718#if DEBUG
1719 switch (block->bbJumpKind)
1720 {
1721 case BBJ_COND:
1722 assert(insertionPoint->OperIsConditionalJump());
1723 break;
1724
1725 case BBJ_SWITCH:
1726 assert((insertionPoint->OperGet() == GT_SWITCH) || (insertionPoint->OperGet() == GT_SWITCH_TABLE));
1727 break;
1728
1729 case BBJ_RETURN:
1730 assert((insertionPoint->OperGet() == GT_RETURN) || (insertionPoint->OperGet() == GT_JMP) ||
1731 (insertionPoint->OperGet() == GT_CALL));
1732 break;
1733
1734 default:
1735 unreached();
1736 }
1737#endif
1738 }
1739
1740 blockRange.InsertBefore(insertionPoint, std::move(range));
1741}
1742
1743#ifdef DEBUG
1744void GenTree::dumpLIRFlags()
1745{
1746 JITDUMP("[%c%c]", IsUnusedValue() ? 'U' : '-', IsRegOptional() ? 'O' : '-');
1747}
1748#endif
1749