[CodeGen] Annotate signed shift lefts with NUW

[majnemer]

Summary

For signed shifts, Op1 << Op2 in C and C++ is UB if the result cannot be
represented in the equivalent unsigned type. While a stronger statement
can be made for C, let's start small and say that a signed shift left
cannot shift out any one bits.

[chandlerc]

This doesn't seem correct for a negative LHS where we only shift out 1s -- I think that should be valid.

Essentially, we seem to have a strange circumstance here where NUW as specified is not a subset of the restrictions of NSW.

[majnemer]

In D8899#153339, @chandlerc wrote:

This doesn't seem correct for a negative LHS where we only shift out 1s -- I think that should be valid.

Essentially, we seem to have a strange circumstance here where NUW as specified is not a subset of the restrictions of NSW.

Negative LHS is forbidden in both C11 and C++14.

C11 6.5.7p4:
If E1 has a signed type and nonnegative value, and E1 × 2**E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

C++14 [expr.shift]p2:
Otherwise, if E1 has a signed type and non-negative value, and E1 × 2**E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

[rsmith]

LGTM

test/CodeGen/compound-type.c

1–3

Can I persuade you to FileCheck-ize this test while you're here?

[chandlerc]

Before we go here, I think we should seriously ask whether we want to undo that restriction on shift left.

I can see arguments both for and against it.

Does GCC already do this optimization?

[sanjoy]

This revision hasn't changed for a while, removing myself from reviewers so that it does not show up in my 'waiting on others' list.

Feel free to re-add my as a reviewer later if needed.

include/clang/Driver/Options.td

def fno_spell_checking : Flag<["-"], "fno-spell-checking">, Group<f_Group>,
   Flags<[CC1Option]>, HelpText<"Disable spell-checking">;
 def fno_stack_protector : Flag<["-"], "fno-stack-protector">, Group<f_Group>,
   HelpText<"Disable the use of stack protectors">;
 def fno_strict_aliasing : Flag<["-"], "fno-strict-aliasing">, Group<f_Group>,
   Flags<[DriverOption, CoreOption]>;
 def fstruct_path_tbaa : Flag<["-"], "fstruct-path-tbaa">, Group<f_Group>;
 def fno_struct_path_tbaa : Flag<["-"], "fno-struct-path-tbaa">, Group<f_Group>;
 def fno_strict_enums : Flag<["-"], "fno-strict-enums">, Group<f_Group>;
+def fno_strict_shifts : Flag<["-"], "fno-strict-shifts">, Group<f_Group>,
+  Flags<[CC1Option]>;
 def fno_strict_overflow : Flag<["-"], "fno-strict-overflow">, Group<f_Group>;
 def fno_threadsafe_statics : Flag<["-"], "fno-threadsafe-statics">, Group<f_Group>,
   Flags<[CC1Option]>, HelpText<"Do not emit code to make initialization of local statics thread safe">;
 def fno_use_cxa_atexit : Flag<["-"], "fno-use-cxa-atexit">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Don't use __cxa_atexit for calling destructors">;
 def fno_use_init_array : Flag<["-"], "fno-use-init-array">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Don't use .init_array instead of .ctors">;
 def fno_unit_at_a_time : Flag<["-"], "fno-unit-at-a-time">, Group<f_Group>;
def fno_standalone_debug : Flag<["-"], "fno-standalone-debug">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Limit debug information produced to reduce size of debug binary">;
 def flimit_debug_info : Flag<["-"], "flimit-debug-info">, Alias<fno_standalone_debug>;
 def fno_limit_debug_info : Flag<["-"], "fno-limit-debug-info">, Alias<fstandalone_debug>;
 def fstrict_aliasing : Flag<["-"], "fstrict-aliasing">, Group<f_Group>,
   Flags<[DriverOption, CoreOption]>;
 def fstrict_enums : Flag<["-"], "fstrict-enums">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Enable optimizations based on the strict definition of an enum's "
            "value range">;
+def fstrict_shifts : Flag<["-"], "fstrict-shifts">, Group<f_Group>,
+  HelpText<"Enable optimizations based on the strict definition of the operands"
+           " that may be correctly passed to a shift operation">;
 def fstrict_overflow : Flag<["-"], "fstrict-overflow">, Group<f_Group>;
 def fsyntax_only : Flag<["-"], "fsyntax-only">, Flags<[DriverOption,CC1Option]>, Group<Action_Group>;
 def ftabstop_EQ : Joined<["-"], "ftabstop=">, Group<f_Group>;
 def ftemplate_depth_EQ : Joined<["-"], "ftemplate-depth=">, Group<f_Group>;
 def ftemplate_depth_ : Joined<["-"], "ftemplate-depth-">, Group<f_Group>;
 def ftemplate_backtrace_limit_EQ : Joined<["-"], "ftemplate-backtrace-limit=">,
                                    Group<f_Group>;
 def foperator_arrow_depth_EQ : Joined<["-"], "foperator-arrow-depth=">,

include/clang/Frontend/CodeGenOptions.def

 CODEGENOPT(SanitizeMemoryTrackOrigins, 2, 0) ///< Enable tracking origins in
                                              ///< MemorySanitizer
 CODEGENOPT(SanitizeCoverage, 3, 0) ///< Enable sanitizer coverage instrumentation.
 CODEGENOPT(SanitizeUndefinedTrapOnError, 1, 0) ///< Set on
                                                /// -fsanitize-undefined-trap-on-error
 CODEGENOPT(SimplifyLibCalls  , 1, 1) ///< Set when -fbuiltin is enabled.
 CODEGENOPT(SoftFloat         , 1, 0) ///< -soft-float.
 CODEGENOPT(StrictEnums       , 1, 0) ///< Optimize based on strict enum definition.
+CODEGENOPT(StrictShifts      , 1, 0) ///< Optimize based on strict shift definition.
 CODEGENOPT(TimePasses        , 1, 0) ///< Set when -ftime-report is enabled.
 CODEGENOPT(UnitAtATime       , 1, 1) ///< Unused. For mirroring GCC optimization
                                      ///< selection.
 CODEGENOPT(UnrollLoops       , 1, 0) ///< Control whether loops are unrolled.
 CODEGENOPT(RerollLoops       , 1, 0) ///< Control whether loops are rerolled.
 CODEGENOPT(UnsafeFPMath      , 1, 0) ///< Allow unsafe floating point optzns.
 CODEGENOPT(UnwindTables      , 1, 0) ///< Emit unwind tables.
 CODEGENOPT(VectorizeBB       , 1, 0) ///< Run basic block vectorizer.

lib/CodeGen/CGExprScalar.cpp

Value *ScalarExprEmitter::EmitShl(const BinOpInfo &Ops) {
   // RHS to the same size as the LHS.
   Value *RHS = Ops.RHS;
   if (Ops.LHS->getType() != RHS->getType())
     RHS = Builder.CreateIntCast(RHS, Ops.LHS->getType(), false, "sh_prom");
 
   bool SanitizeBase = CGF.SanOpts.has(SanitizerKind::ShiftBase) &&
                       Ops.Ty->hasSignedIntegerRepresentation();
   bool SanitizeExponent = CGF.SanOpts.has(SanitizerKind::ShiftExponent);
+  bool HasNUW = false;
   // OpenCL 6.3j: shift values are effectively % word size of LHS.
   if (CGF.getLangOpts().OpenCL)
     RHS =
         Builder.CreateAnd(RHS, GetWidthMinusOneValue(Ops.LHS, RHS), "shl.mask");
   else if ((SanitizeBase || SanitizeExponent) &&
            isa<llvm::IntegerType>(Ops.LHS->getType())) {
     CodeGenFunction::SanitizerScope SanScope(&CGF);
     SmallVector<std::pair<Value *, SanitizerKind>, 2> Checks;
if (SanitizeBase) {
       llvm::PHINode *BaseCheck = Builder.CreatePHI(ValidBase->getType(), 2);
       BaseCheck->addIncoming(Builder.getTrue(), Orig);
       BaseCheck->addIncoming(ValidBase, CheckShiftBase);
       Checks.push_back(std::make_pair(BaseCheck, SanitizerKind::ShiftBase));
     }
 
     assert(!Checks.empty());
     EmitBinOpCheck(Checks, Ops);
+  } else {
+    HasNUW = Ops.Ty->isSignedIntegerOrEnumerationType() &&
+             CGF.CGM.getCodeGenOpts().StrictShifts;
   }
-
-  return Builder.CreateShl(Ops.LHS, RHS, "shl");
+  return Builder.CreateShl(Ops.LHS, RHS, "shl", HasNUW);
 }
 
 Value *ScalarExprEmitter::EmitShr(const BinOpInfo &Ops) {
   // LLVM requires the LHS and RHS to be the same type: promote or truncate the
   // RHS to the same size as the LHS.
   Value *RHS = Ops.RHS;
   if (Ops.LHS->getType() != RHS->getType())
     RHS = Builder.CreateIntCast(RHS, Ops.LHS->getType(), false, "sh_prom");

lib/Driver/Tools.cpp

if (!Args.hasFlag(options::OPT_fstrict_aliasing, StrictAliasingAliasOption,
                     options::OPT_fno_strict_aliasing, TBAAOnByDefault))
     CmdArgs.push_back("-relaxed-aliasing");
   if (!Args.hasFlag(options::OPT_fstruct_path_tbaa,
                     options::OPT_fno_struct_path_tbaa))
     CmdArgs.push_back("-no-struct-path-tbaa");
   if (Args.hasFlag(options::OPT_fstrict_enums, options::OPT_fno_strict_enums,
                    false))
     CmdArgs.push_back("-fstrict-enums");
+  if (!Args.hasFlag(options::OPT_fstrict_shifts, options::OPT_fno_strict_shifts))
+    CmdArgs.push_back("-fno-strict-shifts");
   if (!Args.hasFlag(options::OPT_foptimize_sibling_calls,
                     options::OPT_fno_optimize_sibling_calls))
     CmdArgs.push_back("-mdisable-tail-calls");
 
   // Handle segmented stacks.
   if (Args.hasArg(options::OPT_fsplit_stack))
     CmdArgs.push_back("-split-stacks");
 

lib/Frontend/CompilerInvocation.cpp

static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args, InputKind IK,
   Opts.FatalWarnings = Args.hasArg(OPT_massembler_fatal_warnings);
   Opts.EnableSegmentedStacks = Args.hasArg(OPT_split_stacks);
   Opts.RelaxAll = Args.hasArg(OPT_mrelax_all);
   Opts.OmitLeafFramePointer = Args.hasArg(OPT_momit_leaf_frame_pointer);
   Opts.SaveTempLabels = Args.hasArg(OPT_msave_temp_labels);
   Opts.NoDwarfDirectoryAsm = Args.hasArg(OPT_fno_dwarf_directory_asm);
   Opts.SoftFloat = Args.hasArg(OPT_msoft_float);
   Opts.StrictEnums = Args.hasArg(OPT_fstrict_enums);
+  Opts.StrictShifts = !Args.hasArg(OPT_fno_strict_shifts);
   Opts.UnsafeFPMath = Args.hasArg(OPT_menable_unsafe_fp_math) ||
                       Args.hasArg(OPT_cl_unsafe_math_optimizations) ||
                       Args.hasArg(OPT_cl_fast_relaxed_math);
   Opts.UnwindTables = Args.hasArg(OPT_munwind_tables);
   Opts.RelocationModel = Args.getLastArgValue(OPT_mrelocation_model, "pic");
   Opts.ThreadModel = Args.getLastArgValue(OPT_mthread_model, "posix");
   if (Opts.ThreadModel != "posix" && Opts.ThreadModel != "single")
     Diags.Report(diag::err_drv_invalid_value)

test/CodeGen/compound-type.c

 // RUN: %clang_cc1 < %s -emit-llvm -triple i686-pc-linux-gnu > %t
 // RUN: grep "div i32" %t
-// RUN: grep "shl i32" %t
+// RUN: grep "shl nuw i32" %t
 
 unsigned char a,b;
 void c(void) {a <<= b;}
 void d(void) {a /= b;}

test/OpenMP/atomic_update_codegen.cpp

 // CHECK: atomicrmw sub i32* @{{.+}}, i32 [[EXPR]] monotonic
 #pragma omp atomic
   uix -= uiv;
 // CHECK: [[EXPR:%.+]] = load i32, i32* @{{.+}},
 // CHECK: [[X:%.+]] = load atomic i32, i32* [[X_ADDR:@.+]] monotonic
 // CHECK: br label %[[CONT:.+]]
 // CHECK: [[CONT]]
 // CHECK: [[EXPECTED:%.+]] = phi i32 [ [[X]], %{{.+}} ], [ [[OLD_X:%.+]], %[[CONT]] ]
-// CHECK: [[DESIRED:%.+]] = shl i32 [[EXPECTED]], [[EXPR]]
+// CHECK: [[DESIRED:%.+]] = shl nuw i32 [[EXPECTED]], [[EXPR]]
 // CHECK: [[RES:%.+]] = cmpxchg i32* [[X_ADDR]], i32 [[EXPECTED]], i32 [[DESIRED]] monotonic monotonic
 // CHECK: [[OLD_X]] = extractvalue { i32, i1 } [[RES]], 0
 // CHECK: [[SUCCESS_FAIL:%.+]] = extractvalue { i32, i1 } [[RES]], 1
 // CHECK: br i1 [[SUCCESS_FAIL]], label %[[EXIT:.+]], label %[[CONT]]
 // CHECK: [[EXIT]]
 #pragma omp atomic update
   ix <<= iv;
 // CHECK: [[EXPR:%.+]] = load i32, i32* @{{.+}},
#pragma omp atomic update, seq_cst
   cx = cx >> ucv;
 // CHECK: [[SV:%.+]]  = load i16, i16* @{{.+}},
 // CHECK: [[EXPR:%.+]] = sext i16 [[SV]] to i32
 // CHECK: [[X:%.+]] = load atomic i64, i64* [[ULX_ADDR:@.+]] monotonic
 // CHECK: br label %[[CONT:.+]]
 // CHECK: [[CONT]]
 // CHECK: [[EXPECTED:%.+]] = phi i64 [ [[X]], %{{.+}} ], [ [[OLD_X:%.+]], %[[CONT]] ]
 // CHECK: [[X_RVAL:%.+]] = trunc i64 [[EXPECTED]] to i32
-// CHECK: [[SHL:%.+]] = shl i32 [[EXPR]], [[X_RVAL]]
+// CHECK: [[SHL:%.+]] = shl nuw i32 [[EXPR]], [[X_RVAL]]
 // CHECK: [[DESIRED:%.+]] = sext i32 [[SHL]] to i64
 // CHECK: [[RES:%.+]] = cmpxchg i64* [[ULX_ADDR]], i64 [[EXPECTED]], i64 [[DESIRED]] monotonic monotonic
 // CHECK: [[OLD_X:%.+]] = extractvalue { i64, i1 } [[RES]], 0
 // CHECK: [[SUCCESS_FAIL:%.+]] = extractvalue { i64, i1 } [[RES]], 1
 // CHECK: br i1 [[SUCCESS_FAIL]], label %[[EXIT:.+]], label %[[CONT]]
 // CHECK: [[EXIT]]
 #pragma omp atomic update
   ulx = sv << ulx;