diff --git a/runtime/dex_instruction-inl.h b/runtime/dex_instruction-inl.h
index dd65f2c..3d0fea0 100644
--- a/runtime/dex_instruction-inl.h
+++ b/runtime/dex_instruction-inl.h
@@ -49,6 +49,8 @@
     case k32x: return true;
     case k35c: return true;
     case k3rc: return true;
+    case k45cc: return true;
+    case k4rcc: return true;
     case k51l: return true;
     default: return false;
   }
@@ -79,6 +81,8 @@
     case k32x: return VRegA_32x();
     case k35c: return VRegA_35c();
     case k3rc: return VRegA_3rc();
+    case k45cc: return VRegA_45cc();
+    case k4rcc: return VRegA_4rcc();
     case k51l: return VRegA_51l();
     default:
       LOG(FATAL) << "Tried to access vA of instruction " << Name() << " which has no A operand.";
@@ -206,6 +210,16 @@
   return InstAA(inst_data);
 }
 
+inline uint4_t Instruction::VRegA_45cc(uint16_t inst_data) const {
+  DCHECK_EQ(FormatOf(Opcode()), k45cc);
+  return InstB(inst_data);  // This is labeled A in the spec.
+}
+
+inline uint8_t Instruction::VRegA_4rcc(uint16_t inst_data) const {
+  DCHECK_EQ(FormatOf(Opcode()), k4rcc);
+  return InstAA(inst_data);
+}
+
 //------------------------------------------------------------------------------
 // VRegB
 //------------------------------------------------------------------------------
@@ -229,6 +243,8 @@
     case k32x: return true;
     case k35c: return true;
     case k3rc: return true;
+    case k45cc: return true;
+    case k4rcc: return true;
     case k51l: return true;
     default: return false;
   }
@@ -258,6 +274,8 @@
     case k32x: return VRegB_32x();
     case k35c: return VRegB_35c();
     case k3rc: return VRegB_3rc();
+    case k45cc: return VRegB_45cc();
+    case k4rcc: return VRegB_4rcc();
     case k51l: return VRegB_51l();
     default:
       LOG(FATAL) << "Tried to access vB of instruction " << Name() << " which has no B operand.";
@@ -359,6 +377,16 @@
   return Fetch16(1);
 }
 
+inline uint16_t Instruction::VRegB_45cc() const {
+  DCHECK_EQ(FormatOf(Opcode()), k45cc);
+  return Fetch16(1);
+}
+
+inline uint16_t Instruction::VRegB_4rcc() const {
+  DCHECK_EQ(FormatOf(Opcode()), k4rcc);
+  return Fetch16(1);
+}
+
 inline uint64_t Instruction::VRegB_51l() const {
   DCHECK_EQ(FormatOf(Opcode()), k51l);
   uint64_t vB_wide = Fetch32(1) | ((uint64_t) Fetch32(3) << 32);
@@ -377,6 +405,8 @@
     case k23x: return true;
     case k35c: return true;
     case k3rc: return true;
+    case k45cc: return true;
+    case k4rcc: return true;
     default: return false;
   }
 }
@@ -390,6 +420,8 @@
     case k23x: return VRegC_23x();
     case k35c: return VRegC_35c();
     case k3rc: return VRegC_3rc();
+    case k45cc: return VRegC_45cc();
+    case k4rcc: return VRegC_4rcc();
     default:
       LOG(FATAL) << "Tried to access vC of instruction " << Name() << " which has no C operand.";
       exit(EXIT_FAILURE);
@@ -431,11 +463,52 @@
   return Fetch16(2);
 }
 
+inline uint4_t Instruction::VRegC_45cc() const {
+  DCHECK_EQ(FormatOf(Opcode()), k45cc);
+  return static_cast<uint4_t>(Fetch16(2) & 0x0f);
+}
+
+inline uint16_t Instruction::VRegC_4rcc() const {
+  DCHECK_EQ(FormatOf(Opcode()), k4rcc);
+  return Fetch16(2);
+}
+
+//------------------------------------------------------------------------------
+// VRegH
+//------------------------------------------------------------------------------
+inline bool Instruction::HasVRegH() const {
+  switch (FormatOf(Opcode())) {
+    case k45cc: return true;
+    case k4rcc: return true;
+    default : return false;
+  }
+}
+
+inline int32_t Instruction::VRegH() const {
+  switch (FormatOf(Opcode())) {
+    case k45cc: return VRegH_45cc();
+    case k4rcc: return VRegH_4rcc();
+    default :
+      LOG(FATAL) << "Tried to access vH of instruction " << Name() << " which has no H operand.";
+      exit(EXIT_FAILURE);
+  }
+}
+
+inline uint16_t Instruction::VRegH_45cc() const {
+  DCHECK_EQ(FormatOf(Opcode()), k45cc);
+  return Fetch16(3);
+}
+
+inline uint16_t Instruction::VRegH_4rcc() const {
+  DCHECK_EQ(FormatOf(Opcode()), k4rcc);
+  return Fetch16(3);
+}
+
 inline bool Instruction::HasVarArgs() const {
   return FormatOf(Opcode()) == k35c;
 }
 
-inline void Instruction::GetVarArgs(uint32_t arg[5], uint16_t inst_data) const {
+inline void Instruction::GetVarArgs(uint32_t arg[kMaxVarArgRegs], uint16_t inst_data) const {
   DCHECK_EQ(FormatOf(Opcode()), k35c);
 
   /*
diff --git a/runtime/dex_instruction.cc b/runtime/dex_instruction.cc
index fabc47b..c31d236 100644
--- a/runtime/dex_instruction.cc
+++ b/runtime/dex_instruction.cc
@@ -69,11 +69,12 @@
 
 int const Instruction::kInstructionSizeInCodeUnits[] = {
 #define INSTRUCTION_SIZE(opcode, c, p, format, i, a, v) \
-    (((opcode) == NOP)                        ? -1 :       \
-     (((format) >= k10x) && ((format) <= k10t)) ?  1 :     \
-     (((format) >= k20t) && ((format) <= k22c)) ?  2 :     \
-     (((format) >= k32x) && ((format) <= k3rc)) ?  3 :     \
-      ((format) == k51l)                      ?  5 : -1),
+    (((opcode) == NOP) ? -1 : \
+     (((format) >= k10x) && ((format) <= k10t)) ?  1 : \
+     (((format) >= k20t) && ((format) <= k22c)) ?  2 : \
+     (((format) >= k32x) && ((format) <= k3rc)) ?  3 : \
+     (((format) >= k45cc) && ((format) <= k4rcc)) ? 4 : \
+      ((format) == k51l) ?  5 : -1),
 #include "dex_instruction_list.h"
   DEX_INSTRUCTION_LIST(INSTRUCTION_SIZE)
 #undef DEX_INSTRUCTION_LIST
diff --git a/runtime/dex_instruction.h b/runtime/dex_instruction.h
index 1ac0f11..f437fde 100644
--- a/runtime/dex_instruction.h
+++ b/runtime/dex_instruction.h
@@ -112,6 +112,15 @@
     k31c,  // op vAA, thing@BBBBBBBB
     k35c,  // op {vC, vD, vE, vF, vG}, thing@BBBB (B: count, A: vG)
     k3rc,  // op {vCCCC .. v(CCCC+AA-1)}, meth@BBBB
+
+    // op {vC, vD, vE, vF, vG}, meth@BBBB, proto@HHHH (A: count)
+    // format: AG op BBBB FEDC HHHH
+    k45cc,
+
+    // op {VCCCC .. v(CCCC+AA-1)}, meth@BBBB, proto@HHHH (AA: count)
+    // format: AA op BBBB CCCC HHHH
+    k4rcc,  // op {VCCCC .. v(CCCC+AA-1)}, meth@BBBB, proto@HHHH (AA: count)
+
     k51l,  // op vAA, #+BBBBBBBBBBBBBBBB
   };
 
@@ -227,6 +236,12 @@
     return RelativeAt(3);
   }
 
+  // Returns a pointer to the instruction after this 4xx instruction in the stream.
+  const Instruction* Next_4xx() const {
+    DCHECK(FormatOf(Opcode()) >= k45cc && FormatOf(Opcode()) <= k4rcc);
+    return RelativeAt(4);
+  }
+
   // Returns a pointer to the instruction after this 51l instruction in the stream.
   const Instruction* Next_51l() const {
     DCHECK(FormatOf(Opcode()) == k51l);
@@ -313,6 +328,12 @@
   uint8_t VRegA_51l() const {
     return VRegA_51l(Fetch16(0));
   }
+  uint4_t VRegA_45cc() const {
+    return VRegA_45cc(Fetch16(0));
+  }
+  uint8_t VRegA_4rcc() const {
+    return VRegA_4rcc(Fetch16(0));
+  }
 
   // The following methods return the vA operand for various instruction formats. The "inst_data"
   // parameter holds the first 16 bits of instruction which the returned value is decoded from.
@@ -337,6 +358,8 @@
   uint4_t VRegA_35c(uint16_t inst_data) const;
   uint8_t VRegA_3rc(uint16_t inst_data) const;
   uint8_t VRegA_51l(uint16_t inst_data) const;
+  uint4_t VRegA_45cc(uint16_t inst_data) const;
+  uint8_t VRegA_4rcc(uint16_t inst_data) const;
 
   // VRegB
   bool HasVRegB() const;
@@ -374,6 +397,8 @@
   uint16_t VRegB_35c() const;
   uint16_t VRegB_3rc() const;
   uint64_t VRegB_51l() const;  // vB_wide
+  uint16_t VRegB_45cc() const;
+  uint16_t VRegB_4rcc() const;
 
   // The following methods return the vB operand for all instruction formats where it is encoded in
   // the first 16 bits of instruction. The "inst_data" parameter holds these 16 bits. The returned
@@ -395,6 +420,15 @@
   uint8_t VRegC_23x() const;
   uint4_t VRegC_35c() const;
   uint16_t VRegC_3rc() const;
+  uint4_t VRegC_45cc() const;
+  uint16_t VRegC_4rcc() const;
+
+
+  // VRegH
+  bool HasVRegH() const;
+  int32_t VRegH() const;
+  uint16_t VRegH_45cc() const;
+  uint16_t VRegH_4rcc() const;
 
   // Fills the given array with the 'arg' array of the instruction.
   bool HasVarArgs() const;
diff --git a/runtime/dex_instruction_list.h b/runtime/dex_instruction_list.h
index 40ea285..e974932 100644
--- a/runtime/dex_instruction_list.h
+++ b/runtime/dex_instruction_list.h
@@ -269,8 +269,9 @@
   V(0xF7, UNUSED_F7, "unused-f7", k10x, kIndexUnknown, 0, kVerifyError) \
   V(0xF8, UNUSED_F8, "unused-f8", k10x, kIndexUnknown, 0, kVerifyError) \
   V(0xF9, UNUSED_F9, "unused-f9", k10x, kIndexUnknown, 0, kVerifyError) \
-  V(0xFA, UNUSED_FA, "unused-fa", k10x, kIndexUnknown, 0, kVerifyError) \
-  V(0xFB, UNUSED_FB, "unused-fb", k10x, kIndexUnknown, 0, kVerifyError) \
+  /* TODO(narayan): The following two entries are placeholders. */ \
+  V(0xFA, INVOKE_POLYMORPHIC, "invoke-polymorphic", k45cc, kIndexUnknown, 0, kVerifyError) \
+  V(0xFB, INVOKE_POLYMORPHIC_RANGE, "invoke-polymorphic/range", k4rcc, kIndexUnknown, 0, kVerifyError) \
   V(0xFC, UNUSED_FC, "unused-fc", k10x, kIndexUnknown, 0, kVerifyError) \
   V(0xFD, UNUSED_FD, "unused-fd", k10x, kIndexUnknown, 0, kVerifyError) \
   V(0xFE, UNUSED_FE, "unused-fe", k10x, kIndexUnknown, 0, kVerifyError) \
diff --git a/runtime/dex_instruction_test.cc b/runtime/dex_instruction_test.cc
index 671ac0e..00c8e07 100644
--- a/runtime/dex_instruction_test.cc
+++ b/runtime/dex_instruction_test.cc
@@ -28,4 +28,96 @@
   EXPECT_EQ(Instruction::kVerifyNone, Instruction::VerifyFlagsOf(nop));
 }
 
+static void Build45cc(uint8_t num_args, uint16_t method_idx, uint16_t proto_idx,
+                      uint16_t arg_regs, uint16_t* out) {
+  // A = num argument registers
+  // B = method_idx
+  // C - G = argument registers
+  // H = proto_idx
+  //
+  // op = 0xFA
+  //
+  // format:
+  // AG op BBBB FEDC HHHH
+  out[0] = 0;
+  out[0] |= (num_args << 12);
+  out[0] |= 0x00FA;
+
+  out[1] = method_idx;
+  out[2] = arg_regs;
+  out[3] = proto_idx;
+}
+
+static void Build4rcc(uint16_t num_args, uint16_t method_idx, uint16_t proto_idx,
+                      uint16_t arg_regs_start, uint16_t* out) {
+  // A = num argument registers
+  // B = method_idx
+  // C = first argument register
+  // H = proto_idx
+  //
+  // op = 0xFB
+  //
+  // format:
+  // AA op BBBB CCCC HHHH
+  out[0] = 0;
+  out[0] |= (num_args << 8);
+  out[0] |= 0x00FB;
+
+  out[1] = method_idx;
+  out[2] = arg_regs_start;
+  out[3] = proto_idx;
+}
+
+TEST(Instruction, PropertiesOf45cc) {
+  uint16_t instruction[4];
+  Build45cc(4u /* num_vregs */, 16u /* method_idx */, 32u /* proto_idx */,
+            0xcafe /* arg_regs */, instruction);
+
+  const Instruction* ins = Instruction::At(instruction);
+  ASSERT_EQ(4u, ins->SizeInCodeUnits());
+
+  ASSERT_TRUE(ins->HasVRegA());
+  ASSERT_EQ(4, ins->VRegA());
+  ASSERT_EQ(4u, ins->VRegA_45cc());
+  ASSERT_EQ(4u, ins->VRegA_45cc(instruction[0]));
+
+  ASSERT_TRUE(ins->HasVRegB());
+  ASSERT_EQ(16, ins->VRegB());
+  ASSERT_EQ(16u, ins->VRegB_45cc());
+
+  ASSERT_TRUE(ins->HasVRegC());
+  ASSERT_EQ(0xe, ins->VRegC());
+  ASSERT_EQ(0xe, ins->VRegC_45cc());
+
+  ASSERT_TRUE(ins->HasVRegH());
+  ASSERT_EQ(32, ins->VRegH());
+  ASSERT_EQ(32, ins->VRegH_45cc());
+}
+
+TEST(Instruction, PropertiesOf4rcc) {
+  uint16_t instruction[4];
+  Build4rcc(4u /* num_vregs */, 16u /* method_idx */, 32u /* proto_idx */,
+            0xcafe /* arg_regs */, instruction);
+
+  const Instruction* ins = Instruction::At(instruction);
+  ASSERT_EQ(4u, ins->SizeInCodeUnits());
+
+  ASSERT_TRUE(ins->HasVRegA());
+  ASSERT_EQ(4, ins->VRegA());
+  ASSERT_EQ(4u, ins->VRegA_4rcc());
+  ASSERT_EQ(4u, ins->VRegA_4rcc(instruction[0]));
+
+  ASSERT_TRUE(ins->HasVRegB());
+  ASSERT_EQ(16, ins->VRegB());
+  ASSERT_EQ(16u, ins->VRegB_4rcc());
+
+  ASSERT_TRUE(ins->HasVRegC());
+  ASSERT_EQ(0xcafe, ins->VRegC());
+  ASSERT_EQ(0xcafe, ins->VRegC_4rcc());
+
+  ASSERT_TRUE(ins->HasVRegH());
+  ASSERT_EQ(32, ins->VRegH());
+  ASSERT_EQ(32, ins->VRegH_4rcc());
+}
+
 }  // namespace art
diff --git a/runtime/interpreter/interpreter_switch_impl.cc b/runtime/interpreter/interpreter_switch_impl.cc
index 3623db2..a6349fc 100644
--- a/runtime/interpreter/interpreter_switch_impl.cc
+++ b/runtime/interpreter/interpreter_switch_impl.cc
@@ -2322,9 +2322,12 @@
         inst = inst->Next_2xx();
         break;
       case Instruction::UNUSED_3E ... Instruction::UNUSED_43:
-      case Instruction::UNUSED_F3 ... Instruction::UNUSED_FF:
+      case Instruction::UNUSED_F3 ... Instruction::UNUSED_F9:
+      case Instruction::UNUSED_FC ... Instruction::UNUSED_FF:
       case Instruction::UNUSED_79:
       case Instruction::UNUSED_7A:
+      case Instruction::INVOKE_POLYMORPHIC:
+      case Instruction::INVOKE_POLYMORPHIC_RANGE:
         UnexpectedOpcode(inst, shadow_frame);
     }
   } while (!interpret_one_instruction);
diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc
index daf5ec4..40f12e9 100644
--- a/runtime/verifier/method_verifier.cc
+++ b/runtime/verifier/method_verifier.cc
@@ -3331,9 +3331,12 @@
 
     /* These should never appear during verification. */
     case Instruction::UNUSED_3E ... Instruction::UNUSED_43:
-    case Instruction::UNUSED_F3 ... Instruction::UNUSED_FF:
+    case Instruction::UNUSED_F3 ... Instruction::UNUSED_F9:
+    case Instruction::UNUSED_FC ... Instruction::UNUSED_FF:
     case Instruction::UNUSED_79:
     case Instruction::UNUSED_7A:
+    case Instruction::INVOKE_POLYMORPHIC:
+    case Instruction::INVOKE_POLYMORPHIC_RANGE:
       Fail(VERIFY_ERROR_BAD_CLASS_HARD) << "Unexpected opcode " << inst->DumpString(dex_file_);
       break;