js/src/jsapi-tests/testJitGVN.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  */
   4 /* This Source Code Form is subject to the terms of the Mozilla Public
   5  * License, v. 2.0. If a copy of the MPL was not distributed with this
   6  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   7
   8 #include "jit/IonAnalysis.h"
   9 #include "jit/MIRGenerator.h"
  10 #include "jit/MIRGraph.h"
  11 #include "jit/RangeAnalysis.h"
  12 #include "jit/ValueNumbering.h"
  13
  14 #include "jsapi-tests/testJitMinimalFunc.h"
  15 #include "jsapi-tests/tests.h"
  16
  17 using namespace js;
  18 using namespace js::jit;
  19
  20 static MBasicBlock* FollowTrivialGotos(MBasicBlock* block) {
  21   while (block->phisEmpty() && *block->begin() == block->lastIns() &&
  22          block->lastIns()->isGoto()) {
  23     block = block->lastIns()->toGoto()->getSuccessor(0);
  24   }
  25   return block;
  26 }
  27
  28 BEGIN_TEST(testJitGVN_FixupOSROnlyLoop) {
  29   // This is a testcase which constructs the very rare circumstances that
  30   // require the FixupOSROnlyLoop logic.
  31
  32   MinimalFunc func;
  33
  34   MBasicBlock* entry = func.createEntryBlock();
  35   MBasicBlock* osrEntry = func.createOsrEntryBlock();
  36   MBasicBlock* outerHeader = func.createBlock(entry);
  37   MBasicBlock* merge = func.createBlock(outerHeader);
  38   MBasicBlock* innerHeader = func.createBlock(merge);
  39   MBasicBlock* innerBackedge = func.createBlock(innerHeader);
  40   MBasicBlock* outerBackedge = func.createBlock(innerHeader);
  41   MBasicBlock* exit = func.createBlock(outerHeader);
  42
  43   MConstant* c = MConstant::New(func.alloc, BooleanValue(false));
  44   entry->add(c);
  45   entry->end(MTest::New(func.alloc, c, outerHeader, exit));
  46   osrEntry->end(MGoto::New(func.alloc, merge));
  47
  48   merge->end(MGoto::New(func.alloc, innerHeader));
  49
  50   // Use Beta nodes to hide the constants and suppress folding.
  51   MConstant* x = MConstant::New(func.alloc, BooleanValue(false));
  52   outerHeader->add(x);
  53   MBeta* xBeta =
  54       MBeta::New(func.alloc, x, Range::NewInt32Range(func.alloc, 0, 1));
  55   outerHeader->add(xBeta);
  56   outerHeader->end(MTest::New(func.alloc, xBeta, merge, exit));
  57
  58   MConstant* y = MConstant::New(func.alloc, BooleanValue(false));
  59   innerHeader->add(y);
  60   MBeta* yBeta =
  61       MBeta::New(func.alloc, y, Range::NewInt32Range(func.alloc, 0, 1));
  62   innerHeader->add(yBeta);
  63   innerHeader->end(MTest::New(func.alloc, yBeta, innerBackedge, outerBackedge));
  64
  65   innerBackedge->end(MGoto::New(func.alloc, innerHeader));
  66   outerBackedge->end(MGoto::New(func.alloc, outerHeader));
  67
  68   MConstant* u = MConstant::New(func.alloc, UndefinedValue());
  69   exit->add(u);
  70   exit->end(MReturn::New(func.alloc, u));
  71
  72   MOZ_ALWAYS_TRUE(innerHeader->addPredecessorWithoutPhis(innerBackedge));
  73   MOZ_ALWAYS_TRUE(outerHeader->addPredecessorWithoutPhis(outerBackedge));
  74   MOZ_ALWAYS_TRUE(exit->addPredecessorWithoutPhis(entry));
  75   MOZ_ALWAYS_TRUE(merge->addPredecessorWithoutPhis(osrEntry));
  76
  77   outerHeader->setLoopHeader(outerBackedge);
  78   innerHeader->setLoopHeader(innerBackedge);
  79
  80   if (!func.runGVN()) {
  81     return false;
  82   }
  83
  84   // The loops are no longer reachable from the normal entry. They are
  85   // doinated by the osrEntry.
  86   MOZ_RELEASE_ASSERT(func.graph.osrBlock() == osrEntry);
  87   MBasicBlock* newInner =
  88       FollowTrivialGotos(osrEntry->lastIns()->toGoto()->target());
  89   MBasicBlock* newOuter =
  90       FollowTrivialGotos(newInner->lastIns()->toTest()->ifFalse());
  91   MBasicBlock* newExit = FollowTrivialGotos(entry);
  92   MOZ_RELEASE_ASSERT(newInner->isLoopHeader());
  93   MOZ_RELEASE_ASSERT(newOuter->isLoopHeader());
  94   MOZ_RELEASE_ASSERT(newExit->lastIns()->isReturn());
  95
  96   // One more time.
  97   ClearDominatorTree(func.graph);
  98   if (!func.runGVN()) {
  99     return false;
 100   }
 101
 102   // The loops are no longer reachable from the normal entry. They are
 103   // doinated by the osrEntry.
 104   MOZ_RELEASE_ASSERT(func.graph.osrBlock() == osrEntry);
 105   newInner = FollowTrivialGotos(osrEntry->lastIns()->toGoto()->target());
 106   newOuter = FollowTrivialGotos(newInner->lastIns()->toTest()->ifFalse());
 107   newExit = FollowTrivialGotos(entry);
 108   MOZ_RELEASE_ASSERT(newInner->isLoopHeader());
 109   MOZ_RELEASE_ASSERT(newOuter->isLoopHeader());
 110   MOZ_RELEASE_ASSERT(newExit->lastIns()->isReturn());
 111
 112   return true;
 113 }
 114 END_TEST(testJitGVN_FixupOSROnlyLoop)
 115
 116 BEGIN_TEST(testJitGVN_FixupOSROnlyLoopNested) {
 117   // Same as testJitGVN_FixupOSROnlyLoop but adds another level of loop
 118   // nesting for added excitement.
 119
 120   MinimalFunc func;
 121
 122   MBasicBlock* entry = func.createEntryBlock();
 123   MBasicBlock* osrEntry = func.createOsrEntryBlock();
 124   MBasicBlock* outerHeader = func.createBlock(entry);
 125   MBasicBlock* middleHeader = func.createBlock(outerHeader);
 126   MBasicBlock* merge = func.createBlock(middleHeader);
 127   MBasicBlock* innerHeader = func.createBlock(merge);
 128   MBasicBlock* innerBackedge = func.createBlock(innerHeader);
 129   MBasicBlock* middleBackedge = func.createBlock(innerHeader);
 130   MBasicBlock* outerBackedge = func.createBlock(middleHeader);
 131   MBasicBlock* exit = func.createBlock(outerHeader);
 132
 133   MConstant* c = MConstant::New(func.alloc, BooleanValue(false));
 134   entry->add(c);
 135   entry->end(MTest::New(func.alloc, c, outerHeader, exit));
 136   osrEntry->end(MGoto::New(func.alloc, merge));
 137
 138   merge->end(MGoto::New(func.alloc, innerHeader));
 139
 140   // Use Beta nodes to hide the constants and suppress folding.
 141   MConstant* x = MConstant::New(func.alloc, BooleanValue(false));
 142   outerHeader->add(x);
 143   MBeta* xBeta =
 144       MBeta::New(func.alloc, x, Range::NewInt32Range(func.alloc, 0, 1));
 145   outerHeader->add(xBeta);
 146   outerHeader->end(MTest::New(func.alloc, xBeta, middleHeader, exit));
 147
 148   MConstant* y = MConstant::New(func.alloc, BooleanValue(false));
 149   middleHeader->add(y);
 150   MBeta* yBeta =
 151       MBeta::New(func.alloc, y, Range::NewInt32Range(func.alloc, 0, 1));
 152   middleHeader->add(yBeta);
 153   middleHeader->end(MTest::New(func.alloc, yBeta, merge, outerBackedge));
 154
 155   MConstant* w = MConstant::New(func.alloc, BooleanValue(false));
 156   innerHeader->add(w);
 157   MBeta* wBeta =
 158       MBeta::New(func.alloc, w, Range::NewInt32Range(func.alloc, 0, 1));
 159   innerHeader->add(wBeta);
 160   innerHeader->end(
 161       MTest::New(func.alloc, wBeta, innerBackedge, middleBackedge));
 162
 163   innerBackedge->end(MGoto::New(func.alloc, innerHeader));
 164   middleBackedge->end(MGoto::New(func.alloc, middleHeader));
 165   outerBackedge->end(MGoto::New(func.alloc, outerHeader));
 166
 167   MConstant* u = MConstant::New(func.alloc, UndefinedValue());
 168   exit->add(u);
 169   exit->end(MReturn::New(func.alloc, u));
 170
 171   MOZ_ALWAYS_TRUE(innerHeader->addPredecessorWithoutPhis(innerBackedge));
 172   MOZ_ALWAYS_TRUE(middleHeader->addPredecessorWithoutPhis(middleBackedge));
 173   MOZ_ALWAYS_TRUE(outerHeader->addPredecessorWithoutPhis(outerBackedge));
 174   MOZ_ALWAYS_TRUE(exit->addPredecessorWithoutPhis(entry));
 175   MOZ_ALWAYS_TRUE(merge->addPredecessorWithoutPhis(osrEntry));
 176
 177   outerHeader->setLoopHeader(outerBackedge);
 178   middleHeader->setLoopHeader(middleBackedge);
 179   innerHeader->setLoopHeader(innerBackedge);
 180
 181   if (!func.runGVN()) {
 182     return false;
 183   }
 184
 185   // The loops are no longer reachable from the normal entry. They are
 186   // doinated by the osrEntry.
 187   MOZ_RELEASE_ASSERT(func.graph.osrBlock() == osrEntry);
 188   MBasicBlock* newInner =
 189       FollowTrivialGotos(osrEntry->lastIns()->toGoto()->target());
 190   MBasicBlock* newMiddle =
 191       FollowTrivialGotos(newInner->lastIns()->toTest()->ifFalse());
 192   MBasicBlock* newOuter =
 193       FollowTrivialGotos(newMiddle->lastIns()->toTest()->ifFalse());
 194   MBasicBlock* newExit = FollowTrivialGotos(entry);
 195   MOZ_RELEASE_ASSERT(newInner->isLoopHeader());
 196   MOZ_RELEASE_ASSERT(newMiddle->isLoopHeader());
 197   MOZ_RELEASE_ASSERT(newOuter->isLoopHeader());
 198   MOZ_RELEASE_ASSERT(newExit->lastIns()->isReturn());
 199
 200   // One more time.
 201   ClearDominatorTree(func.graph);
 202   if (!func.runGVN()) {
 203     return false;
 204   }
 205
 206   // The loops are no longer reachable from the normal entry. They are
 207   // doinated by the osrEntry.
 208   MOZ_RELEASE_ASSERT(func.graph.osrBlock() == osrEntry);
 209   newInner = FollowTrivialGotos(osrEntry->lastIns()->toGoto()->target());
 210   newMiddle = FollowTrivialGotos(newInner->lastIns()->toTest()->ifFalse());
 211   newOuter = FollowTrivialGotos(newMiddle->lastIns()->toTest()->ifFalse());
 212   newExit = FollowTrivialGotos(entry);
 213   MOZ_RELEASE_ASSERT(newInner->isLoopHeader());
 214   MOZ_RELEASE_ASSERT(newMiddle->isLoopHeader());
 215   MOZ_RELEASE_ASSERT(newOuter->isLoopHeader());
 216   MOZ_RELEASE_ASSERT(newExit->lastIns()->isReturn());
 217
 218   return true;
 219 }
 220 END_TEST(testJitGVN_FixupOSROnlyLoopNested)
 221
 222 BEGIN_TEST(testJitGVN_PinnedPhis) {
 223   // Set up a loop which gets optimized away, with phis which must be
 224   // cleaned up, permitting more phis to be cleaned up.
 225
 226   MinimalFunc func;
 227
 228   MBasicBlock* entry = func.createEntryBlock();
 229   MBasicBlock* outerHeader = func.createBlock(entry);
 230   MBasicBlock* outerBlock = func.createBlock(outerHeader);
 231   MBasicBlock* innerHeader = func.createBlock(outerBlock);
 232   MBasicBlock* innerBackedge = func.createBlock(innerHeader);
 233   MBasicBlock* exit = func.createBlock(innerHeader);
 234
 235   MPhi* phi0 = MPhi::New(func.alloc);
 236   MPhi* phi1 = MPhi::New(func.alloc);
 237   MPhi* phi2 = MPhi::New(func.alloc);
 238   MPhi* phi3 = MPhi::New(func.alloc);
 239
 240   MParameter* p = func.createParameter();
 241   entry->add(p);
 242   MConstant* z0 = MConstant::New(func.alloc, Int32Value(0));
 243   MConstant* z1 = MConstant::New(func.alloc, Int32Value(1));
 244   MConstant* z2 = MConstant::New(func.alloc, Int32Value(2));
 245   MConstant* z3 = MConstant::New(func.alloc, Int32Value(2));
 246   MOZ_RELEASE_ASSERT(phi0->addInputSlow(z0));
 247   MOZ_RELEASE_ASSERT(phi1->addInputSlow(z1));
 248   MOZ_RELEASE_ASSERT(phi2->addInputSlow(z2));
 249   MOZ_RELEASE_ASSERT(phi3->addInputSlow(z3));
 250   entry->add(z0);
 251   entry->add(z1);
 252   entry->add(z2);
 253   entry->add(z3);
 254   entry->end(MGoto::New(func.alloc, outerHeader));
 255
 256   outerHeader->addPhi(phi0);
 257   outerHeader->addPhi(phi1);
 258   outerHeader->addPhi(phi2);
 259   outerHeader->addPhi(phi3);
 260   outerHeader->end(MGoto::New(func.alloc, outerBlock));
 261
 262   outerBlock->end(MGoto::New(func.alloc, innerHeader));
 263
 264   MConstant* true_ = MConstant::New(func.alloc, BooleanValue(true));
 265   innerHeader->add(true_);
 266   innerHeader->end(MTest::New(func.alloc, true_, innerBackedge, exit));
 267
 268   innerBackedge->end(MGoto::New(func.alloc, innerHeader));
 269
 270   MInstruction* z4 = MAdd::New(func.alloc, phi0, phi1, MIRType::Int32);
 271   MConstant* z5 = MConstant::New(func.alloc, Int32Value(4));
 272   MInstruction* z6 = MAdd::New(func.alloc, phi2, phi3, MIRType::Int32);
 273   MConstant* z7 = MConstant::New(func.alloc, Int32Value(6));
 274   MOZ_RELEASE_ASSERT(phi0->addInputSlow(z4));
 275   MOZ_RELEASE_ASSERT(phi1->addInputSlow(z5));
 276   MOZ_RELEASE_ASSERT(phi2->addInputSlow(z6));
 277   MOZ_RELEASE_ASSERT(phi3->addInputSlow(z7));
 278   exit->add(z4);
 279   exit->add(z5);
 280   exit->add(z6);
 281   exit->add(z7);
 282   exit->end(MGoto::New(func.alloc, outerHeader));
 283
 284   MOZ_ALWAYS_TRUE(innerHeader->addPredecessorWithoutPhis(innerBackedge));
 285   MOZ_ALWAYS_TRUE(outerHeader->addPredecessorWithoutPhis(exit));
 286
 287   outerHeader->setLoopHeader(exit);
 288   innerHeader->setLoopHeader(innerBackedge);
 289
 290   if (!func.runGVN()) {
 291     return false;
 292   }
 293
 294   MOZ_RELEASE_ASSERT(innerHeader->phisEmpty());
 295   MOZ_RELEASE_ASSERT(exit->isDead());
 296
 297   return true;
 298 }
 299 END_TEST(testJitGVN_PinnedPhis)