dfg/DFGIntegerCheckCombiningPhase.cpp

   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
  40 namespace JSC { namespace DFG {
  41
  42 namespace {
  43
  44 static const bool verbose = false;
  45
  46 enum 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
  56 struct 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
 116 struct 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
 139 struct 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
 163 class IntegerCheckCombiningPhase : public Phase {
 164 public:
 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
 183 private:
 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
 395 bool 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