PNaCl: Extend ExpandMulWithOverflow pass to handle uadd.with.overflow too

It turned out that umul.with.overflow wasn't the only *.with.overflow
intrinsic usage introduced by Clang.

I knew that Clang's CGExprCXX.cpp generates umul.with.overflow for an
overflow check for C++'s "new Foo[]".  The same code for handling "new
Foo[]" also generates uadd.with.overflow in some cases.  This happens
if class Foo has a destructor or a delete[] operator that takes a size
argument.  In those cases, the C++ ABI adds a "cookie" to the
allocation which contains the array's size.

Rename the pass to "ExpandArithWithOverflow" and rename files
accordingly.

Also enable the pass.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3434
TEST=*.ll tests + trybots + GCC torture tests

Review URL: https://codereview.chromium.org/15688011

3 files changed, 49 insertions, 32 deletions

diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
index 14225d79b8..0e604dfc8a 100644
--- a/lib/Transforms/NaCl/CMakeLists.txt
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -2,11 +2,11 @@ set(LLVM_LINK_COMPONENTS ipo)
 
 add_llvm_library(LLVMNaClTransforms
   AddPNaClExternalDecls.cpp
+  ExpandArithWithOverflow.cpp
   ExpandByVal.cpp
   ExpandConstantExpr.cpp
   ExpandCtors.cpp
   ExpandGetElementPtr.cpp
-  ExpandMulWithOverflow.cpp
   ExpandTls.cpp
   ExpandTlsConstantExpr.cpp
   ExpandUtils.cpp
diff --git a/lib/Transforms/NaCl/ExpandMulWithOverflow.cpp b/lib/Transforms/NaCl/ExpandArithWithOverflow.cpp
index 171dda1f09..e120b24293 100644
--- a/lib/Transforms/NaCl/ExpandMulWithOverflow.cpp
+++ b/lib/Transforms/NaCl/ExpandArithWithOverflow.cpp
@@ -1,4 +1,4 @@
-//===- ExpandMulWithOverflow.cpp - Expand out usage of umul.with.overflow--===//
+//===- ExpandArithWithOverflow.cpp - Expand out uses of *.with.overflow----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -11,17 +11,19 @@
 // support because they return structs, and we want to omit struct
 // types from IR in PNaCl's stable ABI.
 //
-// However, llvm.umul.with.overflow.*() is used by Clang to implement
-// an overflow check for C++'s new[] operator.  This pass expands out
-// these uses so that PNaCl does not have to support
-// umul.with.overflow as part of PNaCl's stable ABI.
+// However, llvm.{umul,uadd}.with.overflow.*() are used by Clang to
+// implement an overflow check for C++'s new[] operator.  This pass
+// expands out these uses so that PNaCl does not have to support
+// *.with.overflow as part of PNaCl's stable ABI.
 //
-// This pass only handles multiplication by a constant, which is the
-// only case of umul.with.overflow that is currently generated by
+// This pass only handles adding/multiplying by a constant, which is
+// the only use of *.with.overflow that is currently generated by
 // Clang (unless '-ftrapv' is passed to Clang).
 //
 // X * Const overflows iff X > UINT_MAX / Const, where UINT_MAX is the
-// maximum value for the integer type being multiplied.
+// maximum value for the integer type being used.
+//
+// Similarly, X + Const overflows iff X > UINT_MAX - Const.
 //
 //===----------------------------------------------------------------------===//
 
@@ -38,20 +40,20 @@ using namespace llvm;
 namespace {
   // This is a ModulePass so that the pass can easily iterate over all
   // uses of the intrinsics.
-  class ExpandMulWithOverflow : public ModulePass {
+  class ExpandArithWithOverflow : public ModulePass {
   public:
     static char ID; // Pass identification, replacement for typeid
-    ExpandMulWithOverflow() : ModulePass(ID) {
-      initializeExpandMulWithOverflowPass(*PassRegistry::getPassRegistry());
+    ExpandArithWithOverflow() : ModulePass(ID) {
+      initializeExpandArithWithOverflowPass(*PassRegistry::getPassRegistry());
     }
 
     virtual bool runOnModule(Module &M);
   };
 }
 
-char ExpandMulWithOverflow::ID = 0;
-INITIALIZE_PASS(ExpandMulWithOverflow, "expand-mul-with-overflow",
-                "Expand out uses of llvm.umul.with.overflow intrinsics",
+char ExpandArithWithOverflow::ID = 0;
+INITIALIZE_PASS(ExpandArithWithOverflow, "expand-arith-with-overflow",
+                "Expand out some uses of *.with.overflow intrinsics",
                 false, false)
 
 static uint64_t UintTypeMax(unsigned Bits) {
@@ -61,11 +63,13 @@ static uint64_t UintTypeMax(unsigned Bits) {
   return (((uint64_t) 1) << Bits) - 1;
 }
 
-static bool ExpandForIntSize(Module *M, unsigned Bits) {
+static bool ExpandOpForIntSize(Module *M, unsigned Bits, bool Mul) {
   IntegerType *IntTy = IntegerType::get(M->getContext(), Bits);
   SmallVector<Type *, 1> Types;
   Types.push_back(IntTy);
-  std::string Name = Intrinsic::getName(Intrinsic::umul_with_overflow, Types);
+  Intrinsic::ID ID = (Mul ? Intrinsic::umul_with_overflow
+                          : Intrinsic::uadd_with_overflow);
+  std::string Name = Intrinsic::getName(ID, Types);
   Function *Intrinsic = M->getFunction(Name);
   if (!Intrinsic)
     return false;
@@ -73,8 +77,8 @@ static bool ExpandForIntSize(Module *M, unsigned Bits) {
          E = Intrinsic->use_end(); CallIter != E; ) {
     CallInst *Call = dyn_cast<CallInst>(*CallIter++);
     if (!Call) {
-      report_fatal_error("ExpandMulWithOverflow: Taking the address of a "
-                         "umul.with.overflow intrinsic is not allowed");
+      report_fatal_error("ExpandArithWithOverflow: Taking the address of a "
+                         "*.with.overflow intrinsic is not allowed");
     }
     Value *VariableArg;
     ConstantInt *ConstantArg;
@@ -86,15 +90,20 @@ static bool ExpandForIntSize(Module *M, unsigned Bits) {
       ConstantArg = C;
     } else {
       errs() << "Use: " << *Call << "\n";
-      report_fatal_error("ExpandMulWithOverflow: At least one argument of "
-                         "umul.with.overflow must be a constant");
+      report_fatal_error("ExpandArithWithOverflow: At least one argument of "
+                         "*.with.overflow must be a constant");
     }
 
-    Value *Mul = BinaryOperator::Create(
-        Instruction::Mul, VariableArg, ConstantArg,
-        Call->getName() + ".mul", Call);
+    Value *ArithResult = BinaryOperator::Create(
+        (Mul ? Instruction::Mul : Instruction::Add), VariableArg, ConstantArg,
+        Call->getName() + ".arith", Call);
 
-    uint64_t ArgMax = UintTypeMax(Bits) / ConstantArg->getZExtValue();
+    uint64_t ArgMax;
+    if (Mul) {
+      ArgMax = UintTypeMax(Bits) / ConstantArg->getZExtValue();
+    } else {
+      ArgMax = UintTypeMax(Bits) - ConstantArg->getZExtValue();
+    }
     Value *Overflow = new ICmpInst(
         Call, CmpInst::ICMP_UGT, VariableArg, ConstantInt::get(IntTy, ArgMax),
         Call->getName() + ".overflow");
@@ -106,18 +115,18 @@ static bool ExpandForIntSize(Module *M, unsigned Bits) {
       if (!Field) {
         errs() << "Use: " << *U << "\n";
         report_fatal_error(
-            "ExpandMulWithOverflow: Use is not an extractvalue");
+            "ExpandArithWithOverflow: Use is not an extractvalue");
       }
       if (Field->getNumIndices() != 1) {
-        report_fatal_error("ExpandMulWithOverflow: Unexpected indices");
+        report_fatal_error("ExpandArithWithOverflow: Unexpected indices");
       }
       unsigned Index = Field->getIndices()[0];
       if (Index == 0) {
-        Field->replaceAllUsesWith(Mul);
+        Field->replaceAllUsesWith(ArithResult);
       } else if (Index == 1) {
         Field->replaceAllUsesWith(Overflow);
       } else {
-        report_fatal_error("ExpandMulWithOverflow: Unexpected index");
+        report_fatal_error("ExpandArithWithOverflow: Unexpected index");
       }
       Field->eraseFromParent();
     }
@@ -127,7 +136,14 @@ static bool ExpandForIntSize(Module *M, unsigned Bits) {
   return true;
 }
 
-bool ExpandMulWithOverflow::runOnModule(Module &M) {
+static bool ExpandForIntSize(Module *M, unsigned Bits) {
+  bool Modified = false;
+  Modified |= ExpandOpForIntSize(M, Bits, true); // Expand umul
+  Modified |= ExpandOpForIntSize(M, Bits, false); // Expand uadd
+  return Modified;
+}
+
+bool ExpandArithWithOverflow::runOnModule(Module &M) {
   bool Modified = false;
   Modified |= ExpandForIntSize(&M, 64);
   Modified |= ExpandForIntSize(&M, 32);
@@ -136,6 +152,6 @@ bool ExpandMulWithOverflow::runOnModule(Module &M) {
   return Modified;
 }
 
-ModulePass *llvm::createExpandMulWithOverflowPass() {
-  return new ExpandMulWithOverflow();
+ModulePass *llvm::createExpandArithWithOverflowPass() {
+  return new ExpandArithWithOverflow();
 }
diff --git a/lib/Transforms/NaCl/PNaClABISimplify.cpp b/lib/Transforms/NaCl/PNaClABISimplify.cpp
index 37504517d6..47e5fb67e6 100644
--- a/lib/Transforms/NaCl/PNaClABISimplify.cpp
+++ b/lib/Transforms/NaCl/PNaClABISimplify.cpp
@@ -28,6 +28,7 @@ void llvm::PNaClABISimplifyAddPreOptPasses(PassManager &PM) {
   // Remove landingpad blocks made unreachable by LowerInvoke.
   PM.add(createCFGSimplificationPass());
 
+  PM.add(createExpandArithWithOverflowPass());
   PM.add(createExpandVarArgsPass());
   PM.add(createExpandCtorsPass());
   PM.add(createResolveAliasesPass());