[ARM] Negative constants mishandled in ARM CGP

[samparker]

Summary

During type promotion, sometimes we convert negative an add with a negative constant into a sub with a positive constant. The loop that performs this transformation has two issues:

• it iterates over a set, causing non-determinism.
• it breaks, instead of continuing, when it finds the first non-negative operand.

[SjoerdMeijer]

LGTM

lib/Target/ARM/ARMCodeGenPrepare.cpp

class IRPromoter {
   Module *M = nullptr;
   LLVMContext &Ctx;
   // The type we promote to: always i32
   IntegerType *ExtTy = nullptr;
   // 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;
-  SmallPtrSetImpl<Value*> *Visited;
+  SetVector<Value*> *Visited;
   SmallPtrSetImpl<Value*> *Sources;
   SmallPtrSetImpl<Instruction*> *Sinks;
   SmallPtrSetImpl<Instruction*> *SafeToPromote;
 
   void ReplaceAllUsersOfWith(Value *From, Value *To);
   void PrepareConstants(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,
-              SmallPtrSetImpl<Value*> &Visited,
+              SetVector<Value*> &Visited,
               SmallPtrSetImpl<Value*> &Sources,
               SmallPtrSetImpl<Instruction*> &Sinks,
               SmallPtrSetImpl<Instruction*> &SafeToPromote);
 };
 
 class ARMCodeGenPrepare : public FunctionPass {
   const ARMSubtarget *ST = nullptr;
   IRPromoter *Promoter = nullptr;
for (auto *V : *Visited) {
     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())
-          break;
+          continue;
 
         unsigned Opc = I->getOpcode();
         if (Opc != Instruction::Add && Opc != Instruction::Sub)
           continue;
 
         LLVM_DEBUG(dbgs() << "ARM CGP: Adjusting " << *I << "\n");
         auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs());
         Builder.SetInsertPoint(I);
for (auto *V : *Visited) {
     if (auto *I = dyn_cast<Instruction>(Masked))
       NewInsts.insert(I);
 
     ReplaceAllUsersOfWith(Trunc, Masked);
   }
 }
 
 void IRPromoter::Mutate(Type *OrigTy,
-                        SmallPtrSetImpl<Value*> &Visited,
+                        SetVector<Value*> &Visited,
                         SmallPtrSetImpl<Value*> &Sources,
                         SmallPtrSetImpl<Instruction*> &Sinks,
                         SmallPtrSetImpl<Instruction*> &SafeToPromote) {
   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);
if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
     return false;
 
   LLVM_DEBUG(dbgs() << "ARM CGP: TryToPromote: " << *V << ", TypeSize = "
              << TypeSize << "\n");
 
   SetVector<Value*> WorkList;
   SmallPtrSet<Value*, 8> Sources;
   SmallPtrSet<Instruction*, 4> Sinks;
-  SmallPtrSet<Value*, 16> CurrentVisited;
+  SetVector<Value*> CurrentVisited;
   WorkList.insert(V);
 
   // Return true if V was added to the worklist as a supported instruction,
   // if it was already visited, or if we don't need to explore it (e.g.
   // pointer values and GEPs), and false otherwise.
   auto AddLegalInst = [&](Value *V) {
     if (CurrentVisited.count(V))
       return true;

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

 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
   ret i32 %conv4
 }
+
+; CHECK-LABEL: convert_add_order
+; CHECK: orr{{.*}}, #1
+; CHECK: sub{{.*}}, #40
+; CHECK-NOT: uxt
+define i8 @convert_add_order(i8 zeroext %arg) {
+  %mask.0 = and i8 %arg, 1
+  %mask.1 = and i8 %arg, 2
+  %shl = or i8 %arg, 1
+  %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
+}