1  /*
  2   * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
  3   *
  4   * Redistribution and use in source and binary forms, with or without
  5   * modification, are permitted provided that the following conditions
  6   * are met:
  7   * 1. Redistributions of source code must retain the above copyright
  8   *    notice, this list of conditions and the following disclaimer.
  9   * 2. Redistributions in binary form must reproduce the above copyright
 10   *    notice, this list of conditions and the following disclaimer in the
 11   *    documentation and/or other materials provided with the distribution.
 12   *
 13   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 14   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 15   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 16   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 17   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 18   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 19   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 20   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 21   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 22   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 23   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 24   */
 25  
 26  #include "config.h"
 27  #include "B3FixSSA.h"
 28  
 29  #if ENABLE(B3_JIT)
 30  
 31  #include "B3BreakCriticalEdges.h"
 32  #include "B3InsertionSetInlines.h"
 33  #include "B3PhaseScope.h"
 34  #include "B3ProcedureInlines.h"
 35  #include "B3SSACalculator.h"
 36  #include "B3UpsilonValue.h"
 37  #include "B3ValueInlines.h"
 38  #include "B3Variable.h"
 39  #include "B3VariableLiveness.h"
 40  #include "B3VariableValue.h"
 41  #include <wtf/CommaPrinter.h>
 42  #include <wtf/IndexSet.h>
 43  #include <wtf/IndexSparseSet.h>
 44  
 45  namespace JSC { namespace B3 {
 46  
 47  namespace {
 48  
 49  namespace B3FixSSAInternal {
 50  static constexpr bool verbose = false;
 51  }
 52  
 53  void killDeadVariables(Procedure& proc)
 54  {
 55      IndexSet<Variable*> liveVariables;
 56      for (Value* value : proc.values()) {
 57          if (value->opcode() == Get)
 58              liveVariables.add(value->as<VariableValue>()->variable());
 59      }
 60  
 61      for (Value* value : proc.values()) {
 62          if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
 63              value->replaceWithNop();
 64      }
 65  
 66      for (Variable* variable : proc.variables()) {
 67          if (!liveVariables.contains(variable))
 68              proc.deleteVariable(variable);
 69      }
 70  }
 71  
 72  void fixSSALocally(Procedure& proc)
 73  {
 74      IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
 75      for (BasicBlock* block : proc.blocksInPreOrder()) {
 76          mapping.clear();
 77  
 78          for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
 79              Value* value = block->at(valueIndex);
 80              value->performSubstitution();
 81  
 82              switch (value->opcode()) {
 83              case Get: {
 84                  VariableValue* variableValue = value->as<VariableValue>();
 85                  Variable* variable = variableValue->variable();
 86  
 87                  if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
 88                      value->replaceWithIdentity(replacement->value);
 89                  break;
 90              }
 91                  
 92              case Set: {
 93                  VariableValue* variableValue = value->as<VariableValue>();
 94                  Variable* variable = variableValue->variable();
 95  
 96                  mapping.set(variable->index(), value->child(0));
 97                  break;
 98              }
 99  
100              default:
101                  break;
102              }
103          }
104      }
105  }
106  
107  void fixSSAGlobally(Procedure& proc)
108  {
109      VariableLiveness liveness(proc);
110      
111      // Kill any dead Set's. Each Set creates work for us, so this is profitable.
112      for (BasicBlock* block : proc) {
113          VariableLiveness::LocalCalc localCalc(liveness, block);
114          for (unsigned valueIndex = block->size(); valueIndex--;) {
115              Value* value = block->at(valueIndex);
116              if (value->opcode() == Set && !localCalc.isLive(value->as<VariableValue>()->variable()))
117                  value->replaceWithNop();
118              localCalc.execute(valueIndex);
119          }
120      }
121      
122      VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
123      
124      SSACalculator ssa(proc);
125  
126      // Create a SSACalculator::Variable ("calcVar") for every variable.
127      Vector<Variable*> calcVarToVariable;
128      IndexMap<Variable*, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
129  
130      for (Variable* variable : proc.variables()) {
131          SSACalculator::Variable* calcVar = ssa.newVariable();
132          RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
133          calcVarToVariable.append(variable);
134          variableToCalcVar[variable] = calcVar;
135      }
136  
137      // Create Defs for all of the stores to the stack variable.
138      for (BasicBlock* block : proc) {
139          for (Value* value : *block) {
140              if (value->opcode() != Set)
141                  continue;
142  
143              Variable* variable = value->as<VariableValue>()->variable();
144  
145              if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
146                  ssa.newDef(calcVar, block, value->child(0));
147          }
148      }
149  
150      // Decide where Phis are to be inserted. This creates them but does not insert them.
151      {
152          TimingScope timingScope("fixSSA: computePhis");
153          ssa.computePhis(
154              [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
155                  Variable* variable = calcVarToVariable[calcVar->index()];
156                  if (!liveAtHead.isLiveAtHead(block, variable))
157                      return nullptr;
158                  
159                  Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
160                  if (B3FixSSAInternal::verbose) {
161                      dataLog(
162                          "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
163                          deepDump(proc, phi), "\n");
164                  }
165                  return phi;
166              });
167      }
168  
169      // Now perform the conversion.
170      TimingScope timingScope("fixSSA: convert");
171      InsertionSet insertionSet(proc);
172      IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
173      IndexSet<Value*> valuesToDelete;
174      for (BasicBlock* block : proc.blocksInPreOrder()) {
175          mapping.clear();
176          
177          auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
178              KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
179              if (found)
180                  return found->value;
181              
182              SSACalculator::Variable* calcVar = variableToCalcVar[variable];
183              SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
184              if (def) {
185                  mapping.set(variable->index(), def->value());
186                  return def->value();
187              }
188              
189              return insertionSet.insertBottom(valueIndex, origin, variable->type());
190          };
191  
192          for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
193              Variable* variable = calcVarToVariable[phiDef->variable()->index()];
194  
195              insertionSet.insertValue(0, phiDef->value());
196              mapping.set(variable->index(), phiDef->value());
197          }
198  
199          for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
200              Value* value = block->at(valueIndex);
201              value->performSubstitution();
202  
203              switch (value->opcode()) {
204              case Get: {
205                  VariableValue* variableValue = value->as<VariableValue>();
206                  Variable* variable = variableValue->variable();
207  
208                  value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
209                  valuesToDelete.add(value);
210                  break;
211              }
212                  
213              case Set: {
214                  VariableValue* variableValue = value->as<VariableValue>();
215                  Variable* variable = variableValue->variable();
216  
217                  mapping.set(variable->index(), value->child(0));
218                  value->replaceWithNop();
219                  break;
220              }
221  
222              default:
223                  break;
224              }
225          }
226  
227          unsigned upsilonInsertionPoint = block->size() - 1;
228          Origin upsilonOrigin = block->last()->origin();
229          for (BasicBlock* successorBlock : block->successorBlocks()) {
230              for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
231                  Value* phi = phiDef->value();
232                  SSACalculator::Variable* calcVar = phiDef->variable();
233                  Variable* variable = calcVarToVariable[calcVar->index()];
234  
235                  Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
236                  if (B3FixSSAInternal::verbose) {
237                      dataLog(
238                          "Mapped value for ", *variable, " with successor Phi ", *phi,
239                          " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
240                  }
241                  
242                  insertionSet.insert<UpsilonValue>(
243                      upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
244              }
245          }
246  
247          insertionSet.execute(block);
248      }
249      
250      // This is isn't strictly necessary, but it leaves the IR nice and tidy, which is particularly
251      // useful for phases that do size estimates.
252      for (BasicBlock* block : proc) {
253          block->values().removeAllMatching(
254              [&] (Value* value) -> bool {
255                  if (!valuesToDelete.contains(value) && value->opcode() != Nop)
256                      return false;
257                  
258                  proc.deleteValue(value);
259                  return true;
260              });
261      }
262  
263      if (B3FixSSAInternal::verbose) {
264          dataLog("B3 after SSA conversion:\n");
265          dataLog(proc);
266      }
267  }
268  
269  } // anonymous namespace
270  
271  void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
272  {
273      HashMap<Value*, Variable*> map;
274      HashMap<Value*, Variable*> phiMap;
275  
276      // Create stack slots.
277      for (Value* value : values.values(proc.values())) {
278          map.add(value, proc.addVariable(value->type()));
279  
280          if (value->opcode() == Phi)
281              phiMap.add(value, proc.addVariable(value->type()));
282      }
283  
284      if (B3FixSSAInternal::verbose) {
285          dataLog("Demoting values as follows:\n");
286          dataLog("   map = ");
287          CommaPrinter comma;
288          for (auto& entry : map)
289              dataLog(comma, *entry.key, "=>", *entry.value);
290          dataLog("\n");
291          dataLog("   phiMap = ");
292          comma = CommaPrinter();
293          for (auto& entry : phiMap)
294              dataLog(comma, *entry.key, "=>", *entry.value);
295          dataLog("\n");
296      }
297  
298      // Change accesses to the values to accesses to the stack slots.
299      InsertionSet insertionSet(proc);
300      for (BasicBlock* block : proc) {
301          if (block->numPredecessors()) {
302              // Deal with terminals that produce values (i.e. patchpoint terminals, like the ones we
303              // generate for the allocation fast path).
304              Value* value = block->predecessor(0)->last();
305              Variable* variable = map.get(value);
306              if (variable) {
307                  RELEASE_ASSERT(block->numPredecessors() == 1); // Critical edges better be broken.
308                  insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
309              }
310          }
311          
312          for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
313              Value* value = block->at(valueIndex);
314  
315              if (value->opcode() == Phi) {
316                  if (Variable* variable = phiMap.get(value)) {
317                      value->replaceWithIdentity(
318                          insertionSet.insert<VariableValue>(
319                              valueIndex, Get, value->origin(), variable));
320                  }
321              } else {
322                  for (Value*& child : value->children()) {
323                      if (Variable* variable = map.get(child)) {
324                          child = insertionSet.insert<VariableValue>(
325                              valueIndex, Get, value->origin(), variable);
326                      }
327                  }
328  
329                  if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
330                      if (Variable* variable = phiMap.get(upsilon->phi())) {
331                          insertionSet.insert<VariableValue>(
332                              valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
333                          value->replaceWithNop();
334                      }
335                  }
336              }
337  
338              if (Variable* variable = map.get(value)) {
339                  if (valueIndex + 1 < block->size()) {
340                      insertionSet.insert<VariableValue>(
341                          valueIndex + 1, Set, value->origin(), variable, value);
342                  }
343              }
344          }
345          insertionSet.execute(block);
346      }
347  }
348  
349  bool fixSSA(Procedure& proc)
350  {
351      PhaseScope phaseScope(proc, "fixSSA");
352  
353      if (proc.variables().isEmpty())
354          return false;
355      
356      // Lots of variables have trivial local liveness. We can allocate those without any
357      // trouble.
358      fixSSALocally(proc);
359  
360      // Just for sanity, remove any unused variables first. It's unlikely that this code has any
361      // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
362      // it did arise.
363      killDeadVariables(proc);
364      
365      if (proc.variables().isEmpty())
366          return false;
367      
368      breakCriticalEdges(proc);
369  
370      fixSSAGlobally(proc);
371      
372      return true;
373  }
374  
375  } } // namespace JSC::B3
376  
377  #endif // ENABLE(B3_JIT)
378