refactor integer overflow detection, add signed int

Instead of checking for every possible casse which result in overflow,
it is much simpler to perform the operation using integers with bigger
dimension and check if the result overflow

1 files changed, 65 insertions, 41 deletions

diff --git a/lib/Module/IntrinsicCleaner.cpp b/lib/Module/IntrinsicCleaner.cpp
index 9d4f0fec..da97621a 100644
--- a/lib/Module/IntrinsicCleaner.cpp
+++ b/lib/Module/IntrinsicCleaner.cpp
@@ -118,59 +118,83 @@ bool IntrinsicCleanerPass::runOnBasicBlock(BasicBlock &b, Module &M) {
         break;
       }
 
+      case Intrinsic::sadd_with_overflow:
+      case Intrinsic::ssub_with_overflow:
+      case Intrinsic::smul_with_overflow:
       case Intrinsic::uadd_with_overflow:
       case Intrinsic::usub_with_overflow:
       case Intrinsic::umul_with_overflow: {
         IRBuilder<> builder(ii->getParent(), ii);
-        Function *F = builder.GetInsertBlock()->getParent();
 
         Value *op1 = ii->getArgOperand(0);
         Value *op2 = ii->getArgOperand(1);
         
         Value *result = 0;
+        Value *result_ext = 0;
         Value *overflow = 0;
-        if (ii->getIntrinsicID() == Intrinsic::uadd_with_overflow){
-          result = builder.CreateAdd(op1, op2);
-          overflow = builder.CreateICmpULT(result, op1);
-        } else if (ii->getIntrinsicID() == Intrinsic::usub_with_overflow){
-          result = builder.CreateSub(op1, op2);
-          overflow = builder.CreateICmpUGT(result, op1);
-        } else if (ii->getIntrinsicID() == Intrinsic::umul_with_overflow){
-          BasicBlock *entry = builder.GetInsertBlock();
-          entry->setName(Twine(entry->getName(), "_umul_start"));
-          BasicBlock *cont_of = entry->splitBasicBlock(builder.GetInsertPoint(),
-                                                       "umul_end");
-          BasicBlock *on_of = BasicBlock::Create(builder.getContext(),
-                                                 "umul_overflow", F, cont_of);
-
-          // remove the branch inserted by splitBasicBlock, we'll add our own
-          entry->getTerminator()->eraseFromParent();
-          builder.SetInsertPoint(entry);
-          Value *no_overflow = builder.getFalse();
-          Value *one = ConstantInt::getSigned(op1->getType(), 1);
-          Value *op1_g1 = builder.CreateICmpUGT(op1, one);
-          Value *op2_g1 = builder.CreateICmpUGT(op2, one);
-          Value *may_of = builder.CreateAnd(op1_g1, op2_g1);
-          builder.CreateCondBr(may_of, on_of, cont_of);
-
-          builder.SetInsertPoint(on_of);
-          uint64_t bit_size = op1->getType()->getPrimitiveSizeInBits();
-          Value *uint_max = ConstantInt::get(op1->getType(),
-                                             APInt::getMaxValue(bit_size));
-          Value *div1 = builder.CreateUDiv(uint_max, op1);
-          Value *overflow1 = builder.CreateICmpUGT(op2, div1);
-          builder.CreateBr(cont_of);
-
-          builder.SetInsertPoint(cont_of, cont_of->begin());
-          PHINode *phi_of = builder.CreatePHI(no_overflow->getType(), 2);
-          phi_of->addIncoming(overflow1, on_of);
-          phi_of->addIncoming(no_overflow, entry);
-
-          result = builder.CreateMul(op1, op2);
-          overflow = phi_of;
-          block_split = true;
+
+        unsigned int bw = op1->getType()->getPrimitiveSizeInBits();
+        unsigned int bw2 = op1->getType()->getPrimitiveSizeInBits()*2;
+
+        if ((ii->getIntrinsicID() == Intrinsic::uadd_with_overflow) ||
+            (ii->getIntrinsicID() == Intrinsic::usub_with_overflow) ||
+            (ii->getIntrinsicID() == Intrinsic::umul_with_overflow)) {
+
+          Value *op1ext =
+            builder.CreateZExt(op1, IntegerType::get(M.getContext(), bw2));
+          Value *op2ext =
+            builder.CreateZExt(op2, IntegerType::get(M.getContext(), bw2));
+          Value *int_max_s =
+            ConstantInt::get(op1->getType(), APInt::getMaxValue(bw));
+          Value *int_max =
+            builder.CreateZExt(int_max_s, IntegerType::get(M.getContext(), bw2));
+
+          if (ii->getIntrinsicID() == Intrinsic::uadd_with_overflow){
+            result_ext = builder.CreateAdd(op1ext, op2ext);
+          } else if (ii->getIntrinsicID() == Intrinsic::usub_with_overflow){
+            result_ext = builder.CreateSub(op1ext, op2ext);
+          } else if (ii->getIntrinsicID() == Intrinsic::umul_with_overflow){
+            result_ext = builder.CreateMul(op1ext, op2ext);
+          }
+          overflow = builder.CreateICmpUGT(result_ext, int_max);
+
+        } else if ((ii->getIntrinsicID() == Intrinsic::sadd_with_overflow) ||
+                   (ii->getIntrinsicID() == Intrinsic::ssub_with_overflow) ||
+                   (ii->getIntrinsicID() == Intrinsic::smul_with_overflow)) {
+
+          Value *op1ext =
+            builder.CreateSExt(op1, IntegerType::get(M.getContext(), bw2));
+          Value *op2ext =
+            builder.CreateSExt(op2, IntegerType::get(M.getContext(), bw2));
+          Value *int_max_s =
+            ConstantInt::get(op1->getType(), APInt::getSignedMaxValue(bw));
+          Value *int_min_s =
+            ConstantInt::get(op1->getType(), APInt::getSignedMinValue(bw));
+          Value *int_max =
+            builder.CreateSExt(int_max_s, IntegerType::get(M.getContext(), bw2));
+          Value *int_min =
+            builder.CreateSExt(int_min_s, IntegerType::get(M.getContext(), bw2));
+
+          if (ii->getIntrinsicID() == Intrinsic::sadd_with_overflow){
+            result_ext = builder.CreateAdd(op1ext, op2ext);
+          } else if (ii->getIntrinsicID() == Intrinsic::ssub_with_overflow){
+            result_ext = builder.CreateSub(op1ext, op2ext);
+          } else if (ii->getIntrinsicID() == Intrinsic::smul_with_overflow){
+            result_ext = builder.CreateMul(op1ext, op2ext);
+          }
+          overflow = builder.CreateOr(builder.CreateICmpSGT(result_ext, int_max),
+                                      builder.CreateICmpSLT(result_ext, int_min));
         }
 
+        // This trunc cound be replaced by a more general trunc replacement
+        // that allows to detect also undefined behavior in assignments or
+        // overflow in operation with integers whose dimension is smaller than
+        // int's dimension, e.g.
+        //     uint8_t = uint8_t + uint8_t;
+        // if one desires the wrapping should write
+        //     uint8_t = (uint8_t + uint8_t) & 0xFF;
+        // before this, must check if it has side effects on other operations
+        result = builder.CreateTrunc(result_ext, op1->getType());
         Value *resultStruct =
           builder.CreateInsertValue(UndefValue::get(ii->getType()), result, 0);
         resultStruct = builder.CreateInsertValue(resultStruct, overflow, 1);