?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[docs] Fix build-docs.sh
[llvm-project.git] / llvm / unittests / Transforms / Utils / CodeMoverUtilsTest.cpp
blob8554d1a33cadee7dc80a1f3fbb2fb4baaec54550
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 }
678
679 TEST(CodeMoverUtils, IsSafeToMoveTest5) {
680 LLVMContext C;
681
682 std::unique_ptr<Module> M =
683 parseIR(C, R"(define void @dependence(i32* noalias %A, i32* noalias %B){
684 entry:
685 store i32 0, i32* %A, align 4 ; storeA0
686 store i32 2, i32* %A, align 4 ; storeA1
687 %tmp0 = load i32, i32* %A, align 4 ; loadA0
688 store i32 1, i32* %B, align 4 ; storeB0
689 %tmp1 = load i32, i32* %A, align 4 ; loadA1
690 store i32 2, i32* %A, align 4 ; storeA2
691 store i32 4, i32* %B, align 4 ; StoreB1
692 %tmp2 = load i32, i32* %A, align 4 ; loadA2
693 %tmp3 = load i32, i32* %A, align 4 ; loadA3
694 %tmp4 = load i32, i32* %B, align 4 ; loadB2
695 %tmp5 = load i32, i32* %B, align 4 ; loadB3
696 ret void
697 })");
698
699 run(*M, "dependence",
700 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
701 DependenceInfo &DI) {
702 Instruction *LoadA0 = getInstructionByName(F, "tmp0");
703 Instruction *LoadA1 = getInstructionByName(F, "tmp1");
704 Instruction *LoadA2 = getInstructionByName(F, "tmp2");
705 Instruction *LoadA3 = getInstructionByName(F, "tmp3");
706 Instruction *LoadB2 = getInstructionByName(F, "tmp4");
707 Instruction *LoadB3 = getInstructionByName(F, "tmp5");
708 Instruction *StoreA1 = LoadA0->getPrevNode();
709 Instruction *StoreA0 = StoreA1->getPrevNode();
710 Instruction *StoreB0 = LoadA0->getNextNode();
711 Instruction *StoreB1 = LoadA2->getPrevNode();
712 Instruction *StoreA2 = StoreB1->getPrevNode();
713
714 // Input forward dependency
715 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));
716 // Input backward dependency
717 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));
718
719 // Output forward dependency
720 EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI));
721 // Output backward dependency
722 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI));
723
724 // Flow forward dependency
725 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI));
726 // Flow backward dependency
727 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI));
728
729 // Anti forward dependency
730 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));
731 // Anti backward dependency
732 EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI));
733
734 // No input backward dependency
735 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));
736 // No input forward dependency
737 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));
738
739 // No Output forward dependency
740 EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI));
741 // No Output backward dependency
742 EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI));
743
744 // No flow forward dependency
745 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI));
746 // No flow backward dependency
747 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI));
748
749 // No anti backward dependency
750 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI));
751 // No anti forward dependency
752 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));
753 });
754 }
755
756 TEST(CodeMoverUtils, IsSafeToMoveTest6) {
757 LLVMContext C;
758
759 std::unique_ptr<Module> M = parseIR(
760 C, R"(define void @dependence(i1 %cond, i32* noalias %A, i32* noalias %B){
761 entry:
762 br i1 %cond, label %bb0, label %bb1
763 bb0:
764 br label %bb1
765 bb1:
766 store i32 0, i32* %A, align 4 ; storeA0
767 br i1 %cond, label %bb2, label %bb3
768 bb2:
769 br label %bb3
770 bb3:
771 store i32 2, i32* %A, align 4 ; storeA1
772 br i1 %cond, label %bb4, label %bb5
773 bb4:
774 br label %bb5
775 bb5:
776 %tmp0 = load i32, i32* %A, align 4 ; loadA0
777 br i1 %cond, label %bb6, label %bb7
778 bb6:
779 br label %bb7
780 bb7:
781 store i32 1, i32* %B, align 4 ; storeB0
782 br i1 %cond, label %bb8, label %bb9
783 bb8:
784 br label %bb9
785 bb9:
786 %tmp1 = load i32, i32* %A, align 4 ; loadA1
787 br i1 %cond, label %bb10, label %bb11
788 bb10:
789 br label %bb11
790 bb11:
791 store i32 2, i32* %A, align 4 ; storeA2
792 br i1 %cond, label %bb12, label %bb13
793 bb12:
794 br label %bb13
795 bb13:
796 store i32 4, i32* %B, align 4 ; StoreB1
797 br i1 %cond, label %bb14, label %bb15
798 bb14:
799 br label %bb15
800 bb15:
801 %tmp2 = load i32, i32* %A, align 4 ; loadA2
802 br i1 %cond, label %bb16, label %bb17
803 bb16:
804 br label %bb17
805 bb17:
806 %tmp3 = load i32, i32* %A, align 4 ; loadA3
807 br i1 %cond, label %bb18, label %bb19
808 bb18:
809 br label %bb19
810 bb19:
811 %tmp4 = load i32, i32* %B, align 4 ; loadB2
812 br i1 %cond, label %bb20, label %bb21
813 bb20:
814 br label %bb21
815 bb21:
816 %tmp5 = load i32, i32* %B, align 4 ; loadB3
817 ret void
818 })");
819 run(*M, "dependence",
820 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
821 DependenceInfo &DI) {
822 BasicBlock *BB1 = getBasicBlockByName(F, "bb1");
823 BasicBlock *BB3 = getBasicBlockByName(F, "bb3");
824 BasicBlock *BB7 = getBasicBlockByName(F, "bb7");
825 BasicBlock *BB11 = getBasicBlockByName(F, "bb11");
826 BasicBlock *BB13 = getBasicBlockByName(F, "bb13");
827 Instruction *LoadA0 = getInstructionByName(F, "tmp0");
828 Instruction *LoadA1 = getInstructionByName(F, "tmp1");
829 Instruction *LoadA2 = getInstructionByName(F, "tmp2");
830 Instruction *LoadA3 = getInstructionByName(F, "tmp3");
831 Instruction *LoadB2 = getInstructionByName(F, "tmp4");
832 Instruction *LoadB3 = getInstructionByName(F, "tmp5");
833 Instruction &StoreA1 = BB3->front();
834 Instruction &StoreA0 = BB1->front();
835 Instruction &StoreB0 = BB7->front();
836 Instruction &StoreB1 = BB13->front();
837 Instruction &StoreA2 = BB11->front();
838
839 // Input forward dependency
840 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));
841 // Input backward dependency
842 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));
843
844 // Output forward dependency
845 EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI));
846 // Output backward dependency
847 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI));
848
849 // Flow forward dependency
850 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI));
851 // Flow backward dependency
852 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI));
853
854 // Anti forward dependency
855 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI));
856 // Anti backward dependency
857 EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI));
858
859 // No input backward dependency
860 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));
861 // No input forward dependency
862 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));
863
864 // No Output forward dependency
865 EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI));
866 // No Output backward dependency
867 EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI));
868
869 // No flow forward dependency
870 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI));
871 // No flow backward dependency
872 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI));
873
874 // No anti backward dependency
875 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI));
876 // No anti forward dependency
877 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));
878 });
879 }
LLVM monorepo