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