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 38namespace JSC { namespace DFG { 39 40InPlaceAbstractState::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 47InPlaceAbstractState::~InPlaceAbstractState() { } 48 49void 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 93static 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 103void 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 189bool 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 249void InPlaceAbstractState::reset() 250{ 251 m_block = 0; 252 m_isValid = false; 253 m_branchDirection = InvalidBranchDirection; 254} 255 256bool 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 312bool 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 360inline 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 404inline 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 420