PNaCl: Add pass to expand out Clang-generated umul.with.overflow calls

This adds a pass, ExpandMulWithOverflow, to expand out the
llvm.umul.with.overflow calls that Clang generates to implement an
overflow check for C++'s new[] operator.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3434
TEST=expand-mul-with-overflow.ll

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

6 files changed, 209 insertions, 0 deletions

diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index bd385de931..b55970ad84 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -281,6 +281,7 @@ void initializeExpandByValPass(PassRegistry&);
 void initializeExpandConstantExprPass(PassRegistry&);
 void initializeExpandCtorsPass(PassRegistry&);
 void initializeExpandGetElementPtrPass(PassRegistry&);
+void initializeExpandMulWithOverflowPass(PassRegistry&);
 void initializeExpandTlsConstantExprPass(PassRegistry&);
 void initializeExpandTlsPass(PassRegistry&);
 void initializeExpandVarArgsPass(PassRegistry&);
diff --git a/include/llvm/Transforms/NaCl.h b/include/llvm/Transforms/NaCl.h
index c324fa8c0c..af1dee2ebe 100644
--- a/include/llvm/Transforms/NaCl.h
+++ b/include/llvm/Transforms/NaCl.h
@@ -23,6 +23,7 @@ ModulePass *createExpandByValPass();
 FunctionPass *createExpandConstantExprPass();
 ModulePass *createExpandCtorsPass();
 BasicBlockPass *createExpandGetElementPtrPass();
+ModulePass *createExpandMulWithOverflowPass();
 ModulePass *createExpandTlsPass();
 ModulePass *createExpandTlsConstantExprPass();
 ModulePass *createExpandVarArgsPass();
diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
index d289c8912f..1fabdbc1db 100644
--- a/lib/Transforms/NaCl/CMakeLists.txt
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -3,6 +3,7 @@ add_llvm_library(LLVMNaClTransforms
   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/ExpandMulWithOverflow.cpp
new file mode 100644
index 0000000000..171dda1f09
--- /dev/null
+++ b/lib/Transforms/NaCl/ExpandMulWithOverflow.cpp
@@ -0,0 +1,141 @@
+//===- ExpandMulWithOverflow.cpp - Expand out usage of umul.with.overflow--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The llvm.*.with.overflow.*() intrinsics are awkward for PNaCl
+// 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.
+//
+// This pass only handles multiplication by a constant, which is the
+// only case of umul.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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/NaCl.h"
+
+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 {
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    ExpandMulWithOverflow() : ModulePass(ID) {
+      initializeExpandMulWithOverflowPass(*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",
+                false, false)
+
+static uint64_t UintTypeMax(unsigned Bits) {
+  // Avoid doing 1 << 64 because that is undefined on a uint64_t.
+  if (Bits == 64)
+    return ~(uint64_t) 0;
+  return (((uint64_t) 1) << Bits) - 1;
+}
+
+static bool ExpandForIntSize(Module *M, unsigned Bits) {
+  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);
+  Function *Intrinsic = M->getFunction(Name);
+  if (!Intrinsic)
+    return false;
+  for (Value::use_iterator CallIter = Intrinsic->use_begin(),
+         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");
+    }
+    Value *VariableArg;
+    ConstantInt *ConstantArg;
+    if (ConstantInt *C = dyn_cast<ConstantInt>(Call->getArgOperand(0))) {
+      VariableArg = Call->getArgOperand(1);
+      ConstantArg = C;
+    } else if (ConstantInt *C = dyn_cast<ConstantInt>(Call->getArgOperand(1))) {
+      VariableArg = Call->getArgOperand(0);
+      ConstantArg = C;
+    } else {
+      errs() << "Use: " << *Call << "\n";
+      report_fatal_error("ExpandMulWithOverflow: At least one argument of "
+                         "umul.with.overflow must be a constant");
+    }
+
+    Value *Mul = BinaryOperator::Create(
+        Instruction::Mul, VariableArg, ConstantArg,
+        Call->getName() + ".mul", Call);
+
+    uint64_t ArgMax = UintTypeMax(Bits) / ConstantArg->getZExtValue();
+    Value *Overflow = new ICmpInst(
+        Call, CmpInst::ICMP_UGT, VariableArg, ConstantInt::get(IntTy, ArgMax),
+        Call->getName() + ".overflow");
+
+    for (Value::use_iterator FieldIter = Call->use_begin(),
+           E = Call->use_end(); FieldIter != E; ) {
+      User *U = *FieldIter++;
+      ExtractValueInst *Field = dyn_cast<ExtractValueInst>(U);
+      if (!Field) {
+        errs() << "Use: " << *U << "\n";
+        report_fatal_error(
+            "ExpandMulWithOverflow: Use is not an extractvalue");
+      }
+      if (Field->getNumIndices() != 1) {
+        report_fatal_error("ExpandMulWithOverflow: Unexpected indices");
+      }
+      unsigned Index = Field->getIndices()[0];
+      if (Index == 0) {
+        Field->replaceAllUsesWith(Mul);
+      } else if (Index == 1) {
+        Field->replaceAllUsesWith(Overflow);
+      } else {
+        report_fatal_error("ExpandMulWithOverflow: Unexpected index");
+      }
+      Field->eraseFromParent();
+    }
+    Call->eraseFromParent();
+  }
+  Intrinsic->eraseFromParent();
+  return true;
+}
+
+bool ExpandMulWithOverflow::runOnModule(Module &M) {
+  bool Modified = false;
+  Modified |= ExpandForIntSize(&M, 64);
+  Modified |= ExpandForIntSize(&M, 32);
+  Modified |= ExpandForIntSize(&M, 16);
+  Modified |= ExpandForIntSize(&M, 8);
+  return Modified;
+}
+
+ModulePass *llvm::createExpandMulWithOverflowPass() {
+  return new ExpandMulWithOverflow();
+}
diff --git a/test/Transforms/NaCl/expand-mul-with-overflow.ll b/test/Transforms/NaCl/expand-mul-with-overflow.ll
new file mode 100644
index 0000000000..f6957988b0
--- /dev/null
+++ b/test/Transforms/NaCl/expand-mul-with-overflow.ll
@@ -0,0 +1,64 @@
+; RUN: opt %s -expand-mul-with-overflow -S | FileCheck %s
+
+declare {i32, i1} @llvm.umul.with.overflow.i32(i32, i32)
+declare {i64, i1} @llvm.umul.with.overflow.i64(i64, i64)
+
+; CHECK-NOT: @llvm.umul.with.overflow
+
+
+define void @umul32_by_const(i32 %x, i32* %result_val, i1* %result_overflow) {
+  %pair = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 256)
+  %val = extractvalue {i32, i1} %pair, 0
+  %overflow = extractvalue {i32, i1} %pair, 1
+
+  store i32 %val, i32* %result_val
+  store i1 %overflow, i1* %result_overflow
+  ret void
+}
+
+; The bound is 16777215 == 0xffffff == ((1 << 32) - 1) / 256
+; CHECK: define void @umul32_by_const(
+; CHECK-NEXT: %pair.mul = mul i32 %x, 256
+; CHECK-NEXT: %pair.overflow = icmp ugt i32 %x, 16777215
+; CHECK-NEXT: store i32 %pair.mul, i32* %result_val
+; CHECK-NEXT: store i1 %pair.overflow, i1* %result_overflow
+
+
+; Check that the pass can expand multiple uses of the same intrinsic.
+define void @umul32_by_const2(i32 %x, i32* %result_val, i1* %result_overflow) {
+  %pair = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 65536)
+  %val = extractvalue {i32, i1} %pair, 0
+  ; Check that the pass can expand multiple uses of %pair.
+  %overflow1 = extractvalue {i32, i1} %pair, 1
+  %overflow2 = extractvalue {i32, i1} %pair, 1
+
+  store i32 %val, i32* %result_val
+  store i1 %overflow1, i1* %result_overflow
+  store i1 %overflow2, i1* %result_overflow
+  ret void
+}
+
+; CHECK: define void @umul32_by_const2(
+; CHECK-NEXT: %pair.mul = mul i32 %x, 65536
+; CHECK-NEXT: %pair.overflow = icmp ugt i32 %x, 65535
+; CHECK-NEXT: store i32 %pair.mul, i32* %result_val
+; CHECK-NEXT: store i1 %pair.overflow, i1* %result_overflow
+; CHECK-NEXT: store i1 %pair.overflow, i1* %result_overflow
+
+
+define void @umul64_by_const(i64 %x, i64* %result_val, i1* %result_overflow) {
+  ; Multiply by 1 << 55.
+  %pair = call {i64, i1} @llvm.umul.with.overflow.i64(i64 36028797018963968, i64 %x)
+  %val = extractvalue {i64, i1} %pair, 0
+  %overflow = extractvalue {i64, i1} %pair, 1
+
+  store i64 %val, i64* %result_val
+  store i1 %overflow, i1* %result_overflow
+  ret void
+}
+
+; CHECK: define void @umul64_by_const(i64 %x, i64* %result_val, i1* %result_overflow) {
+; CHECK-NEXT: %pair.mul = mul i64 %x, 36028797018963968
+; CHECK-NEXT: %pair.overflow = icmp ugt i64 %x, 511
+; CHECK-NEXT: store i64 %pair.mul, i64* %result_val
+; CHECK-NEXT: store i1 %pair.overflow, i1* %result_overflow
diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp
index 94ff313937..3179e17733 100644
--- a/tools/opt/opt.cpp
+++ b/tools/opt/opt.cpp
@@ -589,6 +589,7 @@ int main(int argc, char **argv) {
   initializeExpandConstantExprPass(Registry);
   initializeExpandCtorsPass(Registry);
   initializeExpandGetElementPtrPass(Registry);
+  initializeExpandMulWithOverflowPass(Registry);
   initializeExpandTlsPass(Registry);
   initializeExpandTlsConstantExprPass(Registry);
   initializeExpandVarArgsPass(Registry);