enhance vmcore to know that udiv's can be exact, and add a trivial

instcombine xform to exercise this.

Nothing forms exact udivs yet though.  This is progress on PR8862

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124992 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/docs/LangRef.html b/docs/LangRef.html
index da365ff808ab05e2fd27a92ad63a7416737cdbd9..f7997495e04ce87581d9e1708f15d94b6ae2b537 100644 (file)
--- a/docs/LangRef.html
+++ b/docs/LangRef.html
@@ -3441,7 +3441,8 @@ Instruction</a> </div>
 
 <h5>Syntax:</h5>
 <pre>
-  &lt;result&gt; = udiv &lt;ty&gt; &lt;op1&gt;, &lt;op2&gt;   <i>; yields {ty}:result</i>
+  &lt;result&gt; = udiv &lt;ty&gt; &lt;op1&gt;, &lt;op2&gt;         <i>; yields {ty}:result</i>
+  &lt;result&gt; = udiv exact &lt;ty&gt; &lt;op1&gt;, &lt;op2&gt;   <i>; yields {ty}:result</i>
 </pre>
 
 <h5>Overview:</h5>
@@ -3460,6 +3461,11 @@ Instruction</a> </div>
 
 <p>Division by zero leads to undefined behavior.</p>
 
+<p>If the <tt>exact</tt> keyword is present, the result value of the
+   <tt>udiv</tt> is a <a href="#trapvalues">trap value</a> if %op1 is not a
+  multiple of %op2 (as such, "((a udiv exact b) mul b) == a").</p>
+
+
 <h5>Example:</h5>
 <pre>
   &lt;result&gt; = udiv i32 4, %var          <i>; yields {i32}:result = 4 / %var</i>

diff --git a/include/llvm/Bitcode/LLVMBitCodes.h b/include/llvm/Bitcode/LLVMBitCodes.h
index d15c3ce93ef58a723ad3033118dbdf6283a1eab7..7692bd28720bc791b64dbfe4ee875c1e950bcb0d 100644 (file)
--- a/include/llvm/Bitcode/LLVMBitCodes.h
+++ b/include/llvm/Bitcode/LLVMBitCodes.h
@@ -199,10 +199,10 @@ namespace bitc {
     OBO_NO_SIGNED_WRAP = 1
   };
 
-  /// SDivOperatorOptionalFlags - Flags for serializing SDivOperator's
-  /// SubclassOptionalData contents.
-  enum SDivOperatorOptionalFlags {
-    SDIV_EXACT = 0
+  /// PossiblyExactOperatorOptionalFlags - Flags for serializing 
+  /// PossiblyExactOperator's SubclassOptionalData contents.
+  enum PossiblyExactOperatorOptionalFlags {
+    PEO_EXACT = 0
   };
 
   // The function body block (FUNCTION_BLOCK_ID) describes function bodies.  It

diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index a7653948f13671b771651195bacf640c0e915965..b782737d31a04d914cfcb93e6829366d94ee458d 100644 (file)
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -725,6 +725,7 @@ public:
   static Constant *getNSWMul(Constant *C1, Constant *C2);
   static Constant *getNUWMul(Constant *C1, Constant *C2);
   static Constant *getExactSDiv(Constant *C1, Constant *C2);
+  static Constant *getExactUDiv(Constant *C1, Constant *C2);
 
   /// Transparently provide more efficient getOperand methods.
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant);

diff --git a/include/llvm/InstrTypes.h b/include/llvm/InstrTypes.h
index 9dcf6883583804b5e9fda06e411dc731719078ec..1bb50b78faee841122bc66f8e877282e53222c2e 100644 (file)
--- a/include/llvm/InstrTypes.h
+++ b/include/llvm/InstrTypes.h
@@ -341,7 +341,7 @@ public:
     BO->setIsExact(true);
     return BO;
   }
-
+  
   /// Helper functions to construct and inspect unary operations (NEG and NOT)
   /// via binary operators SUB and XOR:
   ///

diff --git a/include/llvm/Operator.h b/include/llvm/Operator.h
index 3aae586f1448c778bdfa59e6b8dd865846b28ac2..288edf1224473995077a4e1e10a13401bf3e2b97 100644 (file)
--- a/include/llvm/Operator.h
+++ b/include/llvm/Operator.h
@@ -173,30 +173,47 @@ public:
   }
 };
 
-/// SDivOperator - An Operator with opcode Instruction::SDiv.
-///
-class SDivOperator : public Operator {
+/// PossiblyExactOperator - A udiv or sdiv instruction, which can be marked as
+/// "exact", indicating that no bits are destroyed.
+class PossiblyExactOperator : public Operator {
 public:
   enum {
     IsExact = (1 << 0)
   };
-
-private:
-  ~SDivOperator(); // do not implement
-
+  
   friend class BinaryOperator;
   friend class ConstantExpr;
   void setIsExact(bool B) {
     SubclassOptionalData = (SubclassOptionalData & ~IsExact) | (B * IsExact);
   }
-
+  
+private:
+  ~PossiblyExactOperator(); // do not implement
 public:
   /// isExact - Test whether this division is known to be exact, with
   /// zero remainder.
   bool isExact() const {
     return SubclassOptionalData & IsExact;
   }
-
+  
+  static inline bool classof(const ConstantExpr *CE) {
+    return CE->getOpcode() == Instruction::SDiv ||
+           CE->getOpcode() == Instruction::UDiv;
+  }
+  static inline bool classof(const Instruction *I) {
+    return I->getOpcode() == Instruction::SDiv ||
+           I->getOpcode() == Instruction::UDiv;
+  }
+  static inline bool classof(const Value *V) {
+    return (isa<Instruction>(V) && classof(cast<Instruction>(V))) ||
+    (isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)));
+  }
+};
+  
+/// SDivOperator - An Operator with opcode Instruction::SDiv.
+///
+class SDivOperator : public PossiblyExactOperator {
+public:
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const SDivOperator *) { return true; }
   static inline bool classof(const ConstantExpr *CE) {
@@ -211,6 +228,24 @@ public:
   }
 };
 
+/// UDivOperator - An Operator with opcode Instruction::SDiv.
+///
+class UDivOperator : public PossiblyExactOperator {
+public:
+  // Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const UDivOperator *) { return true; }
+  static inline bool classof(const ConstantExpr *CE) {
+    return CE->getOpcode() == Instruction::UDiv;
+  }
+  static inline bool classof(const Instruction *I) {
+    return I->getOpcode() == Instruction::UDiv;
+  }
+  static inline bool classof(const Value *V) {
+    return (isa<Instruction>(V) && classof(cast<Instruction>(V))) ||
+    (isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)));
+  }
+};
+  
 class GEPOperator : public Operator {
   enum {
     IsInBounds = (1 << 0)

diff --git a/lib/AsmParser/LLParser.cpp b/lib/AsmParser/LLParser.cpp
index 8ef4634417544034ea829dac689843623d9810a0..6d71c9e3e60fcf29fe11d5c0dd9462109e2a3276 100644 (file)
--- a/lib/AsmParser/LLParser.cpp
+++ b/lib/AsmParser/LLParser.cpp
@@ -2304,7 +2304,7 @@ bool LLParser::ParseValID(ValID &ID, PerFunctionState *PFS) {
         if (EatIfPresent(lltok::kw_nuw))
           NUW = true;
       }
-    } else if (Opc == Instruction::SDiv) {
+    } else if (Opc == Instruction::SDiv || Opc == Instruction::UDiv) {
       if (EatIfPresent(lltok::kw_exact))
         Exact = true;
     }
@@ -2347,7 +2347,7 @@ bool LLParser::ParseValID(ValID &ID, PerFunctionState *PFS) {
     unsigned Flags = 0;
     if (NUW)   Flags |= OverflowingBinaryOperator::NoUnsignedWrap;
     if (NSW)   Flags |= OverflowingBinaryOperator::NoSignedWrap;
-    if (Exact) Flags |= SDivOperator::IsExact;
+    if (Exact) Flags |= PossiblyExactOperator::IsExact;
     Constant *C = ConstantExpr::get(Opc, Val0, Val1, Flags);
     ID.ConstantVal = C;
     ID.Kind = ValID::t_Constant;
@@ -3032,7 +3032,8 @@ int LLParser::ParseInstruction(Instruction *&Inst, BasicBlock *BB,
   case lltok::kw_fsub:
   case lltok::kw_fmul:    return ParseArithmetic(Inst, PFS, KeywordVal, 2);
 
-  case lltok::kw_sdiv: {
+  case lltok::kw_sdiv:
+  case lltok::kw_udiv: {
     bool Exact = false;
     if (EatIfPresent(lltok::kw_exact))
       Exact = true;
@@ -3043,7 +3044,6 @@ int LLParser::ParseInstruction(Instruction *&Inst, BasicBlock *BB,
     return Result;
   }
 
-  case lltok::kw_udiv:
   case lltok::kw_urem:
   case lltok::kw_srem:   return ParseArithmetic(Inst, PFS, KeywordVal, 1);
   case lltok::kw_fdiv:

diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index adcad7498910c6cd8cf72eeec4c377d88843aaa4..a744d833026674ce8e580306762c51807dde17cc 100644 (file)
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -1090,8 +1090,9 @@ bool BitcodeReader::ParseConstants() {
               Flags |= OverflowingBinaryOperator::NoSignedWrap;
             if (Record[3] & (1 << bitc::OBO_NO_UNSIGNED_WRAP))
               Flags |= OverflowingBinaryOperator::NoUnsignedWrap;
-          } else if (Opc == Instruction::SDiv) {
-            if (Record[3] & (1 << bitc::SDIV_EXACT))
+          } else if (Opc == Instruction::SDiv ||
+                     Opc == Instruction::UDiv) {
+            if (Record[3] & (1 << bitc::PEO_EXACT))
               Flags |= SDivOperator::IsExact;
           }
         }
@@ -1905,8 +1906,9 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
             cast<BinaryOperator>(I)->setHasNoSignedWrap(true);
           if (Record[OpNum] & (1 << bitc::OBO_NO_UNSIGNED_WRAP))
             cast<BinaryOperator>(I)->setHasNoUnsignedWrap(true);
-        } else if (Opc == Instruction::SDiv) {
-          if (Record[OpNum] & (1 << bitc::SDIV_EXACT))
+        } else if (Opc == Instruction::SDiv ||
+                   Opc == Instruction::UDiv) {
+          if (Record[OpNum] & (1 << bitc::PEO_EXACT))
             cast<BinaryOperator>(I)->setIsExact(true);
         }
       }

diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp
index 702a611cbe52a1b655a85f55e193da0d19a1c68f..f8ef8c668c47aa786b0da93d7f5730316ab70c44 100644 (file)
--- a/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ b/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -470,9 +470,10 @@ static uint64_t GetOptimizationFlags(const Value *V) {
       Flags |= 1 << bitc::OBO_NO_SIGNED_WRAP;
     if (OBO->hasNoUnsignedWrap())
       Flags |= 1 << bitc::OBO_NO_UNSIGNED_WRAP;
-  } else if (const SDivOperator *Div = dyn_cast<SDivOperator>(V)) {
-    if (Div->isExact())
-      Flags |= 1 << bitc::SDIV_EXACT;
+  } else if (const PossiblyExactOperator *PEO =
+               dyn_cast<PossiblyExactOperator>(V)) {
+    if (PEO->isExact())
+      Flags |= 1 << bitc::PEO_EXACT;
   }
 
   return Flags;

diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index 035ee721bfdf73d215bd1d64a4aa7678976a1502..559788b4a904ee4ef82616fb26d72cf93a715627 100644 (file)
--- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -135,8 +135,8 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) {
          BO->getOpcode() == Instruction::SDiv)) {
       Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1);
 
-      // If the division is exact, X % Y is zero.
-      if (SDivOperator *SDiv = dyn_cast<SDivOperator>(BO))
+      // If the division is exact, X % Y is zero, so we end up with X or -X.
+      if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO))
         if (SDiv->isExact()) {
           if (Op1BO == Op1C)
             return ReplaceInstUsesWith(I, Op0BO);

diff --git a/lib/VMCore/AsmWriter.cpp b/lib/VMCore/AsmWriter.cpp
index 1a11d9c7980be1346636b07d07b1ae6f8c6eee2c..5b56cb572cf483decffdad782f7d5496375b02e4 100644 (file)
--- a/lib/VMCore/AsmWriter.cpp
+++ b/lib/VMCore/AsmWriter.cpp
@@ -831,7 +831,8 @@ static void WriteOptimizationInfo(raw_ostream &Out, const User *U) {
       Out << " nuw";
     if (OBO->hasNoSignedWrap())
       Out << " nsw";
-  } else if (const SDivOperator *Div = dyn_cast<SDivOperator>(U)) {
+  } else if (const PossiblyExactOperator *Div =
+               dyn_cast<PossiblyExactOperator>(U)) {
     if (Div->isExact())
       Out << " exact";
   } else if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U)) {

diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 62117b22e6c9ec452c2a3b1e16c2577db3349579..d2359e5bcda48ee5309ce339443f752918595d74 100644 (file)
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -683,7 +683,12 @@ Constant* ConstantExpr::getNUWMul(Constant* C1, Constant* C2) {
 
 Constant* ConstantExpr::getExactSDiv(Constant* C1, Constant* C2) {
   return getTy(C1->getType(), Instruction::SDiv, C1, C2,
-               SDivOperator::IsExact);
+               PossiblyExactOperator::IsExact);
+}
+
+Constant* ConstantExpr::getExactUDiv(Constant* C1, Constant* C2) {
+  return getTy(C1->getType(), Instruction::UDiv, C1, C2,
+               PossiblyExactOperator::IsExact);
 }
 
 // Utility function for determining if a ConstantExpr is a CastOp or not. This

diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp
index 6b561f34af2b5e61aea3b3ebd1deb93b5342f56a..d1290281cb1a5e9071a76fb872730c1156c86a2a 100644 (file)
--- a/lib/VMCore/Instructions.cpp
+++ b/lib/VMCore/Instructions.cpp
@@ -1822,7 +1822,7 @@ void BinaryOperator::setHasNoSignedWrap(bool b) {
 }
 
 void BinaryOperator::setIsExact(bool b) {
-  cast<SDivOperator>(this)->setIsExact(b);
+  cast<PossiblyExactOperator>(this)->setIsExact(b);
 }
 
 bool BinaryOperator::hasNoUnsignedWrap() const {
@@ -1834,7 +1834,7 @@ bool BinaryOperator::hasNoSignedWrap() const {
 }
 
 bool BinaryOperator::isExact() const {
-  return cast<SDivOperator>(this)->isExact();
+  return cast<PossiblyExactOperator>(this)->isExact();
 }
 
 //===----------------------------------------------------------------------===//

diff --git a/test/Assembler/flags.ll b/test/Assembler/flags.ll
index 324190905975865ba3e4c090d524973c1357cf44..82b35b5c21000a2fc14d3176c3b56d1dd9a393bb 100644 (file)
--- a/test/Assembler/flags.ll
+++ b/test/Assembler/flags.ll
@@ -104,6 +104,19 @@ define i64 @sdiv_plain(i64 %x, i64 %y) {
        ret i64 %z
 }
 
+define i64 @udiv_exact(i64 %x, i64 %y) {
+; CHECK: %z = udiv exact i64 %x, %y
+       %z = udiv exact i64 %x, %y
+       ret i64 %z
+}
+
+define i64 @udiv_plain(i64 %x, i64 %y) {
+; CHECK: %z = udiv i64 %x, %y
+       %z = udiv i64 %x, %y
+       ret i64 %z
+}
+
+
 define i64* @gep_nw(i64* %p, i64 %x) {
 ; CHECK: %z = getelementptr inbounds i64* %p, i64 %x
        %z = getelementptr inbounds i64* %p, i64 %x
@@ -136,6 +149,11 @@ define i64 @sdiv_exact_ce() {
        ret i64 sdiv exact (i64 ptrtoint (i64* @addr to i64), i64 91)
 }
 
+define i64 @udiv_exact_ce() {
+; CHECK: ret i64 udiv exact (i64 ptrtoint (i64* @addr to i64), i64 91)
+       ret i64 udiv exact (i64 ptrtoint (i64* @addr to i64), i64 91)
+}
+
 define i64* @gep_nw_ce() {
 ; CHECK: ret i64* getelementptr inbounds (i64* @addr, i64 171)
         ret i64* getelementptr inbounds (i64* @addr, i64 171)
@@ -210,3 +228,4 @@ define i64 @mul_unsigned_ce() {
 ; CHECK: ret i64 mul nuw (i64 ptrtoint (i64* @addr to i64), i64 91)
        ret i64 mul nuw (i64 ptrtoint (i64* @addr to i64), i64 91)
 }
+

diff --git a/test/Transforms/InstCombine/exact-sdiv.ll b/test/Transforms/InstCombine/exact-sdiv.ll
deleted file mode 100644 (file)
index e567754..0000000
--- a/test/Transforms/InstCombine/exact-sdiv.ll
+++ /dev/null
@@ -1,52 +0,0 @@
-; RUN: opt < %s -instcombine -S | FileCheck %s
-
-; CHECK: define i32 @foo
-; CHECK: sdiv i32 %x, 8
-define i32 @foo(i32 %x) {
-  %y = sdiv i32 %x, 8
-  ret i32 %y
-}
-
-; CHECK: define i32 @bar
-; CHECK: ashr i32 %x, 3
-define i32 @bar(i32 %x) {
-  %y = sdiv exact i32 %x, 8
-  ret i32 %y
-}
-
-; CHECK: i32 @a0
-; CHECK: %y = srem i32 %x, 3
-; CHECK: %z = sub i32 %x, %y
-; CHECK: ret i32 %z
-define i32 @a0(i32 %x) {
-  %y = sdiv i32 %x, 3
-  %z = mul i32 %y, 3
-  ret i32 %z
-}
-
-; CHECK: i32 @b0
-; CHECK: ret i32 %x
-define i32 @b0(i32 %x) {
-  %y = sdiv exact i32 %x, 3
-  %z = mul i32 %y, 3
-  ret i32 %z
-}
-
-; CHECK: i32 @a1
-; CHECK: %y = srem i32 %x, 3
-; CHECK: %z = sub i32 %y, %x
-; CHECK: ret i32 %z
-define i32 @a1(i32 %x) {
-  %y = sdiv i32 %x, 3
-  %z = mul i32 %y, -3
-  ret i32 %z
-}
-
-; CHECK: i32 @b1
-; CHECK: %z = sub i32 0, %x
-; CHECK: ret i32 %z
-define i32 @b1(i32 %x) {
-  %y = sdiv exact i32 %x, 3
-  %z = mul i32 %y, -3
-  ret i32 %z
-}

diff --git a/test/Transforms/InstCombine/exact.ll b/test/Transforms/InstCombine/exact.ll
new file mode 100644 (file)
index 0000000..940469e
--- /dev/null
+++ b/test/Transforms/InstCombine/exact.ll
@@ -0,0 +1,60 @@
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; CHECK: define i32 @foo
+; CHECK: sdiv i32 %x, 8
+define i32 @foo(i32 %x) {
+  %y = sdiv i32 %x, 8
+  ret i32 %y
+}
+
+; CHECK: define i32 @bar
+; CHECK: ashr i32 %x, 3
+define i32 @bar(i32 %x) {
+  %y = sdiv exact i32 %x, 8
+  ret i32 %y
+}
+
+; CHECK: i32 @a0
+; CHECK: %y = srem i32 %x, 3
+; CHECK: %z = sub i32 %x, %y
+; CHECK: ret i32 %z
+define i32 @a0(i32 %x) {
+  %y = sdiv i32 %x, 3
+  %z = mul i32 %y, 3
+  ret i32 %z
+}
+
+; CHECK: i32 @b0
+; CHECK: ret i32 %x
+define i32 @b0(i32 %x) {
+  %y = sdiv exact i32 %x, 3
+  %z = mul i32 %y, 3
+  ret i32 %z
+}
+
+; CHECK: i32 @a1
+; CHECK: %y = srem i32 %x, 3
+; CHECK: %z = sub i32 %y, %x
+; CHECK: ret i32 %z
+define i32 @a1(i32 %x) {
+  %y = sdiv i32 %x, 3
+  %z = mul i32 %y, -3
+  ret i32 %z
+}
+
+; CHECK: i32 @b1
+; CHECK: %z = sub i32 0, %x
+; CHECK: ret i32 %z
+define i32 @b1(i32 %x) {
+  %y = sdiv exact i32 %x, 3
+  %z = mul i32 %y, -3
+  ret i32 %z
+}
+
+; CHECK: i32 @b2
+; CHECK: ret i32 %x
+define i32 @b2(i32 %x, i32 %w) {
+  %y = udiv exact i32 %x, %w
+  %z = mul i32 %y, %w
+  ret i32 %z
+}