1 //===- CodeMoverUtils.cpp - Unit tests for CodeMoverUtils ---------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Transforms/Utils/CodeMoverUtils.h" 10 #include "llvm/Analysis/AssumptionCache.h" 11 #include "llvm/Analysis/DependenceAnalysis.h" 12 #include "llvm/Analysis/LoopInfo.h" 13 #include "llvm/Analysis/PostDominators.h" 14 #include "llvm/AsmParser/Parser.h" 15 #include "llvm/IR/Dominators.h" 16 #include "llvm/IR/LLVMContext.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 19 #include "gtest/gtest.h" 20 21 using namespace llvm; 22 23 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { 24 SMDiagnostic Err; 25 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C); 26 if (!Mod) 27 Err.print("CodeMoverUtilsTests", errs()); 28 return Mod; 29 } 30 31 static void run(Module &M, StringRef FuncName, 32 function_ref<void(Function &F, DominatorTree &DT, 33 PostDominatorTree &PDT, DependenceInfo &DI)> 34 Test) { 35 auto *F = M.getFunction(FuncName); 36 DominatorTree DT(*F); 37 PostDominatorTree PDT(*F); 38 TargetLibraryInfoImpl TLII; 39 TargetLibraryInfo TLI(TLII); 40 AssumptionCache AC(*F); 41 AliasAnalysis AA(TLI); 42 LoopInfo LI(DT); 43 ScalarEvolution SE(*F, TLI, AC, DT, LI); 44 DependenceInfo DI(F, &AA, &SE, &LI); 45 Test(*F, DT, PDT, DI); 46 } 47 48 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { 49 for (BasicBlock &BB : F) 50 if (BB.getName() == Name) 51 return &BB; 52 llvm_unreachable("Expected to find basic block!"); 53 } 54 55 static Instruction *getInstructionByName(Function &F, StringRef Name) { 56 for (BasicBlock &BB : F) 57 for (Instruction &I : BB) 58 if (I.getName() == Name) 59 return &I; 60 llvm_unreachable("Expected to find instruction!"); 61 } 62 63 TEST(CodeMoverUtils, IsControlFlowEquivalentSimpleTest) { 64 LLVMContext C; 65 66 // void foo(int &i, bool cond1, bool cond2) { 67 // if (cond1) 68 // i = 1; 69 // if (cond1) 70 // i = 2; 71 // if (cond2) 72 // i = 3; 73 // } 74 std::unique_ptr<Module> M = 75 parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { 76 entry: 77 br i1 %cond1, label %if.first, label %if.first.end 78 if.first: 79 store i32 1, i32* %i, align 4 80 br label %if.first.end 81 if.first.end: 82 br i1 %cond1, label %if.second, label %if.second.end 83 if.second: 84 store i32 2, i32* %i, align 4 85 br label %if.second.end 86 if.second.end: 87 br i1 %cond2, label %if.third, label %if.third.end 88 if.third: 89 store i32 3, i32* %i, align 4 90 br label %if.third.end 91 if.third.end: 92 ret void 93 })"); 94 run(*M, "foo", 95 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 96 DependenceInfo &DI) { 97 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); 98 EXPECT_TRUE( 99 isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); 100 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); 101 EXPECT_TRUE( 102 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); 103 104 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); 105 EXPECT_FALSE( 106 isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); 107 EXPECT_FALSE( 108 isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); 109 }); 110 } 111 112 TEST(CodeMoverUtils, IsControlFlowEquivalentOppositeCondTest) { 113 LLVMContext C; 114 115 // void foo(int &i, unsigned X, unsigned Y) { 116 // if (X < Y) 117 // i = 1; 118 // if (Y > X) 119 // i = 2; 120 // if (X >= Y) 121 // i = 3; 122 // else 123 // i = 4; 124 // if (X == Y) 125 // i = 5; 126 // if (Y == X) 127 // i = 6; 128 // else 129 // i = 7; 130 // if (X != Y) 131 // i = 8; 132 // else 133 // i = 9; 134 // } 135 std::unique_ptr<Module> M = 136 parseIR(C, R"(define void @foo(i32* %i, i32 %X, i32 %Y) { 137 entry: 138 %cmp1 = icmp ult i32 %X, %Y 139 br i1 %cmp1, label %if.first, label %if.first.end 140 if.first: 141 store i32 1, i32* %i, align 4 142 br label %if.first.end 143 if.first.end: 144 %cmp2 = icmp ugt i32 %Y, %X 145 br i1 %cmp2, label %if.second, label %if.second.end 146 if.second: 147 store i32 2, i32* %i, align 4 148 br label %if.second.end 149 if.second.end: 150 %cmp3 = icmp uge i32 %X, %Y 151 br i1 %cmp3, label %if.third, label %if.third.else 152 if.third: 153 store i32 3, i32* %i, align 4 154 br label %if.third.end 155 if.third.else: 156 store i32 4, i32* %i, align 4 157 br label %if.third.end 158 if.third.end: 159 %cmp4 = icmp eq i32 %X, %Y 160 br i1 %cmp4, label %if.fourth, label %if.fourth.end 161 if.fourth: 162 store i32 5, i32* %i, align 4 163 br label %if.fourth.end 164 if.fourth.end: 165 %cmp5 = icmp eq i32 %Y, %X 166 br i1 %cmp5, label %if.fifth, label %if.fifth.else 167 if.fifth: 168 store i32 6, i32* %i, align 4 169 br label %if.fifth.end 170 if.fifth.else: 171 store i32 7, i32* %i, align 4 172 br label %if.fifth.end 173 if.fifth.end: 174 %cmp6 = icmp ne i32 %X, %Y 175 br i1 %cmp6, label %if.sixth, label %if.sixth.else 176 if.sixth: 177 store i32 8, i32* %i, align 4 178 br label %if.sixth.end 179 if.sixth.else: 180 store i32 9, i32* %i, align 4 181 br label %if.sixth.end 182 if.sixth.end: 183 ret void 184 })"); 185 run(*M, "foo", 186 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 187 DependenceInfo &DI) { 188 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); 189 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); 190 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); 191 BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else"); 192 EXPECT_TRUE( 193 isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT)); 194 EXPECT_TRUE( 195 isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT)); 196 EXPECT_FALSE( 197 isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT)); 198 199 BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); 200 BasicBlock *FifthIfBody = getBasicBlockByName(F, "if.fifth"); 201 BasicBlock *FifthElseBody = getBasicBlockByName(F, "if.fifth.else"); 202 EXPECT_FALSE( 203 isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT)); 204 BasicBlock *SixthIfBody = getBasicBlockByName(F, "if.sixth"); 205 EXPECT_TRUE( 206 isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT)); 207 BasicBlock *SixthElseBody = getBasicBlockByName(F, "if.sixth.else"); 208 EXPECT_TRUE( 209 isControlFlowEquivalent(*FourthIfBody, *SixthElseBody, DT, PDT)); 210 EXPECT_TRUE( 211 isControlFlowEquivalent(*FifthIfBody, *SixthElseBody, DT, PDT)); 212 }); 213 } 214 215 TEST(CodeMoverUtils, IsControlFlowEquivalentCondNestTest) { 216 LLVMContext C; 217 218 // void foo(int &i, bool cond1, bool cond2) { 219 // if (cond1) 220 // if (cond2) 221 // i = 1; 222 // if (cond2) 223 // if (cond1) 224 // i = 2; 225 // } 226 std::unique_ptr<Module> M = 227 parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { 228 entry: 229 br i1 %cond1, label %if.outer.first, label %if.first.end 230 if.outer.first: 231 br i1 %cond2, label %if.inner.first, label %if.first.end 232 if.inner.first: 233 store i32 1, i32* %i, align 4 234 br label %if.first.end 235 if.first.end: 236 br i1 %cond2, label %if.outer.second, label %if.second.end 237 if.outer.second: 238 br i1 %cond1, label %if.inner.second, label %if.second.end 239 if.inner.second: 240 store i32 2, i32* %i, align 4 241 br label %if.second.end 242 if.second.end: 243 ret void 244 })"); 245 run(*M, "foo", 246 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 247 DependenceInfo &DI) { 248 BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); 249 BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); 250 BasicBlock *SecondOuterIfBody = 251 getBasicBlockByName(F, "if.outer.second"); 252 BasicBlock *SecondInnerIfBody = 253 getBasicBlockByName(F, "if.inner.second"); 254 EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody, 255 *SecondInnerIfBody, DT, PDT)); 256 EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, 257 *SecondOuterIfBody, DT, PDT)); 258 EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, 259 *SecondInnerIfBody, DT, PDT)); 260 EXPECT_FALSE(isControlFlowEquivalent(*FirstInnerIfBody, 261 *SecondOuterIfBody, DT, PDT)); 262 }); 263 } 264 265 TEST(CodeMoverUtils, IsControlFlowEquivalentImbalanceTest) { 266 LLVMContext C; 267 268 // void foo(int &i, bool cond1, bool cond2) { 269 // if (cond1) 270 // if (cond2) 271 // if (cond3) 272 // i = 1; 273 // if (cond2) 274 // if (cond3) 275 // i = 2; 276 // if (cond1) 277 // if (cond1) 278 // i = 3; 279 // if (cond1) 280 // i = 4; 281 // } 282 std::unique_ptr<Module> M = parseIR( 283 C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2, i1 %cond3) { 284 entry: 285 br i1 %cond1, label %if.outer.first, label %if.first.end 286 if.outer.first: 287 br i1 %cond2, label %if.middle.first, label %if.first.end 288 if.middle.first: 289 br i1 %cond3, label %if.inner.first, label %if.first.end 290 if.inner.first: 291 store i32 1, i32* %i, align 4 292 br label %if.first.end 293 if.first.end: 294 br i1 %cond2, label %if.outer.second, label %if.second.end 295 if.outer.second: 296 br i1 %cond3, label %if.inner.second, label %if.second.end 297 if.inner.second: 298 store i32 2, i32* %i, align 4 299 br label %if.second.end 300 if.second.end: 301 br i1 %cond1, label %if.outer.third, label %if.third.end 302 if.outer.third: 303 br i1 %cond1, label %if.inner.third, label %if.third.end 304 if.inner.third: 305 store i32 3, i32* %i, align 4 306 br label %if.third.end 307 if.third.end: 308 br i1 %cond1, label %if.fourth, label %if.fourth.end 309 if.fourth: 310 store i32 4, i32* %i, align 4 311 br label %if.fourth.end 312 if.fourth.end: 313 ret void 314 })"); 315 run(*M, "foo", 316 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 317 DependenceInfo &DI) { 318 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); 319 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); 320 EXPECT_FALSE( 321 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); 322 323 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third"); 324 BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); 325 EXPECT_TRUE( 326 isControlFlowEquivalent(*ThirdIfBody, *FourthIfBody, DT, PDT)); 327 }); 328 } 329 330 TEST(CodeMoverUtils, IsControlFlowEquivalentPointerTest) { 331 LLVMContext C; 332 333 // void foo(int &i, int *cond) { 334 // if (*cond) 335 // i = 1; 336 // if (*cond) 337 // i = 2; 338 // *cond = 1; 339 // if (*cond) 340 // i = 3; 341 // } 342 std::unique_ptr<Module> M = 343 parseIR(C, R"(define void @foo(i32* %i, i32* %cond) { 344 entry: 345 %0 = load i32, i32* %cond, align 4 346 %tobool1 = icmp ne i32 %0, 0 347 br i1 %tobool1, label %if.first, label %if.first.end 348 if.first: 349 store i32 1, i32* %i, align 4 350 br label %if.first.end 351 if.first.end: 352 %1 = load i32, i32* %cond, align 4 353 %tobool2 = icmp ne i32 %1, 0 354 br i1 %tobool2, label %if.second, label %if.second.end 355 if.second: 356 store i32 2, i32* %i, align 4 357 br label %if.second.end 358 if.second.end: 359 store i32 1, i32* %cond, align 4 360 %2 = load i32, i32* %cond, align 4 361 %tobool3 = icmp ne i32 %2, 0 362 br i1 %tobool3, label %if.third, label %if.third.end 363 if.third: 364 store i32 3, i32* %i, align 4 365 br label %if.third.end 366 if.third.end: 367 ret void 368 })"); 369 run(*M, "foo", 370 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 371 DependenceInfo &DI) { 372 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); 373 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); 374 // Limitation: if we can prove cond haven't been modify between %0 and 375 // %1, then we can prove FirstIfBody and SecondIfBody are control flow 376 // equivalent. 377 EXPECT_FALSE( 378 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); 379 380 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); 381 EXPECT_FALSE( 382 isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); 383 EXPECT_FALSE( 384 isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); 385 }); 386 } 387 388 TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) { 389 LLVMContext C; 390 391 // void foo(bool cond1, bool cond2) { 392 // if (cond1) { 393 // if (cond2) 394 // return; 395 // } else 396 // if (cond2) 397 // return; 398 // return; 399 // } 400 std::unique_ptr<Module> M = 401 parseIR(C, R"(define void @foo(i1 %cond1, i1 %cond2) { 402 idom: 403 br i1 %cond1, label %succ0, label %succ1 404 succ0: 405 br i1 %cond2, label %succ0ret, label %succ0succ1 406 succ0ret: 407 ret void 408 succ0succ1: 409 br label %bb 410 succ1: 411 br i1 %cond2, label %succ1ret, label %succ1succ1 412 succ1ret: 413 ret void 414 succ1succ1: 415 br label %bb 416 bb: 417 ret void 418 })"); 419 run(*M, "foo", 420 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 421 DependenceInfo &DI) { 422 BasicBlock &Idom = F.front(); 423 assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); 424 BasicBlock &BB = F.back(); 425 assert(BB.getName() == "bb" && "Expecting BasicBlock bb"); 426 EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT)); 427 }); 428 } 429 430 TEST(CodeMoverUtils, IsSafeToMoveTest1) { 431 LLVMContext C; 432 433 // void safecall() noexcept willreturn nosync; 434 // void unsafecall(); 435 // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C, 436 // long N) { 437 // X = N / 1; 438 // safecall(); 439 // unsafecall1(); 440 // unsafecall2(); 441 // for (long i = 0; i < N; ++i) { 442 // A[5] = 5; 443 // A[i] = 0; 444 // B[i] = A[i]; 445 // C[i] = A[i]; 446 // A[6] = 6; 447 // } 448 // } 449 std::unique_ptr<Module> M = parseIR( 450 C, R"(define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C 451 , i64 %N) { 452 entry: 453 %X = sdiv i64 1, %N 454 call void @safecall() 455 %cmp1 = icmp slt i64 0, %N 456 call void @unsafecall1() 457 call void @unsafecall2() 458 br i1 %cmp1, label %for.body, label %for.end 459 for.body: 460 %i = phi i64 [ 0, %entry ], [ %inc, %for.body ] 461 %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5 462 store i32 5, i32* %arrayidx_A5, align 4 463 %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i 464 store i32 0, i32* %arrayidx_A, align 4 465 %load1 = load i32, i32* %arrayidx_A, align 4 466 %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i 467 store i32 %load1, i32* %arrayidx_B, align 4 468 %load2 = load i32, i32* %arrayidx_A, align 4 469 %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i 470 store i32 %load2, i32* %arrayidx_C, align 4 471 %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6 472 store i32 6, i32* %arrayidx_A6, align 4 473 %inc = add nsw i64 %i, 1 474 %cmp = icmp slt i64 %inc, %N 475 br i1 %cmp, label %for.body, label %for.end 476 for.end: 477 ret void 478 } 479 declare void @safecall() nounwind nosync willreturn 480 declare void @unsafecall1() 481 declare void @unsafecall2())"); 482 483 run(*M, "foo", 484 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 485 DependenceInfo &DI) { 486 BasicBlock *Entry = getBasicBlockByName(F, "entry"); 487 Instruction *CI_safecall = Entry->front().getNextNode(); 488 assert(isa<CallInst>(CI_safecall) && 489 "Expecting CI_safecall to be a CallInst"); 490 Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode(); 491 assert(isa<CallInst>(CI_unsafecall) && 492 "Expecting CI_unsafecall to be a CallInst"); 493 BasicBlock *ForBody = getBasicBlockByName(F, "for.body"); 494 Instruction &PN = ForBody->front(); 495 assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode"); 496 Instruction *SI_A5 = 497 getInstructionByName(F, "arrayidx_A5")->getNextNode(); 498 Instruction *SI = getInstructionByName(F, "arrayidx_A")->getNextNode(); 499 Instruction *LI1 = getInstructionByName(F, "load1"); 500 Instruction *LI2 = getInstructionByName(F, "load2"); 501 Instruction *SI_A6 = 502 getInstructionByName(F, "arrayidx_A6")->getNextNode(); 503 504 // Can move after CI_safecall, as it does not throw, not synchronize, or 505 // must return. 506 EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), 507 *CI_safecall->getNextNode(), DT, PDT, 508 DI)); 509 510 // Cannot move CI_unsafecall, as it may throw. 511 EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), 512 *CI_unsafecall, DT, PDT, DI)); 513 514 // Moving instruction to non control flow equivalent places are not 515 // supported. 516 EXPECT_FALSE( 517 isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI)); 518 519 // Moving PHINode is not supported. 520 EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), 521 DT, PDT, DI)); 522 523 // Cannot move non-PHINode before PHINode. 524 EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI)); 525 526 // Moving Terminator is not supported. 527 EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), 528 *PN.getNextNode(), DT, PDT, DI)); 529 530 // Cannot move %arrayidx_A after SI, as SI is its user. 531 EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), 532 DT, PDT, DI)); 533 534 // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. 535 EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI)); 536 537 // Cannot move LI2 after SI_A6, as there is a flow dependence. 538 EXPECT_FALSE( 539 isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI)); 540 541 // Cannot move SI after LI1, as there is a anti dependence. 542 EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI)); 543 544 // Cannot move SI_A5 after SI, as there is a output dependence. 545 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI)); 546 547 // Can move LI2 before LI1, as there is only an input dependence. 548 EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI)); 549 }); 550 } 551 552 TEST(CodeMoverUtils, IsSafeToMoveTest2) { 553 LLVMContext C; 554 555 std::unique_ptr<Module> M = 556 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { 557 entry: 558 br i1 %cond, label %if.then.first, label %if.end.first 559 if.then.first: 560 %add = add i32 %op0, %op1 561 %user = add i32 %add, 1 562 br label %if.end.first 563 if.end.first: 564 br i1 %cond, label %if.then.second, label %if.end.second 565 if.then.second: 566 %sub_op0 = add i32 %op0, 1 567 %sub = sub i32 %sub_op0, %op1 568 br label %if.end.second 569 if.end.second: 570 ret void 571 })"); 572 573 run(*M, "foo", 574 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 575 DependenceInfo &DI) { 576 Instruction *AddInst = getInstructionByName(F, "add"); 577 Instruction *SubInst = getInstructionByName(F, "sub"); 578 579 // Cannot move as %user uses %add and %sub doesn't dominates %user. 580 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, PDT, DI)); 581 582 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't 583 // dominates %sub_op0. 584 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, PDT, DI)); 585 }); 586 } 587 588 TEST(CodeMoverUtils, IsSafeToMoveTest3) { 589 LLVMContext C; 590 591 std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) { 592 entry: 593 br label %for.body 594 for.body: 595 %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ] 596 %inc = add nsw i64 %i, 1 597 br label %for.latch 598 for.latch: 599 %cmp = icmp slt i64 %inc, %N 600 br i1 %cmp, label %for.body, label %for.end 601 for.end: 602 ret void 603 })"); 604 605 run(*M, "foo", 606 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 607 DependenceInfo &DI) { 608 Instruction *IncInst = getInstructionByName(F, "inc"); 609 Instruction *CmpInst = getInstructionByName(F, "cmp"); 610 611 // Can move as the incoming block of %inc for %i (%for.latch) dominated 612 // by %cmp. 613 EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, PDT, DI)); 614 }); 615 } 616 617 TEST(CodeMoverUtils, IsSafeToMoveTest4) { 618 LLVMContext C; 619 620 std::unique_ptr<Module> M = 621 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { 622 entry: 623 br i1 %cond, label %if.end.first, label %if.then.first 624 if.then.first: 625 %add = add i32 %op0, %op1 626 %user = add i32 %add, 1 627 br label %if.end.first 628 if.end.first: 629 br i1 %cond, label %if.end.second, label %if.then.second 630 if.then.second: 631 %sub_op0 = add i32 %op0, 1 632 %sub = sub i32 %sub_op0, %op1 633 br label %if.end.second 634 if.end.second: 635 ret void 636 })"); 637 638 run(*M, "foo", 639 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 640 DependenceInfo &DI) { 641 Instruction *AddInst = getInstructionByName(F, "add"); 642 Instruction *SubInst = getInstructionByName(F, "sub"); 643 644 // Cannot move as %user uses %add and %sub doesn't dominates %user. 645 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, PDT, DI)); 646 647 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't 648 // dominates %sub_op0. 649 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, PDT, DI)); 650 }); 651 } 652