First part of PR12251. Add documentation and verifier support for the range

metadata.

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

6 files changed, 165 insertions, 1 deletions

diff --git a/docs/LangRef.html b/docs/LangRef.html
index 81dabc91af..cfe489031e 100644
--- a/docs/LangRef.html
+++ b/docs/LangRef.html
@@ -104,6 +104,7 @@
         <ol>
           <li><a href="#tbaa">'<tt>tbaa</tt>' Metadata</a></li>
           <li><a href="#fpaccuracy">'<tt>fpaccuracy</tt>' Metadata</a></li>
+          <li><a href="#range">'<tt>range</tt>' Metadata</a></li>
         </ol>
       </li>
     </ol>
@@ -3028,6 +3029,39 @@ call void @llvm.dbg.value(metadata !24, i64 0, metadata !25)
 </pre>
 </div>
 
+<!-- _______________________________________________________________________ -->
+<h4>
+  <a name="range">'<tt>range</tt>' Metadata</a>
+</h4>
+
+<div>
+<p><tt>range</tt> metadata may be attached only to loads of integer types. It
+   expresses the possible ranges the loaded value is in. The ranges are
+   represented with a flattened list of integers. The loaded value is known to
+   be in the union of the ranges defined by each consecutive pair. Each pair
+   has the following properties:</p>
+<ul>
+   <li>The type must match the type loaded by the instruction.</li>
+   <li>The pair <tt>a,b</tt> represents the range <tt>[a,b)</tt>.</li>
+   <li>Both <tt>a</tt> and <tt>b</tt> are constants.</li>
+   <li>The range is allowed to wrap.</li>
+   <li>The range should not represent the full or empty set. That is,
+       <tt>a!=b</tt>. </li>
+</ul>
+
+<p>Examples:</p>
+<div class="doc_code">
+<pre>
+  %a = load i8* %x, align 1, !range !0 ; Can only be 0 or 1
+  %b = load i8* %y, align 1, !range !1 ; Can only be 255 (-1), 0 or 1
+  %c = load i8* %z, align 1, !range !2 ; Can only be 0, 1, 3, 4 or 5
+...
+!0 = metadata !{ i8 0, i8 2 }
+!1 = metadata !{ i8 255, i8 2 }
+!2 = metadata !{ i8 0, i8 2, i8 3, i8 6 }
+</pre>
+</div>
+</div>
 </div>
 
 </div>
diff --git a/include/llvm/LLVMContext.h b/include/llvm/LLVMContext.h
index 47d2eaab03..18adcd1e3c 100644
--- a/include/llvm/LLVMContext.h
+++ b/include/llvm/LLVMContext.h
@@ -42,7 +42,8 @@ public:
     MD_dbg = 0,  // "dbg"
     MD_tbaa = 1, // "tbaa"
     MD_prof = 2,  // "prof"
-    MD_fpaccuracy = 3  // "fpaccuracy"
+    MD_fpaccuracy = 3,  // "fpaccuracy"
+    MD_range = 4 // "range"
   };
   
   /// getMDKindID - Return a unique non-zero ID for the specified metadata kind.
diff --git a/lib/VMCore/LLVMContext.cpp b/lib/VMCore/LLVMContext.cpp
index d77e996b5e..68c56212bc 100644
--- a/lib/VMCore/LLVMContext.cpp
+++ b/lib/VMCore/LLVMContext.cpp
@@ -48,6 +48,11 @@ LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) {
   unsigned FPAccuracyID = getMDKindID("fpaccuracy");
   assert(FPAccuracyID == MD_fpaccuracy && "fpaccuracy kind id drifted");
   (void)FPAccuracyID;
+
+  // Create the 'range' metadata kind.
+  unsigned RangeID = getMDKindID("range");
+  assert(RangeID == MD_range && "range kind id drifted");
+  (void)RangeID;
 }
 LLVMContext::~LLVMContext() { delete pImpl; }
 
diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp
index 5b9b2a5258..f62441bea7 100644
--- a/lib/VMCore/Verifier.cpp
+++ b/lib/VMCore/Verifier.cpp
@@ -51,6 +51,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/InlineAsm.h"
 #include "llvm/IntrinsicInst.h"
+#include "llvm/LLVMContext.h"
 #include "llvm/Metadata.h"
 #include "llvm/Module.h"
 #include "llvm/Pass.h"
@@ -1369,6 +1370,25 @@ void Verifier::visitLoadInst(LoadInst &LI) {
     Assert1(LI.getSynchScope() == CrossThread,
             "Non-atomic load cannot have SynchronizationScope specified", &LI);
   }
+
+  if (MDNode *Range = LI.getMetadata(LLVMContext::MD_range)) {
+    unsigned NumOperands = Range->getNumOperands();
+    Assert1(NumOperands % 2 == 0, "Unfinished range!", Range);
+    unsigned NumRanges = NumOperands / 2;
+    Assert1(NumRanges >= 1, "It should have at least one range!", Range);
+    for (unsigned i = 0; i < NumRanges; ++i) {
+      ConstantInt *Low = dyn_cast<ConstantInt>(Range->getOperand(2*i));
+      Assert1(Low, "The lower limit must be an integer!", Low);
+      ConstantInt *High = dyn_cast<ConstantInt>(Range->getOperand(2*i + 1));
+      Assert1(High, "The upper limit must be an integer!", High);
+      Assert1(High->getType() == Low->getType() &&
+              High->getType() == ElTy, "Range types must match load type!",
+              &LI);
+      Assert1(High->getValue() != Low->getValue(), "Range must not be empty!",
+              Range);
+    }
+  }
+
   visitInstruction(LI);
 }
 
@@ -1641,6 +1661,10 @@ void Verifier::visitInstruction(Instruction &I) {
               "Cannot take the address of an inline asm!", &I);
     }
   }
+
+  MDNode *MD = I.getMetadata(LLVMContext::MD_range);
+  Assert1(!MD || isa<LoadInst>(I), "Ranges are only for loads!", &I);
+
   InstsInThisBlock.insert(&I);
 }
 
diff --git a/test/Verifier/range-1.ll b/test/Verifier/range-1.ll
new file mode 100644
index 0000000000..611933a1ec
--- /dev/null
+++ b/test/Verifier/range-1.ll
@@ -0,0 +1,78 @@
+; RUN: not llvm-as < %s -o /dev/null |& FileCheck %s
+
+define void @f1(i8* %x) {
+entry:
+  store i8 0, i8* %x, align 1, !range !0
+  ret void
+}
+!0 = metadata !{i8 0, i8 1}
+; CHECK: Ranges are only for loads!
+; CHECK-NEXT: store i8 0, i8* %x, align 1, !range !0
+
+define i8 @f2(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !1
+  ret i8 %y
+}
+!1 = metadata !{}
+; CHECK: It should have at least one range!
+; CHECK-NEXT: metadata
+
+define i8 @f3(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !2
+  ret i8 %y
+}
+!2 = metadata !{i8 0}
+; CHECK: Unfinished range!
+
+define i8 @f4(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !3
+  ret i8 %y
+}
+!3 = metadata !{double 0.0, i8 0}
+; CHECK: The lower limit must be an integer!
+
+define i8 @f5(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !4
+  ret i8 %y
+}
+!4 = metadata !{i8 0, double 0.0}
+; CHECK: The upper limit must be an integer!
+
+define i8 @f6(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !5
+  ret i8 %y
+}
+!5 = metadata !{i32 0, i8 0}
+; CHECK: Range types must match load type!
+; CHECK:  %y = load
+
+define i8 @f7(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !6
+  ret i8 %y
+}
+!6 = metadata !{i8 0, i32 0}
+; CHECK: Range types must match load type!
+; CHECK:  %y = load
+
+define i8 @f8(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !7
+  ret i8 %y
+}
+!7 = metadata !{i32 0, i32 0}
+; CHECK: Range types must match load type!
+; CHECK:  %y = load
+
+define i8 @f9(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !8
+  ret i8 %y
+}
+!8 = metadata !{i8 0, i8 0}
+; CHECK: Range must not be empty!
diff --git a/test/Verifier/range-2.ll b/test/Verifier/range-2.ll
new file mode 100644
index 0000000000..ef542c8c93
--- /dev/null
+++ b/test/Verifier/range-2.ll
@@ -0,0 +1,22 @@
+; RUN: llvm-as < %s -o /dev/null
+
+define i8 @f1(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !0
+  ret i8 %y
+}
+!0 = metadata !{i8 0, i8 1}
+
+define i8 @f2(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !1
+  ret i8 %y
+}
+!1 = metadata !{i8 255, i8 1}
+
+define i8 @f3(i8* %x) {
+entry:
+  %y = load i8* %x, align 1, !range !2
+  ret i8 %y
+}
+!2 = metadata !{i8 1, i8 3, i8 5, i8 42}