886 lines · cpp
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-exception6//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/IR/Module.h"20#include "llvm/Support/SourceMgr.h"21#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"22#include "gtest/gtest.h"23 24using namespace llvm;25 26static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {27 SMDiagnostic Err;28 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);29 if (!Mod)30 Err.print("CodeMoverUtilsTests", errs());31 return Mod;32}33 34static void run(Module &M, StringRef FuncName,35 function_ref<void(Function &F, DominatorTree &DT,36 PostDominatorTree &PDT, DependenceInfo &DI)>37 Test) {38 auto *F = M.getFunction(FuncName);39 DominatorTree DT(*F);40 PostDominatorTree PDT(*F);41 TargetLibraryInfoImpl TLII(M.getTargetTriple());42 TargetLibraryInfo TLI(TLII);43 AssumptionCache AC(*F);44 AliasAnalysis AA(TLI);45 LoopInfo LI(DT);46 ScalarEvolution SE(*F, TLI, AC, DT, LI);47 DependenceInfo DI(F, &AA, &SE, &LI);48 Test(*F, DT, PDT, DI);49}50 51static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {52 for (BasicBlock &BB : F)53 if (BB.getName() == Name)54 return &BB;55 llvm_unreachable("Expected to find basic block!");56}57 58static Instruction *getInstructionByName(Function &F, StringRef Name) {59 for (BasicBlock &BB : F)60 for (Instruction &I : BB)61 if (I.getName() == Name)62 return &I;63 llvm_unreachable("Expected to find instruction!");64}65 66TEST(CodeMoverUtils, IsControlFlowEquivalentSimpleTest) {67 LLVMContext C;68 69 // void foo(int &i, bool cond1, bool cond2) {70 // if (cond1)71 // i = 1;72 // if (cond1)73 // i = 2;74 // if (cond2)75 // i = 3;76 // }77 std::unique_ptr<Module> M =78 parseIR(C, R"(define void @foo(ptr %i, i1 %cond1, i1 %cond2) {79 entry:80 br i1 %cond1, label %if.first, label %if.first.end81 if.first:82 store i32 1, ptr %i, align 483 br label %if.first.end84 if.first.end:85 br i1 %cond1, label %if.second, label %if.second.end86 if.second:87 store i32 2, ptr %i, align 488 br label %if.second.end89 if.second.end:90 br i1 %cond2, label %if.third, label %if.third.end91 if.third:92 store i32 3, ptr %i, align 493 br label %if.third.end94 if.third.end:95 ret void96 })");97 run(*M, "foo",98 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,99 DependenceInfo &DI) {100 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");101 EXPECT_TRUE(102 isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT));103 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");104 EXPECT_TRUE(105 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));106 107 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");108 EXPECT_FALSE(109 isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT));110 EXPECT_FALSE(111 isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT));112 });113}114 115TEST(CodeMoverUtils, IsControlFlowEquivalentOppositeCondTest) {116 LLVMContext C;117 118 // void foo(int &i, unsigned X, unsigned Y) {119 // if (X < Y)120 // i = 1;121 // if (Y > X)122 // i = 2;123 // if (X >= Y)124 // i = 3;125 // else126 // i = 4;127 // if (X == Y)128 // i = 5;129 // if (Y == X)130 // i = 6;131 // else132 // i = 7;133 // if (X != Y)134 // i = 8;135 // else136 // i = 9;137 // }138 std::unique_ptr<Module> M =139 parseIR(C, R"(define void @foo(ptr %i, i32 %X, i32 %Y) {140 entry:141 %cmp1 = icmp ult i32 %X, %Y142 br i1 %cmp1, label %if.first, label %if.first.end143 if.first:144 store i32 1, ptr %i, align 4145 br label %if.first.end146 if.first.end:147 %cmp2 = icmp ugt i32 %Y, %X148 br i1 %cmp2, label %if.second, label %if.second.end149 if.second:150 store i32 2, ptr %i, align 4151 br label %if.second.end152 if.second.end:153 %cmp3 = icmp uge i32 %X, %Y154 br i1 %cmp3, label %if.third, label %if.third.else155 if.third:156 store i32 3, ptr %i, align 4157 br label %if.third.end158 if.third.else:159 store i32 4, ptr %i, align 4160 br label %if.third.end161 if.third.end:162 %cmp4 = icmp eq i32 %X, %Y163 br i1 %cmp4, label %if.fourth, label %if.fourth.end164 if.fourth:165 store i32 5, ptr %i, align 4166 br label %if.fourth.end167 if.fourth.end:168 %cmp5 = icmp eq i32 %Y, %X169 br i1 %cmp5, label %if.fifth, label %if.fifth.else170 if.fifth:171 store i32 6, ptr %i, align 4172 br label %if.fifth.end173 if.fifth.else:174 store i32 7, ptr %i, align 4175 br label %if.fifth.end176 if.fifth.end:177 %cmp6 = icmp ne i32 %X, %Y178 br i1 %cmp6, label %if.sixth, label %if.sixth.else179 if.sixth:180 store i32 8, ptr %i, align 4181 br label %if.sixth.end182 if.sixth.else:183 store i32 9, ptr %i, align 4184 br label %if.sixth.end185 if.sixth.end:186 ret void187 })");188 run(*M, "foo",189 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,190 DependenceInfo &DI) {191 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");192 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");193 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");194 BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else");195 EXPECT_TRUE(196 isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT));197 EXPECT_TRUE(198 isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT));199 EXPECT_FALSE(200 isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT));201 202 BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth");203 BasicBlock *FifthIfBody = getBasicBlockByName(F, "if.fifth");204 BasicBlock *FifthElseBody = getBasicBlockByName(F, "if.fifth.else");205 EXPECT_FALSE(206 isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT));207 BasicBlock *SixthIfBody = getBasicBlockByName(F, "if.sixth");208 EXPECT_TRUE(209 isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT));210 BasicBlock *SixthElseBody = getBasicBlockByName(F, "if.sixth.else");211 EXPECT_TRUE(212 isControlFlowEquivalent(*FourthIfBody, *SixthElseBody, DT, PDT));213 EXPECT_TRUE(214 isControlFlowEquivalent(*FifthIfBody, *SixthElseBody, DT, PDT));215 });216}217 218TEST(CodeMoverUtils, IsControlFlowEquivalentCondNestTest) {219 LLVMContext C;220 221 // void foo(int &i, bool cond1, bool cond2) {222 // if (cond1)223 // if (cond2)224 // i = 1;225 // if (cond2)226 // if (cond1)227 // i = 2;228 // }229 std::unique_ptr<Module> M =230 parseIR(C, R"(define void @foo(ptr %i, i1 %cond1, i1 %cond2) {231 entry:232 br i1 %cond1, label %if.outer.first, label %if.first.end233 if.outer.first:234 br i1 %cond2, label %if.inner.first, label %if.first.end235 if.inner.first:236 store i32 1, ptr %i, align 4237 br label %if.first.end238 if.first.end:239 br i1 %cond2, label %if.outer.second, label %if.second.end240 if.outer.second:241 br i1 %cond1, label %if.inner.second, label %if.second.end242 if.inner.second:243 store i32 2, ptr %i, align 4244 br label %if.second.end245 if.second.end:246 ret void247 })");248 run(*M, "foo",249 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,250 DependenceInfo &DI) {251 BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first");252 BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first");253 BasicBlock *SecondOuterIfBody =254 getBasicBlockByName(F, "if.outer.second");255 BasicBlock *SecondInnerIfBody =256 getBasicBlockByName(F, "if.inner.second");257 EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody,258 *SecondInnerIfBody, DT, PDT));259 EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody,260 *SecondOuterIfBody, DT, PDT));261 EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody,262 *SecondInnerIfBody, DT, PDT));263 EXPECT_FALSE(isControlFlowEquivalent(*FirstInnerIfBody,264 *SecondOuterIfBody, DT, PDT));265 });266}267 268TEST(CodeMoverUtils, IsControlFlowEquivalentImbalanceTest) {269 LLVMContext C;270 271 // void foo(int &i, bool cond1, bool cond2) {272 // if (cond1)273 // if (cond2)274 // if (cond3)275 // i = 1;276 // if (cond2)277 // if (cond3)278 // i = 2;279 // if (cond1)280 // if (cond1)281 // i = 3;282 // if (cond1)283 // i = 4;284 // }285 std::unique_ptr<Module> M =286 parseIR(C, R"(define void @foo(ptr %i, i1 %cond1, i1 %cond2, i1 %cond3) {287 entry:288 br i1 %cond1, label %if.outer.first, label %if.first.end289 if.outer.first:290 br i1 %cond2, label %if.middle.first, label %if.first.end291 if.middle.first:292 br i1 %cond3, label %if.inner.first, label %if.first.end293 if.inner.first:294 store i32 1, ptr %i, align 4295 br label %if.first.end296 if.first.end:297 br i1 %cond2, label %if.outer.second, label %if.second.end298 if.outer.second:299 br i1 %cond3, label %if.inner.second, label %if.second.end300 if.inner.second:301 store i32 2, ptr %i, align 4302 br label %if.second.end303 if.second.end:304 br i1 %cond1, label %if.outer.third, label %if.third.end305 if.outer.third:306 br i1 %cond1, label %if.inner.third, label %if.third.end307 if.inner.third:308 store i32 3, ptr %i, align 4309 br label %if.third.end310 if.third.end:311 br i1 %cond1, label %if.fourth, label %if.fourth.end312 if.fourth:313 store i32 4, ptr %i, align 4314 br label %if.fourth.end315 if.fourth.end:316 ret void317 })");318 run(*M, "foo",319 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,320 DependenceInfo &DI) {321 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first");322 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second");323 EXPECT_FALSE(324 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));325 326 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third");327 BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth");328 EXPECT_TRUE(329 isControlFlowEquivalent(*ThirdIfBody, *FourthIfBody, DT, PDT));330 });331}332 333TEST(CodeMoverUtils, IsControlFlowEquivalentPointerTest) {334 LLVMContext C;335 336 // void foo(int &i, int *cond) {337 // if (*cond)338 // i = 1;339 // if (*cond)340 // i = 2;341 // *cond = 1;342 // if (*cond)343 // i = 3;344 // }345 std::unique_ptr<Module> M =346 parseIR(C, R"(define void @foo(ptr %i, ptr %cond) {347 entry:348 %0 = load i32, ptr %cond, align 4349 %tobool1 = icmp ne i32 %0, 0350 br i1 %tobool1, label %if.first, label %if.first.end351 if.first:352 store i32 1, ptr %i, align 4353 br label %if.first.end354 if.first.end:355 %1 = load i32, ptr %cond, align 4356 %tobool2 = icmp ne i32 %1, 0357 br i1 %tobool2, label %if.second, label %if.second.end358 if.second:359 store i32 2, ptr %i, align 4360 br label %if.second.end361 if.second.end:362 store i32 1, ptr %cond, align 4363 %2 = load i32, ptr %cond, align 4364 %tobool3 = icmp ne i32 %2, 0365 br i1 %tobool3, label %if.third, label %if.third.end366 if.third:367 store i32 3, ptr %i, align 4368 br label %if.third.end369 if.third.end:370 ret void371 })");372 run(*M, "foo",373 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,374 DependenceInfo &DI) {375 BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");376 BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");377 // Limitation: if we can prove cond haven't been modify between %0 and378 // %1, then we can prove FirstIfBody and SecondIfBody are control flow379 // equivalent.380 EXPECT_FALSE(381 isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));382 383 BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");384 EXPECT_FALSE(385 isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT));386 EXPECT_FALSE(387 isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT));388 });389}390 391TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) {392 LLVMContext C;393 394 // void foo(bool cond1, bool cond2) {395 // if (cond1) {396 // if (cond2)397 // return;398 // } else399 // if (cond2)400 // return;401 // return;402 // }403 std::unique_ptr<Module> M =404 parseIR(C, R"(define void @foo(i1 %cond1, i1 %cond2) {405 idom:406 br i1 %cond1, label %succ0, label %succ1407 succ0:408 br i1 %cond2, label %succ0ret, label %succ0succ1409 succ0ret:410 ret void411 succ0succ1:412 br label %bb413 succ1:414 br i1 %cond2, label %succ1ret, label %succ1succ1415 succ1ret:416 ret void417 succ1succ1:418 br label %bb419 bb:420 ret void421 })");422 run(*M, "foo",423 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,424 DependenceInfo &DI) {425 BasicBlock &Idom = F.front();426 assert(Idom.getName() == "idom" && "Expecting BasicBlock idom");427 BasicBlock &BB = F.back();428 assert(BB.getName() == "bb" && "Expecting BasicBlock bb");429 EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT));430 });431}432 433TEST(CodeMoverUtils, IsSafeToMoveTest1) {434 LLVMContext C;435 436 // void safecall() noexcept willreturn nosync;437 // void unsafecall();438 // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C,439 // long N) {440 // X = N / 1;441 // safecall();442 // unsafecall1();443 // unsafecall2();444 // for (long i = 0; i < N; ++i) {445 // A[5] = 5;446 // A[i] = 0;447 // B[i] = A[i];448 // C[i] = A[i];449 // A[6] = 6;450 // }451 // }452 std::unique_ptr<Module> M = parseIR(453 C, R"(define void @foo(ptr noalias %A, ptr noalias %B, ptr noalias %C454 , i64 %N) {455 entry:456 %X = sdiv i64 1, %N457 call void @safecall()458 %cmp1 = icmp slt i64 0, %N459 call void @unsafecall1()460 call void @unsafecall2()461 br i1 %cmp1, label %for.body, label %for.end462 for.body:463 %i = phi i64 [ 0, %entry ], [ %inc, %for.body ]464 %arrayidx_A5 = getelementptr inbounds i32, ptr %A, i64 5465 store i32 5, ptr %arrayidx_A5, align 4466 %arrayidx_A = getelementptr inbounds i32, ptr %A, i64 %i467 store i32 0, ptr %arrayidx_A, align 4468 %load1 = load i32, ptr %arrayidx_A, align 4469 %arrayidx_B = getelementptr inbounds i32, ptr %B, i64 %i470 store i32 %load1, ptr %arrayidx_B, align 4471 %load2 = load i32, ptr %arrayidx_A, align 4472 %arrayidx_C = getelementptr inbounds i32, ptr %C, i64 %i473 store i32 %load2, ptr %arrayidx_C, align 4474 %arrayidx_A6 = getelementptr inbounds i32, ptr %A, i64 6475 store i32 6, ptr %arrayidx_A6, align 4476 %inc = add nsw i64 %i, 1477 %cmp = icmp slt i64 %inc, %N478 br i1 %cmp, label %for.body, label %for.end479 for.end:480 ret void481 }482 declare void @safecall() nounwind nosync willreturn483 declare void @unsafecall1()484 declare void @unsafecall2())");485 486 run(*M, "foo",487 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,488 DependenceInfo &DI) {489 BasicBlock *Entry = getBasicBlockByName(F, "entry");490 Instruction *CI_safecall = Entry->front().getNextNode();491 assert(isa<CallInst>(CI_safecall) &&492 "Expecting CI_safecall to be a CallInst");493 Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode();494 assert(isa<CallInst>(CI_unsafecall) &&495 "Expecting CI_unsafecall to be a CallInst");496 BasicBlock *ForBody = getBasicBlockByName(F, "for.body");497 Instruction &PN = ForBody->front();498 assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode");499 Instruction *SI_A5 =500 getInstructionByName(F, "arrayidx_A5")->getNextNode();501 Instruction *SI = getInstructionByName(F, "arrayidx_A")->getNextNode();502 Instruction *LI1 = getInstructionByName(F, "load1");503 Instruction *LI2 = getInstructionByName(F, "load2");504 Instruction *SI_A6 =505 getInstructionByName(F, "arrayidx_A6")->getNextNode();506 507 // Can move after CI_safecall, as it does not throw, not synchronize, or508 // must return.509 EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(),510 *CI_safecall->getNextNode(), DT, &PDT,511 &DI));512 513 // Cannot move CI_unsafecall, as it may throw.514 EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(),515 *CI_unsafecall, DT, &PDT, &DI));516 517 // Moving instruction to non control flow equivalent places are not518 // supported.519 EXPECT_FALSE(520 isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, &PDT, &DI));521 522 // Moving PHINode is not supported.523 EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(),524 DT, &PDT, &DI));525 526 // Cannot move non-PHINode before PHINode.527 EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI));528 529 // Moving Terminator is not supported.530 EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(),531 *PN.getNextNode(), DT, &PDT, &DI));532 533 // Cannot move %arrayidx_A after SI, as SI is its user.534 EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(),535 DT, &PDT, &DI));536 537 // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand.538 EXPECT_FALSE(539 isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI));540 541 // Cannot move LI2 after SI_A6, as there is a flow dependence.542 EXPECT_FALSE(543 isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, &DI));544 545 // Cannot move SI after LI1, as there is a anti dependence.546 EXPECT_FALSE(547 isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI));548 549 // Cannot move SI_A5 after SI, as there is a output dependence.550 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI));551 552 // Can move LI2 before LI1, as there is only an input dependence.553 EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI));554 });555}556 557TEST(CodeMoverUtils, IsSafeToMoveTest2) {558 LLVMContext C;559 560 std::unique_ptr<Module> M =561 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {562 entry:563 br i1 %cond, label %if.then.first, label %if.end.first564 if.then.first:565 %add = add i32 %op0, %op1566 %user = add i32 %add, 1567 br label %if.end.first568 if.end.first:569 br i1 %cond, label %if.then.second, label %if.end.second570 if.then.second:571 %sub_op0 = add i32 %op0, 1572 %sub = sub i32 %sub_op0, %op1573 br label %if.end.second574 if.end.second:575 ret void576 })");577 578 run(*M, "foo",579 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,580 DependenceInfo &DI) {581 Instruction *AddInst = getInstructionByName(F, "add");582 Instruction *SubInst = getInstructionByName(F, "sub");583 584 // Cannot move as %user uses %add and %sub doesn't dominates %user.585 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI));586 587 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't588 // dominates %sub_op0.589 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI));590 });591}592 593TEST(CodeMoverUtils, IsSafeToMoveTest3) {594 LLVMContext C;595 596 std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) {597 entry:598 br label %for.body599 for.body:600 %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ]601 %inc = add nsw i64 %i, 1602 br label %for.latch603 for.latch:604 %cmp = icmp slt i64 %inc, %N605 %add = add i64 100, %N606 %add2 = add i64 %add, %N607 br i1 %cmp, label %for.body, label %for.end608 for.end:609 ret void610 })");611 612 run(*M, "foo",613 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,614 DependenceInfo &DI) {615 Instruction *IncInst = getInstructionByName(F, "inc");616 Instruction *CmpInst = getInstructionByName(F, "cmp");617 BasicBlock *BB0 = getBasicBlockByName(F, "for.body");618 BasicBlock *BB1 = getBasicBlockByName(F, "for.latch");619 620 // Can move as the incoming block of %inc for %i (%for.latch) dominated621 // by %cmp.622 EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI));623 624 // Can move as the operands of instructions in BB1 either dominate625 // InsertPoint or appear before that instruction, e.g., %add appears626 // before %add2 although %add does not dominate InsertPoint.627 EXPECT_TRUE(628 isSafeToMoveBefore(*BB1, *BB0->getTerminator(), DT, &PDT, &DI));629 });630}631 632TEST(CodeMoverUtils, IsSafeToMoveTest4) {633 LLVMContext C;634 635 std::unique_ptr<Module> M =636 parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {637 entry:638 br i1 %cond, label %if.end.first, label %if.then.first639 if.then.first:640 %add = add i32 %op0, %op1641 %user = add i32 %add, 1642 %add2 = add i32 %op0, 1643 br label %if.end.first644 if.end.first:645 br i1 %cond, label %if.end.second, label %if.then.second646 if.then.second:647 %sub_op0 = add i32 %op0, 1648 %sub = sub i32 %sub_op0, %op1649 %sub2 = sub i32 %op0, 1650 br label %if.end.second651 if.end.second:652 ret void653 })");654 655 run(*M, "foo",656 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,657 DependenceInfo &DI) {658 Instruction *AddInst = getInstructionByName(F, "add");659 Instruction *AddInst2 = getInstructionByName(F, "add2");660 Instruction *SubInst = getInstructionByName(F, "sub");661 Instruction *SubInst2 = getInstructionByName(F, "sub2");662 663 // Cannot move as %user uses %add and %sub doesn't dominates %user.664 EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI));665 666 // Cannot move as %sub_op0 is an operand of %sub and %add doesn't667 // dominates %sub_op0.668 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI));669 670 // Can move as %add2 and %sub2 are control flow equivalent,671 // although %add2 does not strictly dominate %sub2.672 EXPECT_TRUE(isSafeToMoveBefore(*AddInst2, *SubInst2, DT, &PDT, &DI));673 674 // Can move as %add2 and %sub2 are control flow equivalent,675 // although %add2 does not strictly dominate %sub2.676 EXPECT_TRUE(isSafeToMoveBefore(*SubInst2, *AddInst2, DT, &PDT, &DI));677 678 BasicBlock *BB0 = getBasicBlockByName(F, "if.then.first");679 BasicBlock *BB1 = getBasicBlockByName(F, "if.then.second");680 EXPECT_TRUE(681 isSafeToMoveBefore(*BB0, *BB1->getTerminator(), DT, &PDT, &DI));682 });683}684 685TEST(CodeMoverUtils, IsSafeToMoveTest5) {686 LLVMContext C;687 688 std::unique_ptr<Module> M =689 parseIR(C, R"(define void @dependence(ptr noalias %A, ptr noalias %B){690entry:691 store i32 0, ptr %A, align 4 ; storeA0692 store i32 2, ptr %A, align 4 ; storeA1693 %tmp0 = load i32, ptr %A, align 4 ; loadA0694 store i32 1, ptr %B, align 4 ; storeB0695 %tmp1 = load i32, ptr %A, align 4 ; loadA1696 store i32 2, ptr %A, align 4 ; storeA2697 store i32 4, ptr %B, align 4 ; StoreB1698 %tmp2 = load i32, ptr %A, align 4 ; loadA2699 %tmp3 = load i32, ptr %A, align 4 ; loadA3700 %tmp4 = load i32, ptr %B, align 4 ; loadB2701 %tmp5 = load i32, ptr %B, align 4 ; loadB3702 ret void703})");704 705 run(*M, "dependence",706 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,707 DependenceInfo &DI) {708 Instruction *LoadA0 = getInstructionByName(F, "tmp0");709 Instruction *LoadA1 = getInstructionByName(F, "tmp1");710 Instruction *LoadA2 = getInstructionByName(F, "tmp2");711 Instruction *LoadA3 = getInstructionByName(F, "tmp3");712 Instruction *LoadB2 = getInstructionByName(F, "tmp4");713 Instruction *LoadB3 = getInstructionByName(F, "tmp5");714 Instruction *StoreA1 = LoadA0->getPrevNode();715 Instruction *StoreA0 = StoreA1->getPrevNode();716 Instruction *StoreB0 = LoadA0->getNextNode();717 Instruction *StoreB1 = LoadA2->getPrevNode();718 Instruction *StoreA2 = StoreB1->getPrevNode();719 720 // Input forward dependency721 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));722 // Input backward dependency723 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));724 725 // Output forward dependency726 EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI));727 // Output backward dependency728 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI));729 730 // Flow forward dependency731 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI));732 // Flow backward dependency733 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI));734 735 // Anti forward dependency736 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));737 // Anti backward dependency738 EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI));739 740 // No input backward dependency741 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));742 // No input forward dependency743 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));744 745 // No Output forward dependency746 EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI));747 // No Output backward dependency748 EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI));749 750 // No flow forward dependency751 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI));752 // No flow backward dependency753 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI));754 755 // No anti backward dependency756 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI));757 // No anti forward dependency758 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));759 });760}761 762TEST(CodeMoverUtils, IsSafeToMoveTest6) {763 LLVMContext C;764 765 std::unique_ptr<Module> M = parseIR(766 C, R"(define void @dependence(i1 %cond, ptr noalias %A, ptr noalias %B){767 entry:768 br i1 %cond, label %bb0, label %bb1769 bb0:770 br label %bb1771 bb1:772 store i32 0, ptr %A, align 4 ; storeA0773 br i1 %cond, label %bb2, label %bb3774 bb2:775 br label %bb3776 bb3:777 store i32 2, ptr %A, align 4 ; storeA1778 br i1 %cond, label %bb4, label %bb5779 bb4:780 br label %bb5781 bb5:782 %tmp0 = load i32, ptr %A, align 4 ; loadA0783 br i1 %cond, label %bb6, label %bb7784 bb6:785 br label %bb7786 bb7:787 store i32 1, ptr %B, align 4 ; storeB0788 br i1 %cond, label %bb8, label %bb9789 bb8:790 br label %bb9791 bb9:792 %tmp1 = load i32, ptr %A, align 4 ; loadA1793 br i1 %cond, label %bb10, label %bb11794 bb10:795 br label %bb11796 bb11:797 store i32 2, ptr %A, align 4 ; storeA2798 br i1 %cond, label %bb12, label %bb13799 bb12:800 br label %bb13801 bb13:802 store i32 4, ptr %B, align 4 ; StoreB1803 br i1 %cond, label %bb14, label %bb15804 bb14:805 br label %bb15806 bb15:807 %tmp2 = load i32, ptr %A, align 4 ; loadA2808 br i1 %cond, label %bb16, label %bb17809 bb16:810 br label %bb17811 bb17:812 %tmp3 = load i32, ptr %A, align 4 ; loadA3813 br i1 %cond, label %bb18, label %bb19814 bb18:815 br label %bb19816 bb19:817 %tmp4 = load i32, ptr %B, align 4 ; loadB2818 br i1 %cond, label %bb20, label %bb21819 bb20:820 br label %bb21821 bb21:822 %tmp5 = load i32, ptr %B, align 4 ; loadB3823 ret void824 })");825 run(*M, "dependence",826 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,827 DependenceInfo &DI) {828 BasicBlock *BB1 = getBasicBlockByName(F, "bb1");829 BasicBlock *BB3 = getBasicBlockByName(F, "bb3");830 BasicBlock *BB7 = getBasicBlockByName(F, "bb7");831 BasicBlock *BB11 = getBasicBlockByName(F, "bb11");832 BasicBlock *BB13 = getBasicBlockByName(F, "bb13");833 Instruction *LoadA0 = getInstructionByName(F, "tmp0");834 Instruction *LoadA1 = getInstructionByName(F, "tmp1");835 Instruction *LoadA2 = getInstructionByName(F, "tmp2");836 Instruction *LoadA3 = getInstructionByName(F, "tmp3");837 Instruction *LoadB2 = getInstructionByName(F, "tmp4");838 Instruction *LoadB3 = getInstructionByName(F, "tmp5");839 Instruction &StoreA1 = BB3->front();840 Instruction &StoreA0 = BB1->front();841 Instruction &StoreB0 = BB7->front();842 Instruction &StoreB1 = BB13->front();843 Instruction &StoreA2 = BB11->front();844 845 // Input forward dependency846 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));847 // Input backward dependency848 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));849 850 // Output forward dependency851 EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI));852 // Output backward dependency853 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI));854 855 // Flow forward dependency856 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI));857 // Flow backward dependency858 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI));859 860 // Anti forward dependency861 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI));862 // Anti backward dependency863 EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI));864 865 // No input backward dependency866 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));867 // No input forward dependency868 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));869 870 // No Output forward dependency871 EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI));872 // No Output backward dependency873 EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI));874 875 // No flow forward dependency876 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI));877 // No flow backward dependency878 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI));879 880 // No anti backward dependency881 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI));882 // No anti forward dependency883 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));884 });885}886