[SCCP] Replace new value's value state with removed value's

[StephenFan]

Summary

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.

[nikic]

LGTM

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

133

I found this name confusing. Maybe just moveLatticeValue?

[StephenFan]

Rename to moveLatticeValue.
Don't do insert in moveLatticeValue since the new value may have already existed in valuestate.

[vitalybuka]

There are crashes with sanitizers

[vitalybuka]

Example https://lab.llvm.org/buildbot/#/builders/168/builds/13981
similar with msan and hwasan both arm and x86

[DavidSpickett]

We (Linaro) also saw a 2nd stage compiler crash on our Windows on Arm (AArch64) bot. The revert has fixed that, thanks!

I expect the cause was the same, but can't see the specifics in the logs. If it happens again on reland I'll come back with the reproducer for it.

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

public:
   bool isBlockExecutable(BasicBlock *BB) const;
 
   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
   // block to the 'To' basic block is currently feasible.
   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
 
   std::vector<ValueLatticeElement> 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.
   void resetLatticeValueFor(CallBase *Call);
 
   const ValueLatticeElement &getLatticeValueFor(Value *V) const;
 
   /// getTrackedRetVals - Get the inferred return value map.
public:
   /// this method to erase a function from the module (e.g., if it has been
   /// completely specialized and is no longer needed).
   void markFunctionUnreachable(Function *F);
 
   void visit(Instruction *I);
   void visitCall(CallInst &I);
 
   bool simplifyInstsInBlock(BasicBlock &BB,
-                            SmallPtrSetImpl<Value *> &InsertedValues,
                             Statistic &InstRemovedStat,
                             Statistic &InstReplacedStat);
 
   bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
                               BasicBlock *&NewUnreachableBB) const;
 
   bool tryToReplaceWithConstant(Value *V);
 

llvm/lib/Transforms/IPO/SCCP.cpp

if (Solver.isBlockExecutable(&F.front())) {
             continue;
 
           CB->setAttributes(UpdateAttrs(CB->getAttributes()));
         }
       }
       MadeChanges |= ReplacedPointerArg;
     }
 
-    SmallPtrSet<Value *, 32> InsertedValues;
     for (BasicBlock &BB : F) {
       if (!Solver.isBlockExecutable(&BB)) {
         LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
         ++NumDeadBlocks;
 
         MadeChanges = true;
 
         if (&BB != &F.front())
           BlocksToErase.push_back(&BB);
         continue;
       }
 
       MadeChanges |= Solver.simplifyInstsInBlock(
-          BB, InsertedValues, NumInstRemoved, NumInstReplaced);
+          BB, NumInstRemoved, NumInstReplaced);
     }
 
     DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(F);
     PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(F);
     DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
     // Change dead blocks to unreachable. We do it after replacing constants
     // in all executable blocks, because changeToUnreachable may remove PHI
     // nodes in executable blocks we found values for. The function's entry

llvm/lib/Transforms/Scalar/SCCP.cpp

static bool runSCCP(Function &F, const DataLayout &DL,
   }
 
   bool MadeChanges = false;
 
   // If we decided that there are basic blocks that are dead in this function,
   // delete their contents now.  Note that we cannot actually delete the blocks,
   // as we cannot modify the CFG of the function.
 
-  SmallPtrSet<Value *, 32> InsertedValues;
   SmallVector<BasicBlock *, 8> BlocksToErase;
   for (BasicBlock &BB : F) {
     if (!Solver.isBlockExecutable(&BB)) {
       LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
       ++NumDeadBlocks;
       BlocksToErase.push_back(&BB);
       MadeChanges = true;
       continue;
     }
 
-    MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,
-                                               NumInstRemoved, NumInstReplaced);
+    MadeChanges |=
+        Solver.simplifyInstsInBlock(BB, NumInstRemoved, NumInstReplaced);
   }
 
   // Remove unreachable blocks and non-feasible edges.
   for (BasicBlock *DeadBB : BlocksToErase)
     NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
                                           /*PreserveLCSSA=*/false, &DTU);
 
   BasicBlock *NewUnreachableBB = nullptr;

llvm/lib/Transforms/Utils/SCCPSolver.cpp

bool SCCPSolver::tryToReplaceWithConstant(Value *V) {
 
   // Replaces all of the uses of a variable with uses of the constant.
   V->replaceAllUsesWith(Const);
   return true;
 }
 
 /// Try to use \p Inst's value range from \p Solver to infer the NUW flag.
 static bool refineInstruction(SCCPSolver &Solver,
-                              const SmallPtrSetImpl<Value *> &InsertedValues,
                               Instruction &Inst) {
   if (!isa<OverflowingBinaryOperator>(Inst))
     return false;
 
-  auto GetRange = [&Solver, &InsertedValues](Value *Op) {
+  auto GetRange = [&Solver](Value *Op) {
     if (auto *Const = dyn_cast<ConstantInt>(Op))
       return ConstantRange(Const->getValue());
-    if (isa<Constant>(Op) || InsertedValues.contains(Op)) {
+    if (isa<Constant>(Op)) {
       unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
       return ConstantRange::getFull(Bitwidth);
     }
     return getConstantRange(Solver.getLatticeValueFor(Op), Op->getType(),
                             /*UndefAllowed=*/false);
   };
   auto RangeA = GetRange(Inst.getOperand(0));
   auto RangeB = GetRange(Inst.getOperand(1));
if (!Inst.hasNoSignedWrap()) {
     }
   }
 
   return Changed;
 }
 
 /// Try to replace signed instructions with their unsigned equivalent.
 static bool replaceSignedInst(SCCPSolver &Solver,
-                              SmallPtrSetImpl<Value *> &InsertedValues,
                               Instruction &Inst) {
   // Determine if a signed value is known to be >= 0.
   auto isNonNegative = [&Solver](Value *V) {
     // If this value was constant-folded, it may not have a solver entry.
     // Handle integers. Otherwise, return false.
     if (auto *C = dyn_cast<Constant>(V)) {
       auto *CInt = dyn_cast<ConstantInt>(C);
       return CInt && !CInt->isNegative();
     }
     const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
     return IV.isConstantRange(/*UndefAllowed=*/false) &&
            IV.getConstantRange().isAllNonNegative();
   };
 
   Instruction *NewInst = nullptr;
   switch (Inst.getOpcode()) {
   // Note: We do not fold sitofp -> uitofp here because that could be more
   // expensive in codegen and may not be reversible in the backend.
   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;
   }
   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;
   }
   case Instruction::SDiv:
   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;
     NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", &Inst);
     break;
   }
   default:
     return false;
   }
 
   // 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<Value *> &InsertedValues,
                                       Statistic &InstRemovedStat,
                                       Statistic &InstReplacedStat) {
   bool MadeChanges = false;
   for (Instruction &Inst : make_early_inc_range(BB)) {
     if (Inst.getType()->isVoidTy())
       continue;
     if (tryToReplaceWithConstant(&Inst)) {
       if (canRemoveInstruction(&Inst))
         Inst.eraseFromParent();
 
       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;
     }
   }
   return MadeChanges;
 }
 
 bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
                                         BasicBlock *&NewUnreachableBB) const {
std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
     }
     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.
   void resetLatticeValueFor(CallBase *Call) {
     // Calls to void returning functions do not need invalidation.
     Function *F = Call->getCalledFunction();
     (void)F;
     assert(!F->getReturnType()->isVoidTy() &&
bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
   return Visitor->isEdgeFeasible(From, To);
 }
 
 std::vector<ValueLatticeElement>
 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) {
   Visitor->resetLatticeValueFor(Call);
 }
 
 const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const {
   return Visitor->getLatticeValueFor(V);

llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll

 
 define i16 @sge_with_sext_to_zext_conversion(i8 %a)  {
 ; CHECK-LABEL: @sge_with_sext_to_zext_conversion(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[A:%.*]], 0
 ; 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]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[SEXT_2:%.*]] = sext i8 [[A]] to i16
 ; CHECK-NEXT:    [[ADD_4:%.*]] = add nsw i16 [[SEXT_2]], 1
 ; CHECK-NEXT:    [[ADD_5:%.*]] = add nsw i16 [[SEXT_2]], -128
 ; CHECK-NEXT:    [[ADD_6:%.*]] = add nsw i16 [[SEXT_2]], -127

 define i16 @test_add_in_different_block(i1 %c, i8 %a) {
 ; CHECK-LABEL: @test_add_in_different_block(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A:%.*]], 0
 ; CHECK-NEXT:    [[COND4:%.*]] = select i1 [[CMP]], i8 1, i8 0
 ; 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
 ;
 entry:
   %cmp = icmp eq i8 %a, 0
   %cond4 = select i1 %cmp, i8 1, i8 0
   %conv = sext i8 %cond4 to i16

llvm/test/Transforms/SCCP/ip-ranges-sext.ll

;
   ret i64 %ext
 }
 
 ; sext that can be converted to zext feeds another sext.
 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
   %ext.1 = sext i16 %p to i32
   %ext.2 = sext i32 %ext.1 to i64
   ret i64 %ext.2
 }