1/* 2 * Copyright (C) 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 "DFGIntegerCheckCombiningPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGGraph.h" 32#include "DFGInsertionSet.h" 33#include "DFGPhase.h" 34#include "DFGPredictionPropagationPhase.h" 35#include "DFGVariableAccessDataDump.h" 36#include "JSCInlines.h" 37#include <unordered_map> 38#include <wtf/HashMethod.h> 39 40namespace JSC { namespace DFG { 41 42namespace { 43 44static const bool verbose = false; 45 46enum RangeKind { 47 InvalidRangeKind, 48 49 // This means we did ArithAdd with CheckOverflow. 50 Addition, 51 52 // This means we did CheckInBounds on some length. 53 ArrayBounds 54}; 55 56struct RangeKey { 57 RangeKey() 58 : m_kind(InvalidRangeKind) 59 , m_key(nullptr) 60 { 61 } 62 63 static RangeKey addition(Edge edge) 64 { 65 RangeKey result; 66 result.m_kind = Addition; 67 result.m_source = edge.sanitized(); 68 result.m_key = 0; 69 return result; 70 } 71 72 static RangeKey arrayBounds(Edge edge, Node* key) 73 { 74 RangeKey result; 75 result.m_kind = ArrayBounds; 76 result.m_source = edge.sanitized(); 77 result.m_key = key; 78 return result; 79 } 80 81 bool operator!() const { return m_kind == InvalidRangeKind; } 82 83 unsigned hash() const 84 { 85 return m_kind + m_source.hash() + PtrHash<Node*>::hash(m_key); 86 } 87 88 bool operator==(const RangeKey& other) const 89 { 90 return m_kind == other.m_kind 91 && m_source == other.m_source 92 && m_key == other.m_key; 93 } 94 95 void dump(PrintStream& out) const 96 { 97 switch (m_kind) { 98 case InvalidRangeKind: 99 out.print("InvalidRangeKind("); 100 break; 101 case Addition: 102 out.print("Addition("); 103 break; 104 case ArrayBounds: 105 out.print("ArrayBounds("); 106 break; 107 } 108 out.print(m_source, ", ", m_key, ")"); 109 } 110 111 RangeKind m_kind; 112 Edge m_source; 113 Node* m_key; 114}; 115 116struct RangeKeyAndAddend { 117 RangeKeyAndAddend() 118 : m_addend(0) 119 { 120 } 121 122 RangeKeyAndAddend(RangeKey key, int32_t addend) 123 : m_key(key) 124 , m_addend(addend) 125 { 126 } 127 128 bool operator!() const { return !m_key && !m_addend; } 129 130 void dump(PrintStream& out) const 131 { 132 out.print(m_key, " + ", m_addend); 133 } 134 135 RangeKey m_key; 136 int32_t m_addend; 137}; 138 139struct Range { 140 Range() 141 : m_minBound(0) 142 , m_maxBound(0) 143 , m_count(0) 144 , m_hoisted(false) 145 { 146 } 147 148 void dump(PrintStream& out) const 149 { 150 out.print("(", m_minBound, " @", m_minOrigin, ") .. (", m_maxBound, " @", m_maxOrigin, "), count = ", m_count, ", hoisted = ", m_hoisted); 151 } 152 153 int32_t m_minBound; 154 CodeOrigin m_minOrigin; 155 int32_t m_maxBound; 156 CodeOrigin m_maxOrigin; 157 unsigned m_count; // If this is zero then the bounds won't necessarily make sense. 158 bool m_hoisted; 159}; 160 161} // anonymous namespace 162 163class IntegerCheckCombiningPhase : public Phase { 164public: 165 IntegerCheckCombiningPhase(Graph& graph) 166 : Phase(graph, "integer check combining") 167 , m_insertionSet(graph) 168 { 169 } 170 171 bool run() 172 { 173 ASSERT(m_graph.m_form == SSA); 174 175 m_changed = false; 176 177 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) 178 handleBlock(blockIndex); 179 180 return m_changed; 181 } 182 183private: 184 void handleBlock(BlockIndex blockIndex) 185 { 186 BasicBlock* block = m_graph.block(blockIndex); 187 if (!block) 188 return; 189 190 m_map.clear(); 191 192 // First we collect Ranges. If operations within the range have enough redundancy, 193 // we hoist. And then we remove additions and checks that fall within the max range. 194 195 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { 196 Node* node = block->at(nodeIndex); 197 RangeKeyAndAddend data = rangeKeyAndAddend(node); 198 if (verbose) 199 dataLog("For ", node, ": ", data, "\n"); 200 if (!data) 201 continue; 202 203 Range& range = m_map[data.m_key]; 204 if (verbose) 205 dataLog(" Range: ", range, "\n"); 206 if (range.m_count) { 207 if (data.m_addend > range.m_maxBound) { 208 range.m_maxBound = data.m_addend; 209 range.m_maxOrigin = node->origin.semantic; 210 } else if (data.m_addend < range.m_minBound) { 211 range.m_minBound = data.m_addend; 212 range.m_minOrigin = node->origin.semantic; 213 } 214 } else { 215 range.m_maxBound = data.m_addend; 216 range.m_minBound = data.m_addend; 217 range.m_minOrigin = node->origin.semantic; 218 range.m_maxOrigin = node->origin.semantic; 219 } 220 range.m_count++; 221 if (verbose) 222 dataLog(" New range: ", range, "\n"); 223 } 224 225 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { 226 Node* node = block->at(nodeIndex); 227 RangeKeyAndAddend data = rangeKeyAndAddend(node); 228 if (!data) 229 continue; 230 Range range = m_map[data.m_key]; 231 if (!isValid(data.m_key, range)) 232 continue; 233 234 // Do the hoisting. 235 if (!range.m_hoisted) { 236 switch (data.m_key.m_kind) { 237 case Addition: { 238 if (range.m_minBound < 0) { 239 insertMustAdd( 240 nodeIndex, NodeOrigin(range.m_minOrigin, node->origin.forExit), 241 data.m_key.m_source, range.m_minBound); 242 } 243 if (range.m_maxBound > 0) { 244 insertMustAdd( 245 nodeIndex, NodeOrigin(range.m_maxOrigin, node->origin.forExit), 246 data.m_key.m_source, range.m_maxBound); 247 } 248 break; 249 } 250 251 case ArrayBounds: { 252 Node* minNode; 253 Node* maxNode; 254 255 if (!data.m_key.m_source) { 256 minNode = 0; 257 maxNode = m_insertionSet.insertConstant( 258 nodeIndex, range.m_maxOrigin, jsNumber(range.m_maxBound)); 259 } else { 260 minNode = insertAdd( 261 nodeIndex, NodeOrigin(range.m_minOrigin, node->origin.forExit), 262 data.m_key.m_source, range.m_minBound, Arith::Unchecked); 263 maxNode = insertAdd( 264 nodeIndex, NodeOrigin(range.m_maxOrigin, node->origin.forExit), 265 data.m_key.m_source, range.m_maxBound, Arith::Unchecked); 266 } 267 268 if (minNode) { 269 m_insertionSet.insertNode( 270 nodeIndex, SpecNone, CheckInBounds, node->origin, 271 Edge(minNode, Int32Use), Edge(data.m_key.m_key, Int32Use)); 272 } 273 m_insertionSet.insertNode( 274 nodeIndex, SpecNone, CheckInBounds, node->origin, 275 Edge(maxNode, Int32Use), Edge(data.m_key.m_key, Int32Use)); 276 break; 277 } 278 279 default: 280 RELEASE_ASSERT_NOT_REACHED(); 281 } 282 283 m_changed = true; 284 m_map[data.m_key].m_hoisted = true; 285 } 286 287 // Do the elimination. 288 switch (data.m_key.m_kind) { 289 case Addition: 290 node->setArithMode(Arith::Unchecked); 291 m_changed = true; 292 break; 293 294 case ArrayBounds: 295 node->convertToPhantom(); 296 m_changed = true; 297 break; 298 299 default: 300 RELEASE_ASSERT_NOT_REACHED(); 301 } 302 } 303 304 m_insertionSet.execute(block); 305 } 306 307 RangeKeyAndAddend rangeKeyAndAddend(Node* node) 308 { 309 switch (node->op()) { 310 case ArithAdd: { 311 if (node->arithMode() != Arith::CheckOverflow 312 && node->arithMode() != Arith::CheckOverflowAndNegativeZero) 313 break; 314 if (!m_graph.isInt32Constant(node->child2().node())) 315 break; 316 return RangeKeyAndAddend( 317 RangeKey::addition(node->child1()), 318 m_graph.valueOfInt32Constant(node->child2().node())); 319 } 320 321 case CheckInBounds: { 322 Edge source; 323 int32_t addend; 324 Node* key = node->child2().node(); 325 326 Edge index = node->child1(); 327 328 if (m_graph.isInt32Constant(index.node())) { 329 source = Edge(); 330 addend = m_graph.valueOfInt32Constant(index.node()); 331 } else if ( 332 index->op() == ArithAdd 333 && index->isBinaryUseKind(Int32Use) 334 && m_graph.isInt32Constant(index->child2().node())) { 335 source = index->child1(); 336 addend = m_graph.valueOfInt32Constant(index->child2().node()); 337 } else { 338 source = index; 339 addend = 0; 340 } 341 342 return RangeKeyAndAddend(RangeKey::arrayBounds(source, key), addend); 343 } 344 345 default: 346 break; 347 } 348 349 return RangeKeyAndAddend(); 350 } 351 352 bool isValid(const RangeKey& key, const Range& range) 353 { 354 if (range.m_count < 2) 355 return false; 356 357 switch (key.m_kind) { 358 case ArrayBounds: 359 return (range.m_maxBound - range.m_minBound) >= 0; 360 361 default: 362 return true; 363 } 364 } 365 366 Node* insertAdd( 367 unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend, 368 Arith::Mode arithMode = Arith::CheckOverflow) 369 { 370 if (!addend) 371 return source.node(); 372 return m_insertionSet.insertNode( 373 nodeIndex, source->prediction(), source->result(), 374 ArithAdd, origin, OpInfo(arithMode), source, 375 m_insertionSet.insertConstantForUse( 376 nodeIndex, origin, jsNumber(addend), source.useKind())); 377 } 378 379 Node* insertMustAdd( 380 unsigned nodeIndex, NodeOrigin origin, Edge source, int32_t addend) 381 { 382 Node* result = insertAdd(nodeIndex, origin, source, addend); 383 m_insertionSet.insertNode( 384 nodeIndex, SpecNone, HardPhantom, origin, result->defaultEdge()); 385 return result; 386 } 387 388 typedef std::unordered_map<RangeKey, Range, HashMethod<RangeKey>> RangeMap; 389 RangeMap m_map; 390 391 InsertionSet m_insertionSet; 392 bool m_changed; 393}; 394 395bool performIntegerCheckCombining(Graph& graph) 396{ 397 SamplingRegion samplingRegion("DFG Integer Check Combining Phase"); 398 return runPhase<IntegerCheckCombiningPhase>(graph); 399} 400 401} } // namespace JSC::DFG 402 403#endif // ENABLE(DFG_JIT) 404 405