[RFC] Change cmp instrumentation to distinguish comparisons with const operands

[tch1bo]

Summary

This implementation of SanitizerCoverage instrumentation inserts different callbacks depending on constantness of operands:

1. If both operands are non-const, then a usual __sanitizer_cov_trace_cmp[1248] call is inserted.
2. If exactly one operand is const, then a __sanitizer_cov_trace_const_cmp[1248] call is inserted. The first argument of the call is always the constant one.
3. If both operands are const, then no callback is inserted.

This separation comes useful in fuzzing when tasks like "find one operand of the comparison in input arguments and replace it with the other one" have to be done. The new instrumentation allows us to not waste time on searching the constant operands in the input.

[glider]

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

675

Pay attention to the comment style: single-line comments start with a capital letter and end with a period.

677

Ditto.

679

Nested code should be indented with two spaces.

680

You don't need braces for one-line if body.

test/Instrumentation/SanitizerCoverage/const-cmp-tracing.ll

31

Please add tests for swapped arguments, e.g. "icmp slt 1, i8 %x"

[glider]

Kostya, Dima,

Do we need to put this code behind a flag (probably yes, if we don't want to break the API for the existing users)?
Any other comments?

[dvyukov]

In D36465#835269, @glider wrote:

Kostya, Dima,

Do we need to put this code behind a flag (probably yes, if we don't want to break the API for the existing users)?
Any other comments?

We don't yet have support for this in kernel. When we add it, we add both const and non-const versions. So API issues only affect user-space. So the question goes to Kostya.

[kcc]

I am fine with breaking the API. Whoever uses this API will need to add a tiny bit of code to work with the new compiler (and that code will be compatible with the old version).
It's better to break the API this way than to introduce the flags or weak aliases, etc

Please update the documentation in this patch. (mention that these functions are emitted by clang >= 2017-08-XX)

Make sure to run 'ninja check-fuzzer'. Most likely it will break due to the API change, fix it in libFuzzer (in a simple way, by calling __sanitizer_cov_trace_cmpN)

Find all uses of __sanitizer_cov_trace_cmp1 in projects/compiler-rt/lib/sanitizer_common and update those files.

test/Instrumentation/SanitizerCoverage/const-cmp-tracing.ll

22

Adding CHECK-NEXT is a good idea, do it here and below

27

Add
CHECK: icmp slt i32 1, 0

[dvyukov]

In D36465#835650, @kcc wrote:

I am fine with breaking the API. Whoever uses this API will need to add a tiny bit of code to work with the new compiler (and that code will be compatible with the old version).
It's better to break the API this way than to introduce the flags or weak aliases, etc

Please update the documentation in this patch. (mention that these functions are emitted by clang >= 2017-08-XX)

Make sure to run 'ninja check-fuzzer'. Most likely it will break due to the API change, fix it in libFuzzer (in a simple way, by calling __sanitizer_cov_trace_cmpN)

Find all uses of __sanitizer_cov_trace_cmp1 in projects/compiler-rt/lib/sanitizer_common and update those files.

To save one hop, who do you want this to be split in patches?

[kcc]

To save one hop, who do you want this to be split in patches?

Up to you. But please make sure to not break the bots.

[glider]

tools/clang/docs/SanitizerCoverage.rst

207

Change to "Called before a comparison instruction with non-constant arguments."

238

No need to write the dates here, this isn't a changelog.

250

These are already listed at line 209. I suggest you move the above block there.

254

Extra newline, please remove.

[kcc]

LGTM with nits, thanks!

tools/clang/docs/SanitizerCoverage.rst

242

Move this inside the first block, just under __sanitizer_cov_trace_cmp8

Add a comment:
Arg1 and Arg2 are arguments of the comparison, Arg1 is a compile-time constant.
These callbacks are emitted by -fsanitize-coverage=trace-cmp since 2011-08-XX

249

this comment is redundant.

[glider]

Landed r310600.
Good job!

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

 
 static const char *const SanCovTracePCIndirName =
     "__sanitizer_cov_trace_pc_indir";
 static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc";
 static const char *const SanCovTraceCmp1 = "__sanitizer_cov_trace_cmp1";
 static const char *const SanCovTraceCmp2 = "__sanitizer_cov_trace_cmp2";
 static const char *const SanCovTraceCmp4 = "__sanitizer_cov_trace_cmp4";
 static const char *const SanCovTraceCmp8 = "__sanitizer_cov_trace_cmp8";
+static const char *const SanCovTraceConstCmp1 = 
+    "__sanitizer_cov_trace_const_cmp1";
+static const char *const SanCovTraceConstCmp2 = 
+    "__sanitizer_cov_trace_const_cmp2";
+static const char *const SanCovTraceConstCmp4 = 
+    "__sanitizer_cov_trace_const_cmp4";
+static const char *const SanCovTraceConstCmp8 = 
+    "__sanitizer_cov_trace_const_cmp8";
 static const char *const SanCovTraceDiv4 = "__sanitizer_cov_trace_div4";
 static const char *const SanCovTraceDiv8 = "__sanitizer_cov_trace_div8";
 static const char *const SanCovTraceGep = "__sanitizer_cov_trace_gep";
 static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch";
 static const char *const SanCovModuleCtorName = "sancov.module_ctor";
 static const uint64_t SanCtorAndDtorPriority = 2;
 
 static const char *const SanCovTracePCGuardName =
private:
   }
 
   std::string getSectionName(const std::string &Section) const;
   std::string getSectionStart(const std::string &Section) const;
   std::string getSectionEnd(const std::string &Section) const;
   Function *SanCovTracePCIndir;
   Function *SanCovTracePC, *SanCovTracePCGuard;
   Function *SanCovTraceCmpFunction[4];
+  Function *SanCovTraceConstCmpFunction[4];
   Function *SanCovTraceDivFunction[2];
   Function *SanCovTraceGepFunction;
   Function *SanCovTraceSwitchFunction;
   InlineAsm *EmptyAsm;
   Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy,
-      *Int8Ty, *Int8PtrTy;
+      *Int16Ty, *Int8Ty, *Int8PtrTy;
   Module *CurModule;
   Triple TargetTriple;
   LLVMContext *C;
   const DataLayout *DL;
 
   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
   GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
   GlobalVariable *FunctionPCsArray;  // for pc-table.
bool SanitizerCoverageModule::runOnModule(Module &M) {
   IntptrPtrTy = PointerType::getUnqual(IntptrTy);
   Type *VoidTy = Type::getVoidTy(*C);
   IRBuilder<> IRB(*C);
   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
   Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
   Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
   Int64Ty = IRB.getInt64Ty();
   Int32Ty = IRB.getInt32Ty();
+  Int16Ty = IRB.getInt16Ty();
   Int8Ty = IRB.getInt8Ty();
 
   SanCovTracePCIndir = checkSanitizerInterfaceFunction(
       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy));
   SanCovTraceCmpFunction[0] =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           SanCovTraceCmp1, VoidTy, IRB.getInt8Ty(), IRB.getInt8Ty()));
   SanCovTraceCmpFunction[1] = checkSanitizerInterfaceFunction(
       M.getOrInsertFunction(SanCovTraceCmp2, VoidTy, IRB.getInt16Ty(),
                             IRB.getInt16Ty()));
   SanCovTraceCmpFunction[2] = checkSanitizerInterfaceFunction(
       M.getOrInsertFunction(SanCovTraceCmp4, VoidTy, IRB.getInt32Ty(),
                             IRB.getInt32Ty()));
   SanCovTraceCmpFunction[3] =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty));
 
+  SanCovTraceConstCmpFunction[0] =
+      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+          SanCovTraceConstCmp1, VoidTy, Int8Ty, Int8Ty));
+  SanCovTraceConstCmpFunction[1] =
+      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+          SanCovTraceConstCmp2, VoidTy, Int16Ty, Int16Ty));
+  SanCovTraceConstCmpFunction[2] =
+      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+          SanCovTraceConstCmp4, VoidTy, Int32Ty, Int32Ty));
+  SanCovTraceConstCmpFunction[3] =
+      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+          SanCovTraceConstCmp8, VoidTy, Int64Ty, Int64Ty));
+
   SanCovTraceDivFunction[0] =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           SanCovTraceDiv4, VoidTy, IRB.getInt32Ty()));
   SanCovTraceDivFunction[1] =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           SanCovTraceDiv8, VoidTy, Int64Ty));
   SanCovTraceGepFunction =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           SanCovTraceGep, VoidTy, IntptrTy));
   SanCovTraceSwitchFunction =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy));
   // Make sure smaller parameters are zero-extended to i64 as required by the
   // x86_64 ABI.
   if (TargetTriple.getArch() == Triple::x86_64) {
     for (int i = 0; i < 3; i++) {
       SanCovTraceCmpFunction[i]->addParamAttr(0, Attribute::ZExt);
       SanCovTraceCmpFunction[i]->addParamAttr(1, Attribute::ZExt);
+      SanCovTraceConstCmpFunction[i]->addParamAttr(0, Attribute::ZExt);
+      SanCovTraceConstCmpFunction[i]->addParamAttr(1, Attribute::ZExt);
     }
     SanCovTraceDivFunction[0]->addParamAttr(0, Attribute::ZExt);
   }
 
 
   // We insert an empty inline asm after cov callbacks to avoid callback merge.
   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
                             StringRef(""), StringRef(""),
if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
         continue;
       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
       int CallbackIdx = TypeSize == 8 ? 0 :
                         TypeSize == 16 ? 1 :
                         TypeSize == 32 ? 2 :
                         TypeSize == 64 ? 3 : -1;
       if (CallbackIdx < 0) continue;
       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
+      auto CallbackFunc = SanCovTraceCmpFunction[CallbackIdx];
+      bool FirstIsConst = isa<ConstantInt>(A0);
+      bool SecondIsConst = isa<ConstantInt>(A1);
+      // If both are const, then we don't need such a comparison.
+      if (FirstIsConst && SecondIsConst) continue;
+      // If only one is const, then make it the first callback argument.
+      if (FirstIsConst || SecondIsConst) {
+        CallbackFunc = SanCovTraceConstCmpFunction[CallbackIdx];
+        if (SecondIsConst) 
+          std::swap(A0, A1);
+      }
+
       auto Ty = Type::getIntNTy(*C, TypeSize);
-      IRB.CreateCall(
-          SanCovTraceCmpFunction[CallbackIdx],
-          {IRB.CreateIntCast(A0, Ty, true), IRB.CreateIntCast(A1, Ty, true)});
+      IRB.CreateCall(CallbackFunc, {IRB.CreateIntCast(A0, Ty, true), 
+              IRB.CreateIntCast(A1, Ty, true)});
     }
   }
 }
 
 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
                                                     size_t Idx) {
   BasicBlock::iterator IP = BB.getFirstInsertionPt();
   bool IsEntryBB = &BB == &F.getEntryBlock();

test/Instrumentation/SanitizerCoverage/const-cmp-tracing.ll

+; Test -sanitizer-coverage-trace-compares=1
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -sanitizer-coverage-trace-compares=1  -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+define i32 @foo(i32 %a, i32 %b) #0 {
+entry:
+
+; compare (non-const, non-const)
+  %cmp = icmp slt i32 %a, %b
+; CHECK: call void @__sanitizer_cov_trace_cmp4
+; CHECK-NEXT: icmp slt i32 %a, %b
+
+; compare (const, non-const)
+  icmp slt i32 %a, 1
+; CHECK: call void @__sanitizer_cov_trace_const_cmp4(i32 1, i32 %a)
+; CHECK-NEXT: icmp slt i32 %a, 1
+
+; compare (non-const, const)
+  icmp slt i32 1, %a
+; CHECK: call void @__sanitizer_cov_trace_const_cmp4(i32 1, i32 %a)
+; CHECK-NEXT: icmp slt i32 1, %a
+
+; compare (const, const) - should not be instrumented
+  icmp slt i32 1, 0
+; CHECK-NOT: call void @__sanitizer_cov_trace
+; CHECK icmp slt i32 1, 0
+
+; compare variables of byte size
+  %x = trunc i32 %a to i8
+
+  icmp slt i8 %x, 1
+; CHECK: call void @__sanitizer_cov_trace_const_cmp1(i8 1, i8 %x)
+; CHECK-NEXT: icmp slt i8 %x, 1
+
+  icmp slt i8 1, %x
+; CHECK: call void @__sanitizer_cov_trace_const_cmp1(i8 1, i8 %x)
+; CHECK-NEXT: icmp slt i8 1, %x
+
+; compare variables of word size
+  %y = trunc i32 %a to i16
+
+  icmp slt i16 %y, 1
+; CHECK: call void @__sanitizer_cov_trace_const_cmp2(i16 1, i16 %y)
+; CHECK-NEXT: icmp slt i16 %y, 1
+
+  icmp slt i16 1, %y
+; CHECK: call void @__sanitizer_cov_trace_const_cmp2(i16 1, i16 %y)
+; CHECK-NEXT: icmp slt i16 1, %y
+
+; compare variables of qword size
+  %z = zext i32 %a to i64
+
+  icmp slt i64 %z, 1
+; CHECK: call void @__sanitizer_cov_trace_const_cmp8(i64 1, i64 %z)
+; CHECK-NEXT: icmp slt i64 %z, 1
+
+  icmp slt i64 1, %z
+; CHECK: call void @__sanitizer_cov_trace_const_cmp8(i64 1, i64 %z)
+; CHECK-NEXT: icmp slt i64 1, %z
+
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}

tools/clang/docs/SanitizerCoverage.rst

 Similarly, with ``-fsanitize-coverage=trace-div`` the compiler will instrument
 integer division instructions (to capture the right argument of division)
 and with  ``-fsanitize-coverage=trace-gep`` --
 the `LLVM GEP instructions <http://llvm.org/docs/GetElementPtr.html>`_
 (to capture array indices).
 
 .. code-block:: c++
 
   // Called before a comparison instruction.
   // Arg1 and Arg2 are arguments of the comparison.
   void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2);
   void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2);
   void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2);
   void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2);
 
+  // Called before a comparison instruction if exactly one of the arguments is constant.
+  // Arg1 and Arg2 are arguments of the comparison, Arg1 is a compile-time constant. 
+  // These callbacks are emitted by -fsanitize-coverage=trace-cmp since 2017-08-11
+  void __sanitizer_cov_trace_const_cmp1(uint8_t Arg1, uint8_t Arg2);
+  void __sanitizer_cov_trace_const_cmp2(uint16_t Arg1, uint16_t Arg2);
+  void __sanitizer_cov_trace_const_cmp4(uint32_t Arg1, uint32_t Arg2);
+  void __sanitizer_cov_trace_const_cmp8(uint64_t Arg1, uint64_t Arg2);
+
   // Called before a switch statement.
   // Val is the switch operand.
   // Cases[0] is the number of case constants.
   // Cases[1] is the size of Val in bits.
   // Cases[2:] are the case constants.
   void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases);
 
   // Called before a division statement.
   // Val is the second argument of division.
   void __sanitizer_cov_trace_div4(uint32_t Val);
   void __sanitizer_cov_trace_div8(uint64_t Val);
 
   // Called before a GetElemementPtr (GEP) instruction
   // for every non-constant array index.
   void __sanitizer_cov_trace_gep(uintptr_t Idx);
 
-
 This interface is a subject to change.
 
 Default implementation
 ======================
 
 The sanitizer run-time (AddressSanitizer, MemorySanitizer, etc) provide a
 default implementations of some of the coverage callbacks.
 You may use this implementation to dump the coverage on disk at the process
 exit.
 
 Example:
 
 .. code-block:: console
 
     % cat -n cov.cc
          1  #include <stdio.h>
          2  __attribute__((noinline))
          3  void foo() { printf("foo\n"); }
          4
          5  int main(int argc, char **argv) {
          6    if (argc == 2)
          7      foo();
          8    printf("main\n");
          9  }
     % clang++ -g cov.cc -fsanitize=address -fsanitize-coverage=trace-pc-guard