From cf79773a9006a7e22f3919268b7db381ddcb3abc Mon Sep 17 00:00:00 2001 From: luxufan Date: Sat, 10 Jun 2023 15:48:09 +0800 Subject: [PATCH] [SCCP] Replace new value's value state with removed value's In replaceSignedInst, if a signed instruction can be repalced with unsigned instruction, we created a new instruction and removed the old instruction's value state. If the following instructions has this new instruction as a use operand, transformations like replaceSignedInst and refineInstruction would be blocked. The reason is there is no value state for the new instrution. This patch set the new instruction's value state with the removed instruction's value state. I believe it is correct bacause when we repalce a signed instruction with unsigned instruction, the value state is not changed. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D152337 --- llvm/include/llvm/Transforms/Utils/SCCPSolver.h | 3 +-- llvm/lib/Transforms/IPO/SCCP.cpp | 3 +-- llvm/lib/Transforms/Scalar/SCCP.cpp | 5 ++-- llvm/lib/Transforms/Utils/SCCPSolver.cpp | 31 ++++++++++++------------- llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll | 8 +++---- llvm/test/Transforms/SCCP/ip-ranges-sext.ll | 2 +- 6 files changed, 24 insertions(+), 28 deletions(-) diff --git a/llvm/include/llvm/Transforms/Utils/SCCPSolver.h b/llvm/include/llvm/Transforms/Utils/SCCPSolver.h index 3754b51..09a6160 100644 --- a/llvm/include/llvm/Transforms/Utils/SCCPSolver.h +++ b/llvm/include/llvm/Transforms/Utils/SCCPSolver.h @@ -130,7 +130,7 @@ public: std::vector getStructLatticeValueFor(Value *V) const; - void removeLatticeValueFor(Value *V); + void moveLatticeValue(Value *From, Value *To); /// Invalidate the Lattice Value of \p Call and its users after specializing /// the call. Then recompute it. @@ -184,7 +184,6 @@ public: void visitCall(CallInst &I); bool simplifyInstsInBlock(BasicBlock &BB, - SmallPtrSetImpl &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat); diff --git a/llvm/lib/Transforms/IPO/SCCP.cpp b/llvm/lib/Transforms/IPO/SCCP.cpp index 658d596..85295c7 100644 --- a/llvm/lib/Transforms/IPO/SCCP.cpp +++ b/llvm/lib/Transforms/IPO/SCCP.cpp @@ -209,7 +209,6 @@ static bool runIPSCCP( MadeChanges |= ReplacedPointerArg; } - SmallPtrSet InsertedValues; for (BasicBlock &BB : F) { if (!Solver.isBlockExecutable(&BB)) { LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); @@ -223,7 +222,7 @@ static bool runIPSCCP( } MadeChanges |= Solver.simplifyInstsInBlock( - BB, InsertedValues, NumInstRemoved, NumInstReplaced); + BB, NumInstRemoved, NumInstReplaced); } DominatorTree *DT = FAM->getCachedResult(F); diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp index fcdc503..a5e8f29 100644 --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -92,7 +92,6 @@ static bool runSCCP(Function &F, const DataLayout &DL, // delete their contents now. Note that we cannot actually delete the blocks, // as we cannot modify the CFG of the function. - SmallPtrSet InsertedValues; SmallVector BlocksToErase; for (BasicBlock &BB : F) { if (!Solver.isBlockExecutable(&BB)) { @@ -103,8 +102,8 @@ static bool runSCCP(Function &F, const DataLayout &DL, continue; } - MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues, - NumInstRemoved, NumInstReplaced); + MadeChanges |= + Solver.simplifyInstsInBlock(BB, NumInstRemoved, NumInstReplaced); } // Remove unreachable blocks and non-feasible edges. diff --git a/llvm/lib/Transforms/Utils/SCCPSolver.cpp b/llvm/lib/Transforms/Utils/SCCPSolver.cpp index 902651a..04dfc16 100644 --- a/llvm/lib/Transforms/Utils/SCCPSolver.cpp +++ b/llvm/lib/Transforms/Utils/SCCPSolver.cpp @@ -105,15 +105,14 @@ bool SCCPSolver::tryToReplaceWithConstant(Value *V) { /// Try to use \p Inst's value range from \p Solver to infer the NUW flag. static bool refineInstruction(SCCPSolver &Solver, - const SmallPtrSetImpl &InsertedValues, Instruction &Inst) { if (!isa(Inst)) return false; - auto GetRange = [&Solver, &InsertedValues](Value *Op) { + auto GetRange = [&Solver](Value *Op) { if (auto *Const = dyn_cast(Op)) return ConstantRange(Const->getValue()); - if (isa(Op) || InsertedValues.contains(Op)) { + if (isa(Op)) { unsigned Bitwidth = Op->getType()->getScalarSizeInBits(); return ConstantRange::getFull(Bitwidth); } @@ -146,7 +145,6 @@ static bool refineInstruction(SCCPSolver &Solver, /// Try to replace signed instructions with their unsigned equivalent. static bool replaceSignedInst(SCCPSolver &Solver, - SmallPtrSetImpl &InsertedValues, Instruction &Inst) { // Determine if a signed value is known to be >= 0. auto isNonNegative = [&Solver](Value *V) { @@ -168,7 +166,7 @@ static bool replaceSignedInst(SCCPSolver &Solver, case Instruction::SExt: { // If the source value is not negative, this is a zext. Value *Op0 = Inst.getOperand(0); - if (InsertedValues.count(Op0) || !isNonNegative(Op0)) + if (!isNonNegative(Op0)) return false; NewInst = new ZExtInst(Op0, Inst.getType(), "", &Inst); break; @@ -176,7 +174,7 @@ static bool replaceSignedInst(SCCPSolver &Solver, case Instruction::AShr: { // If the shifted value is not negative, this is a logical shift right. Value *Op0 = Inst.getOperand(0); - if (InsertedValues.count(Op0) || !isNonNegative(Op0)) + if (!isNonNegative(Op0)) return false; NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", &Inst); break; @@ -185,8 +183,7 @@ static bool replaceSignedInst(SCCPSolver &Solver, case Instruction::SRem: { // If both operands are not negative, this is the same as udiv/urem. Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1); - if (InsertedValues.count(Op0) || InsertedValues.count(Op1) || - !isNonNegative(Op0) || !isNonNegative(Op1)) + if (!isNonNegative(Op0) || !isNonNegative(Op1)) return false; auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv : Instruction::URem; @@ -200,15 +197,13 @@ static bool replaceSignedInst(SCCPSolver &Solver, // Wire up the new instruction and update state. assert(NewInst && "Expected replacement instruction"); NewInst->takeName(&Inst); - InsertedValues.insert(NewInst); Inst.replaceAllUsesWith(NewInst); - Solver.removeLatticeValueFor(&Inst); + Solver.moveLatticeValue(&Inst, NewInst); Inst.eraseFromParent(); return true; } bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB, - SmallPtrSetImpl &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat) { bool MadeChanges = false; @@ -221,10 +216,10 @@ bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB, MadeChanges = true; ++InstRemovedStat; - } else if (replaceSignedInst(*this, InsertedValues, Inst)) { + } else if (replaceSignedInst(*this, Inst)) { MadeChanges = true; ++InstReplacedStat; - } else if (refineInstruction(*this, InsertedValues, Inst)) { + } else if (refineInstruction(*this, Inst)) { MadeChanges = true; } } @@ -731,7 +726,11 @@ public: return StructValues; } - void removeLatticeValueFor(Value *V) { ValueState.erase(V); } + void moveLatticeValue(Value *From, Value *To) { + assert(ValueState.count(From) && "From is not existed in ValueState"); + ValueState[To] = ValueState[From]; + ValueState.erase(From); + } /// Invalidate the Lattice Value of \p Call and its users after specializing /// the call. Then recompute it. @@ -2035,8 +2034,8 @@ SCCPSolver::getStructLatticeValueFor(Value *V) const { return Visitor->getStructLatticeValueFor(V); } -void SCCPSolver::removeLatticeValueFor(Value *V) { - return Visitor->removeLatticeValueFor(V); +void SCCPSolver::moveLatticeValue(Value *From, Value *To) { + return Visitor->moveLatticeValue(From, To); } void SCCPSolver::resetLatticeValueFor(CallBase *Call) { diff --git a/llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll b/llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll index 97b471d..02198a1 100644 --- a/llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll +++ b/llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll @@ -125,9 +125,9 @@ define i16 @sge_with_sext_to_zext_conversion(i8 %a) { ; CHECK-NEXT: br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: [[SEXT:%.*]] = zext i8 [[A]] to i16 -; CHECK-NEXT: [[ADD_1:%.*]] = add i16 [[SEXT]], 1 -; CHECK-NEXT: [[ADD_2:%.*]] = add i16 [[SEXT]], -128 -; CHECK-NEXT: [[ADD_3:%.*]] = add i16 [[SEXT]], -127 +; CHECK-NEXT: [[ADD_1:%.*]] = add nuw nsw i16 [[SEXT]], 1 +; CHECK-NEXT: [[ADD_2:%.*]] = add nuw nsw i16 [[SEXT]], -128 +; CHECK-NEXT: [[ADD_3:%.*]] = add nsw i16 [[SEXT]], -127 ; CHECK-NEXT: [[RES_1:%.*]] = xor i16 [[ADD_1]], [[ADD_2]] ; CHECK-NEXT: [[RES_2:%.*]] = xor i16 [[RES_1]], [[ADD_3]] ; CHECK-NEXT: ret i16 [[RES_2]] @@ -222,7 +222,7 @@ define i16 @test_add_in_different_block(i1 %c, i8 %a) { ; CHECK-NEXT: [[CONV:%.*]] = zext i8 [[COND4]] to i16 ; CHECK-NEXT: br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: -; CHECK-NEXT: [[ADD:%.*]] = add i16 1, [[CONV]] +; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 1, [[CONV]] ; CHECK-NEXT: ret i16 [[ADD]] ; CHECK: else: ; CHECK-NEXT: ret i16 0 diff --git a/llvm/test/Transforms/SCCP/ip-ranges-sext.ll b/llvm/test/Transforms/SCCP/ip-ranges-sext.ll index 6fa74b3..5f8a6e5 100644 --- a/llvm/test/Transforms/SCCP/ip-ranges-sext.ll +++ b/llvm/test/Transforms/SCCP/ip-ranges-sext.ll @@ -127,7 +127,7 @@ define i64 @test7(i16 %x) { ; CHECK-LABEL: @test7( ; CHECK-NEXT: [[P:%.*]] = and i16 [[X:%.*]], 15 ; CHECK-NEXT: [[EXT_1:%.*]] = zext i16 [[P]] to i32 -; CHECK-NEXT: [[EXT_2:%.*]] = sext i32 [[EXT_1]] to i64 +; CHECK-NEXT: [[EXT_2:%.*]] = zext i32 [[EXT_1]] to i64 ; CHECK-NEXT: ret i64 [[EXT_2]] ; %p = and i16 %x, 15 -- 2.7.4