diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index e2ba867..ac07721 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -140,6 +140,7 @@
   compiler/jni/jni_compiler_test.cc \
   compiler/oat_test.cc \
   compiler/optimizing/codegen_test.cc \
+  compiler/optimizing/dead_code_elimination_test.cc \
   compiler/optimizing/dominator_test.cc \
   compiler/optimizing/find_loops_test.cc \
   compiler/optimizing/graph_checker_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index f76b66a..3d433d5 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -90,6 +90,7 @@
 	optimizing/code_generator_arm.cc \
 	optimizing/code_generator_x86.cc \
 	optimizing/code_generator_x86_64.cc \
+	optimizing/dead_code_elimination.cc \
 	optimizing/graph_checker.cc \
 	optimizing/graph_visualizer.cc \
 	optimizing/locations.cc \
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
new file mode 100644
index 0000000..2f881d1
--- /dev/null
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "dead_code_elimination.h"
+
+#include "base/bit_vector-inl.h"
+
+namespace art {
+
+void DeadCodeElimination::Run() {
+  // Process basic blocks in post-order in the dominator tree, so that
+  // a dead instruction depending on another dead instruction is
+  // removed.
+  for (HPostOrderIterator b(*graph_); !b.Done(); b.Advance()) {
+    HBasicBlock* block = b.Current();
+    // Traverse this block's instructions in backward order and remove
+    // the unused ones.
+    HBackwardInstructionIterator i(block->GetInstructions());
+    // Skip the first iteration, as the last instruction of a block is
+    // a branching instruction.
+    DCHECK(i.Current()->IsControlFlow());
+    for (i.Advance(); !i.Done(); i.Advance()) {
+      HInstruction* inst = i.Current();
+      DCHECK(!inst->IsControlFlow());
+      if (!inst->HasSideEffects() && !inst->HasUses()) {
+        block->RemoveInstruction(inst);
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
new file mode 100644
index 0000000..48739be
--- /dev/null
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
+#define ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
+
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * Optimization pass performing dead code elimination (removal of
+ * unused variables/instructions) on the SSA form.
+ */
+class DeadCodeElimination : public ValueObject {
+ public:
+  explicit DeadCodeElimination(HGraph* graph)
+      : graph_(graph) {}
+
+  void Run();
+
+ private:
+  HGraph* const graph_;
+
+  DISALLOW_COPY_AND_ASSIGN(DeadCodeElimination);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
new file mode 100644
index 0000000..245bcb2
--- /dev/null
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -0,0 +1,185 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "dead_code_elimination.h"
+#include "pretty_printer.h"
+#include "graph_checker.h"
+#include "optimizing_unit_test.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data,
+                     const std::string& expected_before,
+                     const std::string& expected_after) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateCFG(&allocator, data);
+  ASSERT_NE(graph, nullptr);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+
+  StringPrettyPrinter printer_before(graph);
+  printer_before.VisitInsertionOrder();
+  std::string actual_before = printer_before.str();
+  ASSERT_EQ(actual_before, expected_before);
+
+  DeadCodeElimination(graph).Run();
+
+  StringPrettyPrinter printer_after(graph);
+  printer_after.VisitInsertionOrder();
+  std::string actual_after = printer_after.str();
+  ASSERT_EQ(actual_after, expected_after);
+
+  SSAChecker ssa_checker(&allocator, graph);
+  ssa_checker.VisitInsertionOrder();
+  ASSERT_TRUE(ssa_checker.IsValid());
+}
+
+
+/**
+ * Small three-register program.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v1 <- 1                  0.      const/4 v1, #+1
+ *     v0 <- 0                  1.      const/4 v0, #+0
+ *     if v1 >= 0 goto L1       2.      if-gez v1, +3
+ *     v0 <- v1                 4.      move v0, v1
+ * L1: v2 <- v0 + v1            5.      add-int v2, v0, v1
+ *     return-void              7.      return
+ */
+TEST(DeadCodeElimination, AdditionAndConditionalJump) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::CONST_4 | 0 << 8 | 0 << 12,
+    Instruction::IF_GEZ | 1 << 8, 3,
+    Instruction::MOVE | 0 << 8 | 1 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::RETURN_VOID);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [15, 22, 8]\n"
+    "  5: IntConstant [22, 8]\n"
+    "  19: SuspendCheck\n"
+    "  20: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 5, 2\n"
+    "  8: GreaterThanOrEqual(3, 5) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  12: Goto 3\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
+    "  22: Phi(3, 5) [15]\n"
+    "  15: Add(22, 3)\n"
+    "  17: ReturnVoid\n"
+    "BasicBlock 4, pred: 3\n"
+    "  18: Exit\n"
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  21: Goto 3\n";
+
+  diff_t expected_diff = {
+    { "  3: IntConstant [15, 22, 8]\n", "  3: IntConstant [22, 8]\n" },
+    { "  22: Phi(3, 5) [15]\n",         "  22: Phi(3, 5)\n" },
+    { "  15: Add(22, 3)\n",             removed }
+  };
+  std::string expected_after = Patch(expected_before, expected_diff);
+
+  TestCode(data, expected_before, expected_after);
+}
+
+/**
+ * Three-register program with jumps leading to the creation of many
+ * blocks.
+ *
+ * The intent of this test is to ensure that all dead instructions are
+ * actually pruned at compile-time, thanks to the (backward)
+ * post-order traversal of the the dominator tree.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v0 <- 0                   0.     const/4 v0, #+0
+ *     v1 <- 1                   1.     const/4 v1, #+1
+ *     v2 <- v0 + v1             2.     add-int v2, v0, v1
+ *     goto L2                   4.     goto +4
+ * L1: v1 <- v0 + 3              5.     add-int/lit16 v1, v0, #+3
+ *     goto L3                   7.     goto +4
+ * L2: v0 <- v2 + 2              8.     add-int/lit16 v0, v2, #+2
+ *     goto L1                  10.     goto +(-5)
+ * L3: v2 <- v1 + 4             11.     add-int/lit16 v2, v1, #+4
+ *     return                   13.     return-void
+ */
+TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 8 | 0 << 12,
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::GOTO | 4 << 8,
+    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
+    Instruction::GOTO | 4 << 8,
+    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
+    static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
+    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
+    Instruction::RETURN_VOID);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [9]\n"
+    "  5: IntConstant [9]\n"
+    "  13: IntConstant [14]\n"
+    "  18: IntConstant [19]\n"
+    "  24: IntConstant [25]\n"
+    "  29: SuspendCheck\n"
+    "  30: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 3\n"
+    "  9: Add(3, 5) [19]\n"
+    "  11: Goto 3\n"
+    "BasicBlock 2, pred: 3, succ: 4\n"
+    "  14: Add(19, 13) [25]\n"
+    "  16: Goto 4\n"
+    "BasicBlock 3, pred: 1, succ: 2\n"
+    "  19: Add(9, 18) [14]\n"
+    "  21: SuspendCheck\n"
+    "  22: Goto 2\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  25: Add(14, 24)\n"
+    "  27: ReturnVoid\n"
+    "BasicBlock 5, pred: 4\n"
+    "  28: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_diff = {
+    { "  13: IntConstant [14]\n", removed },
+    { "  24: IntConstant [25]\n", removed },
+    { "  14: Add(19, 13) [25]\n", removed },
+    // The SuspendCheck instruction following this Add instruction
+    // inserts the latter in an environment, thus making it "used" and
+    // therefore non removable.  It ensues that some other Add and
+    // IntConstant instructions cannot be removed, as they are direct
+    // or indirect inputs of the initial Add instruction.
+    { "  19: Add(9, 18) [14]\n",  "  19: Add(9, 18) []\n" },
+    { "  25: Add(14, 24)\n",      removed },
+  };
+  std::string expected_after = Patch(expected_before, expected_diff);
+
+  TestCode(data, expected_before, expected_after);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index eebd64b..9741f71 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -513,6 +513,11 @@
     return SideEffects(((1 << count) - 1) << kFlagChangesCount);
   }
 
+  bool HasSideEffects() const {
+    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+    return (flags_ & all_bits_set) != 0;
+  }
+
  private:
   static constexpr int kFlagChangesSomething = 0;
   static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
@@ -564,6 +569,7 @@
 
   virtual bool NeedsEnvironment() const { return false; }
   virtual bool IsControlFlow() const { return false; }
+  bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
 
   void AddUseAt(HInstruction* user, size_t index) {
     uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 1b930ec..6dd53e5 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -23,6 +23,8 @@
 #include "dex_instruction.h"
 #include "ssa_liveness_analysis.h"
 
+#include "gtest/gtest.h"
+
 namespace art {
 
 #define NUM_INSTRUCTIONS(...)  \
@@ -74,6 +76,24 @@
   return graph;
 }
 
+// Naive string diff data type.
+typedef std::list<std::pair<std::string, std::string>> diff_t;
+
+// An alias for the empty string used to make it clear that a line is
+// removed in a diff.
+static const std::string removed = "";
+
+// Naive patch command: apply a diff to a string.
+inline std::string Patch(const std::string& original, const diff_t& diff) {
+  std::string result = original;
+  for (const auto& p : diff) {
+    std::string::size_type pos = result.find(p.first);
+    EXPECT_NE(pos, std::string::npos);
+    result.replace(pos, p.first.size(), p.second);
+  }
+  return result;
+}
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_