PNaCl ABI: Disallow various operations on the i1 type

Disallow i1 on loads/stores and require the conversions to i8 to be
explicit.  Add a pass, PromoteI1Ops, that adds the conversions.
(Load/store on i1 occur in practice in small_tests for some boolean
globals.)

Disallow i1 for most arithmetic/comparison operations since these
aren't very useful and it's a nuisance for a code generator to have to
support these.  I haven't seen these occur in practice, but
PromoteI1Ops nevertheless expands them.

We still allow and/or/xor on i1 because these do occur in practice,
and they're less of a nuisance to handle because they never overflow:
no truncation to 1 bit is required, unlike with adds.

Restrict the type of alloca's argument.  Clang always uses i32 here.

Disallow i1 in switch instructions.  Clang doesn't generate i1
switches for booleans.

Move CopyLoadOrStoreAttrs() helper into a header to reuse.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3490
TEST=PNaCl toolchain trybots + GCC torture tests + Spec2k

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

10 files changed, 329 insertions, 23 deletions

diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 4e643c4d23..677c6253c4 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -294,6 +294,7 @@ void initializeInsertDivideCheckPass(PassRegistry&);
 void initializeNaClCcRewritePass(PassRegistry&);
 void initializePNaClABIVerifyModulePass(PassRegistry&);
 void initializePNaClABIVerifyFunctionsPass(PassRegistry&);
+void initializePromoteI1OpsPass(PassRegistry&);
 void initializePromoteIntegersPass(PassRegistry&);
 void initializeReplacePtrsWithIntsPass(PassRegistry&);
 void initializeResolveAliasesPass(PassRegistry&);
diff --git a/include/llvm/Transforms/NaCl.h b/include/llvm/Transforms/NaCl.h
index 6924320cfe..2e2a7bc69d 100644
--- a/include/llvm/Transforms/NaCl.h
+++ b/include/llvm/Transforms/NaCl.h
@@ -35,6 +35,7 @@ ModulePass *createExpandTlsConstantExprPass();
 ModulePass *createExpandVarArgsPass();
 ModulePass *createFlattenGlobalsPass();
 ModulePass *createGlobalCleanupPass();
+BasicBlockPass *createPromoteI1OpsPass();
 FunctionPass *createPromoteIntegersPass();
 ModulePass *createReplacePtrsWithIntsPass();
 ModulePass *createResolveAliasesPass();
@@ -54,6 +55,14 @@ void PhiSafeReplaceUses(Use *U, Value *NewVal);
 // Copy debug information from Original to NewInst, and return NewInst.
 Instruction *CopyDebug(Instruction *NewInst, Instruction *Original);
 
+template <class InstType>
+static void CopyLoadOrStoreAttrs(InstType *Dest, InstType *Src) {
+  Dest->setVolatile(Src->isVolatile());
+  Dest->setAlignment(Src->getAlignment());
+  Dest->setOrdering(Src->getOrdering());
+  Dest->setSynchScope(Src->getSynchScope());
+}
+
 // In order to change a function's type, the function must be
 // recreated.  RecreateFunction() recreates Func with type NewType.
 // It copies or moves across everything except the argument values,
diff --git a/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp b/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp
index 9a96d19ed4..80d7da3f19 100644
--- a/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp
+++ b/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp
@@ -79,15 +79,21 @@ bool PNaClABIVerifyFunctions::IsWhitelistedMetadata(unsigned MDKind) {
 }
 
 // A valid pointer type is either:
-//  * a pointer to a valid PNaCl scalar type, or
+//  * a pointer to a valid PNaCl scalar type (except i1), or
 //  * a function pointer (with valid argument and return types).
+//
+// i1 is disallowed so that all loads and stores are a whole number of
+// bytes, and so that we do not need to define whether a store of i1
+// zero-extends.
 static bool isValidPointerType(Type *Ty) {
   if (PointerType *PtrTy = dyn_cast<PointerType>(Ty)) {
     if (PtrTy->getAddressSpace() != 0)
       return false;
-    if (PNaClABITypeChecker::isValidScalarType(PtrTy->getElementType()))
+    Type *EltTy = PtrTy->getElementType();
+    if (PNaClABITypeChecker::isValidScalarType(EltTy) &&
+        !EltTy->isIntegerTy(1))
       return true;
-    if (FunctionType *FTy = dyn_cast<FunctionType>(PtrTy->getElementType()))
+    if (FunctionType *FTy = dyn_cast<FunctionType>(EltTy))
       return PNaClABITypeChecker::isValidFunctionType(FTy);
   }
   return false;
@@ -201,22 +207,12 @@ const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
     case Instruction::Br:
     case Instruction::Unreachable:
     // Binary operations
-    case Instruction::Add:
     case Instruction::FAdd:
-    case Instruction::Sub:
     case Instruction::FSub:
-    case Instruction::Mul:
     case Instruction::FMul:
-    case Instruction::UDiv:
-    case Instruction::SDiv:
     case Instruction::FDiv:
-    case Instruction::URem:
-    case Instruction::SRem:
     case Instruction::FRem:
     // Bitwise binary operations
-    case Instruction::Shl:
-    case Instruction::LShr:
-    case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor:
@@ -233,12 +229,30 @@ const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
     case Instruction::UIToFP:
     case Instruction::SIToFP:
     // Other operations
-    case Instruction::ICmp:
     case Instruction::FCmp:
     case Instruction::PHI:
     case Instruction::Select:
       break;
 
+    // The following operations are of dubious usefulness on 1-bit
+    // values.  Use of the i1 type is disallowed here so that code
+    // generators do not need to support these corner cases.
+    case Instruction::ICmp:
+    // Binary operations
+    case Instruction::Add:
+    case Instruction::Sub:
+    case Instruction::Mul:
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::URem:
+    case Instruction::SRem:
+    case Instruction::Shl:
+    case Instruction::LShr:
+    case Instruction::AShr:
+      if (Inst->getOperand(0)->getType()->isIntegerTy(1))
+        return "arithmetic on i1";
+      break;
+
     // Memory accesses.
     case Instruction::Load: {
       const LoadInst *Load = cast<LoadInst>(Inst);
@@ -290,8 +304,11 @@ const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
       break;
 
     case Instruction::Alloca: {
-      if (!cast<AllocaInst>(Inst)->getAllocatedType()->isIntegerTy(8))
+      const AllocaInst *Alloca = cast<AllocaInst>(Inst);
+      if (!Alloca->getAllocatedType()->isIntegerTy(8))
         return "non-i8 alloca";
+      if (!Alloca->getArraySize()->getType()->isIntegerTy(32))
+        return "alloca array size is not i32";
       break;
     }
 
@@ -345,6 +362,8 @@ const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
       const SwitchInst *Switch = cast<SwitchInst>(Inst);
       if (!isValidScalarOperand(Switch->getCondition()))
         return "bad switch condition";
+      if (Switch->getCondition()->getType()->isIntegerTy(1))
+        return "switch on i1";
 
       // SwitchInst requires the cases to be ConstantInts, but it
       // doesn't require their types to be the same as the condition
diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
index 02c5ac521d..49c5153bf3 100644
--- a/lib/Transforms/NaCl/CMakeLists.txt
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -15,6 +15,7 @@ add_llvm_library(LLVMNaClTransforms
   FlattenGlobals.cpp
   GlobalCleanup.cpp
   PNaClABISimplify.cpp
+  PromoteI1Ops.cpp
   PromoteIntegers.cpp
   ReplacePtrsWithInts.cpp
   RewriteLLVMIntrinsics.cpp
diff --git a/lib/Transforms/NaCl/PNaClABISimplify.cpp b/lib/Transforms/NaCl/PNaClABISimplify.cpp
index a85829eb3b..056b0ae651 100644
--- a/lib/Transforms/NaCl/PNaClABISimplify.cpp
+++ b/lib/Transforms/NaCl/PNaClABISimplify.cpp
@@ -65,6 +65,8 @@ void llvm::PNaClABISimplifyAddPostOptPasses(PassManager &PM) {
   // run.
   PM.add(createExpandSmallArgumentsPass());
 
+  PM.add(createPromoteI1OpsPass());
+
   // We place StripMetadata after optimization passes because
   // optimizations depend on the metadata.
   PM.add(createStripMetadataPass());
diff --git a/lib/Transforms/NaCl/PromoteI1Ops.cpp b/lib/Transforms/NaCl/PromoteI1Ops.cpp
new file mode 100644
index 0000000000..dccf081e26
--- /dev/null
+++ b/lib/Transforms/NaCl/PromoteI1Ops.cpp
@@ -0,0 +1,138 @@
+//===- PromoteI1Ops.cpp - Promote various operations on the i1 type--------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass expands out various operations on the i1 type so that
+// these i1 operations do not need to be supported by the PNaCl
+// translator.
+//
+// This is similar to the PromoteIntegers pass in that it removes uses
+// of an unusual-size integer type.  The difference is that i1 remains
+// a valid type in other operations.  i1 can still be used in phi
+// nodes, "select" instructions, in "sext" and "zext", and so on.  In
+// contrast, the integer types that PromoteIntegers removes are not
+// allowed in any context by PNaCl's ABI verifier.
+//
+// This pass expands out the following:
+//
+//  * i1 loads and stores.
+//  * All i1 comparisons and arithmetic operations, with the exception
+//    of "and", "or" and "xor", because these are used in practice and
+//    don't overflow.
+//
+// "switch" instructions on i1 are also disallowed by the PNaCl ABI
+// verifier, but they don't seem to be generated in practice and so
+// they are not currently expanded out by this pass.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/NaCl.h"
+
+using namespace llvm;
+
+namespace {
+  class PromoteI1Ops : public BasicBlockPass {
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    PromoteI1Ops() : BasicBlockPass(ID) {
+      initializePromoteI1OpsPass(*PassRegistry::getPassRegistry());
+    }
+
+    virtual bool runOnBasicBlock(BasicBlock &BB);
+  };
+}
+
+char PromoteI1Ops::ID = 0;
+INITIALIZE_PASS(PromoteI1Ops, "nacl-promote-i1-ops",
+                "Promote various operations on the i1 type",
+                false, false)
+
+static Value *promoteValue(Value *Val, bool SignExt, Instruction *InsertPt) {
+  Instruction::CastOps CastType =
+      SignExt ? Instruction::SExt : Instruction::ZExt;
+  return CopyDebug(CastInst::Create(CastType, Val,
+                                    Type::getInt8Ty(Val->getContext()),
+                                    Val->getName() + ".expand_i1_val",
+                                    InsertPt), InsertPt);
+}
+
+bool PromoteI1Ops::runOnBasicBlock(BasicBlock &BB) {
+  bool Changed = false;
+
+  Type *I1Ty = Type::getInt1Ty(BB.getContext());
+  Type *I8Ty = Type::getInt8Ty(BB.getContext());
+
+  for (BasicBlock::iterator Iter = BB.begin(), E = BB.end(); Iter != E; ) {
+    Instruction *Inst = Iter++;
+    if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
+      if (Load->getType() == I1Ty) {
+        Changed = true;
+        Value *Ptr = CopyDebug(
+            new BitCastInst(
+                Load->getPointerOperand(), I8Ty->getPointerTo(),
+                Load->getPointerOperand()->getName() + ".i8ptr", Load), Load);
+        LoadInst *NewLoad = new LoadInst(
+            Ptr, Load->getName() + ".pre_trunc", Load);
+        CopyDebug(NewLoad, Load);
+        CopyLoadOrStoreAttrs(NewLoad, Load);
+        Value *Result = CopyDebug(new TruncInst(NewLoad, I1Ty, "", Load), Load);
+        Result->takeName(Load);
+        Load->replaceAllUsesWith(Result);
+        Load->eraseFromParent();
+      }
+    } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
+      if (Store->getValueOperand()->getType() == I1Ty) {
+        Changed = true;
+        Value *Ptr = CopyDebug(
+            new BitCastInst(
+                Store->getPointerOperand(), I8Ty->getPointerTo(),
+                Store->getPointerOperand()->getName() + ".i8ptr", Store),
+            Store);
+        Value *Val = promoteValue(Store->getValueOperand(), false, Store);
+        StoreInst *NewStore = new StoreInst(Val, Ptr, Store);
+        CopyDebug(NewStore, Store);
+        CopyLoadOrStoreAttrs(NewStore, Store);
+        Store->eraseFromParent();
+      }
+    } else if (BinaryOperator *Op = dyn_cast<BinaryOperator>(Inst)) {
+      if (Op->getType() == I1Ty &&
+          !(Op->getOpcode() == Instruction::And ||
+            Op->getOpcode() == Instruction::Or ||
+            Op->getOpcode() == Instruction::Xor)) {
+        Value *Arg1 = promoteValue(Op->getOperand(0), false, Op);
+        Value *Arg2 = promoteValue(Op->getOperand(1), false, Op);
+        Value *NewOp = CopyDebug(
+            BinaryOperator::Create(
+                Op->getOpcode(), Arg1, Arg2,
+                Op->getName() + ".pre_trunc", Op), Op);
+        Value *Result = CopyDebug(new TruncInst(NewOp, I1Ty, "", Op), Op);
+        Result->takeName(Op);
+        Op->replaceAllUsesWith(Result);
+        Op->eraseFromParent();
+      }
+    } else if (ICmpInst *Op = dyn_cast<ICmpInst>(Inst)) {
+      if (Op->getOperand(0)->getType() == I1Ty) {
+        Value *Arg1 = promoteValue(Op->getOperand(0), Op->isSigned(), Op);
+        Value *Arg2 = promoteValue(Op->getOperand(1), Op->isSigned(), Op);
+        Value *Result = CopyDebug(
+            new ICmpInst(Op, Op->getPredicate(), Arg1, Arg2, ""), Op);
+        Result->takeName(Op);
+        Op->replaceAllUsesWith(Result);
+        Op->eraseFromParent();
+      }
+    }
+  }
+  return Changed;
+}
+
+BasicBlockPass *llvm::createPromoteI1OpsPass() {
+  return new PromoteI1Ops();
+}
diff --git a/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp b/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp
index c812f4d432..6e8c6915e5 100644
--- a/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp
+++ b/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp
@@ -334,14 +334,6 @@ static AttributeSet RemovePointerAttrs(LLVMContext &Context,
   return AttributeSet::get(Context, AttrList);
 }
 
-template <class InstType>
-static void CopyLoadOrStoreAttrs(InstType *Dest, InstType *Src) {
-  Dest->setVolatile(Src->isVolatile());
-  Dest->setAlignment(Src->getAlignment());
-  Dest->setOrdering(Src->getOrdering());
-  Dest->setSynchScope(Src->getSynchScope());
-}
-
 static void ConvertInstruction(DataLayout *DL, Type *IntPtrType,
                                FunctionConverter *FC, Instruction *Inst) {
   if (ReturnInst *Ret = dyn_cast<ReturnInst>(Inst)) {
diff --git a/test/NaCl/PNaClABI/abi-i1-operations.ll b/test/NaCl/PNaClABI/abi-i1-operations.ll
new file mode 100644
index 0000000000..4c63683bb8
--- /dev/null
+++ b/test/NaCl/PNaClABI/abi-i1-operations.ll
@@ -0,0 +1,66 @@
+; RUN: pnacl-abicheck < %s | FileCheck %s
+
+; Most arithmetic operations are not very useful on i1, so use of i1
+; is restricted to a subset of operations.
+
+
+; i1 is allowed on these bitwise operations because:
+;  * These operations never overflow.
+;  * They do get generated in practice for combining conditions.
+define internal void @allowed_cases() {
+  %and = and i1 0, 0
+  %or = or i1 0, 0
+  %xor = xor i1 0, 0
+  ret void
+}
+; CHECK-NOT: disallowed
+
+
+define internal void @rejected_cases(i32 %ptr) {
+  ; Loads and stores of i1 are disallowed.  This is done by rejecting
+  ; i1* as a pointer type.
+  %ptr.p = inttoptr i32 %ptr to i1*
+; CHECK: disallowed: bad result type: %ptr.p = inttoptr
+  load i1* %ptr.p, align 1
+; CHECK-NEXT: disallowed: bad pointer: {{.*}} load i1*
+
+  ; i1 arithmetic is of dubious usefulness, so it is rejected.
+  add i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} add
+  sub i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} sub
+  mul i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} mul
+  udiv i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} udiv
+  sdiv i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} sdiv
+  urem i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} urem
+  srem i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} srem
+  shl i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} shl
+  lshr i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} lshr
+  ashr i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} ashr
+
+  ; The same applies to i1 comparisons.
+  icmp eq i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} icmp eq
+  icmp ult i1 0, 0
+; CHECK-NEXT: disallowed: arithmetic on i1: {{.*}} icmp ult
+
+  ; There should be no implicit zero-extension in alloca.
+  alloca i8, i1 1
+; CHECK-NEXT: disallowed: alloca array size is not i32
+
+  ; Switch on i1 is not useful.  "br" should be used instead.
+  switch i1 0, label %next [i1 0, label %next]
+; CHECK-NEXT: disallowed: switch on i1
+next:
+
+  ret void
+}
+; CHECK-NOT: disallowed
diff --git a/test/Transforms/NaCl/promote-i1-ops.ll b/test/Transforms/NaCl/promote-i1-ops.ll
new file mode 100644
index 0000000000..245004b681
--- /dev/null
+++ b/test/Transforms/NaCl/promote-i1-ops.ll
@@ -0,0 +1,77 @@
+; RUN: opt %s -nacl-promote-i1-ops -S | FileCheck %s
+
+; Test that the PromoteI1Ops pass expands out i1 loads/stores and i1
+; comparison and arithmetic operations, with the exception of "and",
+; "or" and "xor".
+
+
+; i1 loads and stores are converted to i8 load and stores with
+; explicit casts.
+
+define i1 @load(i1* %ptr) {
+  %val = load i1* %ptr
+  ret i1 %val
+}
+; CHECK: define i1 @load
+; CHECK-NEXT: %ptr.i8ptr = bitcast i1* %ptr to i8*
+; CHECK-NEXT: %val.pre_trunc = load i8* %ptr.i8ptr
+; CHECK-NEXT: %val = trunc i8 %val.pre_trunc to i1
+
+define void @store(i1 %val, i1* %ptr) {
+  store i1 %val, i1* %ptr
+  ret void
+}
+; CHECK: define void @store
+; CHECK-NEXT: %ptr.i8ptr = bitcast i1* %ptr to i8*
+; CHECK-NEXT: %val.expand_i1_val = zext i1 %val to i8
+; CHECK-NEXT: store i8 %val.expand_i1_val, i8* %ptr.i8ptr
+
+
+; i1 arithmetic and comparisons are converted to their i8 equivalents
+; with explicit casts.
+
+define i1 @add(i1 %x, i1 %y) {
+  %result = add i1 %x, %y
+  ret i1 %result
+}
+; CHECK: define i1 @add
+; CHECK-NEXT: %x.expand_i1_val = zext i1 %x to i8
+; CHECK-NEXT: %y.expand_i1_val = zext i1 %y to i8
+; CHECK-NEXT: %result.pre_trunc = add i8 %x.expand_i1_val, %y.expand_i1_val
+; CHECK-NEXT: %result = trunc i8 %result.pre_trunc to i1
+
+define i1 @compare(i1 %x, i1 %y) {
+  %result = icmp slt i1 %x, %y
+  ret i1 %result
+}
+; CHECK: define i1 @compare
+; CHECK-NEXT: %x.expand_i1_val = sext i1 %x to i8
+; CHECK-NEXT: %y.expand_i1_val = sext i1 %y to i8
+; CHECK-NEXT: %result = icmp slt i8 %x.expand_i1_val, %y.expand_i1_val
+
+
+; Non-shift bitwise operations should not be modified.
+define void @bitwise_ops(i1 %x, i1 %y) {
+  %and = and i1 %x, %y
+  %or = or i1 %x, %y
+  %xor = xor i1 %x, %y
+  ret void
+}
+; CHECK: define void @bitwise_ops
+; CHECK-NEXT: %and = and i1 %x, %y
+; CHECK-NEXT: %or = or i1 %x, %y
+; CHECK-NEXT: %xor = xor i1 %x, %y
+
+
+define void @unchanged_cases(i32 %x, i32 %y, i32* %ptr) {
+  %add = add i32 %x, %y
+  %cmp = icmp slt i32 %x, %y
+  %val = load i32* %ptr
+  store i32 %x, i32* %ptr
+  ret void
+}
+; CHECK: define void @unchanged_cases
+; CHECK-NEXT: %add = add i32 %x, %y
+; CHECK-NEXT: %cmp = icmp slt i32 %x, %y
+; CHECK-NEXT: %val = load i32* %ptr
+; CHECK-NEXT: store i32 %x, i32* %ptr
diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp
index 804382fca7..56ac3ec9a7 100644
--- a/tools/opt/opt.cpp
+++ b/tools/opt/opt.cpp
@@ -620,6 +620,7 @@ int main(int argc, char **argv) {
   initializeInsertDivideCheckPass(Registry);
   initializePNaClABIVerifyFunctionsPass(Registry);
   initializePNaClABIVerifyModulePass(Registry);
+  initializePromoteI1OpsPass(Registry);
   initializePromoteIntegersPass(Registry);
   initializeReplacePtrsWithIntsPass(Registry);
   initializeResolveAliasesPass(Registry);