[SimplifyCFG] Create attribute for fuzzing-specific optimizations.

[morehouse]

Summary

When building with libFuzzer, converting control flow to selects or obscuring the original operands of CMPs reduces the effectiveness of libFuzzer's heuristics.

This patch provides an attribute to disable or modify certain optimizations for optimal fuzzing signal.

Provides a less aggressive alternative to https://reviews.llvm.org/D44057.

[morehouse]

• Update test to new attribute name

[hfinkel]

Another question: Do we actually want to disable select formation, or, do we want to expand all selects into control flow late in the pipeline (i.e., during instruction selection)? The issue here, as I understand it, is that fuzzing depends on control flow paths to differentiate executions. As a result, we really just don't want to have any selects (we don't want ones that the frontend might generate either).

[morehouse]

In D44232#1031563, @hfinkel wrote:

Another question: Do we actually want to disable select formation, or, do we want to expand all selects into control flow late in the pipeline (i.e., during instruction selection)? The issue here, as I understand it, is that fuzzing depends on control flow paths to differentiate executions. As a result, we really just don't want to have any selects (we don't want ones that the frontend might generate either).

I don't think we could do it during instruction selection, since SanitizerCoverage instrumentation is inserted before that. But if we could expand selects right before the SanitizerCoverage instrumentation happens (maybe even during the SanitizerCoverage pass?), that would provide even better coverage signal for fuzzing. Of course, that would be significantly more work.

Another concern comes from https://github.com/google/sanitizers/issues/893#issuecomment-350036791, where simplifyCFG takes two conditions and combines them into a single CMP, resulting in libFuzzer's TraceCMP heuristic becoming useless. So we would probably still want to disable part of simplifyCFG to avoid that.

[hfinkel]

In D44232#1031642, @morehouse wrote:

In D44232#1031563, @hfinkel wrote:

Another question: Do we actually want to disable select formation, or, do we want to expand all selects into control flow late in the pipeline (i.e., during instruction selection)? The issue here, as I understand it, is that fuzzing depends on control flow paths to differentiate executions. As a result, we really just don't want to have any selects (we don't want ones that the frontend might generate either).

I don't think we could do it during instruction selection, since SanitizerCoverage instrumentation is inserted before that. But if we could expand selects right before the SanitizerCoverage instrumentation happens (maybe even during the SanitizerCoverage pass?), that would provide even better coverage signal for fuzzing. Of course, that would be significantly more work.

Shouldn't be too much work. Just turn the logic in CodeGenPrepare::optimizeSelectInst into a utility function, add an aggressive mode, and call it.

Another concern comes from https://github.com/google/sanitizers/issues/893#issuecomment-350036791, where simplifyCFG takes two conditions and combines them into a single CMP, resulting in libFuzzer's TraceCMP heuristic becoming useless. So we would probably still want to disable part of simplifyCFG to avoid that.

I took a quite look at the bug report, but I'm still not exactly sure what's going on. Can you explain? Is the problem that the coverage instrumentation looks at the arguments to a comparison, somehow, but doesn't look through boolean operations?

[morehouse]

In D44232#1031682, @hfinkel wrote:

Shouldn't be too much work. Just turn the logic in CodeGenPrepare::optimizeSelectInst into a utility function, add an aggressive mode, and call it.

Well that's easier than I thought. Thanks for the insight.

I took a quite look at the bug report, but I'm still not exactly sure what's going on. Can you explain? Is the problem that the coverage instrumentation looks at the arguments to a comparison, somehow, but doesn't look through boolean operations?

The coverage instrumentation passes both arguments of every comparison to a __sanitizer_cov_trace[_const]_cmp callback. The callbacks are implemented in libFuzzer. libFuzzer uses a simple (but effective) heuristic that searches the program input for either argument to the comparison and then mutates matches to be close (-1, ==, or +1) to the other argument.

In the bug report, if x > 16 && x < 32 had been translated into a comparison with 16 and a comparison with 32, and if x were found in the program input, libFuzzer would be able to quickly find x==17 or x==31 to take the true branch. But instead, x > 16 && x < 32 is translated to a single unsigned comparison between x - 17 and 15, thereby defeating our heuristic.

[vitalybuka]

LGTM

llvm/lib/AsmParser/LLParser.cpp

1127

no_cfg_select_formation -> nocfgselectformation ?

[morehouse]

Ping. Any objections to moving forward with this patch?

[hfinkel]

In D44232#1042218, @morehouse wrote:

Ping. Any objections to moving forward with this patch?

Yea, I think that we should name this something else. It's more than just disabling select formation (which, as we discussed, we'd probably just want to undo in CGP). The problem is optimizations that interfere with the libFuzzer input-value-matching heuristics -- that's really the thing that we need to disable earlier in the pipeline. Thoughts?

[morehouse]

In D44232#1045010, @hfinkel wrote:

Yea, I think that we should name this something else. It's more than just disabling select formation (which, as we discussed, we'd probably just want to undo in CGP). The problem is optimizations that interfere with the libFuzzer input-value-matching heuristics -- that's really the thing that we need to disable earlier in the pipeline. Thoughts?

no_cfg_select_formation -> no_cfg_cmp_simplification?

[hfinkel]

In D44232#1045092, @morehouse wrote:

In D44232#1045010, @hfinkel wrote:

Yea, I think that we should name this something else. It's more than just disabling select formation (which, as we discussed, we'd probably just want to undo in CGP). The problem is optimizations that interfere with the libFuzzer input-value-matching heuristics -- that's really the thing that we need to disable earlier in the pipeline. Thoughts?

no_cfg_select_formation -> no_cfg_cmp_simplification?

opt_for_fuzzing?

[morehouse]

• Rename attribute to OptForFuzzing.

[vlad.tsyrklevich]

I'd also add this attribute to docs/BitCodeFormat.rst and docs/LangRef.rst

[morehouse]

In D44232#1045996, @vlad.tsyrklevich wrote:

I'd also add this attribute to docs/BitCodeFormat.rst and docs/LangRef.rst

Thanks, added in https://reviews.llvm.org/rL328236.

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum AttributeKindCodes {
   ATTR_KIND_NO_RECURSE = 48,
   ATTR_KIND_INACCESSIBLEMEM_ONLY = 49,
   ATTR_KIND_INACCESSIBLEMEM_OR_ARGMEMONLY = 50,
   ATTR_KIND_ALLOC_SIZE = 51,
   ATTR_KIND_WRITEONLY = 52,
   ATTR_KIND_SPECULATABLE = 53,
   ATTR_KIND_STRICT_FP = 54,
   ATTR_KIND_SANITIZE_HWADDRESS = 55,
+  ATTR_KIND_NO_CFG_SELECT_FORMATION = 56,
 };
 
 enum ComdatSelectionKindCodes {
   COMDAT_SELECTION_KIND_ANY = 1,
   COMDAT_SELECTION_KIND_EXACT_MATCH = 2,
   COMDAT_SELECTION_KIND_LARGEST = 3,
   COMDAT_SELECTION_KIND_NO_DUPLICATES = 4,
   COMDAT_SELECTION_KIND_SAME_SIZE = 5,

llvm/include/llvm/IR/Attributes.td

 def NoAlias : EnumAttr<"noalias">;
 
 /// Callee isn't recognized as a builtin.
 def NoBuiltin : EnumAttr<"nobuiltin">;
 
 /// Function creates no aliases of pointer.
 def NoCapture : EnumAttr<"nocapture">;
 
+/// CFG simplification shouldn't convert control flow to selects.
+def NoCFGSelectFormation : EnumAttr<"no_cfg_select_formation">;
+
 /// Call cannot be duplicated.
 def NoDuplicate : EnumAttr<"noduplicate">;
 
 /// Disable implicit floating point insts.
 def NoImplicitFloat : EnumAttr<"noimplicitfloat">;
 
 /// inline=never.
 def NoInline : EnumAttr<"noinline">;

llvm/lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(inreg);
   KEYWORD(jumptable);
   KEYWORD(minsize);
   KEYWORD(naked);
   KEYWORD(nest);
   KEYWORD(noalias);
   KEYWORD(nobuiltin);
   KEYWORD(nocapture);
+  KEYWORD(no_cfg_select_formation);
   KEYWORD(noduplicate);
   KEYWORD(noimplicitfloat);
   KEYWORD(noinline);
   KEYWORD(norecurse);
   KEYWORD(nonlazybind);
   KEYWORD(nonnull);
   KEYWORD(noredzone);
   KEYWORD(noreturn);

llvm/lib/AsmParser/LLParser.cpp

case lltok::kw_inaccessiblememonly:
       B.addAttribute(Attribute::InaccessibleMemOnly); break;
     case lltok::kw_inaccessiblemem_or_argmemonly:
       B.addAttribute(Attribute::InaccessibleMemOrArgMemOnly); break;
     case lltok::kw_inlinehint: B.addAttribute(Attribute::InlineHint); break;
     case lltok::kw_jumptable: B.addAttribute(Attribute::JumpTable); break;
     case lltok::kw_minsize: B.addAttribute(Attribute::MinSize); break;
     case lltok::kw_naked: B.addAttribute(Attribute::Naked); break;
     case lltok::kw_nobuiltin: B.addAttribute(Attribute::NoBuiltin); break;
+    case lltok::kw_no_cfg_select_formation:
+      B.addAttribute(Attribute::NoCFGSelectFormation); break;
     case lltok::kw_noduplicate: B.addAttribute(Attribute::NoDuplicate); break;
     case lltok::kw_noimplicitfloat:
       B.addAttribute(Attribute::NoImplicitFloat); break;
     case lltok::kw_noinline: B.addAttribute(Attribute::NoInline); break;
     case lltok::kw_nonlazybind: B.addAttribute(Attribute::NonLazyBind); break;
     case lltok::kw_noredzone: B.addAttribute(Attribute::NoRedZone); break;
     case lltok::kw_noreturn: B.addAttribute(Attribute::NoReturn); break;
     case lltok::kw_norecurse: B.addAttribute(Attribute::NoRecurse); break;
while (true) {
     case lltok::kw_alwaysinline:
     case lltok::kw_argmemonly:
     case lltok::kw_builtin:
     case lltok::kw_inlinehint:
     case lltok::kw_jumptable:
     case lltok::kw_minsize:
     case lltok::kw_naked:
     case lltok::kw_nobuiltin:
+    case lltok::kw_no_cfg_select_formation:
     case lltok::kw_noduplicate:
     case lltok::kw_noimplicitfloat:
     case lltok::kw_noinline:
     case lltok::kw_nonlazybind:
     case lltok::kw_noredzone:
     case lltok::kw_noreturn:
     case lltok::kw_nounwind:
     case lltok::kw_optnone:
while (true) {
     case lltok::kw_argmemonly:
     case lltok::kw_builtin:
     case lltok::kw_cold:
     case lltok::kw_inlinehint:
     case lltok::kw_jumptable:
     case lltok::kw_minsize:
     case lltok::kw_naked:
     case lltok::kw_nobuiltin:
+    case lltok::kw_no_cfg_select_formation:
     case lltok::kw_noduplicate:
     case lltok::kw_noimplicitfloat:
     case lltok::kw_noinline:
     case lltok::kw_nonlazybind:
     case lltok::kw_noredzone:
     case lltok::kw_noreturn:
     case lltok::kw_nounwind:
     case lltok::kw_optnone:

llvm/lib/AsmParser/LLToken.h

enum Kind {
   kw_inreg,
   kw_jumptable,
   kw_minsize,
   kw_naked,
   kw_nest,
   kw_noalias,
   kw_nobuiltin,
   kw_nocapture,
+  kw_no_cfg_select_formation,
   kw_noduplicate,
   kw_noimplicitfloat,
   kw_noinline,
   kw_norecurse,
   kw_nonlazybind,
   kw_nonnull,
   kw_noredzone,
   kw_noreturn,

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

static uint64_t getRawAttributeMask(Attribute::AttrKind Val) {
   case Attribute::InaccessibleMemOnly:         return 1ULL << 49;
   case Attribute::InaccessibleMemOrArgMemOnly: return 1ULL << 50;
   case Attribute::SwiftSelf:       return 1ULL << 51;
   case Attribute::SwiftError:      return 1ULL << 52;
   case Attribute::WriteOnly:       return 1ULL << 53;
   case Attribute::Speculatable:    return 1ULL << 54;
   case Attribute::StrictFP:        return 1ULL << 55;
   case Attribute::SanitizeHWAddress: return 1ULL << 56;
+  case Attribute::NoCFGSelectFormation:   return 1ULL << 57;
   case Attribute::Dereferenceable:
     llvm_unreachable("dereferenceable attribute not supported in raw format");
     break;
   case Attribute::DereferenceableOrNull:
     llvm_unreachable("dereferenceable_or_null attribute not supported in raw "
                      "format");
     break;
   case Attribute::ArgMemOnly:
static Attribute::AttrKind getAttrFromCode(uint64_t Code) {
   case bitc::ATTR_KIND_NEST:
     return Attribute::Nest;
   case bitc::ATTR_KIND_NO_ALIAS:
     return Attribute::NoAlias;
   case bitc::ATTR_KIND_NO_BUILTIN:
     return Attribute::NoBuiltin;
   case bitc::ATTR_KIND_NO_CAPTURE:
     return Attribute::NoCapture;
+  case bitc::ATTR_KIND_NO_CFG_SELECT_FORMATION:
+    return Attribute::NoCFGSelectFormation;
   case bitc::ATTR_KIND_NO_DUPLICATE:
     return Attribute::NoDuplicate;
   case bitc::ATTR_KIND_NO_IMPLICIT_FLOAT:
     return Attribute::NoImplicitFloat;
   case bitc::ATTR_KIND_NO_INLINE:
     return Attribute::NoInline;
   case bitc::ATTR_KIND_NO_RECURSE:
     return Attribute::NoRecurse;

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) {
   case Attribute::Nest:
     return bitc::ATTR_KIND_NEST;
   case Attribute::NoAlias:
     return bitc::ATTR_KIND_NO_ALIAS;
   case Attribute::NoBuiltin:
     return bitc::ATTR_KIND_NO_BUILTIN;
   case Attribute::NoCapture:
     return bitc::ATTR_KIND_NO_CAPTURE;
+  case Attribute::NoCFGSelectFormation:
+    return bitc::ATTR_KIND_NO_CFG_SELECT_FORMATION;
   case Attribute::NoDuplicate:
     return bitc::ATTR_KIND_NO_DUPLICATE;
   case Attribute::NoImplicitFloat:
     return bitc::ATTR_KIND_NO_IMPLICIT_FLOAT;
   case Attribute::NoInline:
     return bitc::ATTR_KIND_NO_INLINE;
   case Attribute::NoRecurse:
     return bitc::ATTR_KIND_NO_RECURSE;

llvm/lib/IR/Attributes.cpp

std::string Attribute::getAsString(bool InAttrGrp) const {
   if (hasAttribute(Attribute::Nest))
     return "nest";
   if (hasAttribute(Attribute::NoAlias))
     return "noalias";
   if (hasAttribute(Attribute::NoBuiltin))
     return "nobuiltin";
   if (hasAttribute(Attribute::NoCapture))
     return "nocapture";
+  if (hasAttribute(Attribute::NoCFGSelectFormation))
+    return "no_cfg_select_formation";
   if (hasAttribute(Attribute::NoDuplicate))
     return "noduplicate";
   if (hasAttribute(Attribute::NoImplicitFloat))
     return "noimplicitfloat";
   if (hasAttribute(Attribute::NoInline))
     return "noinline";
   if (hasAttribute(Attribute::NonLazyBind))
     return "nonlazybind";

llvm/lib/IR/Verifier.cpp

static bool isFuncOnlyAttr(Attribute::AttrKind Kind) {
   case Attribute::NoInline:
   case Attribute::AlwaysInline:
   case Attribute::OptimizeForSize:
   case Attribute::StackProtect:
   case Attribute::StackProtectReq:
   case Attribute::StackProtectStrong:
   case Attribute::SafeStack:
   case Attribute::NoRedZone:
+  case Attribute::NoCFGSelectFormation:
   case Attribute::NoImplicitFloat:
   case Attribute::Naked:
   case Attribute::InlineHint:
   case Attribute::StackAlignment:
   case Attribute::UWTable:
   case Attribute::NonLazyBind:
   case Attribute::ReturnsTwice:
   case Attribute::SanitizeAddress:

llvm/lib/Transforms/IPO/ForceFunctionAttrs.cpp

return StringSwitch<Attribute::AttrKind>(Kind)
       .Case("builtin", Attribute::Builtin)
       .Case("cold", Attribute::Cold)
       .Case("convergent", Attribute::Convergent)
       .Case("inlinehint", Attribute::InlineHint)
       .Case("jumptable", Attribute::JumpTable)
       .Case("minsize", Attribute::MinSize)
       .Case("naked", Attribute::Naked)
       .Case("nobuiltin", Attribute::NoBuiltin)
+      .Case("no_cfg_select_formation", Attribute::NoCFGSelectFormation)
       .Case("noduplicate", Attribute::NoDuplicate)
       .Case("noimplicitfloat", Attribute::NoImplicitFloat)
       .Case("noinline", Attribute::NoInline)
       .Case("nonlazybind", Attribute::NonLazyBind)
       .Case("noredzone", Attribute::NoRedZone)
       .Case("noreturn", Attribute::NoReturn)
       .Case("norecurse", Attribute::NoRecurse)
       .Case("nounwind", Attribute::NoUnwind)

llvm/lib/Transforms/Utils/CodeExtractor.cpp

if (Attr.isStringAttribute()) {
       case Attribute::EndAttrKinds:
         continue;
       // Those attributes should be safe to propagate to the extracted function.
       case Attribute::AlwaysInline:
       case Attribute::Cold:
       case Attribute::NoRecurse:
       case Attribute::InlineHint:
       case Attribute::MinSize:
+      case Attribute::NoCFGSelectFormation:
       case Attribute::NoDuplicate:
       case Attribute::NoImplicitFloat:
       case Attribute::NoInline:
       case Attribute::NonLazyBind:
       case Attribute::NoRedZone:
       case Attribute::NoUnwind:
       case Attribute::OptimizeNone:
       case Attribute::OptimizeForSize:

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
                                 const DataLayout &DL) {
   // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
   // statement", which has a very simple dominance structure.  Basically, we
   // are trying to find the condition that is being branched on, which
   // subsequently causes this merge to happen.  We really want control
   // dependence information for this check, but simplifycfg can't keep it up
   // to date, and this catches most of the cases we care about anyway.
   BasicBlock *BB = PN->getParent();
+  const Function *Fn = BB->getParent();
+  if (Fn && Fn->hasFnAttribute(Attribute::NoCFGSelectFormation))
+    return false;
+
   BasicBlock *IfTrue, *IfFalse;
   Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
   if (!IfCond ||
       // Don't bother if the branch will be constant folded trivially.
       isa<ConstantInt>(IfCond))
     return false;
 
   // Okay, we found that we can merge this two-entry phi node into a select.
if (!PPred || (PredPred && PredPred != PPred))
       return nullptr;
     PredPred = PPred;
   }
   return PredPred;
 }
 
 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   BasicBlock *BB = BI->getParent();
+  const Function *Fn = BB->getParent();
+  if (Fn && Fn->hasFnAttribute(Attribute::NoCFGSelectFormation))
+    return false;
 
   // Conditional branch
   if (isValueEqualityComparison(BI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // see if that predecessor totally determines the outcome of this
     // switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))

llvm/test/Transforms/SimplifyCFG/no-select-formation.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+define i32 @foo(i32 %x) no_cfg_select_formation {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4
+  %cmp = icmp sgt i32 %0, 16
+  br i1 %cmp, label %land.rhs, label %land.end
+
+land.rhs:
+  %1 = load i32, i32* %x.addr, align 4
+  %cmp1 = icmp slt i32 %1, 32
+  br label %land.end
+
+land.end:
+  %2 = phi i1 [ false, %entry ], [ %cmp1, %land.rhs ]
+  %conv = zext i1 %2 to i32
+  ret i32 %conv
+
+; CHECK-LABEL: define i32 @foo(i32 %x)
+; CHECK: br i1 %cmp, label %land.rhs, label %land.end
+; CHECK-LABEL: land.rhs:
+; CHECK: br label %land.end
+; CHECK-LABEL: land.end:
+; CHECK: phi {{.*}} %entry {{.*}} %land.rhs
+}
+
+define i32 @bar(i32 %x) {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4
+  %cmp = icmp sgt i32 %0, 16
+  br i1 %cmp, label %land.rhs, label %land.end
+
+land.rhs:
+  %1 = load i32, i32* %x.addr, align 4
+  %cmp1 = icmp slt i32 %1, 32
+  br label %land.end
+
+land.end:
+  %2 = phi i1 [ false, %entry ], [ %cmp1, %land.rhs ]
+  %conv = zext i1 %2 to i32
+  ret i32 %conv
+
+; CHECK-LABEL: define i32 @bar(i32 %x)
+; CHECK-NOT: br
+}