dfg/DFGInPlaceAbstractState.cpp

   1 /*
   2  * Copyright (C) 2013-2015 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 "DFGInPlaceAbstractState.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "CodeBlock.h"
  32 #include "DFGBasicBlock.h"
  33 #include "GetByIdStatus.h"
  34 #include "JSCInlines.h"
  35 #include "PutByIdStatus.h"
  36 #include "StringObject.h"
  37
  38 namespace JSC { namespace DFG {
  39
  40 static const bool verbose = false;
  41
  42 InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
  43     : m_graph(graph)
  44     , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
  45     , m_block(0)
  46 {
  47 }
  48
  49 InPlaceAbstractState::~InPlaceAbstractState() { }
  50
  51 void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
  52 {
  53     ASSERT(!m_block);
  54
  55     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
  56     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
  57     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
  58
  59     for (size_t i = 0; i < basicBlock->size(); i++)
  60         forNode(basicBlock->at(i)).clear();
  61
  62     m_variables = basicBlock->valuesAtHead;
  63
  64     if (m_graph.m_form == SSA) {
  65         HashMap<Node*, AbstractValue>::iterator iter = basicBlock->ssa->valuesAtHead.begin();
  66         HashMap<Node*, AbstractValue>::iterator end = basicBlock->ssa->valuesAtHead.end();
  67         for (; iter != end; ++iter)
  68             forNode(iter->key) = iter->value;
  69     }
  70     basicBlock->cfaShouldRevisit = false;
  71     basicBlock->cfaHasVisited = true;
  72     m_block = basicBlock;
  73     m_isValid = true;
  74     m_foundConstants = false;
  75     m_branchDirection = InvalidBranchDirection;
  76     m_structureClobberState = basicBlock->cfaStructureClobberStateAtHead;
  77 }
  78
  79 static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
  80 {
  81     values.clear();
  82
  83     HashSet<Node*>::iterator iter = live.begin();
  84     HashSet<Node*>::iterator end = live.end();
  85     for (; iter != end; ++iter)
  86         values.add(*iter, AbstractValue());
  87 }
  88
  89 void InPlaceAbstractState::initialize()
  90 {
  91     BasicBlock* root = m_graph.block(0);
  92     root->cfaShouldRevisit = true;
  93     root->cfaHasVisited = false;
  94     root->cfaFoundConstants = false;
  95     root->cfaStructureClobberStateAtHead = StructuresAreWatched;
  96     root->cfaStructureClobberStateAtTail = StructuresAreWatched;
  97     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
  98         root->valuesAtTail.argument(i).clear();
  99
 100         FlushFormat format;
 101         if (m_graph.m_form == SSA)
 102             format = m_graph.m_argumentFormats[i];
 103         else {
 104             Node* node = m_graph.m_arguments[i];
 105             if (!node)
 106                 format = FlushedJSValue;
 107             else {
 108                 ASSERT(node->op() == SetArgument);
 109                 format = node->variableAccessData()->flushFormat();
 110             }
 111         }
 112
 113         switch (format) {
 114         case FlushedInt32:
 115             root->valuesAtHead.argument(i).setType(SpecInt32);
 116             break;
 117         case FlushedBoolean:
 118             root->valuesAtHead.argument(i).setType(SpecBoolean);
 119             break;
 120         case FlushedCell:
 121             root->valuesAtHead.argument(i).setType(m_graph, SpecCell);
 122             break;
 123         case FlushedJSValue:
 124             root->valuesAtHead.argument(i).makeHeapTop();
 125             break;
 126         default:
 127             DFG_CRASH(m_graph, nullptr, "Bad flush format for argument");
 128             break;
 129         }
 130     }
 131     for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
 132         root->valuesAtHead.local(i).clear();
 133         root->valuesAtTail.local(i).clear();
 134     }
 135     for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
 136         BasicBlock* block = m_graph.block(blockIndex);
 137         if (!block)
 138             continue;
 139         ASSERT(block->isReachable);
 140         block->cfaShouldRevisit = false;
 141         block->cfaHasVisited = false;
 142         block->cfaFoundConstants = false;
 143         block->cfaStructureClobberStateAtHead = StructuresAreWatched;
 144         block->cfaStructureClobberStateAtTail = StructuresAreWatched;
 145         for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
 146             block->valuesAtHead.argument(i).clear();
 147             block->valuesAtTail.argument(i).clear();
 148         }
 149         for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
 150             block->valuesAtHead.local(i).clear();
 151             block->valuesAtTail.local(i).clear();
 152         }
 153     }
 154     if (m_graph.m_form == SSA) {
 155         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
 156             BasicBlock* block = m_graph.block(blockIndex);
 157             if (!block)
 158                 continue;
 159             setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
 160             setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
 161         }
 162     }
 163 }
 164
 165 bool InPlaceAbstractState::endBasicBlock(MergeMode mergeMode)
 166 {
 167     ASSERT(m_block);
 168
 169     BasicBlock* block = m_block; // Save the block for successor merging.
 170
 171     block->cfaFoundConstants = m_foundConstants;
 172     block->cfaDidFinish = m_isValid;
 173     block->cfaBranchDirection = m_branchDirection;
 174
 175     if (!m_isValid) {
 176         reset();
 177         return false;
 178     }
 179
 180     bool changed = false;
 181
 182     if ((mergeMode != DontMerge) || !ASSERT_DISABLED) {
 183         changed |= checkAndSet(block->cfaStructureClobberStateAtTail, m_structureClobberState);
 184
 185         switch (m_graph.m_form) {
 186         case ThreadedCPS: {
 187             for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
 188                 AbstractValue& destination = block->valuesAtTail.argument(argument);
 189                 changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
 190             }
 191
 192             for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
 193                 AbstractValue& destination = block->valuesAtTail.local(local);
 194                 changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
 195             }
 196             break;
 197         }
 198
 199         case SSA: {
 200             for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
 201                 changed |= block->valuesAtTail[i].merge(m_variables[i]);
 202
 203             HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
 204             HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
 205             for (; iter != end; ++iter) {
 206                 Node* node = *iter;
 207                 changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
 208             }
 209             break;
 210         }
 211
 212         default:
 213             RELEASE_ASSERT_NOT_REACHED();
 214         }
 215     }
 216
 217     ASSERT(mergeMode != DontMerge || !changed);
 218
 219     reset();
 220
 221     if (mergeMode != MergeToSuccessors)
 222         return changed;
 223
 224     return mergeToSuccessors(block);
 225 }
 226
 227 void InPlaceAbstractState::reset()
 228 {
 229     m_block = 0;
 230     m_isValid = false;
 231     m_branchDirection = InvalidBranchDirection;
 232     m_structureClobberState = StructuresAreWatched;
 233 }
 234
 235 bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
 236 {
 237     if (!node)
 238         return false;
 239
 240     AbstractValue source;
 241
 242     switch (node->op()) {
 243     case Phi:
 244     case SetArgument:
 245     case PhantomLocal:
 246     case Flush:
 247         // The block transfers the value from head to tail.
 248         source = inVariable;
 249         break;
 250
 251     case GetLocal:
 252         // The block refines the value with additional speculations.
 253         source = forNode(node);
 254         break;
 255
 256     case SetLocal:
 257         // The block sets the variable, and potentially refines it, both
 258         // before and after setting it.
 259         source = forNode(node->child1());
 260         if (node->variableAccessData()->flushFormat() == FlushedDouble)
 261             RELEASE_ASSERT(!(source.m_type & ~SpecFullDouble));
 262         break;
 263
 264     default:
 265         RELEASE_ASSERT_NOT_REACHED();
 266         break;
 267     }
 268
 269     if (destination == source) {
 270         // Abstract execution did not change the output value of the variable, for this
 271         // basic block, on this iteration.
 272         return false;
 273     }
 274
 275     // Abstract execution reached a new conclusion about the speculations reached about
 276     // this variable after execution of this basic block. Update the state, and return
 277     // true to indicate that the fixpoint must go on!
 278     destination = source;
 279     return true;
 280 }
 281
 282 bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
 283 {
 284     if (verbose)
 285         dataLog("   Merging from ", pointerDump(from), " to ", pointerDump(to), "\n");
 286     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
 287     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
 288
 289     bool changed = false;
 290
 291     changed |= checkAndSet(
 292         to->cfaStructureClobberStateAtHead,
 293         DFG::merge(from->cfaStructureClobberStateAtTail, to->cfaStructureClobberStateAtHead));
 294
 295     switch (m_graph.m_form) {
 296     case ThreadedCPS: {
 297         for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
 298             AbstractValue& destination = to->valuesAtHead.argument(argument);
 299             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
 300         }
 301
 302         for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
 303             AbstractValue& destination = to->valuesAtHead.local(local);
 304             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
 305         }
 306         break;
 307     }
 308
 309     case SSA: {
 310         for (size_t i = from->valuesAtTail.size(); i--;)
 311             changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
 312
 313         HashSet<Node*>::iterator iter = to->ssa->liveAtHead.begin();
 314         HashSet<Node*>::iterator end = to->ssa->liveAtHead.end();
 315         for (; iter != end; ++iter) {
 316             Node* node = *iter;
 317             if (verbose)
 318                 dataLog("      Merging for ", node, ": from ", from->ssa->valuesAtTail.find(node)->value, " to ", to->ssa->valuesAtHead.find(node)->value, "\n");
 319             changed |= to->ssa->valuesAtHead.find(node)->value.merge(
 320                 from->ssa->valuesAtTail.find(node)->value);
 321             if (verbose)
 322                 dataLog("         Result: ", to->ssa->valuesAtHead.find(node)->value, "\n");
 323         }
 324         break;
 325     }
 326
 327     default:
 328         RELEASE_ASSERT_NOT_REACHED();
 329         break;
 330     }
 331
 332     if (!to->cfaHasVisited)
 333         changed = true;
 334
 335     if (verbose)
 336         dataLog("      Will revisit: ", changed, "\n");
 337     to->cfaShouldRevisit |= changed;
 338
 339     return changed;
 340 }
 341
 342 inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
 343 {
 344     Node* terminal = basicBlock->terminal();
 345
 346     ASSERT(terminal->isTerminal());
 347
 348     switch (terminal->op()) {
 349     case Jump: {
 350         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
 351         return merge(basicBlock, terminal->targetBlock());
 352     }
 353
 354     case Branch: {
 355         ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
 356         bool changed = false;
 357         if (basicBlock->cfaBranchDirection != TakeFalse)
 358             changed |= merge(basicBlock, terminal->branchData()->taken.block);
 359         if (basicBlock->cfaBranchDirection != TakeTrue)
 360             changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
 361         return changed;
 362     }
 363
 364     case Switch: {
 365         // FIXME: It would be cool to be sparse conditional for Switch's. Currently
 366         // we're not. However I somehow doubt that this will ever be a big deal.
 367         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
 368         SwitchData* data = terminal->switchData();
 369         bool changed = merge(basicBlock, data->fallThrough.block);
 370         for (unsigned i = data->cases.size(); i--;)
 371             changed |= merge(basicBlock, data->cases[i].target.block);
 372         return changed;
 373     }
 374
 375     case Return:
 376     case Unreachable:
 377         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
 378         return false;
 379
 380     default:
 381         RELEASE_ASSERT_NOT_REACHED();
 382         return false;
 383     }
 384 }
 385
 386 inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
 387 {
 388     if (!destinationNode)
 389         return false;
 390
 391     ASSERT_UNUSED(sourceNode, sourceNode);
 392
 393     // FIXME: We could do some sparse conditional propagation here!
 394
 395     return destination.merge(source);
 396 }
 397
 398 } } // namespace JSC::DFG
 399
 400 #endif // ENABLE(DFG_JIT)
 401