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/IR/Module.h"
20 #include "llvm/Support/SourceMgr.h"
21 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
22 #include "gtest/gtest.h"
23
24 using namespace llvm;
25
parseIR(LLVMContext & C,const char * IR)26 static 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
run(Module & M,StringRef FuncName,function_ref<void (Function & F,DominatorTree & DT,PostDominatorTree & PDT,DependenceInfo & DI)> Test)34 static 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;
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
getBasicBlockByName(Function & F,StringRef Name)51 static 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
getInstructionByName(Function & F,StringRef Name)58 static 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
TEST(CodeMoverUtils,IsControlFlowEquivalentSimpleTest)66 TEST(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(i32* %i, i1 %cond1, i1 %cond2) {
79 entry:
80 br i1 %cond1, label %if.first, label %if.first.end
81 if.first:
82 store i32 1, i32* %i, align 4
83 br label %if.first.end
84 if.first.end:
85 br i1 %cond1, label %if.second, label %if.second.end
86 if.second:
87 store i32 2, i32* %i, align 4
88 br label %if.second.end
89 if.second.end:
90 br i1 %cond2, label %if.third, label %if.third.end
91 if.third:
92 store i32 3, i32* %i, align 4
93 br label %if.third.end
94 if.third.end:
95 ret void
96 })");
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
TEST(CodeMoverUtils,IsControlFlowEquivalentOppositeCondTest)115 TEST(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 // else
126 // i = 4;
127 // if (X == Y)
128 // i = 5;
129 // if (Y == X)
130 // i = 6;
131 // else
132 // i = 7;
133 // if (X != Y)
134 // i = 8;
135 // else
136 // i = 9;
137 // }
138 std::unique_ptr<Module> M =
139 parseIR(C, R"(define void @foo(i32* %i, i32 %X, i32 %Y) {
140 entry:
141 %cmp1 = icmp ult i32 %X, %Y
142 br i1 %cmp1, label %if.first, label %if.first.end
143 if.first:
144 store i32 1, i32* %i, align 4
145 br label %if.first.end
146 if.first.end:
147 %cmp2 = icmp ugt i32 %Y, %X
148 br i1 %cmp2, label %if.second, label %if.second.end
149 if.second:
150 store i32 2, i32* %i, align 4
151 br label %if.second.end
152 if.second.end:
153 %cmp3 = icmp uge i32 %X, %Y
154 br i1 %cmp3, label %if.third, label %if.third.else
155 if.third:
156 store i32 3, i32* %i, align 4
157 br label %if.third.end
158 if.third.else:
159 store i32 4, i32* %i, align 4
160 br label %if.third.end
161 if.third.end:
162 %cmp4 = icmp eq i32 %X, %Y
163 br i1 %cmp4, label %if.fourth, label %if.fourth.end
164 if.fourth:
165 store i32 5, i32* %i, align 4
166 br label %if.fourth.end
167 if.fourth.end:
168 %cmp5 = icmp eq i32 %Y, %X
169 br i1 %cmp5, label %if.fifth, label %if.fifth.else
170 if.fifth:
171 store i32 6, i32* %i, align 4
172 br label %if.fifth.end
173 if.fifth.else:
174 store i32 7, i32* %i, align 4
175 br label %if.fifth.end
176 if.fifth.end:
177 %cmp6 = icmp ne i32 %X, %Y
178 br i1 %cmp6, label %if.sixth, label %if.sixth.else
179 if.sixth:
180 store i32 8, i32* %i, align 4
181 br label %if.sixth.end
182 if.sixth.else:
183 store i32 9, i32* %i, align 4
184 br label %if.sixth.end
185 if.sixth.end:
186 ret void
187 })");
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
TEST(CodeMoverUtils,IsControlFlowEquivalentCondNestTest)218 TEST(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(i32* %i, i1 %cond1, i1 %cond2) {
231 entry:
232 br i1 %cond1, label %if.outer.first, label %if.first.end
233 if.outer.first:
234 br i1 %cond2, label %if.inner.first, label %if.first.end
235 if.inner.first:
236 store i32 1, i32* %i, align 4
237 br label %if.first.end
238 if.first.end:
239 br i1 %cond2, label %if.outer.second, label %if.second.end
240 if.outer.second:
241 br i1 %cond1, label %if.inner.second, label %if.second.end
242 if.inner.second:
243 store i32 2, i32* %i, align 4
244 br label %if.second.end
245 if.second.end:
246 ret void
247 })");
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
TEST(CodeMoverUtils,IsControlFlowEquivalentImbalanceTest)268 TEST(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 = parseIR(
286 C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2, i1 %cond3) {
287 entry:
288 br i1 %cond1, label %if.outer.first, label %if.first.end
289 if.outer.first:
290 br i1 %cond2, label %if.middle.first, label %if.first.end
291 if.middle.first:
292 br i1 %cond3, label %if.inner.first, label %if.first.end
293 if.inner.first:
294 store i32 1, i32* %i, align 4
295 br label %if.first.end
296 if.first.end:
297 br i1 %cond2, label %if.outer.second, label %if.second.end
298 if.outer.second:
299 br i1 %cond3, label %if.inner.second, label %if.second.end
300 if.inner.second:
301 store i32 2, i32* %i, align 4
302 br label %if.second.end
303 if.second.end:
304 br i1 %cond1, label %if.outer.third, label %if.third.end
305 if.outer.third:
306 br i1 %cond1, label %if.inner.third, label %if.third.end
307 if.inner.third:
308 store i32 3, i32* %i, align 4
309 br label %if.third.end
310 if.third.end:
311 br i1 %cond1, label %if.fourth, label %if.fourth.end
312 if.fourth:
313 store i32 4, i32* %i, align 4
314 br label %if.fourth.end
315 if.fourth.end:
316 ret void
317 })");
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
TEST(CodeMoverUtils,IsControlFlowEquivalentPointerTest)333 TEST(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(i32* %i, i32* %cond) {
347 entry:
348 %0 = load i32, i32* %cond, align 4
349 %tobool1 = icmp ne i32 %0, 0
350 br i1 %tobool1, label %if.first, label %if.first.end
351 if.first:
352 store i32 1, i32* %i, align 4
353 br label %if.first.end
354 if.first.end:
355 %1 = load i32, i32* %cond, align 4
356 %tobool2 = icmp ne i32 %1, 0
357 br i1 %tobool2, label %if.second, label %if.second.end
358 if.second:
359 store i32 2, i32* %i, align 4
360 br label %if.second.end
361 if.second.end:
362 store i32 1, i32* %cond, align 4
363 %2 = load i32, i32* %cond, align 4
364 %tobool3 = icmp ne i32 %2, 0
365 br i1 %tobool3, label %if.third, label %if.third.end
366 if.third:
367 store i32 3, i32* %i, align 4
368 br label %if.third.end
369 if.third.end:
370 ret void
371 })");
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 and
378 // %1, then we can prove FirstIfBody and SecondIfBody are control flow
379 // 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
TEST(CodeMoverUtils,IsControlFlowEquivalentNotPostdomTest)391 TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) {
392 LLVMContext C;
393
394 // void foo(bool cond1, bool cond2) {
395 // if (cond1) {
396 // if (cond2)
397 // return;
398 // } else
399 // 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 %succ1
407 succ0:
408 br i1 %cond2, label %succ0ret, label %succ0succ1
409 succ0ret:
410 ret void
411 succ0succ1:
412 br label %bb
413 succ1:
414 br i1 %cond2, label %succ1ret, label %succ1succ1
415 succ1ret:
416 ret void
417 succ1succ1:
418 br label %bb
419 bb:
420 ret void
421 })");
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
TEST(CodeMoverUtils,IsSafeToMoveTest1)433 TEST(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(i32* noalias %A, i32* noalias %B, i32* noalias %C
454 , i64 %N) {
455 entry:
456 %X = sdiv i64 1, %N
457 call void @safecall()
458 %cmp1 = icmp slt i64 0, %N
459 call void @unsafecall1()
460 call void @unsafecall2()
461 br i1 %cmp1, label %for.body, label %for.end
462 for.body:
463 %i = phi i64 [ 0, %entry ], [ %inc, %for.body ]
464 %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5
465 store i32 5, i32* %arrayidx_A5, align 4
466 %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i
467 store i32 0, i32* %arrayidx_A, align 4
468 %load1 = load i32, i32* %arrayidx_A, align 4
469 %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i
470 store i32 %load1, i32* %arrayidx_B, align 4
471 %load2 = load i32, i32* %arrayidx_A, align 4
472 %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i
473 store i32 %load2, i32* %arrayidx_C, align 4
474 %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6
475 store i32 6, i32* %arrayidx_A6, align 4
476 %inc = add nsw i64 %i, 1
477 %cmp = icmp slt i64 %inc, %N
478 br i1 %cmp, label %for.body, label %for.end
479 for.end:
480 ret void
481 }
482 declare void @safecall() nounwind nosync willreturn
483 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, or
508 // 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 not
518 // 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
TEST(CodeMoverUtils,IsSafeToMoveTest2)557 TEST(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.first
564 if.then.first:
565 %add = add i32 %op0, %op1
566 %user = add i32 %add, 1
567 br label %if.end.first
568 if.end.first:
569 br i1 %cond, label %if.then.second, label %if.end.second
570 if.then.second:
571 %sub_op0 = add i32 %op0, 1
572 %sub = sub i32 %sub_op0, %op1
573 br label %if.end.second
574 if.end.second:
575 ret void
576 })");
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't
588 // dominates %sub_op0.
589 EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI));
590 });
591 }
592
TEST(CodeMoverUtils,IsSafeToMoveTest3)593 TEST(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.body
599 for.body:
600 %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ]
601 %inc = add nsw i64 %i, 1
602 br label %for.latch
603 for.latch:
604 %cmp = icmp slt i64 %inc, %N
605 %add = add i64 100, %N
606 %add2 = add i64 %add, %N
607 br i1 %cmp, label %for.body, label %for.end
608 for.end:
609 ret void
610 })");
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) dominated
621 // by %cmp.
622 EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI));
623
624 // Can move as the operands of instructions in BB1 either dominate
625 // InsertPoint or appear before that instruction, e.g., %add appears
626 // before %add2 although %add does not dominate InsertPoint.
627 EXPECT_TRUE(
628 isSafeToMoveBefore(*BB1, *BB0->getTerminator(), DT, &PDT, &DI));
629 });
630 }
631
TEST(CodeMoverUtils,IsSafeToMoveTest4)632 TEST(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.first
639 if.then.first:
640 %add = add i32 %op0, %op1
641 %user = add i32 %add, 1
642 %add2 = add i32 %op0, 1
643 br label %if.end.first
644 if.end.first:
645 br i1 %cond, label %if.end.second, label %if.then.second
646 if.then.second:
647 %sub_op0 = add i32 %op0, 1
648 %sub = sub i32 %sub_op0, %op1
649 %sub2 = sub i32 %op0, 1
650 br label %if.end.second
651 if.end.second:
652 ret void
653 })");
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't
667 // 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
TEST(CodeMoverUtils,IsSafeToMoveTest5)685 TEST(CodeMoverUtils, IsSafeToMoveTest5) {
686 LLVMContext C;
687
688 std::unique_ptr<Module> M =
689 parseIR(C, R"(define void @dependence(i32* noalias %A, i32* noalias %B){
690 entry:
691 store i32 0, i32* %A, align 4 ; storeA0
692 store i32 2, i32* %A, align 4 ; storeA1
693 %tmp0 = load i32, i32* %A, align 4 ; loadA0
694 store i32 1, i32* %B, align 4 ; storeB0
695 %tmp1 = load i32, i32* %A, align 4 ; loadA1
696 store i32 2, i32* %A, align 4 ; storeA2
697 store i32 4, i32* %B, align 4 ; StoreB1
698 %tmp2 = load i32, i32* %A, align 4 ; loadA2
699 %tmp3 = load i32, i32* %A, align 4 ; loadA3
700 %tmp4 = load i32, i32* %B, align 4 ; loadB2
701 %tmp5 = load i32, i32* %B, align 4 ; loadB3
702 ret void
703 })");
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 dependency
721 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));
722 // Input backward dependency
723 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));
724
725 // Output forward dependency
726 EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI));
727 // Output backward dependency
728 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI));
729
730 // Flow forward dependency
731 EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI));
732 // Flow backward dependency
733 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI));
734
735 // Anti forward dependency
736 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));
737 // Anti backward dependency
738 EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI));
739
740 // No input backward dependency
741 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));
742 // No input forward dependency
743 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));
744
745 // No Output forward dependency
746 EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI));
747 // No Output backward dependency
748 EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI));
749
750 // No flow forward dependency
751 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI));
752 // No flow backward dependency
753 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI));
754
755 // No anti backward dependency
756 EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI));
757 // No anti forward dependency
758 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));
759 });
760 }
761
TEST(CodeMoverUtils,IsSafeToMoveTest6)762 TEST(CodeMoverUtils, IsSafeToMoveTest6) {
763 LLVMContext C;
764
765 std::unique_ptr<Module> M = parseIR(
766 C, R"(define void @dependence(i1 %cond, i32* noalias %A, i32* noalias %B){
767 entry:
768 br i1 %cond, label %bb0, label %bb1
769 bb0:
770 br label %bb1
771 bb1:
772 store i32 0, i32* %A, align 4 ; storeA0
773 br i1 %cond, label %bb2, label %bb3
774 bb2:
775 br label %bb3
776 bb3:
777 store i32 2, i32* %A, align 4 ; storeA1
778 br i1 %cond, label %bb4, label %bb5
779 bb4:
780 br label %bb5
781 bb5:
782 %tmp0 = load i32, i32* %A, align 4 ; loadA0
783 br i1 %cond, label %bb6, label %bb7
784 bb6:
785 br label %bb7
786 bb7:
787 store i32 1, i32* %B, align 4 ; storeB0
788 br i1 %cond, label %bb8, label %bb9
789 bb8:
790 br label %bb9
791 bb9:
792 %tmp1 = load i32, i32* %A, align 4 ; loadA1
793 br i1 %cond, label %bb10, label %bb11
794 bb10:
795 br label %bb11
796 bb11:
797 store i32 2, i32* %A, align 4 ; storeA2
798 br i1 %cond, label %bb12, label %bb13
799 bb12:
800 br label %bb13
801 bb13:
802 store i32 4, i32* %B, align 4 ; StoreB1
803 br i1 %cond, label %bb14, label %bb15
804 bb14:
805 br label %bb15
806 bb15:
807 %tmp2 = load i32, i32* %A, align 4 ; loadA2
808 br i1 %cond, label %bb16, label %bb17
809 bb16:
810 br label %bb17
811 bb17:
812 %tmp3 = load i32, i32* %A, align 4 ; loadA3
813 br i1 %cond, label %bb18, label %bb19
814 bb18:
815 br label %bb19
816 bb19:
817 %tmp4 = load i32, i32* %B, align 4 ; loadB2
818 br i1 %cond, label %bb20, label %bb21
819 bb20:
820 br label %bb21
821 bb21:
822 %tmp5 = load i32, i32* %B, align 4 ; loadB3
823 ret void
824 })");
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 dependency
846 EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));
847 // Input backward dependency
848 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));
849
850 // Output forward dependency
851 EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI));
852 // Output backward dependency
853 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI));
854
855 // Flow forward dependency
856 EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI));
857 // Flow backward dependency
858 EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI));
859
860 // Anti forward dependency
861 EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI));
862 // Anti backward dependency
863 EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI));
864
865 // No input backward dependency
866 EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));
867 // No input forward dependency
868 EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));
869
870 // No Output forward dependency
871 EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI));
872 // No Output backward dependency
873 EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI));
874
875 // No flow forward dependency
876 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI));
877 // No flow backward dependency
878 EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI));
879
880 // No anti backward dependency
881 EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI));
882 // No anti forward dependency
883 EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));
884 });
885 }
886