testJitGVN.cpp (11014B)
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::NewBoolean(func.alloc, 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::NewBoolean(func.alloc, 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::NewBoolean(func.alloc, 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::NewUndefined(func.alloc); 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::NewBoolean(func.alloc, 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::NewBoolean(func.alloc, 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::NewBoolean(func.alloc, 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::NewBoolean(func.alloc, 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::NewUndefined(func.alloc); 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::NewInt32(func.alloc, 0); 243 MConstant* z1 = MConstant::NewInt32(func.alloc, 1); 244 MConstant* z2 = MConstant::NewInt32(func.alloc, 2); 245 MConstant* z3 = MConstant::NewInt32(func.alloc, 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::NewBoolean(func.alloc, 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::NewInt32(func.alloc, 4); 272 MInstruction* z6 = MAdd::New(func.alloc, phi2, phi3, MIRType::Int32); 273 MConstant* z7 = MConstant::NewInt32(func.alloc, 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)