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 "ssaconfig.h"
7#include "ssarenamestate.h"
8
9/**
10 * Constructor - initialize the stacks and counters maps (lclVar -> stack/counter) map.
11 *
12 * @params alloc The allocator class used to allocate jitstd data.
13 */
14SsaRenameState::SsaRenameState(CompAllocator alloc, unsigned lvaCount, bool byrefStatesMatchGcHeapStates)
15 : stacks(nullptr)
16 , definedLocs(alloc)
17 , memoryStack(alloc)
18 , lvaCount(lvaCount)
19 , m_alloc(alloc)
20 , byrefStatesMatchGcHeapStates(byrefStatesMatchGcHeapStates)
21{
22}
23
24/**
25 * Allocates memory for holding pointers to lcl's stacks,
26 * if not allocated already.
27 *
28 */
29void SsaRenameState::EnsureStacks()
30{
31 if (stacks == nullptr)
32 {
33 stacks = m_alloc.allocate<Stack*>(lvaCount);
34 for (unsigned i = 0; i < lvaCount; ++i)
35 {
36 stacks[i] = nullptr;
37 }
38 }
39}
40
41/**
42 * Returns a SSA count number for a local variable from top of the stack.
43 *
44 * @params lclNum The local variable def for which a count has to be returned.
45 * @return the current variable name for the "use".
46 *
47 * @remarks If the stack is empty, then we have an use before a def. To handle this
48 * special case, we need to initialize the count with 'default+1', so the
49 * next definition will always use 'default+1' but return 'default' for
50 * all uses until a definition.
51 *
52 */
53unsigned SsaRenameState::CountForUse(unsigned lclNum)
54{
55 EnsureStacks();
56 DBG_SSA_JITDUMP("[SsaRenameState::CountForUse] V%02u\n", lclNum);
57
58 Stack* stack = stacks[lclNum];
59 noway_assert((stack != nullptr) && !stack->empty());
60 return stack->back().m_count;
61}
62
63/**
64 * Pushes a count value on the variable stack.
65 *
66 * @params lclNum The local variable def whose stack the count needs to be pushed onto.
67 * @params count The current count value that needs to be pushed on to the stack.
68 *
69 * @remarks Usually called when renaming a "def."
70 * Create stack lazily when needed for the first time.
71 */
72void SsaRenameState::Push(BasicBlock* bb, unsigned lclNum, unsigned count)
73{
74 EnsureStacks();
75
76 // We'll use BB00 here to indicate the "block before any real blocks..."
77 DBG_SSA_JITDUMP("[SsaRenameState::Push] " FMT_BB ", V%02u, count = %d\n", bb != nullptr ? bb->bbNum : 0, lclNum,
78 count);
79
80 Stack* stack = stacks[lclNum];
81
82 if (stack == nullptr)
83 {
84 DBG_SSA_JITDUMP("\tCreating a new stack\n");
85 stack = stacks[lclNum] = new (m_alloc) Stack(m_alloc);
86 }
87
88 if (stack->empty() || stack->back().m_bb != bb)
89 {
90 stack->push_back(SsaRenameStateForBlock(bb, count));
91 // Remember that we've pushed a def for this loc (so we don't have
92 // to traverse *all* the locs to do the necessary pops later).
93 definedLocs.push_back(SsaRenameStateLocDef(bb, lclNum));
94 }
95 else
96 {
97 stack->back().m_count = count;
98 }
99
100#ifdef DEBUG
101 if (JitTls::GetCompiler()->verboseSsa)
102 {
103 printf("\tContents of the stack: [");
104 for (Stack::iterator iter2 = stack->begin(); iter2 != stack->end(); iter2++)
105 {
106 printf("<" FMT_BB ", %d>", ((*iter2).m_bb != nullptr ? (*iter2).m_bb->bbNum : 0), (*iter2).m_count);
107 }
108 printf("]\n");
109
110 DumpStacks();
111 }
112#endif
113}
114
115void SsaRenameState::PopBlockStacks(BasicBlock* block)
116{
117 DBG_SSA_JITDUMP("[SsaRenameState::PopBlockStacks] " FMT_BB "\n", block->bbNum);
118 // Iterate over the stacks for all the variables, popping those that have an entry
119 // for "block" on top.
120 while (!definedLocs.empty() && definedLocs.back().m_bb == block)
121 {
122 unsigned lclNum = definedLocs.back().m_lclNum;
123 assert(stacks != nullptr); // Cannot be empty because definedLocs is not empty.
124 Stack* stack = stacks[lclNum];
125 assert(stack != nullptr);
126 assert(stack->back().m_bb == block);
127 stack->pop_back();
128 definedLocs.pop_back();
129 }
130#ifdef DEBUG
131 // It should now be the case that no stack in stacks has an entry for "block" on top --
132 // the loop above popped them all.
133 for (unsigned i = 0; i < lvaCount; ++i)
134 {
135 if (stacks != nullptr && stacks[i] != nullptr && !stacks[i]->empty())
136 {
137 assert(stacks[i]->back().m_bb != block);
138 }
139 }
140 if (JitTls::GetCompiler()->verboseSsa)
141 {
142 DumpStacks();
143 }
144#endif // DEBUG
145}
146
147void SsaRenameState::PopBlockMemoryStack(MemoryKind memoryKind, BasicBlock* block)
148{
149 auto& stack = memoryStack[memoryKind];
150 while (stack.size() > 0 && stack.back().m_bb == block)
151 {
152 stack.pop_back();
153 }
154}
155
156#ifdef DEBUG
157/**
158 * Print the stack data for each variable in a loop.
159 */
160void SsaRenameState::DumpStacks()
161{
162 printf("Dumping stacks:\n-------------------------------\n");
163 if (lvaCount == 0)
164 {
165 printf("None\n");
166 }
167 else
168 {
169 EnsureStacks();
170 for (unsigned i = 0; i < lvaCount; ++i)
171 {
172 Stack* stack = stacks[i];
173 printf("V%02u:\t", i);
174 if (stack != nullptr)
175 {
176 for (Stack::iterator iter2 = stack->begin(); iter2 != stack->end(); ++iter2)
177 {
178 if (iter2 != stack->begin())
179 {
180 printf(", ");
181 }
182 printf("<" FMT_BB ", %2d>", ((*iter2).m_bb != nullptr ? (*iter2).m_bb->bbNum : 0),
183 (*iter2).m_count);
184 }
185 }
186 printf("\n");
187 }
188 }
189}
190#endif // DEBUG
191