From d1a971a156cbd06b552b5d875883e1a89bd6e535 Mon Sep 17 00:00:00 2001 From: Karl Schimpf Date: Wed, 17 Sep 2014 15:38:17 -0700 Subject: [PATCH] Add switch instruction to Subzero bitcode reader. BUG= https://code.google.com/p/nativeclient/issues/detail?id=3892 R=stichnot@chromium.org Review URL: https://codereview.chromium.org/576243002 --- src/IceTypes.cpp | 7 + src/IceTypes.h | 3 + src/PNaClTranslator.cpp | 74 +++++- tests_lit/reader_tests/switch.ll | 496 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 571 insertions(+), 9 deletions(-) create mode 100644 tests_lit/reader_tests/switch.ll diff --git a/src/IceTypes.cpp b/src/IceTypes.cpp index a3e19ae07..29ff4de07 100644 --- a/src/IceTypes.cpp +++ b/src/IceTypes.cpp @@ -228,6 +228,13 @@ Type getCompareResultType(Type Ty) { return IceType_void; } +SizeT getScalarIntBitWidth(Type Ty) { + assert(isScalarIntegerType(Ty)); + if (Ty == Ice::IceType_i1) + return 1; + return typeWidthInBytes(Ty) * CHAR_BIT; +} + // ======================== Dump routines ======================== // const char *typeString(Type Ty) { diff --git a/src/IceTypes.h b/src/IceTypes.h index 4127104f0..cc782ab59 100644 --- a/src/IceTypes.h +++ b/src/IceTypes.h @@ -66,6 +66,9 @@ bool isLoadStoreType(Type Ty); /// allowed. Type getCompareResultType(Type Ty); +/// Returns the number of bits in a scalar integer type. +SizeT getScalarIntBitWidth(Type Ty); + template inline StreamType &operator<<(StreamType &Str, const Type &Ty) { Str << typeString(Ty); diff --git a/src/PNaClTranslator.cpp b/src/PNaClTranslator.cpp index d63232f2b..609804cbb 100644 --- a/src/PNaClTranslator.cpp +++ b/src/PNaClTranslator.cpp @@ -1007,7 +1007,7 @@ private: // Must be forward reference, expand vector to accommodate. if (LocalIndex >= LocalOperands.size()) - LocalOperands.resize(LocalIndex+1); + LocalOperands.resize(LocalIndex + 1); // If element not defined, set it. Ice::Operand *OldOp = LocalOperands[LocalIndex]; @@ -1023,8 +1023,8 @@ private: // Error has occurred. std::string Buffer; raw_string_ostream StrBuf(Buffer); - StrBuf << "Multiple definitions for index " << Index - << ": " << *Op << " and " << *OldOp; + StrBuf << "Multiple definitions for index " << Index << ": " << *Op + << " and " << *OldOp; Error(StrBuf.str()); // TODO(kschimpf) Remove error recovery once implementation complete. LocalOperands[LocalIndex] = Op; @@ -1037,9 +1037,7 @@ private: } // Returns the absolute index of the next value generating instruction. - uint32_t getNextInstIndex() const { - return NextLocalInstIndex; - } + uint32_t getNextInstIndex() const { return NextLocalInstIndex; } // Generates type error message for binary operator Op // operating on Type OpTy. @@ -1682,6 +1680,65 @@ void FunctionParser::ProcessRecord() { InstIsTerminating = true; break; } + case naclbitc::FUNC_CODE_INST_SWITCH: { + // SWITCH: [Condty, Cond, BbIndex, NumCases Case ...] + // where Case = [1, 1, Value, BbIndex]. + // + // Note: Unlike most instructions, we don't infer the type of + // Cond, but provide it as a separate field. There are also + // unnecesary data fields (i.e. constants 1). These were not + // cleaned up in PNaCl bitcode because the bitcode format was + // already frozen when the problem was noticed. + if (!isValidRecordSizeAtLeast(4, "function block switch")) + return; + Ice::Type CondTy = + Context->convertToIceType(Context->getTypeByID(Values[0])); + if (!Ice::isScalarIntegerType(CondTy)) { + std::string Buffer; + raw_string_ostream StrBuf(Buffer); + StrBuf << "Case condition must be non-wide integer. Found: " << CondTy; + Error(StrBuf.str()); + return; + } + Ice::SizeT BitWidth = Ice::getScalarIntBitWidth(CondTy); + Ice::Operand *Cond = getRelativeOperand(Values[1], BaseIndex); + if (CondTy != Cond->getType()) { + std::string Buffer; + raw_string_ostream StrBuf(Buffer); + StrBuf << "Case condition expects type " << CondTy + << ". Found: " << Cond->getType(); + Error(StrBuf.str()); + return; + } + Ice::CfgNode *DefaultLabel = getBranchBasicBlock(Values[2]); + unsigned NumCases = Values[3]; + + // Now recognize each of the cases. + if (!isValidRecordSize(4 + NumCases * 4, "Function block switch")) + return; + Ice::InstSwitch *Switch = + Ice::InstSwitch::create(Func, NumCases, Cond, DefaultLabel); + unsigned ValCaseIndex = 4; // index to beginning of case entry. + for (unsigned CaseIndex = 0; CaseIndex < NumCases; + ++CaseIndex, ValCaseIndex += 4) { + if (Values[ValCaseIndex] != 1 || Values[ValCaseIndex+1] != 1) { + std::string Buffer; + raw_string_ostream StrBuf(Buffer); + StrBuf << "Sequence [1, 1, value, label] expected for case entry " + << "in switch record. (at index" << ValCaseIndex << ")"; + Error(StrBuf.str()); + return; + } + APInt Value(BitWidth, + NaClDecodeSignRotatedValue(Values[ValCaseIndex + 2]), + true); + Ice::CfgNode *Label = getBranchBasicBlock(Values[ValCaseIndex + 3]); + Switch->addBranch(CaseIndex, Value.getSExtValue(), Label); + } + CurrentNode->appendInst(Switch); + InstIsTerminating = true; + break; + } case naclbitc::FUNC_CODE_INST_UNREACHABLE: { // UNREACHABLE: [] if (!isValidRecordSize(0, "function block unreachable")) @@ -1781,11 +1838,10 @@ void FunctionParser::ProcessRecord() { // FORWARDTYPEREF: [opval, ty] if (!isValidRecordSize(2, "function block forward type ref")) return; - setOperand(Values[0], createInstVar( - Context->convertToIceType(Context->getTypeByID(Values[1])))); + setOperand(Values[0], createInstVar(Context->convertToIceType( + Context->getTypeByID(Values[1])))); break; } - case naclbitc::FUNC_CODE_INST_SWITCH: case naclbitc::FUNC_CODE_INST_CALL: case naclbitc::FUNC_CODE_INST_CALL_INDIRECT: default: diff --git a/tests_lit/reader_tests/switch.ll b/tests_lit/reader_tests/switch.ll new file mode 100644 index 000000000..7edaeda5c --- /dev/null +++ b/tests_lit/reader_tests/switch.ll @@ -0,0 +1,496 @@ +; Test switch instructions. + +; RUN: llvm-as < %s | pnacl-freeze -allow-local-symbol-tables \ +; RUN: | %llvm2ice -notranslate -verbose=inst -build-on-read \ +; RUN: -allow-pnacl-reader-error-recovery \ +; RUN: -allow-local-symbol-tables \ +; RUN: | FileCheck %s + +define void @testDefaultSwitch(i32 %a) { +entry: + switch i32 %a, label %exit [ + ] +exit: + ret void +} + +; CHECK: define void @testDefaultSwitch(i32 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 %a, label %exit [ +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define i32 @testSwitch(i32 %a) { +entry: + switch i32 %a, label %sw.default [ + i32 1, label %sw.epilog + i32 2, label %sw.epilog + i32 3, label %sw.epilog + i32 7, label %sw.bb1 + i32 8, label %sw.bb1 + i32 15, label %sw.bb2 + i32 14, label %sw.bb2 + ] + +sw.default: ; preds = %entry + %add = add i32 %a, 27 + br label %sw.epilog + +sw.bb1: ; preds = %entry, %entry + %phitmp = sub i32 21, %a + br label %sw.bb2 + +sw.bb2: ; preds = %sw.bb1, %entry, %entry + %result.0 = phi i32 [ 1, %entry ], [ 1, %entry ], [ %phitmp, %sw.bb1 ] + br label %sw.epilog + +sw.epilog: ; preds = %sw.bb2, %sw.default, %entry, %entry, %entry + %result.1 = phi i32 [ %add, %sw.default ], [ %result.0, %sw.bb2 ], [ 17, %entry ], [ 17, %entry ], [ 17, %entry ] + ret i32 %result.1 +} + +; CHECK-NEXT: define i32 @testSwitch(i32 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 %a, label %sw.default [ +; CHECK-NEXT: i32 1, label %sw.epilog +; CHECK-NEXT: i32 2, label %sw.epilog +; CHECK-NEXT: i32 3, label %sw.epilog +; CHECK-NEXT: i32 7, label %sw.bb1 +; CHECK-NEXT: i32 8, label %sw.bb1 +; CHECK-NEXT: i32 15, label %sw.bb2 +; CHECK-NEXT: i32 14, label %sw.bb2 +; CHECK-NEXT: ] +; CHECK-NEXT: sw.default: +; CHECK-NEXT: %add = add i32 %a, 27 +; CHECK-NEXT: br label %sw.epilog +; CHECK-NEXT: sw.bb1: +; CHECK-NEXT: %phitmp = sub i32 21, %a +; CHECK-NEXT: br label %sw.bb2 +; CHECK-NEXT: sw.bb2: +; CHECK-NEXT: %result.0 = phi i32 [ 1, %entry ], [ 1, %entry ], [ %phitmp, %sw.bb1 ] +; CHECK-NEXT: br label %sw.epilog +; CHECK-NEXT: sw.epilog: +; CHECK-NEXT: %result.1 = phi i32 [ %add, %sw.default ], [ %result.0, %sw.bb2 ], [ 17, %entry ], [ 17, %entry ], [ 17, %entry ] +; CHECK-NEXT: ret i32 %result.1 +; CHECK-NEXT: } + +define void @testSignedI32Values(i32 %a) { +entry: + switch i32 %a, label %labelDefault [ + i32 0, label %label0 + i32 -1, label %labelM1 + i32 3, label %labelOther + i32 -3, label %labelOther + i32 -2147483648, label %labelMin ; min signed i32 + i32 2147483647, label %labelMax ; max signed i32 + ] +labelDefault: + ret void +label0: + ret void +labelM1: + ret void +labelMin: + ret void +labelMax: + ret void +labelOther: + ret void +} + +; CHECK-NEXT: define void @testSignedI32Values(i32 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 %a, label %labelDefault [ +; CHECK-NEXT: i32 0, label %label0 +; CHECK-NEXT: i32 -1, label %labelM1 +; CHECK-NEXT: i32 3, label %labelOther +; CHECK-NEXT: i32 -3, label %labelOther +; CHECK-NEXT: i32 -2147483648, label %labelMin +; CHECK-NEXT: i32 2147483647, label %labelMax +; CHECK-NEXT: ] +; CHECK-NEXT: labelDefault: +; CHECK-NEXT: ret void +; CHECK-NEXT: label0: +; CHECK-NEXT: ret void +; CHECK-NEXT: labelM1: +; CHECK-NEXT: ret void +; CHECK-NEXT: labelMin: +; CHECK-NEXT: ret void +; CHECK-NEXT: labelMax: +; CHECK-NEXT: ret void +; CHECK-NEXT: labelOther: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross signed i32 size boundaries. +define void @testSignedI32Boundary(i32 %a) { +entry: + switch i32 %a, label %exit [ + i32 -2147483649, label %exit ; min signed i32 - 1 + i32 2147483648, label %exit ; max signed i32 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI32Boundary(i32 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 %a, label %exit [ +; CHECK-NEXT: i32 2147483647, label %exit +; CHECK-NEXT: i32 -2147483648, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testUnsignedI32Values(i32 %a) { +entry: + switch i32 %a, label %exit [ + i32 0, label %exit + i32 2147483647, label %exit ; max signed i32 + i32 4294967295, label %exit ; max unsigned i32 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI32Values(i32 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 %a, label %exit [ +; CHECK-NEXT: i32 0, label %exit +; CHECK-NEXT: i32 2147483647, label %exit +; ; Note that -1 is signed version of 4294967295 +; CHECK-NEXT: i32 -1, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross unsigned i32 boundaries. +define void @testUnsignedI32Boundary(i32 %a) { +entry: + switch i32 %a, label %exit [ + i32 4294967296, label %exit ; max unsigned i32 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI32Boundary(i32 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 %a, label %exit [ +; CHECK-NEXT: i32 0, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testSignedI64Values(i64 %a) { +entry: + switch i64 %a, label %exit [ + i64 0, label %exit + i64 -9223372036854775808, label %exit ; min signed i64 + i64 9223372036854775807, label %exit ; max signed i64 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI64Values(i64 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i64 %a, label %exit [ +; CHECK-NEXT: i64 0, label %exit +; CHECK-NEXT: i64 -9223372036854775808, label %exit +; CHECK-NEXT: i64 9223372036854775807, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross signed i64 size boundaries. +define void @testSignedI64Boundary(i64 %a) { +entry: + switch i64 %a, label %exit [ + i64 0, label %exit + i64 -9223372036854775809, label %exit ; min signed i64 - 1 + i64 9223372036854775808, label %exit ; max signed i64 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI64Boundary(i64 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i64 %a, label %exit [ +; CHECK-NEXT: i64 0, label %exit +; CHECK-NEXT: i64 9223372036854775807, label %exit +; CHECK-NEXT: i64 -9223372036854775808, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testUnsignedI64Values(i64 %a) { +entry: + switch i64 %a, label %exit [ + i64 0, label %exit + i64 9223372036854775807, label %exit ; max signed i64 + i64 18446744073709551615, label %exit ; max unsigned i64 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI64Values(i64 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i64 %a, label %exit [ +; CHECK-NEXT: i64 0, label %exit +; CHECK-NEXT: i64 9223372036854775807, label %exit +; CHECK-NEXT: i64 -1, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross unsigned i64 size boundaries. +define void @testUnsignedI64Boundary(i64 %a) { +entry: + switch i64 %a, label %exit [ + i64 18446744073709551616, label %exit ; max unsigned i64 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI64Boundary(i64 %a) { +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i64 %a, label %exit [ +; CHECK-NEXT: i64 0, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testSignedI16Values(i32 %p) { +entry: + %a = trunc i32 %p to i16 + switch i16 %a, label %exit [ + i16 0, label %exit + i16 -1, label %exit + i16 3, label %exit + i16 -3, label %exit + i16 -32768, label %exit ; min signed i16 + i16 32767, label %exit ; max unsigned i16 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI16Values(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i16 +; CHECK-NEXT: switch i16 %a, label %exit [ +; CHECK-NEXT: i16 0, label %exit +; CHECK-NEXT: i16 -1, label %exit +; CHECK-NEXT: i16 3, label %exit +; CHECK-NEXT: i16 -3, label %exit +; CHECK-NEXT: i16 -32768, label %exit +; CHECK-NEXT: i16 32767, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross signed i16 size boundaries. +define void @testSignedI16Boundary(i32 %p) { +entry: + %a = trunc i32 %p to i16 + switch i16 %a, label %exit [ + i16 -32769, label %exit ; min signed i16 - 1 + i16 32768, label %exit ; max unsigned i16 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI16Boundary(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i16 +; CHECK-NEXT: switch i16 %a, label %exit [ +; CHECK-NEXT: i16 32767, label %exit +; CHECK-NEXT: i16 -32768, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testUnsignedI16Values(i32 %p) { +entry: + %a = trunc i32 %p to i16 + switch i16 %a, label %exit [ + i16 0, label %exit + i16 32767, label %exit ; max signed i16 + i16 65535, label %exit ; max unsigned i16 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI16Values(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i16 +; CHECK-NEXT: switch i16 %a, label %exit [ +; CHECK-NEXT: i16 0, label %exit +; CHECK-NEXT: i16 32767, label %exit +; ; Note that -1 is signed version of 65535 +; CHECK-NEXT: i16 -1, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross unsigned i16 size boundaries. +define void @testUnsignedI16Boundary(i32 %p) { +entry: + %a = trunc i32 %p to i16 + switch i16 %a, label %exit [ + i16 65536, label %exit ; max unsigned i16 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI16Boundary(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i16 +; CHECK-NEXT: switch i16 %a, label %exit [ +; CHECK-NEXT: i16 0, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testSignedI8Values(i32 %p) { +entry: + %a = trunc i32 %p to i8 + switch i8 %a, label %exit [ + i8 0, label %exit + i8 -1, label %exit + i8 3, label %exit + i8 -3, label %exit + i8 -128, label %exit ; min signed i8 + i8 127, label %exit ; max unsigned i8 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI8Values(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i8 +; CHECK-NEXT: switch i8 %a, label %exit [ +; CHECK-NEXT: i8 0, label %exit +; CHECK-NEXT: i8 -1, label %exit +; CHECK-NEXT: i8 3, label %exit +; CHECK-NEXT: i8 -3, label %exit +; CHECK-NEXT: i8 -128, label %exit +; CHECK-NEXT: i8 127, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross signed i8 size boundaries. +define void @testSignedI8Boundary(i32 %p) { +entry: + %a = trunc i32 %p to i8 + switch i8 %a, label %exit [ + i8 -129, label %exit ; min signed i8 - 1 + i8 128, label %exit ; max unsigned i8 + 1 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testSignedI8Boundary(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i8 +; CHECK-NEXT: switch i8 %a, label %exit [ +; CHECK-NEXT: i8 127, label %exit +; CHECK-NEXT: i8 -128, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + + +define void @testUnsignedI8Values(i32 %p) { +entry: + %a = trunc i32 %p to i8 + switch i8 %a, label %exit [ + i8 0, label %exit + i8 127, label %exit ; max signed i8 + i8 255, label %exit ; max unsigned i8 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI8Values(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i8 +; CHECK-NEXT: switch i8 %a, label %exit [ +; CHECK-NEXT: i8 0, label %exit +; CHECK-NEXT: i8 127, label %exit +; ; Note that -1 is signed version of 255 +; CHECK-NEXT: i8 -1, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +; Test values that cross unsigned i8 size boundaries. +define void @testUnsignedI8Boundary(i32 %p) { +entry: + %a = trunc i32 %p to i8 + switch i8 %a, label %exit [ + i8 256, label %exit ; max unsigned i8 + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testUnsignedI8Boundary(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i8 +; CHECK-NEXT: switch i8 %a, label %exit [ +; CHECK-NEXT: i8 0, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + +define void @testI1Values(i32 %p) { +entry: + %a = trunc i32 %p to i1 + switch i1 %a, label %exit [ + i1 true, label %exit + i1 false, label %exit + ] +exit: + ret void +} + +; CHECK-NEXT: define void @testI1Values(i32 %p) { +; CHECK-NEXT: entry: +; CHECK-NEXT: %a = trunc i32 %p to i1 +; CHECK-NEXT: switch i1 %a, label %exit [ +; CHECK-NEXT: i1 -1, label %exit +; CHECK-NEXT: i1 0, label %exit +; CHECK-NEXT: ] +; CHECK-NEXT: exit: +; CHECK-NEXT: ret void +; CHECK-NEXT: } + -- 2.11.0