src/jit/ssarenamestate.cpp

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