[ARM] Handle signed icmps in ARMCodeGenPrepare

[samparker]

Summary

Treat signed icmps as 'sinks', allowing them to be in the use-def tree, enabling more promotions to be performed. As a sink, any promoted incoming values need to be truncated before being used by the signed icmp.

[samparker]

Rebased.

[SjoerdMeijer]

test/CodeGen/ARM/arm-cgp-signed-icmps.ll

22

Perhaps better to match registers with "r[0-9]+"?

[samparker]

Changed test regexesess

[samparker]

Rebased.

[SjoerdMeijer]

LGTM

[vitalybuka]

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/22348/steps/check-llvm%20asan/logs/stdio

Command Output (stderr):
--
=================================================================
==40218==ERROR: AddressSanitizer: use-after-poison on address 0x621000003dc8 at pc 0x00000168d853 bp 0x7fff0ab4e990 sp 0x7fff0ab4e988
READ of size 8 at 0x621000003dc8 thread T0
    #0 0x168d852 in getParamType /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/DerivedTypes.h:135:49
    #1 0x168d852 in Mutate /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp:463
    #2 0x168d852 in TryToPromote /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp:658
    #3 0x168d852 in (anonymous namespace)::ARMCodeGenPrepare::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Target/ARM/ARMCodeGenPrepare.cpp:697
    #4 0x476458d in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/LegacyPassManager.cpp:1586:27
    #5 0x4764ba2 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/LegacyPassManager.cpp:1609:16
    #6 0x4765918 in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/LegacyPassManager.cpp:1669:27
    #7 0x4765918 in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/LegacyPassManager.cpp:1774
    #8 0x9f6d5f in compileModule(char**, llvm::LLVMContext&) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/llc/llc.cpp:597:8
    #9 0x9f02d0 in main /b/sanitizer-x86_64-linux-fast/build/llvm/tools/llc/llc.cpp:351:22
    #10 0x7fdfb54d92e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #11 0x8fa609 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/llc+0x8fa609)

0x621000003dc8 is located 200 bytes inside of 4096-byte region [0x621000003d00,0x621000004d00)
allocated by thread T0 here:
    #0 0x9b8a58 in malloc /b/sanitizer-x86_64-linux-fast/build/llvm/projects/compiler-rt/lib/asan/asan_malloc_linux.cc:88
    #1 0xa1e27c in safe_malloc /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/MemAlloc.h:27:18
    #2 0xa1e27c in Allocate /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/Allocator.h:99
    #3 0xa1e27c in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>::StartNewSlab() /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/Allocator.h:346
    #4 0xa1df4e in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>::Allocate(unsigned long, unsigned long) /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/Allocator.h:260:5
    #5 0x482b55a in operator new<llvm::MallocAllocator, 4096, 4096> /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/Allocator.h:454:20
    #6 0x482b55a in llvm::PointerType::get(llvm::Type*, unsigned int) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IR/Type.cpp:628
    #7 0x685b2fb in getUnqual /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/DerivedTypes.h:483:12
    #8 0x685b2fb in llvm::LLParser::ParseType(llvm::Type*&, llvm::Twine const&, bool) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.cpp:2309
    #9 0x68605b4 in ParseType /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.h:384:14
    #10 0x68605b4 in llvm::LLParser::ParseArgumentList(llvm::SmallVectorImpl<llvm::LLParser::ArgInfo>&, bool&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.cpp:2475
    #11 0x682abad in llvm::LLParser::ParseFunctionHeader(llvm::Function*&, bool) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.cpp:5147:7
    #12 0x681e75c in llvm::LLParser::ParseDefine() /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.cpp:502:10
    #13 0x6816ac5 in llvm::LLParser::ParseTopLevelEntities() /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.cpp:316:33
    #14 0x681682b in llvm::LLParser::Run() /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/LLParser.cpp:74:10
    #15 0x67f0ddb in llvm::parseAssemblyInto(llvm::MemoryBufferRef, llvm::Module*, llvm::ModuleSummaryIndex*, llvm::SMDiagnostic&, llvm::SlotMapping*, bool, llvm::StringRef) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/Parser.cpp:38:8
    #16 0x67f1950 in llvm::parseAssembly(llvm::MemoryBufferRef, llvm::SMDiagnostic&, llvm::LLVMContext&, llvm::SlotMapping*, bool, llvm::StringRef) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/AsmParser/Parser.cpp:48:7
    #17 0x48fbf3a in llvm::parseIR(llvm::MemoryBufferRef, llvm::SMDiagnostic&, llvm::LLVMContext&, bool, llvm::StringRef) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IRReader/IRReader.cpp:92:10
    #18 0x48fd026 in llvm::parseIRFile(llvm::StringRef, llvm::SMDiagnostic&, llvm::LLVMContext&, bool, llvm::StringRef) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/IRReader/IRReader.cpp:108:10
    #19 0x9f11d5 in compileModule(char**, llvm::LLVMContext&) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/llc/llc.cpp:405:11
    #20 0x9f02d0 in main /b/sanitizer-x86_64-linux-fast/build/llvm/tools/llc/llc.cpp:351:22
    #21 0x7fdfb54d92e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)

SUMMARY: AddressSanitizer: use-after-poison /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/IR/DerivedTypes.h:135:49 in getParamType
Shadow bytes around the buggy address:
  0x0c427fff8760: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c427fff8770: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c427fff8780: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c427fff8790: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c427fff87a0: 00 00 00 00 f7 00 00 00 00 00 00 00 00 f7 00 00
=>0x0c427fff87b0: 00 00 f7 00 00 00 00 00 00[f7]00 00 00 00 f7 00
  0x0c427fff87c0: 00 00 00 00 00 00 00 f7 00 00 00 00 f7 f7 00 00
  0x0c427fff87d0: 00 00 f7 00 00 00 00 00 00 f7 00 00 00 00 f7 f7
  0x0c427fff87e0: 00 00 00 00 00 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0c427fff87f0: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0c427fff8800: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==40218==ABORTING
FileCheck error: '-' is empty.
FileCheck command line:  /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/FileCheck /b/sanitizer-x86_64-linux-fast/build/llvm/test/CodeGen/ARM/arm-cgp-pointers.ll

--

********************
Testing: 0 .. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
Testing Time: 217.59s
********************
Failing Tests (1):
    LLVM :: CodeGen/ARM/arm-cgp-pointers.ll

  Expected Passes    : 26315
  Expected Failures  : 148
  Unsupported Tests  : 682
  Unexpected Failures: 1
FAILED: test/CMakeFiles/check-llvm 
cd /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/test && /usr/bin/python2.7 /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/./bin/llvm-lit -sv /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/test
ninja: build stopped: subcommand failed.
+ echo @@@STEP_FAILURE@@@
+ echo @@@BUILD_STEP check-clang asan@@@
@@@STEP_FAILURE@@@

[vitalybuka]

I don't see obvious problem here.
If no one is looking into this, I am going to revert?

[vitalybuka]

Reverted with r339806

[samparker]

Thanks for reverting. The issue was that I was assuming that the instruction operands mapped to arguments for CallInsts. Will be recommitting.

[samparker]

Fixed and recommitted in r339858.

lib/Target/ARM/ARMCodeGenPrepare.cpp

   };
 
   if (auto *Store = dyn_cast<StoreInst>(V))
     return UsesNarrowValue(Store->getValueOperand());
   if (auto *Return = dyn_cast<ReturnInst>(V))
     return UsesNarrowValue(Return->getReturnValue());
   if (auto *Trunc = dyn_cast<TruncInst>(V))
     return UsesNarrowValue(Trunc->getOperand(0));
+  if (auto *ICmp = dyn_cast<ICmpInst>(V))
+    return ICmp->isSigned();
 
   return isa<CallInst>(V);
 }
 
 /// Return whether the instruction can be promoted within any modifications to
 /// it's operands or result.
 static bool isSafeOverflow(Instruction *I) {
   // FIXME Do we need NSW too?

                         SmallPtrSetImpl<Value*> &Leaves,
                         SmallPtrSetImpl<Instruction*> &Roots) {
   IRBuilder<> Builder{Ctx};
   Type *ExtTy = Type::getInt32Ty(M->getContext());
   SmallPtrSet<Value*, 8> Promoted;
   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from "
              << ARMCodeGenPrepare::TypeSize << " to 32-bits\n");
 
+  // Cache original types.
+  DenseMap<Value*, Type*> TruncTysMap;
+  for (auto *V : Visited)
+    TruncTysMap[V] = V->getType();
+
   auto ReplaceAllUsersOfWith = [&](Value *From, Value *To) {
     SmallVector<Instruction*, 4> Users;
     Instruction *InstTo = dyn_cast<Instruction>(To);
     for (Use &U : From->uses()) {
       auto *User = cast<Instruction>(U.getUser());
       if (InstTo && User->isIdenticalTo(InstTo))
         continue;
       Users.push_back(User);

       Intrinsic::getDeclaration(M, getNarrowIntrinsic(I));
     Builder.SetInsertPoint(I);
     Builder.SetCurrentDebugLocation(I->getDebugLoc());
     Value *Args[] = { I->getOperand(0), I->getOperand(1) };
     CallInst *Call = Builder.CreateCall(DSPInst, Args);
     ReplaceAllUsersOfWith(I, Call);
     InstsToRemove.push_back(I);
     NewInsts.insert(Call);
+    TruncTysMap[Call] = OrigTy;
   };
 
   auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
     LLVM_DEBUG(dbgs() << "ARM CGP: Inserting ZExt for " << *V << "\n");
     Builder.SetInsertPoint(InsertPt);
     if (auto *I = dyn_cast<Instruction>(V))
       Builder.SetCurrentDebugLocation(I->getDebugLoc());
     auto *ZExt = cast<Instruction>(Builder.CreateZExt(V, ExtTy));
     if (isa<Argument>(V))
       ZExt->moveBefore(InsertPt);
     else
       ZExt->moveAfter(InsertPt);
     ReplaceAllUsersOfWith(V, ZExt);
     NewInsts.insert(ZExt);
+    TruncTysMap[ZExt] = TruncTysMap[V];
   };
 
   // First, insert extending instructions between the leaves and their users.
   LLVM_DEBUG(dbgs() << "ARM CGP: Promoting leaves:\n");
   for (auto V : Leaves) {
     LLVM_DEBUG(dbgs() << " - " << *V << "\n");
     if (auto *I = dyn_cast<Instruction>(V))
       InsertZExt(I, I);

 
     if (!shouldPromote(V) || isPromotedResultSafe(V))
       continue;
 
     // Replace unsafe instructions with appropriate intrinsic calls.
     InsertDSPIntrinsic(cast<Instruction>(V));
   }
 
+  auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction* {
+    if (TruncTy == ExtTy || !isa<Instruction>(V))
+      return nullptr;
+
+    if (!Promoted.count(V) && !NewInsts.count(V))
+      return nullptr;
+
+    LLVM_DEBUG(dbgs() << "ARM CGP: Creating " << *TruncTy << " Trunc for "
+               << *V << "\n");
+    Builder.SetInsertPoint(cast<Instruction>(V));
+    auto *Trunc = cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
+    NewInsts.insert(Trunc);
+    return Trunc;
+  };
+
   LLVM_DEBUG(dbgs() << "ARM CGP: Fixing up the roots:\n");
   // Fix up any stores or returns that use the results of the promoted
   // chain.
   for (auto I : Roots) {
     LLVM_DEBUG(dbgs() << " - " << *I << "\n");
     Type *TruncTy = OrigTy;
     if (auto *Store = dyn_cast<StoreInst>(I)) {
       auto *PtrTy = cast<PointerType>(Store->getPointerOperandType());
       TruncTy = PtrTy->getElementType();
     } else if (isa<ReturnInst>(I)) {
       Function *F = I->getParent()->getParent();
       TruncTy = F->getFunctionType()->getReturnType();
     }
 
+    // Both these will only have one operand to fix.
+    if (isa<StoreInst>(I) || isa<ReturnInst>(I)) {
+      if (Instruction *Trunc = InsertTrunc(I->getOperand(0), TruncTy)) {
+        Trunc->moveBefore(I);
+        I->setOperand(0, Trunc);
+      }
+      continue;
+    }
+
+    // Now handle calls and signed icmps.
     for (unsigned i = 0; i < I->getNumOperands(); ++i) {
-      Value *V = I->getOperand(i);
-      if (Promoted.count(V) || NewInsts.count(V)) {
-        if (auto *Op = dyn_cast<Instruction>(V)) {
-
-          if (auto *Call = dyn_cast<CallInst>(I))
-            TruncTy = Call->getFunctionType()->getParamType(i);
-
-          if (TruncTy == ExtTy)
-            continue;
-
-          LLVM_DEBUG(dbgs() << "ARM CGP: Creating " << *TruncTy
-                     << " Trunc for " << *Op << "\n");
-          Builder.SetInsertPoint(Op);
-          auto *Trunc = cast<Instruction>(Builder.CreateTrunc(Op, TruncTy));
-          Trunc->moveBefore(I);
-          I->setOperand(i, Trunc);
-          NewInsts.insert(Trunc);
-        }
+      if (auto *Call = dyn_cast<CallInst>(I))
+        TruncTy = Call->getFunctionType()->getParamType(i);
+      else
+        TruncTy = TruncTysMap[I->getOperand(i)];
+
+      if (Instruction *Trunc = InsertTrunc(I->getOperand(i), TruncTy)) {
+        Trunc->moveBefore(I);
+        I->setOperand(i, Trunc);
       }
     }
   }
   LLVM_DEBUG(dbgs() << "ARM CGP: Mutation complete.\n");
 }
 
 /// We accept most instructions, as well as Arguments and ConstantInsts. We
 /// Disallow casts other than zext and truncs and only allow calls if their
 /// return value is zeroext. We don't allow opcodes that can introduce sign
 /// bits.
 bool ARMCodeGenPrepare::isSupportedValue(Value *V) {
   LLVM_DEBUG(dbgs() << "ARM CGP: Is " << *V << " supported?\n");
 
-  if (auto *ICmp = dyn_cast<ICmpInst>(V))
-    return ICmp->isEquality() || !ICmp->isSigned();
+  if (isa<ICmpInst>(V))
+    return true;
 
   // Memory instructions
   if (isa<StoreInst>(V) || isa<GetElementPtrInst>(V))
     return true;
 
   // Branches and targets.
   if( isa<BranchInst>(V) || isa<SwitchInst>(V) || isa<BasicBlock>(V))
     return true;

test/CodeGen/ARM/arm-cgp-signed-icmps.ll

+; RUN: llc -mtriple=thumbv8.main -mcpu=cortex-m33 -arm-disable-cgp=false -mattr=-use-misched %s -o - | FileCheck %s --check-prefix=CHECK-COMMON --check-prefix=CHECK-NODSP
+; RUN: llc -mtriple=thumbv7em %s -arm-disable-cgp=false -arm-enable-scalar-dsp=true -o - | FileCheck %s --check-prefix=CHECK-COMMON --check-prefix=CHECK-DSP
+; RUN: llc -mtriple=thumbv8 %s -arm-disable-cgp=false -arm-enable-scalar-dsp=true -arm-enable-scalar-dsp-imms=true -o - | FileCheck %s --check-prefix=CHECK-COMMON --check-prefix=CHECK-DSP-IMM
+
+; CHECK-COMMON-LABEL: eq_sgt
+; CHECK-NODSP: add
+; CHECK-NODSP: uxtb
+; CHECK-NODSP: sxtb
+; CHECK-NODSP: cmp
+; CHECK-NODSP: sub
+; CHECK-NODSP: sxtb
+; CHECK-NODSP: cmp
+
+; CHECK-DSP: add
+; CHECK-DSP: uxtb
+; CHECK-DSP: cmp
+; CHECK-DSP: sxtb
+; CHECK-DSP: sub
+; CHECK-DSP: sxtb
+; CHECK-DSP: cmp
+
+; CHECK-DSP-IMM: uadd8 [[ADD:r[^ ]+]],
+; CHECK-DSP-IMM: cmp [[ADD]],
+; CHECK-DSP-IMM: sxtb [[SEXT0:r[^ ]+]], [[ADD]]
+; CHECK-DSP-IMM: usub8 [[SUB:r[^ ]+]],
+; CHECK-DSP-IMM: sxtb [[SEXT1:r[^ ]+]], [[SUB]]
+; CHECK-DSP-IMM: cmp [[SEXT1]], [[SEXT0]]
+define i8 @eq_sgt(i8* %x, i8 *%y, i8 zeroext %z) {
+entry:
+  %load0 = load i8, i8* %x, align 1
+  %load1 = load i8, i8* %y, align 1
+  %add = add i8 %load0, %z
+  %sub = sub i8 %load1, 1
+  %cmp = icmp eq i8 %add, 200
+  %cmp1 = icmp sgt i8 %sub, %add
+  %res0 = select i1 %cmp, i8 35, i8 47
+  %res1 = select i1 %cmp1, i8 %res0, i8 %sub
+  ret i8 %res1
+}
+
+; CHECK-COMMON-LABEL: ugt_slt
+; CHECK-NODSP: sub
+; CHECK-NODSP: sxth
+; CHECK-NODSP: uxth
+; CHECK-NODSP: add
+; CHECK-NODSP: sxth
+; CHECK-NODSP: cmp
+; CHECK-NODSP: cmp
+
+; CHECK-DSP: sxth [[ARG:r[^ ]+]], r2
+; CHECK-DSP: subs [[SUB:r[^ ]+]],
+; CHECK-DSP: uadd16 [[ADD:r[^ ]+]],
+; CHECK-DSP: sxth.w [[SEXT:r[^ ]+]], [[ADD]]
+; CHECK-DSP: cmp [[SEXT]], [[ARG]]
+; CHECK-DSP-NOT: uxt
+; CHECK-DSP: cmp [[SUB]], r2
+define i16 @ugt_slt(i16 *%x, i16 zeroext %y, i16 zeroext %z) {
+entry:
+  %load0 = load i16, i16* %x, align 1
+  %add = add i16 %load0, %z
+  %sub = sub i16 %y, 1
+  %cmp = icmp slt i16 %add, %z
+  %cmp1 = icmp ugt i16 %sub, %z
+  %res0 = select i1 %cmp, i16 35, i16 -1
+  %res1 = select i1 %cmp1, i16 %res0, i16 0
+  ret i16 %res1
+}
+
+; CHECK-COMMON-LABEL: urem_trunc_icmps
+; CHECK-COMMON-NOT: uxt
+; CHECK-COMMON: sxtb [[SEXT:r[^ ]+]],
+; CHECK-COMMON: cmp [[SEXT]], #7
+define void @urem_trunc_icmps(i16** %in, i32* %g, i32* %k) {
+entry:
+  %ptr = load i16*, i16** %in, align 4
+  %ld = load i16, i16* %ptr, align 2
+  %cmp.i = icmp eq i16 %ld, 0
+  br i1 %cmp.i, label %exit, label %cond.false.i
+
+cond.false.i:
+  %rem = urem i16 5, %ld
+  %extract.t = trunc i16 %rem to i8
+  br label %body
+
+body:
+  %cond.in.i.off0 = phi i8 [ %extract.t, %cond.false.i ], [ %add, %for.inc ]
+  %cmp = icmp sgt i8 %cond.in.i.off0, 7
+  %conv5 = zext i1 %cmp to i32
+  store i32 %conv5, i32* %g, align 4
+  %.pr = load i32, i32* %k, align 4
+  %tobool13150 = icmp eq i32 %.pr, 0
+  br i1 %tobool13150, label %for.inc, label %exit
+
+for.inc:
+  %add = add nuw i8 %cond.in.i.off0, 1
+  br label %body
+
+exit:
+  ret void
+}