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