diff --git a/compiler/optimizing/scheduler.h b/compiler/optimizing/scheduler.h
new file mode 100644
index 0000000..ab0dad4
--- /dev/null
+++ b/compiler/optimizing/scheduler.h
@@ -0,0 +1,487 @@
+/*
+ * Copyright (C) 2016 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_SCHEDULER_H_
+#define ART_COMPILER_OPTIMIZING_SCHEDULER_H_
+
+#include <fstream>
+
+#include "base/time_utils.h"
+#include "driver/compiler_driver.h"
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+// General description of instruction scheduling.
+//
+// This pass tries to improve the quality of the generated code by reordering
+// instructions in the graph to avoid execution delays caused by execution
+// dependencies.
+// Currently, scheduling is performed at the block level, so no `HInstruction`
+// ever leaves its block in this pass.
+//
+// The scheduling process iterates through blocks in the graph. For blocks that
+// we can and want to schedule:
+// 1) Build a dependency graph for instructions.
+//    It includes data dependencies (inputs/uses), but also environment
+//    dependencies and side-effect dependencies.
+// 2) Schedule the dependency graph.
+//    This is a topological sort of the dependency graph, using heuristics to
+//    decide what node to scheduler first when there are multiple candidates.
+//
+// A few factors impacting the quality of the scheduling are:
+// - The heuristics used to decide what node to schedule in the topological sort
+//   when there are multiple valid candidates. There is a wide range of
+//   complexity possible here, going from a simple model only considering
+//   latencies, to a super detailed CPU pipeline model.
+// - Fewer dependencies in the dependency graph give more freedom for the
+//   scheduling heuristics. For example de-aliasing can allow possibilities for
+//   reordering of memory accesses.
+// - The level of abstraction of the IR. It is easier to evaluate scheduling for
+//   IRs that translate to a single assembly instruction than for IRs
+//   that generate multiple assembly instructions or generate different code
+//   depending on properties of the IR.
+// - Scheduling is performed before register allocation, it is not aware of the
+//   impact of moving instructions on register allocation.
+//
+//
+// The scheduling code uses the terms predecessors, successors, and dependencies.
+// This can be confusing at times, so here are clarifications.
+// These terms are used from the point of view of the program dependency graph. So
+// the inputs of an instruction are part of its dependencies, and hence part its
+// predecessors. So the uses of an instruction are (part of) its successors.
+// (Side-effect dependencies can yield predecessors or successors that are not
+// inputs or uses.)
+//
+// Here is a trivial example. For the Java code:
+//
+//    int a = 1 + 2;
+//
+// we would have the instructions
+//
+//    i1 HIntConstant 1
+//    i2 HIntConstant 2
+//    i3 HAdd [i1,i2]
+//
+// `i1` and `i2` are predecessors of `i3`.
+// `i3` is a successor of `i1` and a successor of `i2`.
+// In a scheduling graph for this code we would have three nodes `n1`, `n2`,
+// and `n3` (respectively for instructions `i1`, `i1`, and `i3`).
+// Conceptually the program dependency graph for this would contain two edges
+//
+//    n1 -> n3
+//    n2 -> n3
+//
+// Since we schedule backwards (starting from the last instruction in each basic
+// block), the implementation of nodes keeps a list of pointers their
+// predecessors. So `n3` would keep pointers to its predecessors `n1` and `n2`.
+//
+// Node dependencies are also referred to from the program dependency graph
+// point of view: we say that node `B` immediately depends on `A` if there is an
+// edge from `A` to `B` in the program dependency graph. `A` is a predecessor of
+// `B`, `B` is a successor of `A`. In the example above `n3` depends on `n1` and
+// `n2`.
+// Since nodes in the scheduling graph keep a list of their predecessors, node
+// `B` will have a pointer to its predecessor `A`.
+// As we schedule backwards, `B` will be selected for scheduling before `A` is.
+//
+// So the scheduling for the example above could happen as follow
+//
+//    |---------------------------+------------------------|
+//    | candidates for scheduling | instructions scheduled |
+//    | --------------------------+------------------------|
+//
+// The only node without successors is `n3`, so it is the only initial
+// candidate.
+//
+//    | n3                        | (none)                 |
+//
+// We schedule `n3` as the last (and only) instruction. All its predecessors
+// that do not have any unscheduled successors become candidate. That is, `n1`
+// and `n2` become candidates.
+//
+//    | n1, n2                    | n3                     |
+//
+// One of the candidates is selected. In practice this is where scheduling
+// heuristics kick in, to decide which of the candidates should be selected.
+// In this example, let it be `n1`. It is scheduled before previously scheduled
+// nodes (in program order). There are no other nodes to add to the list of
+// candidates.
+//
+//    | n2                        | n1                     |
+//    |                           | n3                     |
+//
+// The only candidate available for scheduling is `n2`. Schedule it before
+// (in program order) the previously scheduled nodes.
+//
+//    | (none)                    | n2                     |
+//    |                           | n1                     |
+//    |                           | n3                     |
+//    |---------------------------+------------------------|
+//
+// So finally the instructions will be executed in the order `i2`, `i1`, and `i3`.
+// In this trivial example, it does not matter which of `i1` and `i2` is
+// scheduled first since they are constants. However the same process would
+// apply if `i1` and `i2` were actual operations (for example `HMul` and `HDiv`).
+
+// Set to true to have instruction scheduling dump scheduling graphs to the file
+// `scheduling_graphs.dot`. See `SchedulingGraph::DumpAsDotGraph()`.
+static constexpr bool kDumpDotSchedulingGraphs = false;
+
+// Typically used as a default instruction latency.
+static constexpr uint32_t kGenericInstructionLatency = 1;
+
+class HScheduler;
+
+/**
+ * A node representing an `HInstruction` in the `SchedulingGraph`.
+ */
+class SchedulingNode : public ArenaObject<kArenaAllocScheduler> {
+ public:
+  SchedulingNode(HInstruction* instr, ArenaAllocator* arena, bool is_scheduling_barrier)
+      : latency_(0),
+        internal_latency_(0),
+        critical_path_(0),
+        instruction_(instr),
+        is_scheduling_barrier_(is_scheduling_barrier),
+        data_predecessors_(arena->Adapter(kArenaAllocScheduler)),
+        other_predecessors_(arena->Adapter(kArenaAllocScheduler)),
+        num_unscheduled_successors_(0) {
+    data_predecessors_.reserve(kPreallocatedPredecessors);
+  }
+
+  void AddDataPredecessor(SchedulingNode* predecessor) {
+    data_predecessors_.push_back(predecessor);
+    predecessor->num_unscheduled_successors_++;
+  }
+
+  void AddOtherPredecessor(SchedulingNode* predecessor) {
+    other_predecessors_.push_back(predecessor);
+    predecessor->num_unscheduled_successors_++;
+  }
+
+  void DecrementNumberOfUnscheduledSuccessors() {
+    num_unscheduled_successors_--;
+  }
+
+  void MaybeUpdateCriticalPath(uint32_t other_critical_path) {
+    critical_path_ = std::max(critical_path_, other_critical_path);
+  }
+
+  bool HasUnscheduledSuccessors() const {
+    return num_unscheduled_successors_ != 0;
+  }
+
+  HInstruction* GetInstruction() const { return instruction_; }
+  uint32_t GetLatency() const { return latency_; }
+  void SetLatency(uint32_t latency) { latency_ = latency; }
+  uint32_t GetInternalLatency() const { return internal_latency_; }
+  void SetInternalLatency(uint32_t internal_latency) { internal_latency_ = internal_latency; }
+  uint32_t GetCriticalPath() const { return critical_path_; }
+  bool IsSchedulingBarrier() const { return is_scheduling_barrier_; }
+  const ArenaVector<SchedulingNode*>& GetDataPredecessors() const { return data_predecessors_; }
+  const ArenaVector<SchedulingNode*>& GetOtherPredecessors() const { return other_predecessors_; }
+
+ private:
+  // The latency of this node. It represents the latency between the moment the
+  // last instruction for this node has executed to the moment the result
+  // produced by this node is available to users.
+  uint32_t latency_;
+  // This represents the time spent *within* the generated code for this node.
+  // It should be zero for nodes that only generate a single instruction.
+  uint32_t internal_latency_;
+
+  // The critical path from this instruction to the end of scheduling. It is
+  // used by the scheduling heuristics to measure the priority of this instruction.
+  // It is defined as
+  //     critical_path_ = latency_ + max((use.internal_latency_ + use.critical_path_) for all uses)
+  // (Note that here 'uses' is equivalent to 'data successors'. Also see comments in
+  // `HScheduler::Schedule(SchedulingNode* scheduling_node)`).
+  uint32_t critical_path_;
+
+  // The instruction that this node represents.
+  HInstruction* const instruction_;
+
+  // If a node is scheduling barrier, other nodes cannot be scheduled before it.
+  const bool is_scheduling_barrier_;
+
+  // The lists of predecessors. They cannot be scheduled before this node. Once
+  // this node is scheduled, we check whether any of its predecessors has become a
+  // valid candidate for scheduling.
+  // Predecessors in `data_predecessors_` are data dependencies. Those in
+  // `other_predecessors_` contain side-effect dependencies, environment
+  // dependencies, and scheduling barrier dependencies.
+  ArenaVector<SchedulingNode*> data_predecessors_;
+  ArenaVector<SchedulingNode*> other_predecessors_;
+
+  // The number of unscheduled successors for this node. This number is
+  // decremented as successors are scheduled. When it reaches zero this node
+  // becomes a valid candidate to schedule.
+  uint32_t num_unscheduled_successors_;
+
+  static constexpr size_t kPreallocatedPredecessors = 4;
+};
+
+/*
+ * Directed acyclic graph for scheduling.
+ */
+class SchedulingGraph : public ValueObject {
+ public:
+  SchedulingGraph(const HScheduler* scheduler, ArenaAllocator* arena)
+      : scheduler_(scheduler),
+        arena_(arena),
+        contains_scheduling_barrier_(false),
+        nodes_map_(arena_->Adapter(kArenaAllocScheduler)) {}
+
+  SchedulingNode* AddNode(HInstruction* instr, bool is_scheduling_barrier = false) {
+    SchedulingNode* node = new (arena_) SchedulingNode(instr, arena_, is_scheduling_barrier);
+    nodes_map_.Insert(std::make_pair(instr, node));
+    contains_scheduling_barrier_ |= is_scheduling_barrier;
+    AddDependencies(instr, is_scheduling_barrier);
+    return node;
+  }
+
+  void Clear() {
+    nodes_map_.Clear();
+    contains_scheduling_barrier_ = false;
+  }
+
+  SchedulingNode* GetNode(const HInstruction* instr) const {
+    auto it = nodes_map_.Find(instr);
+    if (it == nodes_map_.end()) {
+      return nullptr;
+    } else {
+      return it->second;
+    }
+  }
+
+  bool IsSchedulingBarrier(const HInstruction* instruction) const;
+
+  bool HasImmediateDataDependency(const SchedulingNode* node, const SchedulingNode* other) const;
+  bool HasImmediateDataDependency(const HInstruction* node, const HInstruction* other) const;
+  bool HasImmediateOtherDependency(const SchedulingNode* node, const SchedulingNode* other) const;
+  bool HasImmediateOtherDependency(const HInstruction* node, const HInstruction* other) const;
+
+  size_t Size() const {
+    return nodes_map_.Size();
+  }
+
+  // Dump the scheduling graph, in dot file format, appending it to the file
+  // `scheduling_graphs.dot`.
+  void DumpAsDotGraph(const std::string& description,
+                      const ArenaVector<SchedulingNode*>& initial_candidates);
+
+ protected:
+  void AddDependency(SchedulingNode* node, SchedulingNode* dependency, bool is_data_dependency);
+  void AddDataDependency(SchedulingNode* node, SchedulingNode* dependency) {
+    AddDependency(node, dependency, /*is_data_dependency*/true);
+  }
+  void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) {
+    AddDependency(node, dependency, /*is_data_dependency*/false);
+  }
+
+  // Add dependencies nodes for the given `HInstruction`: inputs, environments, and side-effects.
+  void AddDependencies(HInstruction* instruction, bool is_scheduling_barrier = false);
+
+  const HScheduler* const scheduler_;
+
+  ArenaAllocator* const arena_;
+
+  bool contains_scheduling_barrier_;
+
+  ArenaHashMap<const HInstruction*, SchedulingNode*> nodes_map_;
+};
+
+/*
+ * The visitors derived from this base class are used by schedulers to evaluate
+ * the latencies of `HInstruction`s.
+ */
+class SchedulingLatencyVisitor : public HGraphDelegateVisitor {
+ public:
+  // This class and its sub-classes will never be used to drive a visit of an
+  // `HGraph` but only to visit `HInstructions` one at a time, so we do not need
+  // to pass a valid graph to `HGraphDelegateVisitor()`.
+  SchedulingLatencyVisitor() : HGraphDelegateVisitor(nullptr) {}
+
+  void VisitInstruction(HInstruction* instruction) OVERRIDE {
+    LOG(FATAL) << "Error visiting " << instruction->DebugName() << ". "
+        "Architecture-specific scheduling latency visitors must handle all instructions"
+        " (potentially by overriding the generic `VisitInstruction()`.";
+    UNREACHABLE();
+  }
+
+  void Visit(HInstruction* instruction) {
+    instruction->Accept(this);
+  }
+
+  void CalculateLatency(SchedulingNode* node) {
+    // By default nodes have no internal latency.
+    last_visited_internal_latency_ = 0;
+    Visit(node->GetInstruction());
+  }
+
+  uint32_t GetLastVisitedLatency() const { return last_visited_latency_; }
+  uint32_t GetLastVisitedInternalLatency() const { return last_visited_internal_latency_; }
+
+ protected:
+  // The latency of the most recent visited SchedulingNode.
+  // This is for reporting the latency value to the user of this visitor.
+  uint32_t last_visited_latency_;
+  // This represents the time spent *within* the generated code for the most recent visited
+  // SchedulingNode. This is for reporting the internal latency value to the user of this visitor.
+  uint32_t last_visited_internal_latency_;
+};
+
+class SchedulingNodeSelector : public ArenaObject<kArenaAllocScheduler> {
+ public:
+  virtual SchedulingNode* PopHighestPriorityNode(ArenaVector<SchedulingNode*>* nodes,
+                                                 const SchedulingGraph& graph) = 0;
+  virtual ~SchedulingNodeSelector() {}
+ protected:
+  static void DeleteNodeAtIndex(ArenaVector<SchedulingNode*>* nodes, size_t index) {
+    (*nodes)[index] = nodes->back();
+    nodes->pop_back();
+  }
+};
+
+/*
+ * Select a `SchedulingNode` at random within the candidates.
+ */
+class RandomSchedulingNodeSelector : public SchedulingNodeSelector {
+ public:
+  explicit RandomSchedulingNodeSelector() : seed_(0) {
+    seed_  = static_cast<uint32_t>(NanoTime());
+    srand(seed_);
+  }
+
+  SchedulingNode* PopHighestPriorityNode(ArenaVector<SchedulingNode*>* nodes,
+                                         const SchedulingGraph& graph) OVERRIDE {
+    UNUSED(graph);
+    DCHECK(!nodes->empty());
+    size_t select = rand_r(&seed_) % nodes->size();
+    SchedulingNode* select_node = (*nodes)[select];
+    DeleteNodeAtIndex(nodes, select);
+    return select_node;
+  }
+
+  uint32_t seed_;
+};
+
+/*
+ * Select a `SchedulingNode` according to critical path information,
+ * with heuristics to favor certain instruction patterns like materialized condition.
+ */
+class CriticalPathSchedulingNodeSelector : public SchedulingNodeSelector {
+ public:
+  CriticalPathSchedulingNodeSelector() : prev_select_(nullptr) {}
+
+  SchedulingNode* PopHighestPriorityNode(ArenaVector<SchedulingNode*>* nodes,
+                                         const SchedulingGraph& graph) OVERRIDE;
+
+ protected:
+  SchedulingNode* GetHigherPrioritySchedulingNode(SchedulingNode* candidate,
+                                                  SchedulingNode* check) const;
+
+  SchedulingNode* SelectMaterializedCondition(ArenaVector<SchedulingNode*>* nodes,
+                                               const SchedulingGraph& graph) const;
+
+ private:
+  const SchedulingNode* prev_select_;
+};
+
+class HScheduler {
+ public:
+  HScheduler(ArenaAllocator* arena,
+             SchedulingLatencyVisitor* latency_visitor,
+             SchedulingNodeSelector* selector)
+      : arena_(arena),
+        latency_visitor_(latency_visitor),
+        selector_(selector),
+        only_optimize_loop_blocks_(true),
+        scheduling_graph_(this, arena),
+        candidates_(arena_->Adapter(kArenaAllocScheduler)) {}
+  virtual ~HScheduler() {}
+
+  void Schedule(HGraph* graph);
+
+  void SetOnlyOptimizeLoopBlocks(bool loop_only) { only_optimize_loop_blocks_ = loop_only; }
+
+  // Instructions can not be rescheduled across a scheduling barrier.
+  virtual bool IsSchedulingBarrier(const HInstruction* instruction) const;
+
+ protected:
+  void Schedule(HBasicBlock* block);
+  void Schedule(SchedulingNode* scheduling_node);
+  void Schedule(HInstruction* instruction);
+
+  // Any instruction returning `false` via this method will prevent its
+  // containing basic block from being scheduled.
+  // This method is used to restrict scheduling to instructions that we know are
+  // safe to handle.
+  virtual bool IsSchedulable(const HInstruction* instruction) const;
+  bool IsSchedulable(const HBasicBlock* block) const;
+
+  void CalculateLatency(SchedulingNode* node) {
+    latency_visitor_->CalculateLatency(node);
+    node->SetLatency(latency_visitor_->GetLastVisitedLatency());
+    node->SetInternalLatency(latency_visitor_->GetLastVisitedInternalLatency());
+  }
+
+  ArenaAllocator* const arena_;
+  SchedulingLatencyVisitor* const latency_visitor_;
+  SchedulingNodeSelector* const selector_;
+  bool only_optimize_loop_blocks_;
+
+  // We instantiate the members below as part of this class to avoid
+  // instantiating them locally for every chunk scheduled.
+  SchedulingGraph scheduling_graph_;
+  // A pointer indicating where the next instruction to be scheduled will be inserted.
+  HInstruction* cursor_;
+  // The list of candidates for scheduling. A node becomes a candidate when all
+  // its predecessors have been scheduled.
+  ArenaVector<SchedulingNode*> candidates_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HScheduler);
+};
+
+inline bool SchedulingGraph::IsSchedulingBarrier(const HInstruction* instruction) const {
+  return scheduler_->IsSchedulingBarrier(instruction);
+}
+
+class HInstructionScheduling : public HOptimization {
+ public:
+  HInstructionScheduling(HGraph* graph, InstructionSet instruction_set)
+      : HOptimization(graph, kInstructionScheduling),
+        instruction_set_(instruction_set) {}
+
+  void Run() {
+    Run(/*only_optimize_loop_blocks*/ true, /*schedule_randomly*/ false);
+  }
+  void Run(bool only_optimize_loop_blocks, bool schedule_randomly);
+
+  static constexpr const char* kInstructionScheduling = "scheduler";
+
+  const InstructionSet instruction_set_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HInstructionScheduling);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_SCHEDULER_H_