[CodeMoverUtils] Add more data dependency related test case

[RithikSharma]

Summary

This patch adds more test case focusing on data dependency

[bmahjour]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

697

This should be EXPECT_FALSE!

[Whitney]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

698

should this be flow dependency? as the dependency is still read after write.

[Whitney]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

679

This may make it more clear:

Instruction *LoadA0 = getInstructionByName(F, "tmp0");
Instruction *LoadA1 = getInstructionByName(F, "tmp1");
Instruction *LoadA2 = getInstructionByName(F, "tmp2");
Instruction *LoadA3 = getInstructionByName(F, "tmp3");
Instruction *LoadB2 = getInstructionByName(F, "tmp4");
Instruction *LoadB3 = getInstructionByName(F, "tmp5");
Instruction *StoreA1 = LoadA0->getPrevNode();
Instruction *StoreA0 = StoreA1->getPrevNode();
Instruction *StoreB0 = LoadA0->getNextNode();
Instruction *StoreB1 = LoadA2->getPrevNode();
Instruction *StoreA2 = StoreB1->getPrevNode();

// Input forward dependency
EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));
// Input backward dependency
EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));

// Output forward dependency
EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI));
// Output backward dependency
EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI));

// Flow forward dependency
EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI));
// Flow backward dependency
EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI));

// Anti forward dependency
EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));
// Anti backward dependency
EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI));
       
// No input backward dependency
EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));
// No input forward dependency
EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));

// No output forward dependency
EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI));
// No output backward dependency
EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI));

// No flow forward dependency
EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI));
// No flow backward dependency
EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI));

// No anti backward dependency
EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI));
// No anti forward dependency
EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));

[Whitney]

https://reviews.llvm.org/rG167cac3100f5145186db678e497028a426ace655

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

run(*M, "foo",
         // Cannot move as %user uses %add and %sub doesn't dominates %user.
         EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI));
 
         // Cannot move as %sub_op0 is an operand of %sub and %add doesn't
         // dominates %sub_op0.
         EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI));
       });
 }
+
+TEST(CodeMoverUtils, IsSafeToMoveTest5) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M =
+      parseIR(C, R"(define void @dependence(i32* noalias %A, i32* noalias %B){
+entry:
+    store i32 0, i32* %A, align 4 ; storeA0
+    store i32 2, i32* %A, align 4 ; storeA1
+    %tmp0 = load i32, i32* %A, align 4 ; loadA0
+    store i32 1, i32* %B, align 4 ; storeB0
+    %tmp1 = load i32, i32* %A, align 4 ; loadA1
+    store i32 2, i32* %A, align 4 ; storeA2 
+    store i32 4, i32* %B, align 4 ; StoreB1 
+    %tmp2 = load i32, i32* %A, align 4 ; loadA2 
+    %tmp3 = load i32, i32* %A, align 4 ; loadA3 
+    %tmp4 = load i32, i32* %B, align 4 ; loadB2
+    %tmp5 = load i32, i32* %B, align 4 ; loadB3
+    ret void
+})");
+
+  run(*M, "dependence",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Instruction *LoadA0 = getInstructionByName(F, "tmp0");
+        Instruction *StoreA1 = LoadA0->getPrevNode();
+        Instruction *StoreA0 = StoreA1->getPrevNode();
+        // Output forward dependency
+        EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI));
+        // Output backward dependency
+        EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI));
+
+        Instruction *LoadA2 = getInstructionByName(F, "tmp2");
+        Instruction *StoreB1 = LoadA2->getPrevNode();
+        Instruction *StoreA2 = StoreB1->getNextNode();
+        // No Output forward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI));
+        // No Output backward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI));
+
+        Instruction *StoreB0 = LoadA0->getNextNode();
+        // Flow backward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI));
+        // Anti forward dependency
+        EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI));
+
+        Instruction *LoadA1 = getInstructionByName(F, "tmp1");
+        // Anti backward dependency
+        EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI));
+        // Flow forward dependency
+        EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));
+        // No anti forward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI));
+        // No flow backward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI));
+        // No anti backward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI));
+        // No flow forward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI));
+
+        Instruction *LoadA3 = getInstructionByName(F, "tmp3");
+        Instruction *LoadB2 = getInstructionByName(F, "tmp4");
+        Instruction *LoadB3 = getInstructionByName(F, "tmp5");
+        // Input forward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI));
+        // Input backward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI));
+        // No input backward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI));
+        // No input forward dependency
+        EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI));
+      });
+}