[ARM][CGP] Skip nuw values in PrepareConstants

[samparker]

Summary

PrepareConstants step converts add/sub with 'negative' immediates to sub/add with a 'positive' imm to make promotion more simple. nuw already states that the add shouldn't cause an unsigned overflow, so it shouldn't need any tweaking. Plus, we also don't allow a sub with a 'negative' immediate to be safe underflow, so this functionality has been removed. The PrepareConstants step now just handles the add instructions that we've determined would be safe if they underflow.

[SjoerdMeijer]

lib/Target/ARM/ARMCodeGenPrepare.cpp

480 ↗

(On Diff #199999)

Perhaps you can be more specific here:

adds that safely wrap

This is for unsigned values for which behaviour is well defined as wrapping or modulo behaviour.

The Instructions that exhibit this behaviour are added to a list SafeUnderflow in function isSafeOverflow, which all looks a bit inconsistent (yep, I'm bikeshedding names ;-)).

[samparker]

Cheers! I've swapped out 'overflow' and 'underflow' terms for wrap.

[SjoerdMeijer]

Looks like a good improvement to me.

lib/Target/ARM/ARMCodeGenPrepare.cpp

305 ↗

(On Diff #200241)

Looking at this example and comment again, we are explaining that this is not equivalent:

%sub = sub i8 %a, 2
%cmp = icmp ule i8 %sub, 254
=>
%a32 = zext i8 %a to i32
%sub1 = sub i32 %a32, 2
%cmp = icmp ule i32 %sub1, 254

and alive agrees with us :-) and gives the same values: https://rise4fun.com/Alive/6gzR

And changing the sub to a sub with constant 1 shows it is all good.

llvm/trunk/lib/Target/ARM/ARMCodeGenPrepare.cpp

class IRPromoter {
   // The type of the value that the search began from, either i8 or i16.
   // This defines the max range of the values that we allow in the promoted
   // tree.
   IntegerType *OrigTy = nullptr;
   SetVector<Value*> *Visited;
   SmallPtrSetImpl<Value*> *Sources;
   SmallPtrSetImpl<Instruction*> *Sinks;
   SmallPtrSetImpl<Instruction*> *SafeToPromote;
+  SmallPtrSetImpl<Instruction*> *SafeWrap;
 
   void ReplaceAllUsersOfWith(Value *From, Value *To);
-  void PrepareConstants(void);
+  void PrepareWrappingAdds(void);
   void ExtendSources(void);
   void ConvertTruncs(void);
   void PromoteTree(void);
   void TruncateSinks(void);
   void Cleanup(void);
 
 public:
   IRPromoter(Module *M) : M(M), Ctx(M->getContext()),
                           ExtTy(Type::getInt32Ty(Ctx)) { }
 
 
   void Mutate(Type *OrigTy,
               SetVector<Value*> &Visited,
               SmallPtrSetImpl<Value*> &Sources,
               SmallPtrSetImpl<Instruction*> &Sinks,
-              SmallPtrSetImpl<Instruction*> &SafeToPromote);
+              SmallPtrSetImpl<Instruction*> &SafeToPromote,
+              SmallPtrSetImpl<Instruction*> &SafeWrap);
 };
 
 class ARMCodeGenPrepare : public FunctionPass {
   const ARMSubtarget *ST = nullptr;
   IRPromoter *Promoter = nullptr;
   std::set<Value*> AllVisited;
   SmallPtrSet<Instruction*, 8> SafeToPromote;
+  SmallPtrSet<Instruction*, 4> SafeWrap;
 
-  bool isSafeOverflow(Instruction *I);
+  bool isSafeWrap(Instruction *I);
   bool isSupportedValue(Value *V);
   bool isLegalToPromote(Value *V);
   bool TryToPromote(Value *V);
 
 public:
   static char ID;
   static unsigned TypeSize;
   Type *OrigTy = nullptr;
static bool isSink(Value *V) {
   if (auto *Switch = dyn_cast<SwitchInst>(V))
     return LessThanTypeSize(Switch->getCondition());
   if (auto *ICmp = dyn_cast<ICmpInst>(V))
     return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
 
   return isa<CallInst>(V);
 }
 
-/// Return whether the instruction can be promoted within any modifications to
-/// its operands or result.
-bool ARMCodeGenPrepare::isSafeOverflow(Instruction *I) {
-  // FIXME Do we need NSW too?
-  if (isa<OverflowingBinaryOperator>(I) && I->hasNoUnsignedWrap())
-    return true;
-
-  // We can support a, potentially, overflowing instruction (I) if:
+/// Return whether this instruction can safely wrap.
+bool ARMCodeGenPrepare::isSafeWrap(Instruction *I) {
+  // We can support a, potentially, wrapping instruction (I) if:
   // - It is only used by an unsigned icmp.
   // - The icmp uses a constant.
-  // - The overflowing value (I) is decreasing, i.e would underflow - wrapping
+  // - The wrapping value (I) is decreasing, i.e would underflow - wrapping
   //   around zero to become a larger number than before.
-  // - The underflowing instruction (I) also uses a constant.
+  // - The wrapping instruction (I) also uses a constant.
   //
   // We can then use the two constants to calculate whether the result would
   // wrap in respect to itself in the original bitwidth. If it doesn't wrap,
   // just underflows the range, the icmp would give the same result whether the
   // result has been truncated or not. We calculate this by:
   // - Zero extending both constants, if needed, to 32-bits.
   // - Take the absolute value of I's constant, adding this to the icmp const.
   // - Check that this value is not out of range for small type. If it is, it
if (Total.ugt(Max.zext(Total.getBitWidth())))
       return false;
   } else if (Max.getBitWidth() > Total.getBitWidth()) {
     if (Total.zext(Max.getBitWidth()).ugt(Max))
       return false;
   } else if (Total.ugt(Max))
     return false;
 
   LLVM_DEBUG(dbgs() << "ARM CGP: Allowing safe overflow for " << *I << "\n");
+  SafeWrap.insert(I);
   return true;
 }
 
 static bool shouldPromote(Value *V) {
   if (!isa<IntegerType>(V->getType()) || isSink(V))
     return false;
 
   if (isSource(V))
     return true;
 
   auto *I = dyn_cast<Instruction>(V);
   if (!I)
     return false;
 
   if (isa<ICmpInst>(I))
     return false;
 
   return true;
 }
 
 /// Return whether we can safely mutate V's type to ExtTy without having to be
 /// concerned with zero extending or truncation.
 static bool isPromotedResultSafe(Value *V) {
+  if (GenerateSignBits(V))
+    return false;
+
   if (!isa<Instruction>(V))
     return true;
 
-  if (GenerateSignBits(V))
-    return false;
+  if (!isa<OverflowingBinaryOperator>(V))
+    return true;
 
-  return !isa<OverflowingBinaryOperator>(V);
+  return cast<Instruction>(V)->hasNoUnsignedWrap();
 }
 
 /// Return the intrinsic for the instruction that can perform the same
 /// operation but on a narrow type. This is using the parallel dsp intrinsics
 /// on scalar values.
 static Intrinsic::ID getNarrowIntrinsic(Instruction *I) {
   // Whether we use the signed or unsigned versions of these intrinsics
   // doesn't matter because we're not using the GE bits that they set in
void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {
   for (auto *U : Users)
     U->replaceUsesOfWith(From, To);
 
   if (ReplacedAll)
     if (auto *I = dyn_cast<Instruction>(From))
       InstsToRemove.insert(I);
 }
 
-void IRPromoter::PrepareConstants() {
+void IRPromoter::PrepareWrappingAdds() {
+  LLVM_DEBUG(dbgs() << "ARM CGP: Prepare underflowing adds.\n");
   IRBuilder<> Builder{Ctx};
-  // First step is to prepare the instructions for mutation. Most constants
-  // just need to be zero extended into their new type, but complications arise
-  // because:
-  // - For nuw binary operators, negative immediates would need sign extending;
-  //   however, instead we'll change them to positive and zext them. We can do
-  //   this because:
-  //   > The operators that can wrap are: add, sub, mul and shl.
-  //   > shl interprets its second operand as unsigned and if the first operand
-  //     is an immediate, it will need zext to be nuw.
-  //   > I'm assuming mul has to interpret immediates as unsigned for nuw.
-  //   > Which leaves the nuw add and sub to be handled; as with shl, if an
-  //     immediate is used as operand 0, it will need zext to be nuw.
-  // - We also allow add and sub to safely overflow in certain circumstances
-  //   and only when the value (operand 0) is being decreased.
-  //
-  // For adds and subs, that are either nuw or safely wrap and use a negative
-  // immediate as operand 1, we create an equivalent instruction using a
-  // positive immediate. That positive immediate can then be zext along with
-  // all the other immediates later.
-  for (auto *V : *Visited) {
-    if (!isa<Instruction>(V))
-      continue;
-
-    auto *I = cast<Instruction>(V);
-    if (SafeToPromote->count(I)) {
 
-      if (!isa<OverflowingBinaryOperator>(I))
-        continue;
-
-      if (auto *Const = dyn_cast<ConstantInt>(I->getOperand(1))) {
-        if (!Const->isNegative())
-          continue;
-
-        unsigned Opc = I->getOpcode();
-        if (Opc != Instruction::Add && Opc != Instruction::Sub)
-          continue;
+  // For adds that safely wrap and use a negative immediate as operand 1, we
+  // create an equivalent instruction using a positive immediate.
+  // That positive immediate can then be zext along with all the other
+  // immediates later.
+  for (auto *I : *SafeWrap) {
+    if (I->getOpcode() != Instruction::Add)
 
-        LLVM_DEBUG(dbgs() << "ARM CGP: Adjusting " << *I << "\n");
-        auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs());
-        Builder.SetInsertPoint(I);
-        Value *NewVal = Opc == Instruction::Sub ?
-          Builder.CreateAdd(I->getOperand(0), NewConst) :
-          Builder.CreateSub(I->getOperand(0), NewConst);
-        LLVM_DEBUG(dbgs() << "ARM CGP: New equivalent: " << *NewVal << "\n");
-
-        if (auto *NewInst = dyn_cast<Instruction>(NewVal)) {
-          NewInst->copyIRFlags(I);
-          NewInsts.insert(NewInst);
-        }
-        InstsToRemove.insert(I);
-        I->replaceAllUsesWith(NewVal);
-      }
-    }
+    assert((isa<ConstantInt>(I->getOperand(1)) &&
+            cast<ConstantInt>(I->getOperand(1))->isNegative()) &&
+           "Wrapping should have a negative immediate as the second operand");
+
+    auto Const = cast<ConstantInt>(I->getOperand(1));
+    Value *NewVal = Builder.CreateSub(I->getOperand(0), NewConst);
+    LLVM_DEBUG(dbgs() << "ARM CGP: New equivalent: " << *NewVal << "\n");
   }
   for (auto *I : NewInsts)
     Visited->insert(I);
 }
 
 void IRPromoter::ExtendSources() {
   IRBuilder<> Builder{Ctx};
 
for (auto *I : InstsToRemove) {
     I->dropAllReferences();
     I->eraseFromParent();
   }
 
   InstsToRemove.clear();
   NewInsts.clear();
   TruncTysMap.clear();
   Promoted.clear();
+  SafeToPromote->clear();
+  SafeWrap->clear();
 }
 
 void IRPromoter::ConvertTruncs() {
   LLVM_DEBUG(dbgs() << "ARM CGP: Converting truncs..\n");
   IRBuilder<> Builder{Ctx};
 
   for (auto *V : *Visited) {
     if (!isa<TruncInst>(V) || Sources->count(V))
for (auto *V : *Visited) {
     ReplaceAllUsersOfWith(Trunc, Masked);
   }
 }
 
 void IRPromoter::Mutate(Type *OrigTy,
                         SetVector<Value*> &Visited,
                         SmallPtrSetImpl<Value*> &Sources,
                         SmallPtrSetImpl<Instruction*> &Sinks,
-                        SmallPtrSetImpl<Instruction*> &SafeToPromote) {
+                        SmallPtrSetImpl<Instruction*> &SafeToPromote,
+                        SmallPtrSetImpl<Instruction*> &SafeWrap) {
   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from "
              << ARMCodeGenPrepare::TypeSize << " to 32-bits\n");
 
   assert(isa<IntegerType>(OrigTy) && "expected integer type");
   this->OrigTy = cast<IntegerType>(OrigTy);
   assert(OrigTy->getPrimitiveSizeInBits() < ExtTy->getPrimitiveSizeInBits() &&
          "original type not smaller than extended type");
 
   this->Visited = &Visited;
   this->Sources = &Sources;
   this->Sinks = &Sinks;
   this->SafeToPromote = &SafeToPromote;
+  this->SafeWrap = &SafeWrap;
 
   // Cache original types of the values that will likely need truncating
   for (auto *I : Sinks) {
     if (auto *Call = dyn_cast<CallInst>(I)) {
       for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
         Value *Arg = Call->getArgOperand(i);
         TruncTysMap[Call].push_back(Arg->getType());
       }
     } else if (auto *Switch = dyn_cast<SwitchInst>(I))
       TruncTysMap[I].push_back(Switch->getCondition()->getType());
     else {
       for (unsigned i = 0; i < I->getNumOperands(); ++i)
         TruncTysMap[I].push_back(I->getOperand(i)->getType());
     }
   }
   for (auto *V : Visited) {
     if (!isa<TruncInst>(V) || Sources.count(V))
       continue;
     auto *Trunc = cast<TruncInst>(V);
     TruncTysMap[Trunc].push_back(Trunc->getDestTy());
   }
 
-  // Convert adds and subs using negative immediates to equivalent instructions
-  // that use positive constants.
-  PrepareConstants();
+  // Convert adds using negative immediates to equivalent instructions that use
+  // positive constants.
+  PrepareWrappingAdds();
 
   // Insert zext instructions between sources and their users.
   ExtendSources();
 
   // Promote visited instructions, mutating their types in place. Also insert
   // DSP intrinsics, if enabled, for adds and subs which would be unsafe to
   // promote.
   PromoteTree();
bool ARMCodeGenPrepare::isLegalToPromote(Value *V) {
 
   auto *I = dyn_cast<Instruction>(V);
   if (!I)
     return true;
 
   if (SafeToPromote.count(I))
    return true;
 
-  if (isPromotedResultSafe(V) || isSafeOverflow(I)) {
+  if (isPromotedResultSafe(V) || isSafeWrap(I)) {
     SafeToPromote.insert(I);
     return true;
   }
 
   if (I->getOpcode() != Instruction::Add && I->getOpcode() != Instruction::Sub)
     return false;
 
   // If promotion is not safe, can we use a DSP instruction to natively
for (auto *V : CurrentVisited) {
     if (Sinks.count(cast<Instruction>(V)))
       continue;
     ++ToPromote;
   }
 
   if (ToPromote < 2)
     return false;
 
-  Promoter->Mutate(OrigTy, CurrentVisited, Sources, Sinks, SafeToPromote);
+  Promoter->Mutate(OrigTy, CurrentVisited, Sources, Sinks, SafeToPromote,
+                   SafeWrap);
   return true;
 }
 
 bool ARMCodeGenPrepare::doInitialization(Module &M) {
   Promoter = new IRPromoter(&M);
   return false;
 }
 

llvm/trunk/test/CodeGen/ARM/CGP/arm-cgp-overflow.ll

-; RUN: llc -mtriple=thumbv8m.main -mcpu=cortex-m33 %s -arm-disable-cgp=false -o - | FileCheck %s
+; RUN: llc -mtriple=thumbv8m.main -mcpu=cortex-m33 -mattr=-use-misched %s -arm-disable-cgp=false -o - | FileCheck %s
 
 ; CHECK: overflow_add
 ; CHECK: add
 ; CHECK: uxth
 ; CHECK: cmp
 define zeroext i16 @overflow_add(i16 zeroext %a, i16 zeroext %b) {
   %add = add i16 %a, %b
   %or = or i16 %add, 1
entry:
   %0 = load i8, i8* %b, align 1
   %sub = sub nuw nsw i8 -8, %0
   %cmp = icmp ugt i8 %sub, 252
   %conv4 = zext i1 %cmp to i32
   ret i32 %conv4
 }
 
 ; CHECK-LABEL: safe_sub_var_imm
-; CHECK:      add.w [[ADD:r[0-9]+]], r0, #8
+; CHECK:      sub.w [[ADD:r[0-9]+]], r0, #248
 ; CHECK-NOT:  uxt
 ; CHECK:      cmp [[ADD]], #252
 define i32 @safe_sub_var_imm(i8* %b) {
 entry:
   %0 = load i8, i8* %b, align 1
   %sub = sub nuw nsw i8 %0, -8
   %cmp = icmp ugt i8 %sub, 252
   %conv4 = zext i1 %cmp to i32
entry:
   %0 = load i8, i8* %b, align 1
   %add = add nuw nsw i8 -127, %0
   %cmp = icmp ugt i8 %add, 127
   %conv4 = zext i1 %cmp to i32
   ret i32 %conv4
 }
 
 ; CHECK-LABEL: safe_add_var_imm
-; CHECK:      sub.w [[SUB:r[0-9]+]], r0, #127
+; CHECK:      add.w [[SUB:r[0-9]+]], r0, #129
 ; CHECK-NOT:  uxt
 ; CHECK:      cmp [[SUB]], #127
 define i32 @safe_add_var_imm(i8* %b) {
 entry:
   %0 = load i8, i8* %b, align 1
   %add = add nuw nsw i8 %0, -127
   %cmp = icmp ugt i8 %add, 127
   %conv4 = zext i1 %cmp to i32
define i8 @convert_add_order(i8 zeroext %arg) {
   %add = add nuw i8 %shl, 10
   %cmp.0 = icmp ult i8 %add, 60
   %sub = add nsw i8 %shl, -40
   %cmp.1 = icmp ult i8 %sub, 20
   %mask.sel = select i1 %cmp.1, i8 %mask.0, i8 %mask.1
   %res = select i1 %cmp.0, i8 %mask.sel, i8 %arg
   ret i8 %res
 }
+
+; CHECK-LABEL: underflow_if_sub
+; CHECK: add{{.}} [[ADD:r[0-9]+]], #245
+; CHECK: cmp [[ADD]], r1
+define i8 @underflow_if_sub(i32 %arg, i8 zeroext %arg1) {
+  %cmp = icmp sgt i32 %arg, 0
+  %conv = zext i1 %cmp to i32
+  %and = and i32 %arg, %conv
+  %trunc = trunc i32 %and to i8
+  %conv1 = add nuw nsw i8 %trunc, -11
+  %cmp.1 = icmp ult i8 %conv1, %arg1
+  %res = select i1 %cmp.1, i8 %conv1, i8 100
+  ret i8 %res
+}
+
+; CHECK-LABEL: underflow_if_sub_signext
+; CHECK: uxtb [[UXT1:r[0-9]+]], r1
+; CHECK: sub{{.*}} [[SUB:r[0-9]+]], #11
+; CHECK: uxtb [[UXT_SUB:r[0-9]+]], [[SUB]]
+; CHECK: cmp{{.*}}[[UXT_SUB]]
+define i8 @underflow_if_sub_signext(i32 %arg, i8 signext %arg1) {
+  %cmp = icmp sgt i32 %arg, 0
+  %conv = zext i1 %cmp to i32
+  %and = and i32 %arg, %conv
+  %trunc = trunc i32 %and to i8
+  %conv1 = add nuw nsw i8 %trunc, -11
+  %cmp.1 = icmp ugt i8 %arg1, %conv1
+  %res = select i1 %cmp.1, i8 %conv1, i8 100
+  ret i8 %res
+}