/sccp.diff Secret
Created
April 27, 2020 20:32
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
commit 6f106bd6f8aa6254acf60a5fc1e35d86abb5491b | |
Author: Nikita Popov <nikita.ppv@gmail.com> | |
Date: Mon Apr 27 21:49:03 2020 +0200 | |
Control widening at phi nodes | |
diff --git llvm/lib/Transforms/Scalar/SCCP.cpp llvm/lib/Transforms/Scalar/SCCP.cpp | |
index 75133828929f..da64db8a9209 100644 | |
--- llvm/lib/Transforms/Scalar/SCCP.cpp | |
+++ llvm/lib/Transforms/Scalar/SCCP.cpp | |
@@ -152,6 +152,10 @@ class SCCPSolver : public InstVisitor<SCCPSolver> { | |
// The BasicBlock work list | |
SmallVector<BasicBlock *, 64> BBWorkList; | |
+ // Phi arguments when phi was last visited, and how often it has been widened. | |
+ DenseMap<PHINode *, SmallVector<std::pair<ValueLatticeElement, unsigned>, 0>> | |
+ PhiWideningInfo; | |
+ | |
/// KnownFeasibleEdges - Entries in this set are edges which have already had | |
/// PHI nodes retriggered. | |
using Edge = std::pair<BasicBlock *, BasicBlock *>; | |
@@ -403,10 +407,8 @@ private: | |
/// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV | |
/// changes. | |
bool mergeInValue(ValueLatticeElement &IV, Value *V, | |
- ValueLatticeElement MergeWithV, | |
- ValueLatticeElement::MergeOptions Opts = { | |
- /*MayIncludeUndef=*/false, /*CheckWiden=*/true}) { | |
- if (IV.mergeIn(MergeWithV, Opts)) { | |
+ ValueLatticeElement MergeWithV) { | |
+ if (IV.mergeIn(MergeWithV)) { | |
pushToWorkList(IV, V); | |
LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : " | |
<< IV << "\n"); | |
@@ -415,12 +417,10 @@ private: | |
return false; | |
} | |
- bool mergeInValue(Value *V, ValueLatticeElement MergeWithV, | |
- ValueLatticeElement::MergeOptions Opts = { | |
- /*MayIncludeUndef=*/false, /*CheckWiden=*/true}) { | |
+ bool mergeInValue(Value *V, ValueLatticeElement MergeWithV) { | |
assert(!V->getType()->isStructTy() && | |
"non-structs should use markConstant"); | |
- return mergeInValue(ValueState[V], V, MergeWithV, Opts); | |
+ return mergeInValue(ValueState[V], V, MergeWithV); | |
} | |
/// getValueState - Return the ValueLatticeElement object that corresponds to | |
@@ -731,6 +731,11 @@ void SCCPSolver::visitPHINode(PHINode &PN) { | |
if (PN.getNumIncomingValues() > 64) | |
return (void)markOverdefined(&PN); | |
+ auto &WideningInfo = PhiWideningInfo[&PN]; | |
+ if (WideningInfo.empty()) | |
+ WideningInfo.resize(PN.getNumIncomingValues(), | |
+ std::make_pair(ValueLatticeElement(), 0)); | |
+ | |
// Look at all of the executable operands of the PHI node. If any of them | |
// are overdefined, the PHI becomes overdefined as well. If they are all | |
// constant, and they agree with each other, the PHI becomes the identical | |
@@ -743,6 +748,22 @@ void SCCPSolver::visitPHINode(PHINode &PN) { | |
continue; | |
ValueLatticeElement &Res = getValueState(&PN); | |
+ | |
+ // If a phi argument range has been widened, go to overdefined. | |
+ auto &Info = WideningInfo[i]; | |
+ if (Info.first.isConstantRange() && IV.isConstantRange() && | |
+ Info.first.getConstantRange() != IV.getConstantRange()) | |
+ Info.second++; | |
+ Info.first = IV; | |
+ | |
+ const unsigned MaxWidenings = 0; | |
+ if (Info.second > MaxWidenings) { | |
+ LLVM_DEBUG(dbgs() << "Widened " << PN << " " << Info.second << " times, " | |
+ << "going to overdefined"); | |
+ Changed |= Res.markOverdefined(); | |
+ break; | |
+ } | |
+ | |
Changed |= Res.mergeIn(IV); | |
if (Res.isOverdefined()) | |
break; | |
@@ -1208,8 +1229,7 @@ void SCCPSolver::handleCallArguments(CallBase &CB) { | |
mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg); | |
} | |
} else | |
- mergeInValue(&*AI, getValueState(*CAI), | |
- ValueLatticeElement::MergeOptions().setCheckWiden(false)); | |
+ mergeInValue(&*AI, getValueState(*CAI)); | |
} | |
} | |
} | |
diff --git llvm/test/Transforms/SCCP/conditions-ranges.ll llvm/test/Transforms/SCCP/conditions-ranges.ll | |
index baaf8cbf1c2f..3aa7a6b843d8 100644 | |
--- llvm/test/Transforms/SCCP/conditions-ranges.ll | |
+++ llvm/test/Transforms/SCCP/conditions-ranges.ll | |
@@ -1194,7 +1194,8 @@ define void @f20_ne_0_nuked_by_and(i32 %arg) local_unnamed_addr #0 { | |
; CHECK-NEXT: [[BC:%.*]] = call i1 @cond() | |
; CHECK-NEXT: br i1 [[BC]], label [[BB139:%.*]], label [[BB122]] | |
; CHECK: bb139: | |
-; CHECK-NEXT: call void @use(i1 false) | |
+; CHECK-NEXT: [[TMP140:%.*]] = icmp eq i32 [[TMP136]], 0 | |
+; CHECK-NEXT: call void @use(i1 [[TMP140]]) | |
; CHECK-NEXT: ret void | |
; | |
bb11: ; preds = %bb1 | |
diff --git llvm/test/Transforms/SCCP/constant-range-struct.ll llvm/test/Transforms/SCCP/constant-range-struct.ll | |
index 6a602feefa4c..290437d386aa 100644 | |
--- llvm/test/Transforms/SCCP/constant-range-struct.ll | |
+++ llvm/test/Transforms/SCCP/constant-range-struct.ll | |
@@ -102,22 +102,14 @@ define void @struct2_caller() { | |
; CHECK-NEXT: [[S:%.*]] = call { i64, i64 } @struct2() | |
; CHECK-NEXT: [[V1:%.*]] = extractvalue { i64, i64 } [[S]], 0 | |
; CHECK-NEXT: [[V2:%.*]] = extractvalue { i64, i64 } [[S]], 1 | |
-; CHECK-NEXT: [[T_1:%.*]] = icmp ne i64 [[V1]], 10 | |
-; CHECK-NEXT: call void @use(i1 [[T_1]]) | |
-; CHECK-NEXT: [[T_2:%.*]] = icmp ult i64 [[V1]], 100 | |
-; CHECK-NEXT: call void @use(i1 [[T_2]]) | |
-; CHECK-NEXT: [[T_3:%.*]] = icmp ne i64 [[V2]], 0 | |
-; CHECK-NEXT: call void @use(i1 [[T_3]]) | |
-; CHECK-NEXT: [[T_4:%.*]] = icmp ult i64 [[V2]], 301 | |
-; CHECK-NEXT: call void @use(i1 [[T_4]]) | |
-; CHECK-NEXT: [[F_1:%.*]] = icmp eq i64 [[V1]], 10 | |
-; CHECK-NEXT: call void @use(i1 [[F_1]]) | |
-; CHECK-NEXT: [[F_2:%.*]] = icmp ult i64 [[V1]], 19 | |
-; CHECK-NEXT: call void @use(i1 [[F_2]]) | |
-; CHECK-NEXT: [[F_3:%.*]] = icmp eq i64 [[V2]], 50 | |
-; CHECK-NEXT: call void @use(i1 [[F_3]]) | |
-; CHECK-NEXT: [[F_4:%.*]] = icmp ugt i64 [[V2]], 301 | |
-; CHECK-NEXT: call void @use(i1 [[F_4]]) | |
+; CHECK-NEXT: call void @use(i1 true) | |
+; CHECK-NEXT: call void @use(i1 true) | |
+; CHECK-NEXT: call void @use(i1 true) | |
+; CHECK-NEXT: call void @use(i1 true) | |
+; CHECK-NEXT: call void @use(i1 false) | |
+; CHECK-NEXT: call void @use(i1 false) | |
+; CHECK-NEXT: call void @use(i1 false) | |
+; CHECK-NEXT: call void @use(i1 false) | |
; CHECK-NEXT: [[C_1:%.*]] = icmp eq i64 [[V1]], 25 | |
; CHECK-NEXT: call void @use(i1 [[C_1]]) | |
; CHECK-NEXT: [[C_2:%.*]] = icmp ult i64 [[V1]], 25 | |
diff --git llvm/test/Transforms/SCCP/ip-ranges-phis.ll llvm/test/Transforms/SCCP/ip-ranges-phis.ll | |
index a6634c1b8a6b..900791ba9922 100644 | |
--- llvm/test/Transforms/SCCP/ip-ranges-phis.ll | |
+++ llvm/test/Transforms/SCCP/ip-ranges-phis.ll | |
@@ -49,15 +49,23 @@ define internal i32 @f2(i32 %x, i32 %y, i32 %z, i1 %cmp.1, i1 %cmp.2) { | |
; CHECK-NEXT: [[C_1:%.*]] = icmp sgt i32 [[P]], 5 | |
; CHECK-NEXT: [[C_2:%.*]] = icmp eq i32 [[P]], 0 | |
; CHECK-NEXT: [[C_3:%.*]] = icmp slt i32 [[P]], 0 | |
+; CHECK-NEXT: [[C_4:%.*]] = icmp sgt i32 [[P]], 10 | |
+; CHECK-NEXT: [[C_5:%.*]] = icmp sle i32 [[P]], 10 | |
+; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[P]], -11 | |
+; CHECK-NEXT: [[C_7:%.*]] = icmp slt i32 [[P]], -11 | |
; CHECK-NEXT: [[V_1:%.*]] = select i1 [[C_1]], i32 10, i32 100 | |
; CHECK-NEXT: [[V_2:%.*]] = select i1 [[C_2]], i32 20, i32 200 | |
; CHECK-NEXT: [[V_3:%.*]] = select i1 [[C_3]], i32 30, i32 300 | |
+; CHECK-NEXT: [[V_4:%.*]] = select i1 [[C_4]], i32 40, i32 400 | |
+; CHECK-NEXT: [[V_5:%.*]] = select i1 [[C_5]], i32 50, i32 500 | |
+; CHECK-NEXT: [[V_6:%.*]] = select i1 [[C_6]], i32 60, i32 600 | |
+; CHECK-NEXT: [[V_7:%.*]] = select i1 [[C_7]], i32 70, i32 700 | |
; CHECK-NEXT: [[R_1:%.*]] = add i32 [[V_1]], [[V_2]] | |
; CHECK-NEXT: [[R_2:%.*]] = add i32 [[R_1]], [[V_3]] | |
-; CHECK-NEXT: [[R_3:%.*]] = add i32 [[R_2]], 400 | |
-; CHECK-NEXT: [[R_4:%.*]] = add i32 [[R_3]], 50 | |
-; CHECK-NEXT: [[R_5:%.*]] = add i32 [[R_4]], 60 | |
-; CHECK-NEXT: [[R_6:%.*]] = add i32 [[R_4]], 700 | |
+; CHECK-NEXT: [[R_3:%.*]] = add i32 [[R_2]], [[V_4]] | |
+; CHECK-NEXT: [[R_4:%.*]] = add i32 [[R_3]], [[V_5]] | |
+; CHECK-NEXT: [[R_5:%.*]] = add i32 [[R_4]], [[V_6]] | |
+; CHECK-NEXT: [[R_6:%.*]] = add i32 [[R_4]], [[V_7]] | |
; CHECK-NEXT: ret i32 [[R_6]] | |
; | |
diff --git llvm/test/Transforms/SCCP/widening.ll llvm/test/Transforms/SCCP/widening.ll | |
index 9f5e1c78ae3a..5a7d8219b2b7 100644 | |
--- llvm/test/Transforms/SCCP/widening.ll | |
+++ llvm/test/Transforms/SCCP/widening.ll | |
@@ -17,10 +17,8 @@ define void @test_2_incoming_constants(i32 %x) { | |
; SCCP: exit: | |
; SCCP-NEXT: [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ] | |
; SCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 | |
-; SCCP-NEXT: [[T_1:%.*]] = icmp ult i32 [[A]], 20 | |
-; SCCP-NEXT: call void @use(i1 [[T_1]]) | |
-; SCCP-NEXT: [[F_1:%.*]] = icmp ugt i32 [[A]], 10 | |
-; SCCP-NEXT: call void @use(i1 [[F_1]]) | |
+; SCCP-NEXT: call void @use(i1 true) | |
+; SCCP-NEXT: call void @use(i1 false) | |
; SCCP-NEXT: ret void | |
; | |
; IPSCCP-LABEL: @test_2_incoming_constants( | |
@@ -32,10 +30,8 @@ define void @test_2_incoming_constants(i32 %x) { | |
; IPSCCP: exit: | |
; IPSCCP-NEXT: [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ] | |
; IPSCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 | |
-; IPSCCP-NEXT: [[T_1:%.*]] = icmp ult i32 [[A]], 20 | |
-; IPSCCP-NEXT: call void @use(i1 [[T_1]]) | |
-; IPSCCP-NEXT: [[F_1:%.*]] = icmp ugt i32 [[A]], 10 | |
-; IPSCCP-NEXT: call void @use(i1 [[F_1]]) | |
+; IPSCCP-NEXT: call void @use(i1 true) | |
+; IPSCCP-NEXT: call void @use(i1 false) | |
; IPSCCP-NEXT: ret void | |
; | |
entry: | |
@@ -68,10 +64,8 @@ define void @test_3_incoming_constants(i32 %x) { | |
; SCCP: exit: | |
; SCCP-NEXT: [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ] | |
; SCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 | |
-; SCCP-NEXT: [[T_1:%.*]] = icmp ult i32 [[A]], 20 | |
-; SCCP-NEXT: call void @use(i1 [[T_1]]) | |
-; SCCP-NEXT: [[F_1:%.*]] = icmp ugt i32 [[A]], 10 | |
-; SCCP-NEXT: call void @use(i1 [[F_1]]) | |
+; SCCP-NEXT: call void @use(i1 true) | |
+; SCCP-NEXT: call void @use(i1 false) | |
; SCCP-NEXT: ret void | |
; | |
; IPSCCP-LABEL: @test_3_incoming_constants( | |
@@ -86,10 +80,8 @@ define void @test_3_incoming_constants(i32 %x) { | |
; IPSCCP: exit: | |
; IPSCCP-NEXT: [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ] | |
; IPSCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 | |
-; IPSCCP-NEXT: [[T_1:%.*]] = icmp ult i32 [[A]], 20 | |
-; IPSCCP-NEXT: call void @use(i1 [[T_1]]) | |
-; IPSCCP-NEXT: [[F_1:%.*]] = icmp ugt i32 [[A]], 10 | |
-; IPSCCP-NEXT: call void @use(i1 [[F_1]]) | |
+; IPSCCP-NEXT: call void @use(i1 true) | |
+; IPSCCP-NEXT: call void @use(i1 false) | |
; IPSCCP-NEXT: ret void | |
; | |
entry: | |
@@ -132,10 +124,8 @@ define void @test_5_incoming_constants(i32 %x) { | |
; SCCP: exit: | |
; SCCP-NEXT: [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ], [ 3, [[BB3]] ], [ 4, [[BB4]] ] | |
; SCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 | |
-; SCCP-NEXT: [[T_1:%.*]] = icmp ult i32 [[A]], 20 | |
-; SCCP-NEXT: call void @use(i1 [[T_1]]) | |
-; SCCP-NEXT: [[F_1:%.*]] = icmp ugt i32 [[A]], 10 | |
-; SCCP-NEXT: call void @use(i1 [[F_1]]) | |
+; SCCP-NEXT: call void @use(i1 true) | |
+; SCCP-NEXT: call void @use(i1 false) | |
; SCCP-NEXT: ret void | |
; | |
; IPSCCP-LABEL: @test_5_incoming_constants( | |
@@ -156,10 +146,8 @@ define void @test_5_incoming_constants(i32 %x) { | |
; IPSCCP: exit: | |
; IPSCCP-NEXT: [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ], [ 3, [[BB3]] ], [ 4, [[BB4]] ] | |
; IPSCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 | |
-; IPSCCP-NEXT: [[T_1:%.*]] = icmp ult i32 [[A]], 20 | |
-; IPSCCP-NEXT: call void @use(i1 [[T_1]]) | |
-; IPSCCP-NEXT: [[F_1:%.*]] = icmp ugt i32 [[A]], 10 | |
-; IPSCCP-NEXT: call void @use(i1 [[F_1]]) | |
+; IPSCCP-NEXT: call void @use(i1 true) | |
+; IPSCCP-NEXT: call void @use(i1 false) | |
; IPSCCP-NEXT: ret void | |
; | |
entry: | |
@@ -369,8 +357,7 @@ define void @loop_with_header_1(i32 %x) { | |
; IPSCCP-NEXT: [[C_1:%.*]] = icmp slt i32 [[IV]], 2 | |
; IPSCCP-NEXT: br i1 [[C_1]], label [[LOOP_BODY]], label [[EXIT:%.*]] | |
; IPSCCP: loop.body: | |
-; IPSCCP-NEXT: [[T_1:%.*]] = icmp slt i32 [[IV]], 2 | |
-; IPSCCP-NEXT: call void @use(i1 [[T_1]]) | |
+; IPSCCP-NEXT: call void @use(i1 true) | |
; IPSCCP-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1 | |
; IPSCCP-NEXT: br label [[LOOP_HEADER]] | |
; IPSCCP: exit: | |
@@ -418,8 +405,7 @@ define void @loop_with_header_2(i32 %x) { | |
; IPSCCP-NEXT: [[C_1:%.*]] = icmp slt i32 [[IV]], 200 | |
; IPSCCP-NEXT: br i1 [[C_1]], label [[LOOP_BODY]], label [[EXIT:%.*]] | |
; IPSCCP: loop.body: | |
-; IPSCCP-NEXT: [[T_1:%.*]] = icmp slt i32 [[IV]], 200 | |
-; IPSCCP-NEXT: call void @use(i1 [[T_1]]) | |
+; IPSCCP-NEXT: call void @use(i1 true) | |
; IPSCCP-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1 | |
; IPSCCP-NEXT: br label [[LOOP_HEADER]] | |
; IPSCCP: exit: |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment