Skip to content

Instantly share code, notes, and snippets.

@nikic

nikic/sccp.diff Secret

Created April 27, 2020 20:32
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