[JumpThread] Enhance finding partial redundant loads by continuing scanning single predecessor
Summary: While scanning predecessors to find an available loaded value, if the predecessor has a single predecessor, we can continue scanning through the single predecessor.
Reviewers: mcrosier, rengolin, reames, davidxl, haicheng
Reviewed By: rengolin
Subscribers: zzheng, llvm-commits
Differential Revision: https://reviews.llvm.org/D29200
llvm-svn: 293896
diff --git a/llvm/include/llvm/Analysis/Loads.h b/llvm/include/llvm/Analysis/Loads.h
index e167f36..f9700c3 100644
--- a/llvm/include/llvm/Analysis/Loads.h
+++ b/llvm/include/llvm/Analysis/Loads.h
@@ -85,7 +85,8 @@
BasicBlock::iterator &ScanFrom,
unsigned MaxInstsToScan = DefMaxInstsToScan,
AliasAnalysis *AA = nullptr,
- bool *IsLoadCSE = nullptr);
+ bool *IsLoadCSE = nullptr,
+ unsigned *NumScanedInst = nullptr);
}
diff --git a/llvm/lib/Analysis/Loads.cpp b/llvm/lib/Analysis/Loads.cpp
index e46541e..5d842db 100644
--- a/llvm/lib/Analysis/Loads.cpp
+++ b/llvm/lib/Analysis/Loads.cpp
@@ -312,7 +312,8 @@
BasicBlock *ScanBB,
BasicBlock::iterator &ScanFrom,
unsigned MaxInstsToScan,
- AliasAnalysis *AA, bool *IsLoadCSE) {
+ AliasAnalysis *AA, bool *IsLoadCSE,
+ unsigned *NumScanedInst) {
if (MaxInstsToScan == 0)
MaxInstsToScan = ~0U;
@@ -344,6 +345,9 @@
// Restore ScanFrom to expected value in case next test succeeds
ScanFrom++;
+ if (NumScanedInst)
+ ++(*NumScanedInst);
+
// Don't scan huge blocks.
if (MaxInstsToScan-- == 0)
return nullptr;
diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
index e8e4033..c463b1a 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -982,10 +982,25 @@
// Scan the predecessor to see if the value is available in the pred.
BBIt = PredBB->end();
- Value *PredAvailable = FindAvailableLoadedValue(LI, PredBB, BBIt,
- DefMaxInstsToScan,
- nullptr,
- &IsLoadCSE);
+ unsigned NumScanedInst = 0;
+ Value *PredAvailable =
+ FindAvailableLoadedValue(LI, PredBB, BBIt, DefMaxInstsToScan, nullptr,
+ &IsLoadCSE, &NumScanedInst);
+
+ // If PredBB has a single predecessor, continue scanning through the single
+ // precessor.
+ BasicBlock *SinglePredBB = PredBB;
+ while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
+ NumScanedInst < DefMaxInstsToScan) {
+ SinglePredBB = SinglePredBB->getSinglePredecessor();
+ if (SinglePredBB) {
+ BBIt = SinglePredBB->end();
+ PredAvailable = FindAvailableLoadedValue(
+ LI, SinglePredBB, BBIt, (DefMaxInstsToScan - NumScanedInst),
+ nullptr, &IsLoadCSE, &NumScanedInst);
+ }
+ }
+
if (!PredAvailable) {
OneUnavailablePred = PredBB;
continue;
diff --git a/llvm/test/Transforms/JumpThreading/thread-loads.ll b/llvm/test/Transforms/JumpThreading/thread-loads.ll
index f54672d..782de28 100644
--- a/llvm/test/Transforms/JumpThreading/thread-loads.ll
+++ b/llvm/test/Transforms/JumpThreading/thread-loads.ll
@@ -302,6 +302,85 @@
ret void
}
+define i32 @fn_SinglePred(i1 %c2,i64* %P) {
+; CHECK-LABEL: @fn_SinglePred
+; CHECK-LABEL: entry:
+; CHECK: %[[L1:.*]] = load i64, i64* %P
+; CHECK: br i1 %c, label %cond3, label %cond1
+; CHECK-LABEL: cond2:
+; CHECK-NOT: load
+; CHECK: %[[PHI:.*]] = phi i64 [ %[[L1]], %cond1 ]
+; CHECK: call void @fn2(i64 %[[PHI]])
+; CHECK: br label %end
+; CHECK-LABEL: cond3:
+; CHECK: call void @fn2(i64 %l1)
+; CHECK: call void @fn3(i64 %l1)
+
+entry:
+ %l1 = load i64, i64* %P
+ %c = icmp eq i64 %l1, 0
+ br i1 %c, label %cond2, label %cond1
+
+cond1:
+ br i1 %c2, label %cond2, label %end
+
+cond2:
+ %l2 = load i64, i64* %P
+ call void @fn2(i64 %l2)
+ %c3 = icmp eq i64 %l2, 0
+ br i1 %c3, label %cond3, label %end
+
+cond3:
+ call void @fn3(i64 %l2)
+ br label %end
+
+end:
+ ret i32 0
+}
+
+define i32 @fn_SinglePredMultihop(i1 %c1, i1 %c2,i64* %P) {
+; CHECK-LABEL: @fn_SinglePredMultihop
+; CHECK-LABEL: entry:
+; CHECK: %[[L1:.*]] = load i64, i64* %P
+; CHECK: br i1 %c0, label %cond3, label %cond0
+; CHECK-LABEL: cond2:
+; CHECK-NOT: load
+; CHECK: %[[PHI:.*]] = phi i64 [ %[[L1]], %cond1 ]
+; CHECK: call void @fn2(i64 %[[PHI]])
+; CHECK: br label %end
+; CHECK-LABEL: cond3:
+; CHECK: call void @fn2(i64 %l1)
+; CHECK: call void @fn3(i64 %l1)
+
+entry:
+ %l1 = load i64, i64* %P
+ %c0 = icmp eq i64 %l1, 0
+ br i1 %c0, label %cond2, label %cond0
+
+cond0:
+ br i1 %c1, label %cond1, label %end
+
+cond1:
+ br i1 %c2, label %cond2, label %end
+
+cond2:
+ %l2 = load i64, i64* %P
+ call void @fn2(i64 %l2)
+ %c3 = icmp eq i64 %l2, 0
+ br i1 %c3, label %cond3, label %end
+
+cond3:
+ call void @fn3(i64 %l2)
+ br label %end
+
+end:
+ ret i32 0
+}
+
+declare void @fn2(i64)
+declare void @fn3(i64)
+
+
!0 = !{!3, !3, i64 0}
!1 = !{!"omnipotent char", !2}
!2 = !{!"Simple C/C++ TBAA"}