ABI verifier: Verify types of global variables and initializers.

Loosely based on lib/VMCore/TypeFinder.cpp but I can't use that directly because it's not streaming-friendly.
constexprs in initializers are also supported.

R=jvoung@chromium.org,eliben@chromium.org,mseaborn@chromium.org
BUG= https://code.google.com/p/nativeclient/issues/detail?id=2196
TEST=llvm regression

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

3 files changed, 230 insertions, 2 deletions

diff --git a/lib/Analysis/NaCl/CheckTypes.h b/lib/Analysis/NaCl/CheckTypes.h
new file mode 100644
index 0000000000..336dc0302f
--- /dev/null
+++ b/lib/Analysis/NaCl/CheckTypes.h
@@ -0,0 +1,109 @@
+//===- CheckTypes.h - Verify PNaCl ABI rules --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Common type-checking code for module and function-level passes
+//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LIB_ANALYSIS_NACL_CHECKTYPES_H
+#define LIB_ANALYSIS_NACL_CHECKTYPES_H
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Support/raw_ostream.h"
+
+class TypeChecker {
+ public:
+  bool IsValidType(const llvm::Type* Ty) {
+    if (VisitedTypes.count(Ty))
+      return VisitedTypes[Ty];
+
+    unsigned Width;
+    bool Valid = false;
+    switch (Ty->getTypeID()) {
+      // Allowed primitive types
+      case llvm::Type::VoidTyID:
+      case llvm::Type::FloatTyID:
+      case llvm::Type::DoubleTyID:
+      case llvm::Type::LabelTyID:
+      case llvm::Type::MetadataTyID:
+        Valid = true;
+        break;
+      // Disallowed primitive types
+      case llvm::Type::HalfTyID:
+      case llvm::Type::X86_FP80TyID:
+      case llvm::Type::FP128TyID:
+      case llvm::Type::PPC_FP128TyID:
+      case llvm::Type::X86_MMXTyID:
+        Valid = false;
+        break;
+      // Derived types
+      case llvm::Type::VectorTyID:
+        Valid = false;
+        break;
+      case llvm::Type::IntegerTyID:
+        Width = llvm::cast<const llvm::IntegerType>(Ty)->getBitWidth();
+        Valid = (Width == 1 || Width == 8 || Width == 16 ||
+                 Width == 32 || Width == 64);
+        break;
+      case llvm::Type::FunctionTyID:
+      case llvm::Type::StructTyID:
+      case llvm::Type::ArrayTyID:
+      case llvm::Type::PointerTyID:
+        // These types are valid if their contained or pointed-to types are
+        // valid. Since struct/pointer subtype relationships may be circular,
+        // mark the current type as valid to avoid infinite recursion
+        Valid = true;
+        VisitedTypes[Ty] = true;
+        for (llvm::Type::subtype_iterator I = Ty->subtype_begin(),
+                 E = Ty->subtype_end(); I != E; ++I)
+          Valid &= IsValidType(*I);
+        break;
+        // Handle NumTypeIDs, and no default case,
+        // so we get a warning if new types are added
+      case llvm::Type::NumTypeIDs:
+        Valid = false;
+        break;
+    }
+
+    VisitedTypes[Ty] = Valid;
+    return Valid;
+  }
+
+  bool CheckTypesInValue(const llvm::Value* V) {
+    // TODO: Checking types in values probably belongs in its
+    // own value checker which also handles the various types of
+    // constexpr (in particular, blockaddr constexprs cause this code
+    // to assert rather than go off and try to verify the BBs of a function)
+    // But this code is in a good consistent checkpoint-able state.
+    assert(llvm::isa<llvm::Constant>(V));
+    if (VisitedConstants.count(V))
+      return VisitedConstants[V];
+
+    bool Valid = IsValidType(V->getType());
+    VisitedConstants[V] = Valid;
+
+    const llvm::User *U = llvm::cast<llvm::User>(V);
+    for (llvm::Constant::const_op_iterator I = U->op_begin(),
+             E = U->op_end(); I != E; ++I)
+      Valid &= CheckTypesInValue(*I);
+    VisitedConstants[V] = Valid;
+    return Valid;
+  }
+
+ private:
+  // To avoid walking constexprs and types multiple times, keep a cache of
+  // what we have seen. This is also used to prevent infinite recursion e.g.
+  // in case of structures like linked lists with pointers to themselves.
+  llvm::DenseMap<const llvm::Value*, bool> VisitedConstants;
+  llvm::DenseMap<const llvm::Type*, bool> VisitedTypes;
+};
+
+#endif // LIB_ANALYSIS_NACL_CHECKTYPES_H
diff --git a/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp b/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
index 5062f710f6..3b35668656 100644
--- a/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
+++ b/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
@@ -14,10 +14,14 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Twine.h"
+#include "llvm/DerivedTypes.h"
 #include "llvm/Module.h"
 #include "llvm/Pass.h"
+
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Analysis/NaCl.h"
+
+#include "CheckTypes.h"
 using namespace llvm;
 
 namespace {
@@ -32,6 +36,10 @@ struct PNaClABIVerifyModule : public ModulePass {
   // simpler. In the future we will probably want to make it do something
   // useful.
   virtual void print(llvm::raw_ostream &O, const Module *M) const {};
+ private:
+  // Ideally this would share an instance with the Function pass.
+  // TODO: see if that's feasible when we add checking in bodies
+  TypeChecker TC;
 };
 
 static const char* LinkageName(GlobalValue::LinkageTypes LT) {
@@ -63,10 +71,26 @@ static const char* LinkageName(GlobalValue::LinkageTypes LT) {
 } // end anonymous namespace
 
 bool PNaClABIVerifyModule::runOnModule(Module &M) {
-  // Check GV linkage types
+
   for (Module::const_global_iterator MI = M.global_begin(), ME = M.global_end();
        MI != ME; ++MI) {
-    switch(MI->getLinkage()) {
+    // Check types of global variables and their initializers
+    if (!TC.IsValidType(MI->getType())) {
+      errs() << (Twine("Variable ") + MI->getName() +
+                 " has disallowed type: ");
+      // GVs are pointers, so print the pointed-to type for clarity
+      MI->getType()->getContainedType(0)->print(errs());
+      errs() << "\n";
+    } else if (MI->hasInitializer() &&
+               !TC.CheckTypesInValue(MI->getInitializer())) {
+      errs() << (Twine("Initializer for ") + MI->getName() +
+                 " has disallowed type: ");
+      MI->getInitializer()->print(errs());
+      errs() << "\n";
+    }
+
+    // Check GV linkage types
+    switch (MI->getLinkage()) {
       case GlobalValue::ExternalLinkage:
       case GlobalValue::AvailableExternallyLinkage:
       case GlobalValue::InternalLinkage:
@@ -78,6 +102,12 @@ bool PNaClABIVerifyModule::runOnModule(Module &M) {
                 LinkageName(MI->getLinkage()) + "\n");
     }
   }
+  // No aliases allowed for now.
+  for (Module::alias_iterator MI = M.alias_begin(),
+           E = M.alias_end(); MI != E; ++MI)
+    errs() << (Twine("Variable ") + MI->getName() +
+               " is an alias (disallowed)\n");
+
   return false;
 }
 
diff --git a/test/NaCl/PNaClABI/types.ll b/test/NaCl/PNaClABI/types.ll
new file mode 100644
index 0000000000..3656b0a51d
--- /dev/null
+++ b/test/NaCl/PNaClABI/types.ll
@@ -0,0 +1,89 @@
+; RUN: opt -verify-pnaclabi-module -analyze < %s |& FileCheck %s
+; Test types allowed by PNaCl ABI
+
+; Basic global types
+; CHECK: Variable i4 has disallowed type: i4
+@i4 = private global i4 0
+; CHECK: Variable i33 has disallowed type: i33
+@i33 = private global i33 0
+; CHECK: Variable i128 has disallowed type: i128
+@i128 = private global i128 0
+; CHECK: Variable hlf has disallowed type: half
+@hlf = private global half 0.0
+; CHECK: Variable fp80 has disallowed type: x86_fp80
+@fp80 = private global x86_fp80 undef
+; CHECK: Variable f128 has disallowed type: fp128
+@f128 = private global fp128 undef
+; CHECK: Variable ppc128 has disallowed type: ppc_fp128
+@ppc128 = private global ppc_fp128 undef
+; CHECK: Variable mmx has disallowed type: x86_mmx
+@mmx = private global x86_mmx undef
+
+@i1 = private global i1 0
+@i8 = private global i8 0
+@i16 = private global i16 0
+@i32 = private global i32 0
+@i64 = private global i64 0
+@flt = private global float 0.0
+@dbl = private global double 0.0
+
+
+; global derived types
+@p1 = private global i32* undef
+@a1 = private global [1 x i32] undef
+@s1 = private global { i32, float } undef
+@f1 = private global void (i32) * undef
+; CHECK-NOT: disallowed
+; CHECK: Variable v1 has disallowed type: <2 x i32>
+@v1 = private global <2 x i32> undef
+; CHECK-NOT: disallowed
+@ps1 = private global <{ i8, i32 }> undef
+
+
+; named types. with the current implementation, bogus named types are legal
+; until they are actually attempted to be used. Might want to fix that.
+%struct.s1 = type { half, float}
+; CHECK: Variable s11 has disallowed type: %struct.s1 = type { half, float }
+@s11 = private global %struct.s1 undef
+; CHECK-NOT: disallowed
+%struct.s2 = type { i32, i32}
+@s12 = private global %struct.s2 undef
+
+
+; types in arrays, structs, etc
+; CHECK: Variable p2 has disallowed type: half*
+@p2 = private global half* undef
+; CHECK: Variable a2 has disallowed type: [2 x i33]
+@a2 = private global [ 2 x i33 ] undef
+; CHECK: Variable s2 has disallowed type: { half, i32 }
+@s2 = private global { half, i32 } undef
+; CHECK: Variable s3 has disallowed type: { float, i33 }
+@s3 = private global { float, i33 } undef
+; CHECK: Variable s4 has disallowed type: { i32, { i32, half }, float }
+@s4 = private global { i32, { i32, half }, float } undef
+; CHECK-NOT: disallowed
+@s5 = private global { i32, { i32, double }, float } undef
+
+; Initializers with constexprs
+; CHECK: Variable cc1 has disallowed type: half
+@cc1 = private global half 0.0
+; CHECK: Initializer for ce1 has disallowed type: i8* bitcast (half* @cc1 to i8*)
+@ce1 = private global i8 * bitcast (half* @cc1 to i8*)
+@cc2 = private global { i32, half } undef
+; CHECK: Initializer for ce2 has disallowed type: i32* getelementptr inbounds ({ i32, half }* @cc2, i32 0, i32 0)
+@ce2 = private global i32 * getelementptr ({ i32, half } * @cc2, i32 0, i32 0)
+
+; Circularities:  here to make sure the verifier doesn't crash or assert.
+
+; This oddity is perfectly legal according to the IR and ABI verifiers.
+; Might want to fix that. (good luck initializing one of these, though.)
+%struct.snake = type { i32, %struct.tail }
+%struct.tail = type { %struct.snake, i32 }
+@foo = private global %struct.snake undef
+
+%struct.linked = type { i32, %struct.linked * }
+@list1 = private global %struct.linked { i32 0, %struct.linked* null }
+; CHECK-NOT: disallowed
+
+; CHECK: Variable alias1 is an alias (disallowed)
+@alias1 = alias i32* @i32