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/Analysis/TargetLibraryInfo.h" 16 #include "llvm/AsmParser/Parser.h" 17 #include "llvm/IR/Dominators.h" 18 #include "llvm/IR/LLVMContext.h" 19 #include "llvm/Support/SourceMgr.h" 20 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 21 #include "gtest/gtest.h" 22 23 using namespace llvm; 24 25 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { 26 SMDiagnostic Err; 27 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C); 28 if (!Mod) 29 Err.print("CodeMoverUtilsTests", errs()); 30 return Mod; 31 } 32 33 static void run(Module &M, StringRef FuncName, 34 function_ref<void(Function &F, DominatorTree &DT, 35 PostDominatorTree &PDT, DependenceInfo &DI)> 36 Test) { 37 auto *F = M.getFunction(FuncName); 38 DominatorTree DT(*F); 39 PostDominatorTree PDT(*F); 40 TargetLibraryInfoImpl TLII; 41 TargetLibraryInfo TLI(TLII); 42 AssumptionCache AC(*F); 43 AliasAnalysis AA(TLI); 44 LoopInfo LI(DT); 45 ScalarEvolution SE(*F, TLI, AC, DT, LI); 46 DependenceInfo DI(F, &AA, &SE, &LI); 47 Test(*F, DT, PDT, DI); 48 } 49 50 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { 51 for (BasicBlock &BB : F) 52 if (BB.getName() == Name) 53 return &BB; 54 llvm_unreachable("Expected to find basic block!"); 55 } 56 57 static Instruction *getInstructionByName(Function &F, StringRef Name) { 58 for (BasicBlock &BB : F) 59 for (Instruction &I : BB) 60 if (I.getName() == Name) 61 return &I; 62 llvm_unreachable("Expected to find instruction!"); 63 } 64 65 TEST(CodeMoverUtils, IsControlFlowEquivalentSimpleTest) { 66 LLVMContext C; 67 68 // void foo(int &i, bool cond1, bool cond2) { 69 // if (cond1) 70 // i = 1; 71 // if (cond1) 72 // i = 2; 73 // if (cond2) 74 // i = 3; 75 // } 76 std::unique_ptr<Module> M = 77 parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { 78 entry: 79 br i1 %cond1, label %if.first, label %if.first.end 80 if.first: 81 store i32 1, i32* %i, align 4 82 br label %if.first.end 83 if.first.end: 84 br i1 %cond1, label %if.second, label %if.second.end 85 if.second: 86 store i32 2, i32* %i, align 4 87 br label %if.second.end 88 if.second.end: 89 br i1 %cond2, label %if.third, label %if.third.end 90 if.third: 91 store i32 3, i32* %i, align 4 92 br label %if.third.end 93 if.third.end: 94 ret void 95 })"); 96 run(*M, "foo", 97 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 98 DependenceInfo &DI) { 99 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); 100 EXPECT_TRUE( 101 isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); 102 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); 103 EXPECT_TRUE( 104 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); 105 106 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); 107 EXPECT_FALSE( 108 isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); 109 EXPECT_FALSE( 110 isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); 111 }); 112 } 113 114 TEST(CodeMoverUtils, IsControlFlowEquivalentOppositeCondTest) { 115 LLVMContext C; 116 117 // void foo(int &i, unsigned X, unsigned Y) { 118 // if (X < Y) 119 // i = 1; 120 // if (Y > X) 121 // i = 2; 122 // if (X >= Y) 123 // i = 3; 124 // else 125 // i = 4; 126 // if (X == Y) 127 // i = 5; 128 // if (Y == X) 129 // i = 6; 130 // else 131 // i = 7; 132 // if (X != Y) 133 // i = 8; 134 // else 135 // i = 9; 136 // } 137 std::unique_ptr<Module> M = 138 parseIR(C, R"(define void @foo(i32* %i, i32 %X, i32 %Y) { 139 entry: 140 %cmp1 = icmp ult i32 %X, %Y 141 br i1 %cmp1, label %if.first, label %if.first.end 142 if.first: 143 store i32 1, i32* %i, align 4 144 br label %if.first.end 145 if.first.end: 146 %cmp2 = icmp ugt i32 %Y, %X 147 br i1 %cmp2, label %if.second, label %if.second.end 148 if.second: 149 store i32 2, i32* %i, align 4 150 br label %if.second.end 151 if.second.end: 152 %cmp3 = icmp uge i32 %X, %Y 153 br i1 %cmp3, label %if.third, label %if.third.else 154 if.third: 155 store i32 3, i32* %i, align 4 156 br label %if.third.end 157 if.third.else: 158 store i32 4, i32* %i, align 4 159 br label %if.third.end 160 if.third.end: 161 %cmp4 = icmp eq i32 %X, %Y 162 br i1 %cmp4, label %if.fourth, label %if.fourth.end 163 if.fourth: 164 store i32 5, i32* %i, align 4 165 br label %if.fourth.end 166 if.fourth.end: 167 %cmp5 = icmp eq i32 %Y, %X 168 br i1 %cmp5, label %if.fifth, label %if.fifth.else 169 if.fifth: 170 store i32 6, i32* %i, align 4 171 br label %if.fifth.end 172 if.fifth.else: 173 store i32 7, i32* %i, align 4 174 br label %if.fifth.end 175 if.fifth.end: 176 %cmp6 = icmp ne i32 %X, %Y 177 br i1 %cmp6, label %if.sixth, label %if.sixth.else 178 if.sixth: 179 store i32 8, i32* %i, align 4 180 br label %if.sixth.end 181 if.sixth.else: 182 store i32 9, i32* %i, align 4 183 br label %if.sixth.end 184 if.sixth.end: 185 ret void 186 })"); 187 run(*M, "foo", 188 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 189 DependenceInfo &DI) { 190 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); 191 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); 192 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); 193 BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else"); 194 EXPECT_TRUE( 195 isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT)); 196 EXPECT_TRUE( 197 isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT)); 198 EXPECT_FALSE( 199 isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT)); 200 201 BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); 202 BasicBlock *FifthIfBody = getBasicBlockByName(F, "if.fifth"); 203 BasicBlock *FifthElseBody = getBasicBlockByName(F, "if.fifth.else"); 204 EXPECT_FALSE( 205 isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT)); 206 BasicBlock *SixthIfBody = getBasicBlockByName(F, "if.sixth"); 207 EXPECT_TRUE( 208 isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT)); 209 BasicBlock *SixthElseBody = getBasicBlockByName(F, "if.sixth.else"); 210 EXPECT_TRUE( 211 isControlFlowEquivalent(*FourthIfBody, *SixthElseBody, DT, PDT)); 212 EXPECT_TRUE( 213 isControlFlowEquivalent(*FifthIfBody, *SixthElseBody, DT, PDT)); 214 }); 215 } 216 217 TEST(CodeMoverUtils, IsControlFlowEquivalentCondNestTest) { 218 LLVMContext C; 219 220 // void foo(int &i, bool cond1, bool cond2) { 221 // if (cond1) 222 // if (cond2) 223 // i = 1; 224 // if (cond2) 225 // if (cond1) 226 // i = 2; 227 // } 228 std::unique_ptr<Module> M = 229 parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { 230 entry: 231 br i1 %cond1, label %if.outer.first, label %if.first.end 232 if.outer.first: 233 br i1 %cond2, label %if.inner.first, label %if.first.end 234 if.inner.first: 235 store i32 1, i32* %i, align 4 236 br label %if.first.end 237 if.first.end: 238 br i1 %cond2, label %if.outer.second, label %if.second.end 239 if.outer.second: 240 br i1 %cond1, label %if.inner.second, label %if.second.end 241 if.inner.second: 242 store i32 2, i32* %i, align 4 243 br label %if.second.end 244 if.second.end: 245 ret void 246 })"); 247 run(*M, "foo", 248 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 249 DependenceInfo &DI) { 250 BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); 251 BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); 252 BasicBlock *SecondOuterIfBody = 253 getBasicBlockByName(F, "if.outer.second"); 254 BasicBlock *SecondInnerIfBody = 255 getBasicBlockByName(F, "if.inner.second"); 256 EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody, 257 *SecondInnerIfBody, DT, PDT)); 258 EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, 259 *SecondOuterIfBody, DT, PDT)); 260 EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, 261 *SecondInnerIfBody, DT, PDT)); 262 EXPECT_FALSE(isControlFlowEquivalent(*FirstInnerIfBody, 263 *SecondOuterIfBody, DT, PDT)); 264 }); 265 } 266 267 TEST(CodeMoverUtils, IsControlFlowEquivalentImbalanceTest) { 268 LLVMContext C; 269 270 // void foo(int &i, bool cond1, bool cond2) { 271 // if (cond1) 272 // if (cond2) 273 // if (cond3) 274 // i = 1; 275 // if (cond2) 276 // if (cond3) 277 // i = 2; 278 // if (cond1) 279 // if (cond1) 280 // i = 3; 281 // if (cond1) 282 // i = 4; 283 // } 284 std::unique_ptr<Module> M = parseIR( 285 C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2, i1 %cond3) { 286 entry: 287 br i1 %cond1, label %if.outer.first, label %if.first.end 288 if.outer.first: 289 br i1 %cond2, label %if.middle.first, label %if.first.end 290 if.middle.first: 291 br i1 %cond3, label %if.inner.first, label %if.first.end 292 if.inner.first: 293 store i32 1, i32* %i, align 4 294 br label %if.first.end 295 if.first.end: 296 br i1 %cond2, label %if.outer.second, label %if.second.end 297 if.outer.second: 298 br i1 %cond3, label %if.inner.second, label %if.second.end 299 if.inner.second: 300 store i32 2, i32* %i, align 4 301 br label %if.second.end 302 if.second.end: 303 br i1 %cond1, label %if.outer.third, label %if.third.end 304 if.outer.third: 305 br i1 %cond1, label %if.inner.third, label %if.third.end 306 if.inner.third: 307 store i32 3, i32* %i, align 4 308 br label %if.third.end 309 if.third.end: 310 br i1 %cond1, label %if.fourth, label %if.fourth.end 311 if.fourth: 312 store i32 4, i32* %i, align 4 313 br label %if.fourth.end 314 if.fourth.end: 315 ret void 316 })"); 317 run(*M, "foo", 318 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 319 DependenceInfo &DI) { 320 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); 321 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); 322 EXPECT_FALSE( 323 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); 324 325 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third"); 326 BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); 327 EXPECT_TRUE( 328 isControlFlowEquivalent(*ThirdIfBody, *FourthIfBody, DT, PDT)); 329 }); 330 } 331 332 TEST(CodeMoverUtils, IsControlFlowEquivalentPointerTest) { 333 LLVMContext C; 334 335 // void foo(int &i, int *cond) { 336 // if (*cond) 337 // i = 1; 338 // if (*cond) 339 // i = 2; 340 // *cond = 1; 341 // if (*cond) 342 // i = 3; 343 // } 344 std::unique_ptr<Module> M = 345 parseIR(C, R"(define void @foo(i32* %i, i32* %cond) { 346 entry: 347 %0 = load i32, i32* %cond, align 4 348 %tobool1 = icmp ne i32 %0, 0 349 br i1 %tobool1, label %if.first, label %if.first.end 350 if.first: 351 store i32 1, i32* %i, align 4 352 br label %if.first.end 353 if.first.end: 354 %1 = load i32, i32* %cond, align 4 355 %tobool2 = icmp ne i32 %1, 0 356 br i1 %tobool2, label %if.second, label %if.second.end 357 if.second: 358 store i32 2, i32* %i, align 4 359 br label %if.second.end 360 if.second.end: 361 store i32 1, i32* %cond, align 4 362 %2 = load i32, i32* %cond, align 4 363 %tobool3 = icmp ne i32 %2, 0 364 br i1 %tobool3, label %if.third, label %if.third.end 365 if.third: 366 store i32 3, i32* %i, align 4 367 br label %if.third.end 368 if.third.end: 369 ret void 370 })"); 371 run(*M, "foo", 372 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 373 DependenceInfo &DI) { 374 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); 375 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); 376 // Limitation: if we can prove cond haven't been modify between %0 and 377 // %1, then we can prove FirstIfBody and SecondIfBody are control flow 378 // equivalent. 379 EXPECT_FALSE( 380 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); 381 382 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); 383 EXPECT_FALSE( 384 isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); 385 EXPECT_FALSE( 386 isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); 387 }); 388 } 389 390 TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) { 391 LLVMContext C; 392 393 // void foo(bool cond1, bool cond2) { 394 // if (cond1) { 395 // if (cond2) 396 // return; 397 // } else 398 // if (cond2) 399 // return; 400 // return; 401 // } 402 std::unique_ptr<Module> M = 403 parseIR(C, R"(define void @foo(i1 %cond1, i1 %cond2) { 404 idom: 405 br i1 %cond1, label %succ0, label %succ1 406 succ0: 407 br i1 %cond2, label %succ0ret, label %succ0succ1 408 succ0ret: 409 ret void 410 succ0succ1: 411 br label %bb 412 succ1: 413 br i1 %cond2, label %succ1ret, label %succ1succ1 414 succ1ret: 415 ret void 416 succ1succ1: 417 br label %bb 418 bb: 419 ret void 420 })"); 421 run(*M, "foo", 422 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 423 DependenceInfo &DI) { 424 BasicBlock &Idom = F.front(); 425 assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); 426 BasicBlock &BB = F.back(); 427 assert(BB.getName() == "bb" && "Expecting BasicBlock bb"); 428 EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT)); 429 }); 430 } 431 432 TEST(CodeMoverUtils, IsSafeToMoveTest1) { 433 LLVMContext C; 434 435 // void safecall() noexcept willreturn nosync; 436 // void unsafecall(); 437 // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C, 438 // long N) { 439 // X = N / 1; 440 // safecall(); 441 // unsafecall1(); 442 // unsafecall2(); 443 // for (long i = 0; i < N; ++i) { 444 // A[5] = 5; 445 // A[i] = 0; 446 // B[i] = A[i]; 447 // C[i] = A[i]; 448 // A[6] = 6; 449 // } 450 // } 451 std::unique_ptr<Module> M = parseIR( 452 C, R"(define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C 453 , i64 %N) { 454 entry: 455 %X = sdiv i64 1, %N 456 call void @safecall() 457 %cmp1 = icmp slt i64 0, %N 458 call void @unsafecall1() 459 call void @unsafecall2() 460 br i1 %cmp1, label %for.body, label %for.end 461 for.body: 462 %i = phi i64 [ 0, %entry ], [ %inc, %for.body ] 463 %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5 464 store i32 5, i32* %arrayidx_A5, align 4 465 %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i 466 store i32 0, i32* %arrayidx_A, align 4 467 %load1 = load i32, i32* %arrayidx_A, align 4 468 %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i 469 store i32 %load1, i32* %arrayidx_B, align 4 470 %load2 = load i32, i32* %arrayidx_A, align 4 471 %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i 472 store i32 %load2, i32* %arrayidx_C, align 4 473 %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6 474 store i32 6, i32* %arrayidx_A6, align 4 475 %inc = add nsw i64 %i, 1 476 %cmp = icmp slt i64 %inc, %N 477 br i1 %cmp, label %for.body, label %for.end 478 for.end: 479 ret void 480 } 481 declare void @safecall() nounwind nosync willreturn 482 declare void @unsafecall1() 483 declare void @unsafecall2())"); 484 485 run(*M, "foo", 486 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 487 DependenceInfo &DI) { 488 BasicBlock *Entry = getBasicBlockByName(F, "entry"); 489 Instruction *CI_safecall = Entry->front().getNextNode(); 490 assert(isa<CallInst>(CI_safecall) && 491 "Expecting CI_safecall to be a CallInst"); 492 Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode(); 493 assert(isa<CallInst>(CI_unsafecall) && 494 "Expecting CI_unsafecall to be a CallInst"); 495 BasicBlock *ForBody = getBasicBlockByName(F, "for.body"); 496 Instruction &PN = ForBody->front(); 497 assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode"); 498 Instruction *SI_A5 = 499 getInstructionByName(F, "arrayidx_A5")->getNextNode(); 500 Instruction *SI = getInstructionByName(F, "arrayidx_A")->getNextNode(); 501 Instruction *LI1 = getInstructionByName(F, "load1"); 502 Instruction *LI2 = getInstructionByName(F, "load2"); 503 Instruction *SI_A6 = 504 getInstructionByName(F, "arrayidx_A6")->getNextNode(); 505 506 // Can move after CI_safecall, as it does not throw, not synchronize, or 507 // must return. 508 EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), 509 *CI_safecall->getNextNode(), DT, &PDT, 510 &DI)); 511 512 // Cannot move CI_unsafecall, as it may throw. 513 EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), 514 *CI_unsafecall, DT, &PDT, &DI)); 515 516 // Moving instruction to non control flow equivalent places are not 517 // supported. 518 EXPECT_FALSE( 519 isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, &PDT, &DI)); 520 521 // Moving PHINode is not supported. 522 EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), 523 DT, &PDT, &DI)); 524 525 // Cannot move non-PHINode before PHINode. 526 EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI)); 527 528 // Moving Terminator is not supported. 529 EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), 530 *PN.getNextNode(), DT, &PDT, &DI)); 531 532 // Cannot move %arrayidx_A after SI, as SI is its user. 533 EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), 534 DT, &PDT, &DI)); 535 536 // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. 537 EXPECT_FALSE( 538 isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI)); 539 540 // Cannot move LI2 after SI_A6, as there is a flow dependence. 541 EXPECT_FALSE( 542 isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, &DI)); 543 544 // Cannot move SI after LI1, as there is a anti dependence. 545 EXPECT_FALSE( 546 isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI)); 547 548 // Cannot move SI_A5 after SI, as there is a output dependence. 549 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI)); 550 551 // Can move LI2 before LI1, as there is only an input dependence. 552 EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI)); 553 }); 554 } 555 556 TEST(CodeMoverUtils, IsSafeToMoveTest2) { 557 LLVMContext C; 558 559 std::unique_ptr<Module> M = 560 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { 561 entry: 562 br i1 %cond, label %if.then.first, label %if.end.first 563 if.then.first: 564 %add = add i32 %op0, %op1 565 %user = add i32 %add, 1 566 br label %if.end.first 567 if.end.first: 568 br i1 %cond, label %if.then.second, label %if.end.second 569 if.then.second: 570 %sub_op0 = add i32 %op0, 1 571 %sub = sub i32 %sub_op0, %op1 572 br label %if.end.second 573 if.end.second: 574 ret void 575 })"); 576 577 run(*M, "foo", 578 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 579 DependenceInfo &DI) { 580 Instruction *AddInst = getInstructionByName(F, "add"); 581 Instruction *SubInst = getInstructionByName(F, "sub"); 582 583 // Cannot move as %user uses %add and %sub doesn't dominates %user. 584 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); 585 586 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't 587 // dominates %sub_op0. 588 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); 589 }); 590 } 591 592 TEST(CodeMoverUtils, IsSafeToMoveTest3) { 593 LLVMContext C; 594 595 std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) { 596 entry: 597 br label %for.body 598 for.body: 599 %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ] 600 %inc = add nsw i64 %i, 1 601 br label %for.latch 602 for.latch: 603 %cmp = icmp slt i64 %inc, %N 604 %add = add i64 100, %N 605 %add2 = add i64 %add, %N 606 br i1 %cmp, label %for.body, label %for.end 607 for.end: 608 ret void 609 })"); 610 611 run(*M, "foo", 612 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 613 DependenceInfo &DI) { 614 Instruction *IncInst = getInstructionByName(F, "inc"); 615 Instruction *CmpInst = getInstructionByName(F, "cmp"); 616 BasicBlock *BB0 = getBasicBlockByName(F, "for.body"); 617 BasicBlock *BB1 = getBasicBlockByName(F, "for.latch"); 618 619 // Can move as the incoming block of %inc for %i (%for.latch) dominated 620 // by %cmp. 621 EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI)); 622 623 // Can move as the operands of instructions in BB1 either dominate 624 // InsertPoint or appear before that instruction, e.g., %add appears 625 // before %add2 although %add does not dominate InsertPoint. 626 EXPECT_TRUE( 627 isSafeToMoveBefore(*BB1, *BB0->getTerminator(), DT, &PDT, &DI)); 628 }); 629 } 630 631 TEST(CodeMoverUtils, IsSafeToMoveTest4) { 632 LLVMContext C; 633 634 std::unique_ptr<Module> M = 635 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { 636 entry: 637 br i1 %cond, label %if.end.first, label %if.then.first 638 if.then.first: 639 %add = add i32 %op0, %op1 640 %user = add i32 %add, 1 641 %add2 = add i32 %op0, 1 642 br label %if.end.first 643 if.end.first: 644 br i1 %cond, label %if.end.second, label %if.then.second 645 if.then.second: 646 %sub_op0 = add i32 %op0, 1 647 %sub = sub i32 %sub_op0, %op1 648 %sub2 = sub i32 %op0, 1 649 br label %if.end.second 650 if.end.second: 651 ret void 652 })"); 653 654 run(*M, "foo", 655 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 656 DependenceInfo &DI) { 657 Instruction *AddInst = getInstructionByName(F, "add"); 658 Instruction *AddInst2 = getInstructionByName(F, "add2"); 659 Instruction *SubInst = getInstructionByName(F, "sub"); 660 Instruction *SubInst2 = getInstructionByName(F, "sub2"); 661 662 // Cannot move as %user uses %add and %sub doesn't dominates %user. 663 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); 664 665 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't 666 // dominates %sub_op0. 667 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); 668 669 // Can move as %add2 and %sub2 are control flow equivalent, 670 // although %add2 does not strictly dominate %sub2. 671 EXPECT_TRUE(isSafeToMoveBefore(*AddInst2, *SubInst2, DT, &PDT, &DI)); 672 673 // Can move as %add2 and %sub2 are control flow equivalent, 674 // although %add2 does not strictly dominate %sub2. 675 EXPECT_TRUE(isSafeToMoveBefore(*SubInst2, *AddInst2, DT, &PDT, &DI)); 676 677 BasicBlock *BB0 = getBasicBlockByName(F, "if.then.first"); 678 BasicBlock *BB1 = getBasicBlockByName(F, "if.then.second"); 679 EXPECT_TRUE( 680 isSafeToMoveBefore(*BB0, *BB1->getTerminator(), DT, &PDT, &DI)); 681 }); 682 } 683 684 TEST(CodeMoverUtils, IsSafeToMoveTest5) { 685 LLVMContext C; 686 687 std::unique_ptr<Module> M = 688 parseIR(C, R"(define void @dependence(i32* noalias %A, i32* noalias %B){ 689 entry: 690 store i32 0, i32* %A, align 4 ; storeA0 691 store i32 2, i32* %A, align 4 ; storeA1 692 %tmp0 = load i32, i32* %A, align 4 ; loadA0 693 store i32 1, i32* %B, align 4 ; storeB0 694 %tmp1 = load i32, i32* %A, align 4 ; loadA1 695 store i32 2, i32* %A, align 4 ; storeA2 696 store i32 4, i32* %B, align 4 ; StoreB1 697 %tmp2 = load i32, i32* %A, align 4 ; loadA2 698 %tmp3 = load i32, i32* %A, align 4 ; loadA3 699 %tmp4 = load i32, i32* %B, align 4 ; loadB2 700 %tmp5 = load i32, i32* %B, align 4 ; loadB3 701 ret void 702 })"); 703 704 run(*M, "dependence", 705 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 706 DependenceInfo &DI) { 707 Instruction *LoadA0 = getInstructionByName(F, "tmp0"); 708 Instruction *LoadA1 = getInstructionByName(F, "tmp1"); 709 Instruction *LoadA2 = getInstructionByName(F, "tmp2"); 710 Instruction *LoadA3 = getInstructionByName(F, "tmp3"); 711 Instruction *LoadB2 = getInstructionByName(F, "tmp4"); 712 Instruction *LoadB3 = getInstructionByName(F, "tmp5"); 713 Instruction *StoreA1 = LoadA0->getPrevNode(); 714 Instruction *StoreA0 = StoreA1->getPrevNode(); 715 Instruction *StoreB0 = LoadA0->getNextNode(); 716 Instruction *StoreB1 = LoadA2->getPrevNode(); 717 Instruction *StoreA2 = StoreB1->getPrevNode(); 718 719 // Input forward dependency 720 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); 721 // Input backward dependency 722 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); 723 724 // Output forward dependency 725 EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI)); 726 // Output backward dependency 727 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI)); 728 729 // Flow forward dependency 730 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI)); 731 // Flow backward dependency 732 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI)); 733 734 // Anti forward dependency 735 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI)); 736 // Anti backward dependency 737 EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI)); 738 739 // No input backward dependency 740 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); 741 // No input forward dependency 742 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); 743 744 // No Output forward dependency 745 EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI)); 746 // No Output backward dependency 747 EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI)); 748 749 // No flow forward dependency 750 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI)); 751 // No flow backward dependency 752 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI)); 753 754 // No anti backward dependency 755 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI)); 756 // No anti forward dependency 757 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); 758 }); 759 } 760 761 TEST(CodeMoverUtils, IsSafeToMoveTest6) { 762 LLVMContext C; 763 764 std::unique_ptr<Module> M = parseIR( 765 C, R"(define void @dependence(i1 %cond, i32* noalias %A, i32* noalias %B){ 766 entry: 767 br i1 %cond, label %bb0, label %bb1 768 bb0: 769 br label %bb1 770 bb1: 771 store i32 0, i32* %A, align 4 ; storeA0 772 br i1 %cond, label %bb2, label %bb3 773 bb2: 774 br label %bb3 775 bb3: 776 store i32 2, i32* %A, align 4 ; storeA1 777 br i1 %cond, label %bb4, label %bb5 778 bb4: 779 br label %bb5 780 bb5: 781 %tmp0 = load i32, i32* %A, align 4 ; loadA0 782 br i1 %cond, label %bb6, label %bb7 783 bb6: 784 br label %bb7 785 bb7: 786 store i32 1, i32* %B, align 4 ; storeB0 787 br i1 %cond, label %bb8, label %bb9 788 bb8: 789 br label %bb9 790 bb9: 791 %tmp1 = load i32, i32* %A, align 4 ; loadA1 792 br i1 %cond, label %bb10, label %bb11 793 bb10: 794 br label %bb11 795 bb11: 796 store i32 2, i32* %A, align 4 ; storeA2 797 br i1 %cond, label %bb12, label %bb13 798 bb12: 799 br label %bb13 800 bb13: 801 store i32 4, i32* %B, align 4 ; StoreB1 802 br i1 %cond, label %bb14, label %bb15 803 bb14: 804 br label %bb15 805 bb15: 806 %tmp2 = load i32, i32* %A, align 4 ; loadA2 807 br i1 %cond, label %bb16, label %bb17 808 bb16: 809 br label %bb17 810 bb17: 811 %tmp3 = load i32, i32* %A, align 4 ; loadA3 812 br i1 %cond, label %bb18, label %bb19 813 bb18: 814 br label %bb19 815 bb19: 816 %tmp4 = load i32, i32* %B, align 4 ; loadB2 817 br i1 %cond, label %bb20, label %bb21 818 bb20: 819 br label %bb21 820 bb21: 821 %tmp5 = load i32, i32* %B, align 4 ; loadB3 822 ret void 823 })"); 824 run(*M, "dependence", 825 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 826 DependenceInfo &DI) { 827 BasicBlock *BB1 = getBasicBlockByName(F, "bb1"); 828 BasicBlock *BB3 = getBasicBlockByName(F, "bb3"); 829 BasicBlock *BB7 = getBasicBlockByName(F, "bb7"); 830 BasicBlock *BB11 = getBasicBlockByName(F, "bb11"); 831 BasicBlock *BB13 = getBasicBlockByName(F, "bb13"); 832 Instruction *LoadA0 = getInstructionByName(F, "tmp0"); 833 Instruction *LoadA1 = getInstructionByName(F, "tmp1"); 834 Instruction *LoadA2 = getInstructionByName(F, "tmp2"); 835 Instruction *LoadA3 = getInstructionByName(F, "tmp3"); 836 Instruction *LoadB2 = getInstructionByName(F, "tmp4"); 837 Instruction *LoadB3 = getInstructionByName(F, "tmp5"); 838 Instruction &StoreA1 = BB3->front(); 839 Instruction &StoreA0 = BB1->front(); 840 Instruction &StoreB0 = BB7->front(); 841 Instruction &StoreB1 = BB13->front(); 842 Instruction &StoreA2 = BB11->front(); 843 844 // Input forward dependency 845 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); 846 // Input backward dependency 847 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); 848 849 // Output forward dependency 850 EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI)); 851 // Output backward dependency 852 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI)); 853 854 // Flow forward dependency 855 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI)); 856 // Flow backward dependency 857 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI)); 858 859 // Anti forward dependency 860 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI)); 861 // Anti backward dependency 862 EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI)); 863 864 // No input backward dependency 865 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); 866 // No input forward dependency 867 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); 868 869 // No Output forward dependency 870 EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI)); 871 // No Output backward dependency 872 EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI)); 873 874 // No flow forward dependency 875 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI)); 876 // No flow backward dependency 877 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI)); 878 879 // No anti backward dependency 880 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI)); 881 // No anti forward dependency 882 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); 883 }); 884 } 885