dfg/DFGInPlaceAbstractState.cpp

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