text: /*
   * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in the
   *    documentation and/or other materials provided with the distribution.
   *
   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
   */
  
  #include "config.h"
  #include "B3FixSSA.h"
  
  #if ENABLE(B3_JIT)
  
  #include "B3BasicBlockInlines.h"
  #include "B3BreakCriticalEdges.h"
  #include "B3Dominators.h"
  #include "B3InsertionSetInlines.h"
  #include "B3PhaseScope.h"
  #include "B3ProcedureInlines.h"
  #include "B3SSACalculator.h"
  #include "B3UpsilonValue.h"
  #include "B3ValueInlines.h"
  #include "B3Variable.h"
  #include "B3VariableLiveness.h"
  #include "B3VariableValue.h"
  #include <wtf/CommaPrinter.h>
  #include <wtf/IndexSet.h>
  #include <wtf/IndexSparseSet.h>
  
  namespace JSC { namespace B3 {
  
  namespace {
  
  const bool verbose = false;
  
  void killDeadVariables(Procedure& proc)
  {
      IndexSet<Variable*> liveVariables;
      for (Value* value : proc.values()) {
          if (value->opcode() == Get)
              liveVariables.add(value->as<VariableValue>()->variable());
      }
  
      for (Value* value : proc.values()) {
          if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
              value->replaceWithNop();
      }
  
      for (Variable* variable : proc.variables()) {
          if (!liveVariables.contains(variable))
              proc.deleteVariable(variable);
      }
  }
  
  void fixSSALocally(Procedure& proc)
  {
      IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
      for (BasicBlock* block : proc.blocksInPreOrder()) {
          mapping.clear();
  
          for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
              Value* value = block->at(valueIndex);
              value->performSubstitution();
  
              switch (value->opcode()) {
              case Get: {
                  VariableValue* variableValue = value->as<VariableValue>();
                  Variable* variable = variableValue->variable();
  
                  if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
                      value->replaceWithIdentity(replacement->value);
                  break;
              }
                  
              case Set: {
                  VariableValue* variableValue = value->as<VariableValue>();
                  Variable* variable = variableValue->variable();
  
                  mapping.set(variable->index(), value->child(0));
                  break;
              }
  
              default:
                  break;
              }
          }
      }
  }
  
  void fixSSAGlobally(Procedure& proc)
  {
      VariableLiveness liveness(proc);
      
      // Kill any dead Set's. Each Set creates work for us, so this is profitable.
      for (BasicBlock* block : proc) {
          VariableLiveness::LocalCalc localCalc(liveness, block);
          for (unsigned valueIndex = block->size(); valueIndex--;) {
              Value* value = block->at(valueIndex);
              if (value->opcode() == Set && !localCalc.isLive(value->as<VariableValue>()->variable()))
                  value->replaceWithNop();
              localCalc.execute(valueIndex);
          }
      }
      
      VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
      
      SSACalculator ssa(proc);
  
      // Create a SSACalculator::Variable ("calcVar") for every variable.
      Vector<Variable*> calcVarToVariable;
      IndexMap<Variable*, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
  
      for (Variable* variable : proc.variables()) {
          SSACalculator::Variable* calcVar = ssa.newVariable();
          RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
          calcVarToVariable.append(variable);
          variableToCalcVar[variable] = calcVar;
      }
  
      // Create Defs for all of the stores to the stack variable.
      for (BasicBlock* block : proc) {
          for (Value* value : *block) {
              if (value->opcode() != Set)
                  continue;
  
              Variable* variable = value->as<VariableValue>()->variable();
  
              if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
                  ssa.newDef(calcVar, block, value->child(0));
          }
      }
  
      // Decide where Phis are to be inserted. This creates them but does not insert them.
      {
          TimingScope timingScope("fixSSA: computePhis");
          ssa.computePhis(
              [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
                  Variable* variable = calcVarToVariable[calcVar->index()];
                  if (!liveAtHead.isLiveAtHead(block, variable))
                      return nullptr;
                  
                  Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
                  if (verbose) {
                      dataLog(
                          "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
                          deepDump(proc, phi), "\n");
                  }
                  return phi;
              });
      }
  
      // Now perform the conversion.
      TimingScope timingScope("fixSSA: convert");
      InsertionSet insertionSet(proc);
      IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
      for (BasicBlock* block : proc.blocksInPreOrder()) {
          mapping.clear();
          
          auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
              KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
              if (found)
                  return found->value;
              
              SSACalculator::Variable* calcVar = variableToCalcVar[variable];
              SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
              if (def) {
                  mapping.set(variable->index(), def->value());
                  return def->value();
              }
              
              return insertionSet.insertBottom(valueIndex, origin, variable->type());
          };
  
          for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
              Variable* variable = calcVarToVariable[phiDef->variable()->index()];
  
              insertionSet.insertValue(0, phiDef->value());
              mapping.set(variable->index(), phiDef->value());
          }
  
          for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
              Value* value = block->at(valueIndex);
              value->performSubstitution();
  
              switch (value->opcode()) {
              case Get: {
                  VariableValue* variableValue = value->as<VariableValue>();
                  Variable* variable = variableValue->variable();
  
                  value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
                  break;
              }
                  
              case Set: {
                  VariableValue* variableValue = value->as<VariableValue>();
                  Variable* variable = variableValue->variable();
  
                  mapping.set(variable->index(), value->child(0));
                  value->replaceWithNop();
                  break;
              }
  
              default:
                  break;
              }
          }
  
          unsigned upsilonInsertionPoint = block->size() - 1;
          Origin upsilonOrigin = block->last()->origin();
          for (BasicBlock* successorBlock : block->successorBlocks()) {
              for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
                  Value* phi = phiDef->value();
                  SSACalculator::Variable* calcVar = phiDef->variable();
                  Variable* variable = calcVarToVariable[calcVar->index()];
  
                  Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
                  if (verbose) {
                      dataLog(
                          "Mapped value for ", *variable, " with successor Phi ", *phi,
                          " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
                  }
                  
                  insertionSet.insert<UpsilonValue>(
                      upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
              }
          }
  
          insertionSet.execute(block);
      }
  
      if (verbose) {
          dataLog("B3 after SSA conversion:\n");
          dataLog(proc);
      }
  }
  
  } // anonymous namespace
  
  void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
  {
      HashMap<Value*, Variable*> map;
      HashMap<Value*, Variable*> phiMap;
  
      // Create stack slots.
      for (Value* value : values.values(proc.values())) {
          map.add(value, proc.addVariable(value->type()));
  
          if (value->opcode() == Phi)
              phiMap.add(value, proc.addVariable(value->type()));
      }
  
      if (verbose) {
          dataLog("Demoting values as follows:\n");
          dataLog("   map = ");
          CommaPrinter comma;
          for (auto& entry : map)
              dataLog(comma, *entry.key, "=>", *entry.value);
          dataLog("\n");
          dataLog("   phiMap = ");
          comma = CommaPrinter();
          for (auto& entry : phiMap)
              dataLog(comma, *entry.key, "=>", *entry.value);
          dataLog("\n");
      }
  
      // Change accesses to the values to accesses to the stack slots.
      InsertionSet insertionSet(proc);
      for (BasicBlock* block : proc) {
          for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
              Value* value = block->at(valueIndex);
  
              if (value->opcode() == Phi) {
                  if (Variable* variable = phiMap.get(value)) {
                      value->replaceWithIdentity(
                          insertionSet.insert<VariableValue>(
                              valueIndex, Get, value->origin(), variable));
                  }
              } else {
                  for (Value*& child : value->children()) {
                      if (Variable* variable = map.get(child)) {
                          child = insertionSet.insert<VariableValue>(
                              valueIndex, Get, value->origin(), variable);
                      }
                  }
  
                  if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
                      if (Variable* variable = phiMap.get(upsilon->phi())) {
                          insertionSet.insert<VariableValue>(
                              valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
                          value->replaceWithNop();
                      }
                  }
              }
  
              if (Variable* variable = map.get(value)) {
                  insertionSet.insert<VariableValue>(
                      valueIndex + 1, Set, value->origin(), variable, value);
              }
          }
          insertionSet.execute(block);
      }
  }
  
  bool fixSSA(Procedure& proc)
  {
      PhaseScope phaseScope(proc, "fixSSA");
  
      // Lots of variables have trivial local liveness. We can allocate those without any
      // trouble.
      fixSSALocally(proc);
  
      // Just for sanity, remove any unused variables first. It's unlikely that this code has any
      // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
      // it did arise.
      killDeadVariables(proc);
      
      if (proc.variables().isEmpty())
          return false;
      
      // We know that we have variables to optimize, so do that now.
      breakCriticalEdges(proc);
  
      fixSSAGlobally(proc);
      
      return true;
  }
  
  } } // namespace JSC::B3
  
  #endif // ENABLE(B3_JIT)
  
  