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( 537 isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI)); 538 539 // Cannot move LI2 after SI_A6, as there is a flow dependence. 540 EXPECT_FALSE( 541 isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, &DI)); 542 543 // Cannot move SI after LI1, as there is a anti dependence. 544 EXPECT_FALSE( 545 isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI)); 546 547 // Cannot move SI_A5 after SI, as there is a output dependence. 548 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI)); 549 550 // Can move LI2 before LI1, as there is only an input dependence. 551 EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI)); 552 }); 553 } 554 555 TEST(CodeMoverUtils, IsSafeToMoveTest2) { 556 LLVMContext C; 557 558 std::unique_ptr<Module> M = 559 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { 560 entry: 561 br i1 %cond, label %if.then.first, label %if.end.first 562 if.then.first: 563 %add = add i32 %op0, %op1 564 %user = add i32 %add, 1 565 br label %if.end.first 566 if.end.first: 567 br i1 %cond, label %if.then.second, label %if.end.second 568 if.then.second: 569 %sub_op0 = add i32 %op0, 1 570 %sub = sub i32 %sub_op0, %op1 571 br label %if.end.second 572 if.end.second: 573 ret void 574 })"); 575 576 run(*M, "foo", 577 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 578 DependenceInfo &DI) { 579 Instruction *AddInst = getInstructionByName(F, "add"); 580 Instruction *SubInst = getInstructionByName(F, "sub"); 581 582 // Cannot move as %user uses %add and %sub doesn't dominates %user. 583 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); 584 585 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't 586 // dominates %sub_op0. 587 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); 588 }); 589 } 590 591 TEST(CodeMoverUtils, IsSafeToMoveTest3) { 592 LLVMContext C; 593 594 std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) { 595 entry: 596 br label %for.body 597 for.body: 598 %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ] 599 %inc = add nsw i64 %i, 1 600 br label %for.latch 601 for.latch: 602 %cmp = icmp slt i64 %inc, %N 603 br i1 %cmp, label %for.body, label %for.end 604 for.end: 605 ret void 606 })"); 607 608 run(*M, "foo", 609 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 610 DependenceInfo &DI) { 611 Instruction *IncInst = getInstructionByName(F, "inc"); 612 Instruction *CmpInst = getInstructionByName(F, "cmp"); 613 614 // Can move as the incoming block of %inc for %i (%for.latch) dominated 615 // by %cmp. 616 EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI)); 617 }); 618 } 619 620 TEST(CodeMoverUtils, IsSafeToMoveTest4) { 621 LLVMContext C; 622 623 std::unique_ptr<Module> M = 624 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { 625 entry: 626 br i1 %cond, label %if.end.first, label %if.then.first 627 if.then.first: 628 %add = add i32 %op0, %op1 629 %user = add i32 %add, 1 630 br label %if.end.first 631 if.end.first: 632 br i1 %cond, label %if.end.second, label %if.then.second 633 if.then.second: 634 %sub_op0 = add i32 %op0, 1 635 %sub = sub i32 %sub_op0, %op1 636 br label %if.end.second 637 if.end.second: 638 ret void 639 })"); 640 641 run(*M, "foo", 642 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 643 DependenceInfo &DI) { 644 Instruction *AddInst = getInstructionByName(F, "add"); 645 Instruction *SubInst = getInstructionByName(F, "sub"); 646 647 // Cannot move as %user uses %add and %sub doesn't dominates %user. 648 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); 649 650 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't 651 // dominates %sub_op0. 652 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); 653 }); 654 } 655 656 TEST(CodeMoverUtils, IsSafeToMoveTest5) { 657 LLVMContext C; 658 659 std::unique_ptr<Module> M = 660 parseIR(C, R"(define void @dependence(i32* noalias %A, i32* noalias %B){ 661 entry: 662 store i32 0, i32* %A, align 4 ; storeA0 663 store i32 2, i32* %A, align 4 ; storeA1 664 %tmp0 = load i32, i32* %A, align 4 ; loadA0 665 store i32 1, i32* %B, align 4 ; storeB0 666 %tmp1 = load i32, i32* %A, align 4 ; loadA1 667 store i32 2, i32* %A, align 4 ; storeA2 668 store i32 4, i32* %B, align 4 ; StoreB1 669 %tmp2 = load i32, i32* %A, align 4 ; loadA2 670 %tmp3 = load i32, i32* %A, align 4 ; loadA3 671 %tmp4 = load i32, i32* %B, align 4 ; loadB2 672 %tmp5 = load i32, i32* %B, align 4 ; loadB3 673 ret void 674 })"); 675 676 run(*M, "dependence", 677 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 678 DependenceInfo &DI) { 679 Instruction *LoadA0 = getInstructionByName(F, "tmp0"); 680 Instruction *LoadA1 = getInstructionByName(F, "tmp1"); 681 Instruction *LoadA2 = getInstructionByName(F, "tmp2"); 682 Instruction *LoadA3 = getInstructionByName(F, "tmp3"); 683 Instruction *LoadB2 = getInstructionByName(F, "tmp4"); 684 Instruction *LoadB3 = getInstructionByName(F, "tmp5"); 685 Instruction *StoreA1 = LoadA0->getPrevNode(); 686 Instruction *StoreA0 = StoreA1->getPrevNode(); 687 Instruction *StoreB0 = LoadA0->getNextNode(); 688 Instruction *StoreB1 = LoadA2->getPrevNode(); 689 Instruction *StoreA2 = StoreB1->getPrevNode(); 690 691 // Input forward dependency 692 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); 693 // Input backward dependency 694 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); 695 696 // Output forward dependency 697 EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI)); 698 // Output backward dependency 699 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI)); 700 701 // Flow forward dependency 702 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI)); 703 // Flow backward dependency 704 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI)); 705 706 // Anti forward dependency 707 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI)); 708 // Anti backward dependency 709 EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI)); 710 711 // No input backward dependency 712 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); 713 // No input forward dependency 714 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); 715 716 // No Output forward dependency 717 EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI)); 718 // No Output backward dependency 719 EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI)); 720 721 // No flow forward dependency 722 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI)); 723 // No flow backward dependency 724 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI)); 725 726 // No anti backward dependency 727 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI)); 728 // No anti forward dependency 729 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); 730 }); 731 } 732 733 TEST(CodeMoverUtils, IsSafeToMoveTest6) { 734 LLVMContext C; 735 736 std::unique_ptr<Module> M = parseIR( 737 C, R"(define void @dependence(i1 %cond, i32* noalias %A, i32* noalias %B){ 738 entry: 739 br i1 %cond, label %bb0, label %bb1 740 bb0: 741 br label %bb1 742 bb1: 743 store i32 0, i32* %A, align 4 ; storeA0 744 br i1 %cond, label %bb2, label %bb3 745 bb2: 746 br label %bb3 747 bb3: 748 store i32 2, i32* %A, align 4 ; storeA1 749 br i1 %cond, label %bb4, label %bb5 750 bb4: 751 br label %bb5 752 bb5: 753 %tmp0 = load i32, i32* %A, align 4 ; loadA0 754 br i1 %cond, label %bb6, label %bb7 755 bb6: 756 br label %bb7 757 bb7: 758 store i32 1, i32* %B, align 4 ; storeB0 759 br i1 %cond, label %bb8, label %bb9 760 bb8: 761 br label %bb9 762 bb9: 763 %tmp1 = load i32, i32* %A, align 4 ; loadA1 764 br i1 %cond, label %bb10, label %bb11 765 bb10: 766 br label %bb11 767 bb11: 768 store i32 2, i32* %A, align 4 ; storeA2 769 br i1 %cond, label %bb12, label %bb13 770 bb12: 771 br label %bb13 772 bb13: 773 store i32 4, i32* %B, align 4 ; StoreB1 774 br i1 %cond, label %bb14, label %bb15 775 bb14: 776 br label %bb15 777 bb15: 778 %tmp2 = load i32, i32* %A, align 4 ; loadA2 779 br i1 %cond, label %bb16, label %bb17 780 bb16: 781 br label %bb17 782 bb17: 783 %tmp3 = load i32, i32* %A, align 4 ; loadA3 784 br i1 %cond, label %bb18, label %bb19 785 bb18: 786 br label %bb19 787 bb19: 788 %tmp4 = load i32, i32* %B, align 4 ; loadB2 789 br i1 %cond, label %bb20, label %bb21 790 bb20: 791 br label %bb21 792 bb21: 793 %tmp5 = load i32, i32* %B, align 4 ; loadB3 794 ret void 795 })"); 796 run(*M, "dependence", 797 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 798 DependenceInfo &DI) { 799 BasicBlock *BB1 = getBasicBlockByName(F, "bb1"); 800 BasicBlock *BB3 = getBasicBlockByName(F, "bb3"); 801 BasicBlock *BB7 = getBasicBlockByName(F, "bb7"); 802 BasicBlock *BB11 = getBasicBlockByName(F, "bb11"); 803 BasicBlock *BB13 = getBasicBlockByName(F, "bb13"); 804 Instruction *LoadA0 = getInstructionByName(F, "tmp0"); 805 Instruction *LoadA1 = getInstructionByName(F, "tmp1"); 806 Instruction *LoadA2 = getInstructionByName(F, "tmp2"); 807 Instruction *LoadA3 = getInstructionByName(F, "tmp3"); 808 Instruction *LoadB2 = getInstructionByName(F, "tmp4"); 809 Instruction *LoadB3 = getInstructionByName(F, "tmp5"); 810 Instruction &StoreA1 = BB3->front(); 811 Instruction &StoreA0 = BB1->front(); 812 Instruction &StoreB0 = BB7->front(); 813 Instruction &StoreB1 = BB13->front(); 814 Instruction &StoreA2 = BB11->front(); 815 816 // Input forward dependency 817 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); 818 // Input backward dependency 819 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); 820 821 // Output forward dependency 822 EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI)); 823 // Output backward dependency 824 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI)); 825 826 // Flow forward dependency 827 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI)); 828 // Flow backward dependency 829 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI)); 830 831 // Anti forward dependency 832 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI)); 833 // Anti backward dependency 834 EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI)); 835 836 // No input backward dependency 837 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); 838 // No input forward dependency 839 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); 840 841 // No Output forward dependency 842 EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI)); 843 // No Output backward dependency 844 EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI)); 845 846 // No flow forward dependency 847 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI)); 848 // No flow backward dependency 849 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI)); 850 851 // No anti backward dependency 852 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI)); 853 // No anti forward dependency 854 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); 855 }); 856 } 857