diff --git a/compiler/Android.mk b/compiler/Android.mk
index 7ac1c6b..2ccc1fb 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -125,7 +125,6 @@
 	buffered_output_stream.cc \
 	compiler.cc \
 	elf_fixup.cc \
-	elf_patcher.cc \
 	elf_stripper.cc \
 	elf_writer.cc \
 	elf_writer_quick.cc \
diff --git a/compiler/compiled_method.cc b/compiler/compiled_method.cc
index ba5bd30..698bf3b 100644
--- a/compiler/compiled_method.cc
+++ b/compiler/compiled_method.cc
@@ -152,14 +152,16 @@
                                const std::vector<uint8_t>& mapping_table,
                                const std::vector<uint8_t>& vmap_table,
                                const std::vector<uint8_t>& native_gc_map,
-                               const std::vector<uint8_t>* cfi_info)
+                               const std::vector<uint8_t>* cfi_info,
+                               const ArrayRef<LinkerPatch>& patches)
     : CompiledCode(driver, instruction_set, quick_code), frame_size_in_bytes_(frame_size_in_bytes),
       core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask),
       src_mapping_table_(driver->DeduplicateSrcMappingTable(src_mapping_table->Arrange())),
       mapping_table_(driver->DeduplicateMappingTable(mapping_table)),
       vmap_table_(driver->DeduplicateVMapTable(vmap_table)),
       gc_map_(driver->DeduplicateGCMap(native_gc_map)),
-      cfi_info_(driver->DeduplicateCFIInfo(cfi_info)) {
+      cfi_info_(driver->DeduplicateCFIInfo(cfi_info)),
+      patches_(patches.begin(), patches.end()) {
 }
 
 CompiledMethod::CompiledMethod(CompilerDriver* driver,
@@ -178,7 +180,8 @@
       mapping_table_(driver->DeduplicateMappingTable(mapping_table)),
       vmap_table_(driver->DeduplicateVMapTable(stack_map)),
       gc_map_(nullptr),
-      cfi_info_(nullptr) {
+      cfi_info_(nullptr),
+      patches_() {
 }
 
 CompiledMethod::CompiledMethod(CompilerDriver* driver,
@@ -195,7 +198,8 @@
       mapping_table_(driver->DeduplicateMappingTable(std::vector<uint8_t>())),
       vmap_table_(driver->DeduplicateVMapTable(std::vector<uint8_t>())),
       gc_map_(driver->DeduplicateGCMap(std::vector<uint8_t>())),
-      cfi_info_(driver->DeduplicateCFIInfo(cfi_info)) {
+      cfi_info_(driver->DeduplicateCFIInfo(cfi_info)),
+      patches_() {
 }
 
 // Constructs a CompiledMethod for the Portable compiler.
@@ -208,7 +212,9 @@
       src_mapping_table_(driver->DeduplicateSrcMappingTable(SrcMap())),
       mapping_table_(driver->DeduplicateMappingTable(std::vector<uint8_t>())),
       vmap_table_(driver->DeduplicateVMapTable(std::vector<uint8_t>())),
-      gc_map_(driver->DeduplicateGCMap(gc_map)) {
+      gc_map_(driver->DeduplicateGCMap(gc_map)),
+      cfi_info_(nullptr),
+      patches_() {
 }
 
 CompiledMethod::CompiledMethod(CompilerDriver* driver, InstructionSet instruction_set,
@@ -219,7 +225,9 @@
       src_mapping_table_(driver->DeduplicateSrcMappingTable(SrcMap())),
       mapping_table_(driver->DeduplicateMappingTable(std::vector<uint8_t>())),
       vmap_table_(driver->DeduplicateVMapTable(std::vector<uint8_t>())),
-      gc_map_(driver->DeduplicateGCMap(std::vector<uint8_t>())) {
+      gc_map_(driver->DeduplicateGCMap(std::vector<uint8_t>())),
+      cfi_info_(nullptr),
+      patches_() {
 }
 
 }  // namespace art
diff --git a/compiler/compiled_method.h b/compiler/compiled_method.h
index cc46b92..cdae8d2 100644
--- a/compiler/compiled_method.h
+++ b/compiler/compiled_method.h
@@ -22,7 +22,9 @@
 #include <vector>
 
 #include "instruction_set.h"
+#include "method_reference.h"
 #include "utils.h"
+#include "utils/array_ref.h"
 
 namespace llvm {
   class Function;
@@ -171,6 +173,101 @@
   }
 };
 
+enum LinkerPatchType {
+  kLinkerPatchMethod,
+  kLinkerPatchCall,
+  kLinkerPatchCallRelative,  // NOTE: Actual patching is instruction_set-dependent.
+  kLinkerPatchType,
+};
+
+class LinkerPatch {
+ public:
+  static LinkerPatch MethodPatch(size_t literal_offset,
+                                 const DexFile* target_dex_file,
+                                 uint32_t target_method_idx) {
+    return LinkerPatch(literal_offset, kLinkerPatchMethod,
+                       target_method_idx, target_dex_file);
+  }
+
+  static LinkerPatch CodePatch(size_t literal_offset,
+                               const DexFile* target_dex_file,
+                               uint32_t target_method_idx) {
+    return LinkerPatch(literal_offset, kLinkerPatchCall,
+                       target_method_idx, target_dex_file);
+  }
+
+  static LinkerPatch RelativeCodePatch(size_t literal_offset,
+                                       const DexFile* target_dex_file,
+                                       uint32_t target_method_idx) {
+    return LinkerPatch(literal_offset, kLinkerPatchCallRelative,
+                       target_method_idx, target_dex_file);
+  }
+
+  static LinkerPatch TypePatch(size_t literal_offset,
+                               const DexFile* target_dex_file,
+                               uint32_t target_type_idx) {
+    return LinkerPatch(literal_offset, kLinkerPatchType, target_type_idx, target_dex_file);
+  }
+
+  LinkerPatch(const LinkerPatch& other) = default;
+  LinkerPatch& operator=(const LinkerPatch& other) = default;
+
+  size_t LiteralOffset() const {
+    return literal_offset_;
+  }
+
+  LinkerPatchType Type() const {
+    return patch_type_;
+  }
+
+  MethodReference TargetMethod() const {
+    DCHECK(patch_type_ == kLinkerPatchMethod ||
+           patch_type_ == kLinkerPatchCall || patch_type_ == kLinkerPatchCallRelative);
+    return MethodReference(target_dex_file_, target_idx_);
+  }
+
+  const DexFile* TargetTypeDexFile() const {
+    DCHECK(patch_type_ == kLinkerPatchType);
+    return target_dex_file_;
+  }
+
+  uint32_t TargetTypeIndex() const {
+    DCHECK(patch_type_ == kLinkerPatchType);
+    return target_idx_;
+  }
+
+ private:
+  LinkerPatch(size_t literal_offset, LinkerPatchType patch_type,
+              uint32_t target_idx, const DexFile* target_dex_file)
+      : literal_offset_(literal_offset),
+        patch_type_(patch_type),
+        target_idx_(target_idx),
+        target_dex_file_(target_dex_file) {
+  }
+
+  size_t literal_offset_;
+  LinkerPatchType patch_type_;
+  uint32_t target_idx_;  // Method index (Call/Method patches) or type index (Type patches).
+  const DexFile* target_dex_file_;
+
+  friend bool operator==(const LinkerPatch& lhs, const LinkerPatch& rhs);
+  friend bool operator<(const LinkerPatch& lhs, const LinkerPatch& rhs);
+};
+
+inline bool operator==(const LinkerPatch& lhs, const LinkerPatch& rhs) {
+  return lhs.literal_offset_ == rhs.literal_offset_ &&
+      lhs.patch_type_ == rhs.patch_type_ &&
+      lhs.target_idx_ == rhs.target_idx_ &&
+      lhs.target_dex_file_ == rhs.target_dex_file_;
+}
+
+inline bool operator<(const LinkerPatch& lhs, const LinkerPatch& rhs) {
+  return (lhs.literal_offset_ != rhs.literal_offset_) ? lhs.literal_offset_ < rhs.literal_offset_
+      : (lhs.patch_type_ != rhs.patch_type_) ? lhs.patch_type_ < rhs.patch_type_
+      : (lhs.target_idx_ != rhs.target_idx_) ? lhs.target_idx_ < rhs.target_idx_
+      : lhs.target_dex_file_ < rhs.target_dex_file_;
+}
+
 class CompiledMethod FINAL : public CompiledCode {
  public:
   // Constructs a CompiledMethod for Quick.
@@ -184,7 +281,8 @@
                  const std::vector<uint8_t>& mapping_table,
                  const std::vector<uint8_t>& vmap_table,
                  const std::vector<uint8_t>& native_gc_map,
-                 const std::vector<uint8_t>* cfi_info);
+                 const std::vector<uint8_t>* cfi_info,
+                 const ArrayRef<LinkerPatch>& patches = ArrayRef<LinkerPatch>());
 
   // Constructs a CompiledMethod for Optimizing.
   CompiledMethod(CompilerDriver* driver,
@@ -250,6 +348,10 @@
     return cfi_info_;
   }
 
+  const std::vector<LinkerPatch>& GetPatches() const {
+    return patches_;
+  }
+
  private:
   // For quick code, the size of the activation used by the code.
   const size_t frame_size_in_bytes_;
@@ -269,6 +371,8 @@
   std::vector<uint8_t>* gc_map_;
   // For quick code, a FDE entry for the debug_frame section.
   std::vector<uint8_t>* cfi_info_;
+  // For quick code, linker patches needed by the method.
+  std::vector<LinkerPatch> patches_;
 };
 
 }  // namespace art
diff --git a/compiler/dex/quick/arm/arm_lir.h b/compiler/dex/quick/arm/arm_lir.h
index b95789e..d935bc3 100644
--- a/compiler/dex/quick/arm/arm_lir.h
+++ b/compiler/dex/quick/arm/arm_lir.h
@@ -528,6 +528,7 @@
   kThumb2Vldms,      // vldms rd, <list>.
   kThumb2Vstms,      // vstms rd, <list>.
   kThumb2BUncond,    // b <label>.
+  kThumb2Bl,         // bl with linker fixup. [11110] S imm10 [11] J1 [1] J2 imm11.
   kThumb2MovImm16H,  // similar to kThumb2MovImm16, but target high hw.
   kThumb2AddPCR,     // Thumb2 2-operand add with hard-coded PC target.
   kThumb2Adr,        // Special purpose encoding of ADR for switch tables.
diff --git a/compiler/dex/quick/arm/assemble_arm.cc b/compiler/dex/quick/arm/assemble_arm.cc
index dcec861..cf34948 100644
--- a/compiler/dex/quick/arm/assemble_arm.cc
+++ b/compiler/dex/quick/arm/assemble_arm.cc
@@ -968,6 +968,10 @@
                  kFmtOff24, -1, -1, kFmtUnused, -1, -1, kFmtUnused, -1, -1,
                  kFmtUnused, -1, -1, NO_OPERAND | IS_BRANCH,
                  "b", "!0t", 4, kFixupT2Branch),
+    ENCODING_MAP(kThumb2Bl,           0xf000d000,
+                 kFmtOff24, -1, -1, kFmtUnused, -1, -1, kFmtUnused, -1, -1,
+                 kFmtUnused, -1, -1, IS_UNARY_OP | IS_BRANCH | REG_DEF_LR | NEEDS_FIXUP,
+                 "bl", "!0T", 4, kFixupLabel),
     ENCODING_MAP(kThumb2MovImm16H,       0xf2c00000,
                  kFmtBitBlt, 11, 8, kFmtImm16, -1, -1, kFmtUnused, -1, -1,
                  kFmtUnused, -1, -1, IS_BINARY_OP | REG_DEF0 | REG_USE0,
diff --git a/compiler/dex/quick/arm/call_arm.cc b/compiler/dex/quick/arm/call_arm.cc
index f6588fe..b721e02 100644
--- a/compiler/dex/quick/arm/call_arm.cc
+++ b/compiler/dex/quick/arm/call_arm.cc
@@ -20,6 +20,8 @@
 #include "codegen_arm.h"
 #include "dex/quick/mir_to_lir-inl.h"
 #include "gc/accounting/card_table.h"
+#include "mirror/art_method.h"
+#include "mirror/object_array-inl.h"
 #include "entrypoints/quick/quick_entrypoints.h"
 
 namespace art {
@@ -499,4 +501,117 @@
   NewLIR1(kThumbBx, rs_rARM_LR.GetReg());
 }
 
+static bool ArmUseRelativeCall(CompilationUnit* cu, const MethodReference& target_method) {
+  // Emit relative calls only within a dex file due to the limited range of the BL insn.
+  return cu->dex_file == target_method.dex_file;
+}
+
+/*
+ * Bit of a hack here - in the absence of a real scheduling pass,
+ * emit the next instruction in static & direct invoke sequences.
+ */
+static int ArmNextSDCallInsn(CompilationUnit* cu, CallInfo* info,
+                             int state, const MethodReference& target_method,
+                             uint32_t unused,
+                             uintptr_t direct_code, uintptr_t direct_method,
+                             InvokeType type) {
+  Mir2Lir* cg = static_cast<Mir2Lir*>(cu->cg.get());
+  if (direct_code != 0 && direct_method != 0) {
+    switch (state) {
+    case 0:  // Get the current Method* [sets kArg0]
+      if (direct_code != static_cast<uintptr_t>(-1)) {
+        cg->LoadConstant(cg->TargetPtrReg(kInvokeTgt), direct_code);
+      } else if (ArmUseRelativeCall(cu, target_method)) {
+        // Defer to linker patch.
+      } else {
+        cg->LoadCodeAddress(target_method, type, kInvokeTgt);
+      }
+      if (direct_method != static_cast<uintptr_t>(-1)) {
+        cg->LoadConstant(cg->TargetReg(kArg0, kRef), direct_method);
+      } else {
+        cg->LoadMethodAddress(target_method, type, kArg0);
+      }
+      break;
+    default:
+      return -1;
+    }
+  } else {
+    RegStorage arg0_ref = cg->TargetReg(kArg0, kRef);
+    switch (state) {
+    case 0:  // Get the current Method* [sets kArg0]
+      // TUNING: we can save a reg copy if Method* has been promoted.
+      cg->LoadCurrMethodDirect(arg0_ref);
+      break;
+    case 1:  // Get method->dex_cache_resolved_methods_
+      cg->LoadRefDisp(arg0_ref,
+                      mirror::ArtMethod::DexCacheResolvedMethodsOffset().Int32Value(),
+                      arg0_ref,
+                      kNotVolatile);
+      // Set up direct code if known.
+      if (direct_code != 0) {
+        if (direct_code != static_cast<uintptr_t>(-1)) {
+          cg->LoadConstant(cg->TargetPtrReg(kInvokeTgt), direct_code);
+        } else if (ArmUseRelativeCall(cu, target_method)) {
+          // Defer to linker patch.
+        } else {
+          CHECK_LT(target_method.dex_method_index, target_method.dex_file->NumMethodIds());
+          cg->LoadCodeAddress(target_method, type, kInvokeTgt);
+        }
+      }
+      break;
+    case 2:  // Grab target method*
+      CHECK_EQ(cu->dex_file, target_method.dex_file);
+      cg->LoadRefDisp(arg0_ref,
+                      mirror::ObjectArray<mirror::Object>::OffsetOfElement(
+                          target_method.dex_method_index).Int32Value(),
+                      arg0_ref,
+                      kNotVolatile);
+      break;
+    case 3:  // Grab the code from the method*
+      if (direct_code == 0) {
+        // kInvokeTgt := arg0_ref->entrypoint
+        cg->LoadWordDisp(arg0_ref,
+                         mirror::ArtMethod::EntryPointFromQuickCompiledCodeOffset().Int32Value(),
+                         cg->TargetPtrReg(kInvokeTgt));
+      }
+      break;
+    default:
+      return -1;
+    }
+  }
+  return state + 1;
+}
+
+NextCallInsn ArmMir2Lir::GetNextSDCallInsn() {
+  return ArmNextSDCallInsn;
+}
+
+LIR* ArmMir2Lir::CallWithLinkerFixup(const MethodReference& target_method, InvokeType type) {
+  // For ARM, just generate a relative BL instruction that will be filled in at 'link time'.
+  // If the target turns out to be too far, the linker will generate a thunk for dispatch.
+  int target_method_idx = target_method.dex_method_index;
+  const DexFile* target_dex_file = target_method.dex_file;
+
+  // Generate the call instruction and save index, dex_file, and type.
+  // NOTE: Method deduplication takes linker patches into account, so we can just pass 0
+  // as a placeholder for the offset.
+  LIR* call = RawLIR(current_dalvik_offset_, kThumb2Bl, 0,
+                     target_method_idx, WrapPointer(const_cast<DexFile*>(target_dex_file)), type);
+  AppendLIR(call);
+  call_method_insns_.push_back(call);
+  return call;
+}
+
+LIR* ArmMir2Lir::GenCallInsn(const MirMethodLoweringInfo& method_info) {
+  LIR* call_insn;
+  if (method_info.FastPath() && ArmUseRelativeCall(cu_, method_info.GetTargetMethod()) &&
+      (method_info.GetSharpType() == kDirect || method_info.GetSharpType() == kStatic) &&
+      method_info.DirectCode() == static_cast<uintptr_t>(-1)) {
+    call_insn = CallWithLinkerFixup(method_info.GetTargetMethod(), method_info.GetSharpType());
+  } else {
+    call_insn = OpReg(kOpBlx, TargetPtrReg(kInvokeTgt));
+  }
+  return call_insn;
+}
+
 }  // namespace art
diff --git a/compiler/dex/quick/arm/codegen_arm.h b/compiler/dex/quick/arm/codegen_arm.h
index 84881e0..932dd87 100644
--- a/compiler/dex/quick/arm/codegen_arm.h
+++ b/compiler/dex/quick/arm/codegen_arm.h
@@ -20,6 +20,7 @@
 #include "arm_lir.h"
 #include "dex/compiler_internals.h"
 #include "dex/quick/mir_to_lir.h"
+#include "utils/arena_containers.h"
 
 namespace art {
 
@@ -185,6 +186,28 @@
       return false;  // Wide FPRs are formed by pairing.
     }
 
+    NextCallInsn GetNextSDCallInsn() OVERRIDE;
+
+    /*
+     * @brief Generate a relative call to the method that will be patched at link time.
+     * @param target_method The MethodReference of the method to be invoked.
+     * @param type How the method will be invoked.
+     * @returns Call instruction
+     */
+    LIR* CallWithLinkerFixup(const MethodReference& target_method, InvokeType type);
+
+    /*
+     * @brief Generate the actual call insn based on the method info.
+     * @param method_info the lowering info for the method call.
+     * @returns Call instruction
+     */
+    LIR* GenCallInsn(const MirMethodLoweringInfo& method_info) OVERRIDE;
+
+    /*
+     * @brief Handle ARM specific literals.
+     */
+    void InstallLiteralPools() OVERRIDE;
+
     LIR* InvokeTrampoline(OpKind op, RegStorage r_tgt, QuickEntrypointEnum trampoline) OVERRIDE;
     size_t GetInstructionOffset(LIR* lir);
 
@@ -215,6 +238,8 @@
     static constexpr ResourceMask GetRegMaskArm(RegStorage reg);
     static constexpr ResourceMask EncodeArmRegList(int reg_list);
     static constexpr ResourceMask EncodeArmRegFpcsList(int reg_list);
+
+    ArenaVector<LIR*> call_method_insns_;
 };
 
 }  // namespace art
diff --git a/compiler/dex/quick/arm/target_arm.cc b/compiler/dex/quick/arm/target_arm.cc
index aaf4449..dd8f7fe 100644
--- a/compiler/dex/quick/arm/target_arm.cc
+++ b/compiler/dex/quick/arm/target_arm.cc
@@ -452,6 +452,11 @@
                  reinterpret_cast<uintptr_t>(base_addr) + lir->offset + 4 + (operand << 1),
                  lir->target);
              break;
+           case 'T':
+             snprintf(tbuf, arraysize(tbuf), "%s", PrettyMethod(
+                 static_cast<uint32_t>(lir->operands[1]),
+                 *reinterpret_cast<const DexFile*>(UnwrapPointer(lir->operands[2]))).c_str());
+             break;
            case 'u': {
              int offset_1 = lir->operands[0];
              int offset_2 = NEXT_LIR(lir)->operands[0];
@@ -551,7 +556,9 @@
 }
 
 ArmMir2Lir::ArmMir2Lir(CompilationUnit* cu, MIRGraph* mir_graph, ArenaAllocator* arena)
-    : Mir2Lir(cu, mir_graph, arena) {
+    : Mir2Lir(cu, mir_graph, arena),
+      call_method_insns_(arena->Adapter()) {
+  call_method_insns_.reserve(100);
   // Sanity check - make sure encoding map lines up.
   for (int i = 0; i < kArmLast; i++) {
     if (ArmMir2Lir::EncodingMap[i].opcode != i) {
@@ -823,4 +830,21 @@
   return res;
 }
 
+void ArmMir2Lir::InstallLiteralPools() {
+  // PC-relative calls to methods.
+  patches_.reserve(call_method_insns_.size());
+  for (LIR* p : call_method_insns_) {
+      DCHECK_EQ(p->opcode, kThumb2Bl);
+      uint32_t target_method_idx = p->operands[1];
+      const DexFile* target_dex_file =
+          reinterpret_cast<const DexFile*>(UnwrapPointer(p->operands[2]));
+
+      patches_.push_back(LinkerPatch::RelativeCodePatch(p->offset,
+                                                        target_dex_file, target_method_idx));
+  }
+
+  // And do the normal processing.
+  Mir2Lir::InstallLiteralPools();
+}
+
 }  // namespace art
diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index bd2a942..3135892 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -472,20 +472,15 @@
     Push32(code_buffer_, data_lir->operands[0]);
     data_lir = NEXT_LIR(data_lir);
   }
+  // TODO: patches_.reserve() as needed.
   // Push code and method literals, record offsets for the compiler to patch.
   data_lir = code_literal_list_;
   while (data_lir != NULL) {
     uint32_t target_method_idx = data_lir->operands[0];
     const DexFile* target_dex_file =
         reinterpret_cast<const DexFile*>(UnwrapPointer(data_lir->operands[1]));
-    cu_->compiler_driver->AddCodePatch(cu_->dex_file,
-                                       cu_->class_def_idx,
-                                       cu_->method_idx,
-                                       cu_->invoke_type,
-                                       target_method_idx,
-                                       target_dex_file,
-                                       static_cast<InvokeType>(data_lir->operands[2]),
-                                       code_buffer_.size());
+    patches_.push_back(LinkerPatch::CodePatch(code_buffer_.size(),
+                                              target_dex_file, target_method_idx));
     const DexFile::MethodId& target_method_id = target_dex_file->GetMethodId(target_method_idx);
     // unique value based on target to ensure code deduplication works
     PushPointer(code_buffer_, &target_method_id, cu_->target64);
@@ -496,14 +491,8 @@
     uint32_t target_method_idx = data_lir->operands[0];
     const DexFile* target_dex_file =
         reinterpret_cast<const DexFile*>(UnwrapPointer(data_lir->operands[1]));
-    cu_->compiler_driver->AddMethodPatch(cu_->dex_file,
-                                         cu_->class_def_idx,
-                                         cu_->method_idx,
-                                         cu_->invoke_type,
-                                         target_method_idx,
-                                         target_dex_file,
-                                         static_cast<InvokeType>(data_lir->operands[2]),
-                                         code_buffer_.size());
+    patches_.push_back(LinkerPatch::MethodPatch(code_buffer_.size(),
+                                                target_dex_file, target_method_idx));
     const DexFile::MethodId& target_method_id = target_dex_file->GetMethodId(target_method_idx);
     // unique value based on target to ensure code deduplication works
     PushPointer(code_buffer_, &target_method_id, cu_->target64);
@@ -512,16 +501,12 @@
   // Push class literals.
   data_lir = class_literal_list_;
   while (data_lir != NULL) {
-    uint32_t target_method_idx = data_lir->operands[0];
+    uint32_t target_type_idx = data_lir->operands[0];
     const DexFile* class_dex_file =
       reinterpret_cast<const DexFile*>(UnwrapPointer(data_lir->operands[1]));
-    cu_->compiler_driver->AddClassPatch(cu_->dex_file,
-                                        cu_->class_def_idx,
-                                        cu_->method_idx,
-                                        target_method_idx,
-                                        class_dex_file,
-                                        code_buffer_.size());
-    const DexFile::TypeId& target_method_id = class_dex_file->GetTypeId(target_method_idx);
+    patches_.push_back(LinkerPatch::TypePatch(code_buffer_.size(),
+                                              class_dex_file, target_type_idx));
+    const DexFile::TypeId& target_method_id = class_dex_file->GetTypeId(target_type_idx);
     // unique value based on target to ensure code deduplication works
     PushPointer(code_buffer_, &target_method_id, cu_->target64);
     data_lir = NEXT_LIR(data_lir);
@@ -1006,6 +991,7 @@
       live_sreg_(0),
       core_vmap_table_(mir_graph->GetArena()->Adapter()),
       fp_vmap_table_(mir_graph->GetArena()->Adapter()),
+      patches_(mir_graph->GetArena()->Adapter()),
       num_core_spills_(0),
       num_fp_spills_(0),
       frame_size_(0),
@@ -1097,11 +1083,17 @@
     vmap_encoder.PushBackUnsigned(0u);  // Size is 0.
   }
 
+  // Sort patches by literal offset for better deduplication.
+  std::sort(patches_.begin(), patches_.end(), [](const LinkerPatch& lhs, const LinkerPatch& rhs) {
+    return lhs.LiteralOffset() < rhs.LiteralOffset();
+  });
+
   std::unique_ptr<std::vector<uint8_t>> cfi_info(ReturnFrameDescriptionEntry());
   CompiledMethod* result =
       new CompiledMethod(cu_->compiler_driver, cu_->instruction_set, code_buffer_, frame_size_,
                          core_spill_mask_, fp_spill_mask_, &src_mapping_table_, encoded_mapping_table_,
-                         vmap_encoder.GetData(), native_gc_map_, cfi_info.get());
+                         vmap_encoder.GetData(), native_gc_map_, cfi_info.get(),
+                         ArrayRef<LinkerPatch>(patches_));
   return result;
 }
 
diff --git a/compiler/dex/quick/gen_invoke.cc b/compiler/dex/quick/gen_invoke.cc
index 960f217..67a75cb 100755
--- a/compiler/dex/quick/gen_invoke.cc
+++ b/compiler/dex/quick/gen_invoke.cc
@@ -14,6 +14,7 @@
  * limitations under the License.
  */
 
+#include "arm/codegen_arm.h"
 #include "dex/compiler_ir.h"
 #include "dex/frontend.h"
 #include "dex/quick/dex_file_method_inliner.h"
@@ -27,7 +28,7 @@
 #include "mirror/object_array-inl.h"
 #include "mirror/string.h"
 #include "mir_to_lir-inl.h"
-#include "x86/codegen_x86.h"
+#include "scoped_thread_state_change.h"
 
 namespace art {
 
@@ -493,15 +494,15 @@
                           uint32_t unused,
                           uintptr_t direct_code, uintptr_t direct_method,
                           InvokeType type) {
+  DCHECK(cu->instruction_set != kX86 && cu->instruction_set != kX86_64 &&
+         cu->instruction_set != kThumb2 && cu->instruction_set != kArm);
   Mir2Lir* cg = static_cast<Mir2Lir*>(cu->cg.get());
   if (direct_code != 0 && direct_method != 0) {
     switch (state) {
     case 0:  // Get the current Method* [sets kArg0]
       if (direct_code != static_cast<uintptr_t>(-1)) {
-        if (cu->instruction_set != kX86 && cu->instruction_set != kX86_64) {
-          cg->LoadConstant(cg->TargetPtrReg(kInvokeTgt), direct_code);
-        }
-      } else if (cu->instruction_set != kX86 && cu->instruction_set != kX86_64) {
+        cg->LoadConstant(cg->TargetPtrReg(kInvokeTgt), direct_code);
+      } else {
         cg->LoadCodeAddress(target_method, type, kInvokeTgt);
       }
       if (direct_method != static_cast<uintptr_t>(-1)) {
@@ -529,7 +530,7 @@
       if (direct_code != 0) {
         if (direct_code != static_cast<uintptr_t>(-1)) {
           cg->LoadConstant(cg->TargetPtrReg(kInvokeTgt), direct_code);
-        } else if (cu->instruction_set != kX86 && cu->instruction_set != kX86_64) {
+        } else {
           CHECK_LT(target_method.dex_method_index, target_method.dex_file->NumMethodIds());
           cg->LoadCodeAddress(target_method, type, kInvokeTgt);
         }
@@ -547,7 +548,7 @@
         if (CommonCallCodeLoadCodePointerIntoInvokeTgt(info, &arg0_ref, cu, cg)) {
           break;                                    // kInvokeTgt := arg0_ref->entrypoint
         }
-      } else if (cu->instruction_set != kX86 && cu->instruction_set != kX86_64) {
+      } else {
         break;
       }
       // Intentional fallthrough for x86
@@ -1683,31 +1684,6 @@
   GenInvokeNoInline(info);
 }
 
-static LIR* GenInvokeNoInlineCall(Mir2Lir* mir_to_lir, InvokeType type) {
-  QuickEntrypointEnum trampoline;
-  switch (type) {
-    case kInterface:
-      trampoline = kQuickInvokeInterfaceTrampolineWithAccessCheck;
-      break;
-    case kDirect:
-      trampoline = kQuickInvokeDirectTrampolineWithAccessCheck;
-      break;
-    case kStatic:
-      trampoline = kQuickInvokeStaticTrampolineWithAccessCheck;
-      break;
-    case kSuper:
-      trampoline = kQuickInvokeSuperTrampolineWithAccessCheck;
-      break;
-    case kVirtual:
-      trampoline = kQuickInvokeVirtualTrampolineWithAccessCheck;
-      break;
-    default:
-      LOG(FATAL) << "Unexpected invoke type";
-      trampoline = kQuickInvokeInterfaceTrampolineWithAccessCheck;
-  }
-  return mir_to_lir->InvokeTrampoline(kOpBlx, RegStorage::InvalidReg(), trampoline);
-}
-
 void Mir2Lir::GenInvokeNoInline(CallInfo* info) {
   int call_state = 0;
   LIR* null_ck;
@@ -1721,7 +1697,7 @@
   cu_->compiler_driver->ProcessedInvoke(method_info.GetInvokeType(), method_info.StatsFlags());
   BeginInvoke(info);
   InvokeType original_type = static_cast<InvokeType>(method_info.GetInvokeType());
-  info->type = static_cast<InvokeType>(method_info.GetSharpType());
+  info->type = method_info.GetSharpType();
   bool fast_path = method_info.FastPath();
   bool skip_this;
   if (info->type == kInterface) {
@@ -1731,10 +1707,10 @@
     if (fast_path) {
       p_null_ck = &null_ck;
     }
-    next_call_insn = fast_path ? NextSDCallInsn : NextDirectCallInsnSP;
+    next_call_insn = fast_path ? GetNextSDCallInsn() : NextDirectCallInsnSP;
     skip_this = false;
   } else if (info->type == kStatic) {
-    next_call_insn = fast_path ? NextSDCallInsn : NextStaticCallInsnSP;
+    next_call_insn = fast_path ? GetNextSDCallInsn() : NextStaticCallInsnSP;
     skip_this = false;
   } else if (info->type == kSuper) {
     DCHECK(!fast_path);  // Fast path is a direct call.
@@ -1762,25 +1738,9 @@
     call_state = next_call_insn(cu_, info, call_state, target_method, method_info.VTableIndex(),
                                 method_info.DirectCode(), method_info.DirectMethod(), original_type);
   }
-  LIR* call_inst;
-  if (cu_->instruction_set != kX86 && cu_->instruction_set != kX86_64) {
-    call_inst = OpReg(kOpBlx, TargetPtrReg(kInvokeTgt));
-  } else {
-    if (fast_path) {
-      if (method_info.DirectCode() == static_cast<uintptr_t>(-1)) {
-        // We can have the linker fixup a call relative.
-        call_inst =
-          reinterpret_cast<X86Mir2Lir*>(this)->CallWithLinkerFixup(target_method, info->type);
-      } else {
-        call_inst = OpMem(kOpBlx, TargetReg(kArg0, kRef),
-                          mirror::ArtMethod::EntryPointFromQuickCompiledCodeOffset().Int32Value());
-      }
-    } else {
-      call_inst = GenInvokeNoInlineCall(this, info->type);
-    }
-  }
+  LIR* call_insn = GenCallInsn(method_info);
   EndInvoke(info);
-  MarkSafepointPC(call_inst);
+  MarkSafepointPC(call_insn);
 
   ClobberCallerSave();
   if (info->result.location != kLocInvalid) {
@@ -1795,4 +1755,14 @@
   }
 }
 
+NextCallInsn Mir2Lir::GetNextSDCallInsn() {
+  return NextSDCallInsn;
+}
+
+LIR* Mir2Lir::GenCallInsn(const MirMethodLoweringInfo& method_info) {
+  DCHECK(cu_->instruction_set != kX86 && cu_->instruction_set != kX86_64 &&
+         cu_->instruction_set != kThumb2 && cu_->instruction_set != kArm);
+  return OpReg(kOpBlx, TargetPtrReg(kInvokeTgt));
+}
+
 }  // namespace art
diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h
index 01aa11d..67a8c0f 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -138,6 +138,7 @@
 struct RegisterInfo;
 class DexFileMethodInliner;
 class MIRGraph;
+class MirMethodLoweringInfo;
 class Mir2Lir;
 
 typedef int (*NextCallInsn)(CompilationUnit*, CallInfo*, int,
@@ -909,6 +910,15 @@
                                                             bool safepoint_pc);
     void GenInvoke(CallInfo* info);
     void GenInvokeNoInline(CallInfo* info);
+    virtual NextCallInsn GetNextSDCallInsn();
+
+    /*
+     * @brief Generate the actual call insn based on the method info.
+     * @param method_info the lowering info for the method call.
+     * @returns Call instruction
+     */
+    virtual LIR* GenCallInsn(const MirMethodLoweringInfo& method_info);
+
     virtual void FlushIns(RegLocation* ArgLocs, RegLocation rl_method);
     virtual int GenDalvikArgsNoRange(CallInfo* info, int call_state, LIR** pcrLabel,
                              NextCallInsn next_call_insn,
@@ -1712,6 +1722,7 @@
     ArenaVector<uint32_t> core_vmap_table_;
     ArenaVector<uint32_t> fp_vmap_table_;
     std::vector<uint8_t> native_gc_map_;
+    ArenaVector<LinkerPatch> patches_;
     int num_core_spills_;
     int num_fp_spills_;
     int frame_size_;
diff --git a/compiler/dex/quick/x86/call_x86.cc b/compiler/dex/quick/x86/call_x86.cc
index 5b92512..441ec9e 100644
--- a/compiler/dex/quick/x86/call_x86.cc
+++ b/compiler/dex/quick/x86/call_x86.cc
@@ -19,6 +19,8 @@
 #include "codegen_x86.h"
 #include "dex/quick/mir_to_lir-inl.h"
 #include "gc/accounting/card_table.h"
+#include "mirror/art_method.h"
+#include "mirror/object_array-inl.h"
 #include "x86_lir.h"
 
 namespace art {
@@ -330,4 +332,58 @@
   MarkPossibleNullPointerException(opt_flags);
 }
 
+/*
+ * Bit of a hack here - in the absence of a real scheduling pass,
+ * emit the next instruction in static & direct invoke sequences.
+ */
+static int X86NextSDCallInsn(CompilationUnit* cu, CallInfo* info,
+                             int state, const MethodReference& target_method,
+                             uint32_t unused,
+                             uintptr_t direct_code, uintptr_t direct_method,
+                             InvokeType type) {
+  Mir2Lir* cg = static_cast<Mir2Lir*>(cu->cg.get());
+  if (direct_method != 0) {
+    switch (state) {
+    case 0:  // Get the current Method* [sets kArg0]
+      if (direct_method != static_cast<uintptr_t>(-1)) {
+        cg->LoadConstant(cg->TargetReg(kArg0, kRef), direct_method);
+      } else {
+        cg->LoadMethodAddress(target_method, type, kArg0);
+      }
+      break;
+    default:
+      return -1;
+    }
+  } else {
+    RegStorage arg0_ref = cg->TargetReg(kArg0, kRef);
+    switch (state) {
+    case 0:  // Get the current Method* [sets kArg0]
+      // TUNING: we can save a reg copy if Method* has been promoted.
+      cg->LoadCurrMethodDirect(arg0_ref);
+      break;
+    case 1:  // Get method->dex_cache_resolved_methods_
+      cg->LoadRefDisp(arg0_ref,
+                      mirror::ArtMethod::DexCacheResolvedMethodsOffset().Int32Value(),
+                      arg0_ref,
+                      kNotVolatile);
+      break;
+    case 2:  // Grab target method*
+      CHECK_EQ(cu->dex_file, target_method.dex_file);
+      cg->LoadRefDisp(arg0_ref,
+                      mirror::ObjectArray<mirror::Object>::OffsetOfElement(
+                          target_method.dex_method_index).Int32Value(),
+                      arg0_ref,
+                      kNotVolatile);
+      break;
+    default:
+      return -1;
+    }
+  }
+  return state + 1;
+}
+
+NextCallInsn X86Mir2Lir::GetNextSDCallInsn() {
+  return X86NextSDCallInsn;
+}
+
 }  // namespace art
diff --git a/compiler/dex/quick/x86/codegen_x86.h b/compiler/dex/quick/x86/codegen_x86.h
index 80da962..8edfc01 100644
--- a/compiler/dex/quick/x86/codegen_x86.h
+++ b/compiler/dex/quick/x86/codegen_x86.h
@@ -341,6 +341,7 @@
 
   void FlushIns(RegLocation* ArgLocs, RegLocation rl_method) OVERRIDE;
 
+  NextCallInsn GetNextSDCallInsn() OVERRIDE;
   int GenDalvikArgsNoRange(CallInfo* info, int call_state, LIR** pcrLabel,
                            NextCallInsn next_call_insn,
                            const MethodReference& target_method,
@@ -361,7 +362,14 @@
    * @param type How the method will be invoked.
    * @returns Call instruction
    */
-  virtual LIR * CallWithLinkerFixup(const MethodReference& target_method, InvokeType type);
+  LIR* CallWithLinkerFixup(const MethodReference& target_method, InvokeType type);
+
+  /*
+   * @brief Generate the actual call insn based on the method info.
+   * @param method_info the lowering info for the method call.
+   * @returns Call instruction
+   */
+  LIR* GenCallInsn(const MirMethodLoweringInfo& method_info) OVERRIDE;
 
   /*
    * @brief Handle x86 specific literals
diff --git a/compiler/dex/quick/x86/target_x86.cc b/compiler/dex/quick/x86/target_x86.cc
index d3eafc9..760358e 100755
--- a/compiler/dex/quick/x86/target_x86.cc
+++ b/compiler/dex/quick/x86/target_x86.cc
@@ -24,6 +24,7 @@
 #include "dex/quick/mir_to_lir-inl.h"
 #include "dex/reg_storage_eq.h"
 #include "mirror/array.h"
+#include "mirror/art_method.h"
 #include "mirror/string.h"
 #include "oat.h"
 #include "x86_lir.h"
@@ -1002,25 +1003,65 @@
   class_type_address_insns_.push_back(move);
 }
 
-LIR *X86Mir2Lir::CallWithLinkerFixup(const MethodReference& target_method, InvokeType type) {
+LIR* X86Mir2Lir::CallWithLinkerFixup(const MethodReference& target_method, InvokeType type) {
   /*
    * For x86, just generate a 32 bit call relative instruction, that will be filled
-   * in at 'link time'.  For now, put a unique value based on target to ensure that
-   * code deduplication works.
+   * in at 'link time'.
    */
   int target_method_idx = target_method.dex_method_index;
   const DexFile* target_dex_file = target_method.dex_file;
-  const DexFile::MethodId& target_method_id = target_dex_file->GetMethodId(target_method_idx);
-  uintptr_t target_method_id_ptr = reinterpret_cast<uintptr_t>(&target_method_id);
 
   // Generate the call instruction with the unique pointer and save index, dex_file, and type.
-  LIR *call = RawLIR(current_dalvik_offset_, kX86CallI, static_cast<int>(target_method_id_ptr),
+  // NOTE: Method deduplication takes linker patches into account, so we can just pass 0
+  // as a placeholder for the offset.
+  LIR* call = RawLIR(current_dalvik_offset_, kX86CallI, 0,
                      target_method_idx, WrapPointer(const_cast<DexFile*>(target_dex_file)), type);
   AppendLIR(call);
   call_method_insns_.push_back(call);
   return call;
 }
 
+static LIR* GenInvokeNoInlineCall(Mir2Lir* mir_to_lir, InvokeType type) {
+  QuickEntrypointEnum trampoline;
+  switch (type) {
+    case kInterface:
+      trampoline = kQuickInvokeInterfaceTrampolineWithAccessCheck;
+      break;
+    case kDirect:
+      trampoline = kQuickInvokeDirectTrampolineWithAccessCheck;
+      break;
+    case kStatic:
+      trampoline = kQuickInvokeStaticTrampolineWithAccessCheck;
+      break;
+    case kSuper:
+      trampoline = kQuickInvokeSuperTrampolineWithAccessCheck;
+      break;
+    case kVirtual:
+      trampoline = kQuickInvokeVirtualTrampolineWithAccessCheck;
+      break;
+    default:
+      LOG(FATAL) << "Unexpected invoke type";
+      trampoline = kQuickInvokeInterfaceTrampolineWithAccessCheck;
+  }
+  return mir_to_lir->InvokeTrampoline(kOpBlx, RegStorage::InvalidReg(), trampoline);
+}
+
+LIR* X86Mir2Lir::GenCallInsn(const MirMethodLoweringInfo& method_info) {
+  LIR* call_insn;
+  if (method_info.FastPath()) {
+    if (method_info.DirectCode() == static_cast<uintptr_t>(-1)) {
+      // We can have the linker fixup a call relative.
+      call_insn = CallWithLinkerFixup(method_info.GetTargetMethod(), method_info.GetSharpType());
+    } else {
+      call_insn = OpMem(kOpBlx, TargetReg(kArg0, kRef),
+                        mirror::ArtMethod::EntryPointFromQuickCompiledCodeOffset().Int32Value());
+    }
+  } else {
+    call_insn = GenInvokeNoInlineCall(this, method_info.GetSharpType());
+  }
+  return call_insn;
+}
+
 void X86Mir2Lir::InstallLiteralPools() {
   // These are handled differently for x86.
   DCHECK(code_literal_list_ == nullptr);
@@ -1056,11 +1097,8 @@
 
       // The offset to patch is the last 4 bytes of the instruction.
       int patch_offset = p->offset + p->flags.size - 4;
-      cu_->compiler_driver->AddMethodPatch(cu_->dex_file, cu_->class_def_idx,
-                                           cu_->method_idx, cu_->invoke_type,
-                                           target_method_idx, target_dex_file,
-                                           static_cast<InvokeType>(p->operands[4]),
-                                           patch_offset);
+      patches_.push_back(LinkerPatch::MethodPatch(patch_offset,
+                                                  target_dex_file, target_method_idx));
   }
 
   // Handle the fixups for class types.
@@ -1069,16 +1107,16 @@
 
       const DexFile* class_dex_file =
         reinterpret_cast<const DexFile*>(UnwrapPointer(p->operands[3]));
-      uint32_t target_method_idx = p->operands[2];
+      uint32_t target_type_idx = p->operands[2];
 
       // The offset to patch is the last 4 bytes of the instruction.
       int patch_offset = p->offset + p->flags.size - 4;
-      cu_->compiler_driver->AddClassPatch(cu_->dex_file, cu_->class_def_idx,
-                                          cu_->method_idx, target_method_idx, class_dex_file,
-                                          patch_offset);
+      patches_.push_back(LinkerPatch::TypePatch(patch_offset,
+                                                class_dex_file, target_type_idx));
   }
 
   // And now the PC-relative calls to methods.
+  patches_.reserve(call_method_insns_.size());
   for (LIR* p : call_method_insns_) {
       DCHECK_EQ(p->opcode, kX86CallI);
       uint32_t target_method_idx = p->operands[1];
@@ -1087,11 +1125,8 @@
 
       // The offset to patch is the last 4 bytes of the instruction.
       int patch_offset = p->offset + p->flags.size - 4;
-      cu_->compiler_driver->AddRelativeCodePatch(cu_->dex_file, cu_->class_def_idx,
-                                                 cu_->method_idx, cu_->invoke_type,
-                                                 target_method_idx, target_dex_file,
-                                                 static_cast<InvokeType>(p->operands[3]),
-                                                 patch_offset, -4 /* offset */);
+      patches_.push_back(LinkerPatch::RelativeCodePatch(patch_offset,
+                                                        target_dex_file, target_method_idx));
   }
 
   // And do the normal processing.
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index 990c1c8..cdb816d 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -342,6 +342,8 @@
       freezing_constructor_lock_("freezing constructor lock"),
       compiled_classes_lock_("compiled classes lock"),
       compiled_methods_lock_("compiled method lock"),
+      compiled_methods_(),
+      non_relative_linker_patch_count_(0u),
       image_(image),
       image_classes_(image_classes),
       thread_count_(thread_count),
@@ -426,18 +428,6 @@
     MutexLock mu(self, compiled_methods_lock_);
     STLDeleteValues(&compiled_methods_);
   }
-  {
-    MutexLock mu(self, compiled_methods_lock_);
-    STLDeleteElements(&code_to_patch_);
-  }
-  {
-    MutexLock mu(self, compiled_methods_lock_);
-    STLDeleteElements(&methods_to_patch_);
-  }
-  {
-    MutexLock mu(self, compiled_methods_lock_);
-    STLDeleteElements(&classes_to_patch_);
-  }
   CHECK_PTHREAD_CALL(pthread_key_delete, (tls_key_), "delete tls key");
   compiler_->UnInit();
 }
@@ -1320,77 +1310,6 @@
   return result;
 }
 
-void CompilerDriver::AddCodePatch(const DexFile* dex_file,
-                                  uint16_t referrer_class_def_idx,
-                                  uint32_t referrer_method_idx,
-                                  InvokeType referrer_invoke_type,
-                                  uint32_t target_method_idx,
-                                  const DexFile* target_dex_file,
-                                  InvokeType target_invoke_type,
-                                  size_t literal_offset) {
-  MutexLock mu(Thread::Current(), compiled_methods_lock_);
-  code_to_patch_.push_back(new CallPatchInformation(dex_file,
-                                                    referrer_class_def_idx,
-                                                    referrer_method_idx,
-                                                    referrer_invoke_type,
-                                                    target_method_idx,
-                                                    target_dex_file,
-                                                    target_invoke_type,
-                                                    literal_offset));
-}
-void CompilerDriver::AddRelativeCodePatch(const DexFile* dex_file,
-                                          uint16_t referrer_class_def_idx,
-                                          uint32_t referrer_method_idx,
-                                          InvokeType referrer_invoke_type,
-                                          uint32_t target_method_idx,
-                                          const DexFile* target_dex_file,
-                                          InvokeType target_invoke_type,
-                                          size_t literal_offset,
-                                          int32_t pc_relative_offset) {
-  MutexLock mu(Thread::Current(), compiled_methods_lock_);
-  code_to_patch_.push_back(new RelativeCallPatchInformation(dex_file,
-                                                            referrer_class_def_idx,
-                                                            referrer_method_idx,
-                                                            referrer_invoke_type,
-                                                            target_method_idx,
-                                                            target_dex_file,
-                                                            target_invoke_type,
-                                                            literal_offset,
-                                                            pc_relative_offset));
-}
-void CompilerDriver::AddMethodPatch(const DexFile* dex_file,
-                                    uint16_t referrer_class_def_idx,
-                                    uint32_t referrer_method_idx,
-                                    InvokeType referrer_invoke_type,
-                                    uint32_t target_method_idx,
-                                    const DexFile* target_dex_file,
-                                    InvokeType target_invoke_type,
-                                    size_t literal_offset) {
-  MutexLock mu(Thread::Current(), compiled_methods_lock_);
-  methods_to_patch_.push_back(new CallPatchInformation(dex_file,
-                                                       referrer_class_def_idx,
-                                                       referrer_method_idx,
-                                                       referrer_invoke_type,
-                                                       target_method_idx,
-                                                       target_dex_file,
-                                                       target_invoke_type,
-                                                       literal_offset));
-}
-void CompilerDriver::AddClassPatch(const DexFile* dex_file,
-                                    uint16_t referrer_class_def_idx,
-                                    uint32_t referrer_method_idx,
-                                    uint32_t target_type_idx,
-                                    const DexFile* target_type_dex_file,
-                                    size_t literal_offset) {
-  MutexLock mu(Thread::Current(), compiled_methods_lock_);
-  classes_to_patch_.push_back(new TypePatchInformation(dex_file,
-                                                       referrer_class_def_idx,
-                                                       referrer_method_idx,
-                                                       target_type_idx,
-                                                       target_type_dex_file,
-                                                       literal_offset));
-}
-
 class ParallelCompilationManager {
  public:
   typedef void Callback(const ParallelCompilationManager* manager, size_t index);
@@ -2076,11 +1995,19 @@
 
   Thread* self = Thread::Current();
   if (compiled_method != nullptr) {
+    // Count non-relative linker patches.
+    size_t non_relative_linker_patch_count = 0u;
+    for (const LinkerPatch& patch : compiled_method->GetPatches()) {
+      if (patch.Type() != kLinkerPatchCallRelative) {
+        ++non_relative_linker_patch_count;
+      }
+    }
     MethodReference ref(&dex_file, method_idx);
     DCHECK(GetCompiledMethod(ref) == nullptr) << PrettyMethod(method_idx, dex_file);
     {
       MutexLock mu(self, compiled_methods_lock_);
       compiled_methods_.Put(ref, compiled_method);
+      non_relative_linker_patch_count_ += non_relative_linker_patch_count;
     }
     DCHECK(GetCompiledMethod(ref) != nullptr) << PrettyMethod(method_idx, dex_file);
   }
@@ -2138,6 +2065,11 @@
   return it->second;
 }
 
+size_t CompilerDriver::GetNonRelativeLinkerPatchCount() const {
+  MutexLock mu(Thread::Current(), compiled_methods_lock_);
+  return non_relative_linker_patch_count_;
+}
+
 void CompilerDriver::AddRequiresConstructorBarrier(Thread* self, const DexFile* dex_file,
                                                    uint16_t class_def_index) {
   WriterMutexLock mu(self, freezing_constructor_lock_);
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index e7bd357..c445683 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -169,6 +169,8 @@
 
   CompiledMethod* GetCompiledMethod(MethodReference ref) const
       LOCKS_EXCLUDED(compiled_methods_lock_);
+  size_t GetNonRelativeLinkerPatchCount() const
+      LOCKS_EXCLUDED(compiled_methods_lock_);
 
   void AddRequiresConstructorBarrier(Thread* self, const DexFile* dex_file,
                                      uint16_t class_def_index);
@@ -313,43 +315,6 @@
   const VerifiedMethod* GetVerifiedMethod(const DexFile* dex_file, uint32_t method_idx) const;
   bool IsSafeCast(const DexCompilationUnit* mUnit, uint32_t dex_pc);
 
-  // Record patch information for later fix up.
-  void AddCodePatch(const DexFile* dex_file,
-                    uint16_t referrer_class_def_idx,
-                    uint32_t referrer_method_idx,
-                    InvokeType referrer_invoke_type,
-                    uint32_t target_method_idx,
-                    const DexFile* target_dex_file,
-                    InvokeType target_invoke_type,
-                    size_t literal_offset)
-      LOCKS_EXCLUDED(compiled_methods_lock_);
-  void AddRelativeCodePatch(const DexFile* dex_file,
-                            uint16_t referrer_class_def_idx,
-                            uint32_t referrer_method_idx,
-                            InvokeType referrer_invoke_type,
-                            uint32_t target_method_idx,
-                            const DexFile* target_dex_file,
-                            InvokeType target_invoke_type,
-                            size_t literal_offset,
-                            int32_t pc_relative_offset)
-      LOCKS_EXCLUDED(compiled_methods_lock_);
-  void AddMethodPatch(const DexFile* dex_file,
-                      uint16_t referrer_class_def_idx,
-                      uint32_t referrer_method_idx,
-                      InvokeType referrer_invoke_type,
-                      uint32_t target_method_idx,
-                      const DexFile* target_dex_file,
-                      InvokeType target_invoke_type,
-                      size_t literal_offset)
-      LOCKS_EXCLUDED(compiled_methods_lock_);
-  void AddClassPatch(const DexFile* dex_file,
-                     uint16_t referrer_class_def_idx,
-                     uint32_t referrer_method_idx,
-                     uint32_t target_method_idx,
-                     const DexFile* target_dex_file,
-                     size_t literal_offset)
-      LOCKS_EXCLUDED(compiled_methods_lock_);
-
   bool GetSupportBootImageFixup() const {
     return support_boot_image_fixup_;
   }
@@ -386,9 +351,6 @@
     return thread_count_;
   }
 
-  class CallPatchInformation;
-  class TypePatchInformation;
-
   bool GetDumpPasses() const {
     return dump_passes_;
   }
@@ -397,189 +359,6 @@
     return timings_logger_;
   }
 
-  class PatchInformation {
-   public:
-    const DexFile& GetDexFile() const {
-      return *dex_file_;
-    }
-    uint16_t GetReferrerClassDefIdx() const {
-      return referrer_class_def_idx_;
-    }
-    uint32_t GetReferrerMethodIdx() const {
-      return referrer_method_idx_;
-    }
-    size_t GetLiteralOffset() const {
-      return literal_offset_;
-    }
-
-    virtual bool IsCall() const {
-      return false;
-    }
-    virtual bool IsType() const {
-      return false;
-    }
-    virtual const CallPatchInformation* AsCall() const {
-      LOG(FATAL) << "Unreachable";
-      return nullptr;
-    }
-    virtual const TypePatchInformation* AsType() const {
-      LOG(FATAL) << "Unreachable";
-      return nullptr;
-    }
-
-   protected:
-    PatchInformation(const DexFile* dex_file,
-                     uint16_t referrer_class_def_idx,
-                     uint32_t referrer_method_idx,
-                     size_t literal_offset)
-      : dex_file_(dex_file),
-        referrer_class_def_idx_(referrer_class_def_idx),
-        referrer_method_idx_(referrer_method_idx),
-        literal_offset_(literal_offset) {
-      CHECK(dex_file_ != nullptr);
-    }
-    virtual ~PatchInformation() {}
-
-    const DexFile* const dex_file_;
-    const uint16_t referrer_class_def_idx_;
-    const uint32_t referrer_method_idx_;
-    const size_t literal_offset_;
-
-    friend class CompilerDriver;
-  };
-
-  class CallPatchInformation : public PatchInformation {
-   public:
-    InvokeType GetReferrerInvokeType() const {
-      return referrer_invoke_type_;
-    }
-    uint32_t GetTargetMethodIdx() const {
-      return target_method_idx_;
-    }
-    const DexFile* GetTargetDexFile() const {
-      return target_dex_file_;
-    }
-    InvokeType GetTargetInvokeType() const {
-      return target_invoke_type_;
-    }
-
-    const CallPatchInformation* AsCall() const {
-      return this;
-    }
-    bool IsCall() const {
-      return true;
-    }
-    virtual bool IsRelative() const {
-      return false;
-    }
-    virtual int RelativeOffset() const {
-      return 0;
-    }
-
-   protected:
-    CallPatchInformation(const DexFile* dex_file,
-                         uint16_t referrer_class_def_idx,
-                         uint32_t referrer_method_idx,
-                         InvokeType referrer_invoke_type,
-                         uint32_t target_method_idx,
-                         const DexFile* target_dex_file,
-                         InvokeType target_invoke_type,
-                         size_t literal_offset)
-        : PatchInformation(dex_file, referrer_class_def_idx,
-                           referrer_method_idx, literal_offset),
-          referrer_invoke_type_(referrer_invoke_type),
-          target_method_idx_(target_method_idx),
-          target_dex_file_(target_dex_file),
-          target_invoke_type_(target_invoke_type) {
-    }
-
-   private:
-    const InvokeType referrer_invoke_type_;
-    const uint32_t target_method_idx_;
-    const DexFile* target_dex_file_;
-    const InvokeType target_invoke_type_;
-
-    friend class CompilerDriver;
-    DISALLOW_COPY_AND_ASSIGN(CallPatchInformation);
-  };
-
-  class RelativeCallPatchInformation : public CallPatchInformation {
-   public:
-    bool IsRelative() const {
-      return true;
-    }
-    int RelativeOffset() const {
-      return offset_;
-    }
-
-   private:
-    RelativeCallPatchInformation(const DexFile* dex_file,
-                                 uint16_t referrer_class_def_idx,
-                                 uint32_t referrer_method_idx,
-                                 InvokeType referrer_invoke_type,
-                                 uint32_t target_method_idx,
-                                 const DexFile* target_dex_file,
-                                 InvokeType target_invoke_type,
-                                 size_t literal_offset,
-                                 int32_t pc_relative_offset)
-        : CallPatchInformation(dex_file, referrer_class_def_idx,
-                           referrer_method_idx, referrer_invoke_type, target_method_idx,
-                           target_dex_file, target_invoke_type, literal_offset),
-          offset_(pc_relative_offset) {
-    }
-
-    const int offset_;
-
-    friend class CompilerDriver;
-    DISALLOW_COPY_AND_ASSIGN(RelativeCallPatchInformation);
-  };
-
-  class TypePatchInformation : public PatchInformation {
-   public:
-    const DexFile& GetTargetTypeDexFile() const {
-      return *target_type_dex_file_;
-    }
-
-    uint32_t GetTargetTypeIdx() const {
-      return target_type_idx_;
-    }
-
-    bool IsType() const {
-      return true;
-    }
-    const TypePatchInformation* AsType() const {
-      return this;
-    }
-
-   private:
-    TypePatchInformation(const DexFile* dex_file,
-                         uint16_t referrer_class_def_idx,
-                         uint32_t referrer_method_idx,
-                         uint32_t target_type_idx,
-                         const DexFile* target_type_dex_file,
-                         size_t literal_offset)
-        : PatchInformation(dex_file, referrer_class_def_idx,
-                           referrer_method_idx, literal_offset),
-          target_type_idx_(target_type_idx), target_type_dex_file_(target_type_dex_file) {
-    }
-
-    const uint32_t target_type_idx_;
-    const DexFile* target_type_dex_file_;
-
-    friend class CompilerDriver;
-    DISALLOW_COPY_AND_ASSIGN(TypePatchInformation);
-  };
-
-  const std::vector<const CallPatchInformation*>& GetCodeToPatch() const {
-    return code_to_patch_;
-  }
-  const std::vector<const CallPatchInformation*>& GetMethodsToPatch() const {
-    return methods_to_patch_;
-  }
-  const std::vector<const TypePatchInformation*>& GetClassesToPatch() const {
-    return classes_to_patch_;
-  }
-
   // Checks if class specified by type_idx is one of the image_classes_
   bool IsImageClass(const char* descriptor) const;
 
@@ -689,10 +468,6 @@
   static void CompileClass(const ParallelCompilationManager* context, size_t class_def_index)
       LOCKS_EXCLUDED(Locks::mutator_lock_);
 
-  std::vector<const CallPatchInformation*> code_to_patch_;
-  std::vector<const CallPatchInformation*> methods_to_patch_;
-  std::vector<const TypePatchInformation*> classes_to_patch_;
-
   const CompilerOptions* const compiler_options_;
   VerificationResults* const verification_results_;
   DexFileToMethodInlinerMap* const method_inliner_map_;
@@ -715,6 +490,9 @@
   // All method references that this compiler has compiled.
   mutable Mutex compiled_methods_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
   MethodTable compiled_methods_ GUARDED_BY(compiled_methods_lock_);
+  // Number of non-relative patches in all compiled methods. These patches need space
+  // in the .oat_patches ELF section if requested in the compiler options.
+  size_t non_relative_linker_patch_count_ GUARDED_BY(compiled_methods_lock_);
 
   const bool image_;
 
diff --git a/compiler/elf_builder.h b/compiler/elf_builder.h
index e535b6d..3be2478 100644
--- a/compiler/elf_builder.h
+++ b/compiler/elf_builder.h
@@ -412,6 +412,7 @@
 
 class CodeOutput {
  public:
+  virtual void SetCodeOffset(size_t offset) = 0;
   virtual bool Write(OutputStream* out) = 0;
   virtual ~CodeOutput() {}
 };
@@ -423,6 +424,7 @@
       output_(output) {}
 
   bool DoActualWrite(File* elf_file) OVERRIDE {
+    output_->SetCodeOffset(this->offset_);
     std::unique_ptr<BufferedOutputStream> output_stream(
         new BufferedOutputStream(new FileOutputStream(elf_file)));
     if (!output_->Write(output_stream.get())) {
diff --git a/compiler/elf_patcher.cc b/compiler/elf_patcher.cc
deleted file mode 100644
index 0646b75..0000000
--- a/compiler/elf_patcher.cc
+++ /dev/null
@@ -1,295 +0,0 @@
-/*
- * 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 "elf_patcher.h"
-
-#include <vector>
-#include <set>
-
-#include "class_linker.h"
-#include "elf_file.h"
-#include "elf_utils.h"
-#include "mirror/art_field-inl.h"
-#include "mirror/art_method-inl.h"
-#include "mirror/array-inl.h"
-#include "mirror/class-inl.h"
-#include "mirror/class_loader.h"
-#include "mirror/dex_cache-inl.h"
-#include "mirror/object-inl.h"
-#include "mirror/object_array-inl.h"
-#include "mirror/string-inl.h"
-#include "oat.h"
-#include "os.h"
-#include "utils.h"
-
-namespace art {
-
-bool ElfPatcher::Patch(const CompilerDriver* driver, ElfFile* elf_file,
-                       const std::string& oat_location,
-                       ImageAddressCallback cb, void* cb_data,
-                       std::string* error_msg) {
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  const OatFile* oat_file = class_linker->FindOpenedOatFileFromOatLocation(oat_location);
-  if (oat_file == nullptr) {
-    CHECK(Runtime::Current()->IsCompiler());
-    oat_file = OatFile::Open(oat_location, oat_location, NULL, false, error_msg);
-    if (oat_file == nullptr) {
-      *error_msg = StringPrintf("Unable to find or open oat file at '%s': %s", oat_location.c_str(),
-                                error_msg->c_str());
-      return false;
-    }
-    CHECK_EQ(class_linker->RegisterOatFile(oat_file), oat_file);
-  }
-  return ElfPatcher::Patch(driver, elf_file, oat_file,
-                           reinterpret_cast<uintptr_t>(oat_file->Begin()), cb, cb_data, error_msg);
-}
-
-bool ElfPatcher::Patch(const CompilerDriver* driver, ElfFile* elf, const OatFile* oat_file,
-                       uintptr_t oat_data_start, ImageAddressCallback cb, void* cb_data,
-                       std::string* error_msg) {
-  Elf32_Shdr* data_sec = elf->FindSectionByName(".rodata");
-  if (data_sec == nullptr) {
-    *error_msg = "Unable to find .rodata section and oat header";
-    return false;
-  }
-  OatHeader* oat_header = reinterpret_cast<OatHeader*>(elf->Begin() + data_sec->sh_offset);
-  if (!oat_header->IsValid()) {
-    *error_msg = "Oat header was not valid";
-    return false;
-  }
-
-  ElfPatcher p(driver, elf, oat_file, oat_header, oat_data_start, cb, cb_data, error_msg);
-  return p.PatchElf();
-}
-
-mirror::ArtMethod* ElfPatcher::GetTargetMethod(const CompilerDriver::CallPatchInformation* patch) {
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  StackHandleScope<1> hs(Thread::Current());
-  Handle<mirror::DexCache> dex_cache(
-      hs.NewHandle(class_linker->FindDexCache(*patch->GetTargetDexFile())));
-  mirror::ArtMethod* method = class_linker->ResolveMethod(*patch->GetTargetDexFile(),
-                                                          patch->GetTargetMethodIdx(),
-                                                          dex_cache,
-                                                          NullHandle<mirror::ClassLoader>(),
-                                                          NullHandle<mirror::ArtMethod>(),
-                                                          patch->GetTargetInvokeType());
-  CHECK(method != NULL)
-    << patch->GetTargetDexFile()->GetLocation() << " " << patch->GetTargetMethodIdx();
-  CHECK(!method->IsRuntimeMethod())
-    << patch->GetTargetDexFile()->GetLocation() << " " << patch->GetTargetMethodIdx();
-  CHECK(dex_cache->GetResolvedMethods()->Get(patch->GetTargetMethodIdx()) == method)
-    << patch->GetTargetDexFile()->GetLocation() << " " << patch->GetReferrerMethodIdx() << " "
-    << PrettyMethod(dex_cache->GetResolvedMethods()->Get(patch->GetTargetMethodIdx())) << " "
-    << PrettyMethod(method);
-  return method;
-}
-
-mirror::Class* ElfPatcher::GetTargetType(const CompilerDriver::TypePatchInformation* patch) {
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  StackHandleScope<2> hs(Thread::Current());
-  Handle<mirror::DexCache> dex_cache(hs.NewHandle(class_linker->FindDexCache(
-          patch->GetTargetTypeDexFile())));
-  mirror::Class* klass = class_linker->ResolveType(patch->GetTargetTypeDexFile(),
-                                                   patch->GetTargetTypeIdx(),
-                                                   dex_cache, NullHandle<mirror::ClassLoader>());
-  CHECK(klass != NULL)
-    << patch->GetTargetTypeDexFile().GetLocation() << " " << patch->GetTargetTypeIdx();
-  CHECK(dex_cache->GetResolvedTypes()->Get(patch->GetTargetTypeIdx()) == klass)
-    << patch->GetDexFile().GetLocation() << " " << patch->GetReferrerMethodIdx() << " "
-    << PrettyClass(dex_cache->GetResolvedTypes()->Get(patch->GetTargetTypeIdx())) << " "
-    << PrettyClass(klass);
-  return klass;
-}
-
-void ElfPatcher::AddPatch(uintptr_t p) {
-  if (write_patches_ && patches_set_.find(p) == patches_set_.end()) {
-    patches_set_.insert(p);
-    patches_.push_back(p);
-  }
-}
-
-uint32_t* ElfPatcher::GetPatchLocation(uintptr_t patch_ptr) {
-  CHECK_GE(patch_ptr, reinterpret_cast<uintptr_t>(oat_file_->Begin()));
-  CHECK_LE(patch_ptr, reinterpret_cast<uintptr_t>(oat_file_->End()));
-  uintptr_t off = patch_ptr - reinterpret_cast<uintptr_t>(oat_file_->Begin());
-  uintptr_t ret = reinterpret_cast<uintptr_t>(oat_header_) + off;
-
-  CHECK_GE(ret, reinterpret_cast<uintptr_t>(elf_file_->Begin()));
-  CHECK_LT(ret, reinterpret_cast<uintptr_t>(elf_file_->End()));
-  return reinterpret_cast<uint32_t*>(ret);
-}
-
-void ElfPatcher::SetPatchLocation(const CompilerDriver::PatchInformation* patch, uint32_t value) {
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  const void* quick_oat_code = class_linker->GetQuickOatCodeFor(patch->GetDexFile(),
-                                                                patch->GetReferrerClassDefIdx(),
-                                                                patch->GetReferrerMethodIdx());
-  // TODO: make this Thumb2 specific
-  uint8_t* base = reinterpret_cast<uint8_t*>(reinterpret_cast<uintptr_t>(quick_oat_code) & ~0x1);
-  uintptr_t patch_ptr = reinterpret_cast<uintptr_t>(base + patch->GetLiteralOffset());
-  uint32_t* patch_location = GetPatchLocation(patch_ptr);
-  if (kIsDebugBuild) {
-    if (patch->IsCall()) {
-      const CompilerDriver::CallPatchInformation* cpatch = patch->AsCall();
-      const DexFile::MethodId& id =
-          cpatch->GetTargetDexFile()->GetMethodId(cpatch->GetTargetMethodIdx());
-      uint32_t expected = reinterpret_cast<uintptr_t>(&id) & 0xFFFFFFFF;
-      uint32_t actual = *patch_location;
-      CHECK(actual == expected || actual == value) << "Patching call failed: " << std::hex
-          << " actual=" << actual
-          << " expected=" << expected
-          << " value=" << value;
-    }
-    if (patch->IsType()) {
-      const CompilerDriver::TypePatchInformation* tpatch = patch->AsType();
-      const DexFile::TypeId& id = tpatch->GetTargetTypeDexFile().GetTypeId(tpatch->GetTargetTypeIdx());
-      uint32_t expected = reinterpret_cast<uintptr_t>(&id) & 0xFFFFFFFF;
-      uint32_t actual = *patch_location;
-      CHECK(actual == expected || actual == value) << "Patching type failed: " << std::hex
-          << " actual=" << actual
-          << " expected=" << expected
-          << " value=" << value;
-    }
-  }
-  *patch_location = value;
-  oat_header_->UpdateChecksum(patch_location, sizeof(value));
-
-  if (patch->IsCall() && patch->AsCall()->IsRelative()) {
-    // We never record relative patches.
-    return;
-  }
-  uintptr_t loc = patch_ptr - (reinterpret_cast<uintptr_t>(oat_file_->Begin()) +
-                               oat_header_->GetExecutableOffset());
-  CHECK_GT(patch_ptr, reinterpret_cast<uintptr_t>(oat_file_->Begin()) +
-                      oat_header_->GetExecutableOffset());
-  CHECK_LT(loc, oat_file_->Size() - oat_header_->GetExecutableOffset());
-  AddPatch(loc);
-}
-
-bool ElfPatcher::PatchElf() {
-  // TODO if we are adding patches the resulting ELF file might have a
-  // potentially rather large amount of free space where patches might have been
-  // placed. We should adjust the ELF file to get rid of this excess space.
-  if (write_patches_) {
-    patches_.reserve(compiler_driver_->GetCodeToPatch().size() +
-                     compiler_driver_->GetMethodsToPatch().size() +
-                     compiler_driver_->GetClassesToPatch().size());
-  }
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  ScopedAssertNoThreadSuspension ants(Thread::Current(), "ElfPatcher");
-
-  typedef std::vector<const CompilerDriver::CallPatchInformation*> CallPatches;
-  const CallPatches& code_to_patch = compiler_driver_->GetCodeToPatch();
-  for (size_t i = 0; i < code_to_patch.size(); i++) {
-    const CompilerDriver::CallPatchInformation* patch = code_to_patch[i];
-
-    mirror::ArtMethod* target = GetTargetMethod(patch);
-    uintptr_t quick_code = reinterpret_cast<uintptr_t>(class_linker->GetQuickOatCodeFor(target));
-    DCHECK_NE(quick_code, 0U) << PrettyMethod(target);
-    const OatFile* target_oat =
-        class_linker->FindOpenedOatDexFileForDexFile(*patch->GetTargetDexFile())->GetOatFile();
-    // Get where the data actually starts. if target is this oat_file_ it is oat_data_start_,
-    // otherwise it is wherever target_oat is loaded.
-    uintptr_t oat_data_addr = GetBaseAddressFor(target_oat);
-    uintptr_t code_base = reinterpret_cast<uintptr_t>(target_oat->Begin());
-    uintptr_t code_offset = quick_code - code_base;
-    bool is_quick_offset = false;
-    if (quick_code == reinterpret_cast<uintptr_t>(GetQuickToInterpreterBridge())) {
-      is_quick_offset = true;
-      code_offset = oat_header_->GetQuickToInterpreterBridgeOffset();
-    } else if (quick_code ==
-        reinterpret_cast<uintptr_t>(class_linker->GetQuickGenericJniTrampoline())) {
-      CHECK(target->IsNative());
-      is_quick_offset = true;
-      code_offset = oat_header_->GetQuickGenericJniTrampolineOffset();
-    }
-    uintptr_t value;
-    if (patch->IsRelative()) {
-      // value to patch is relative to the location being patched
-      const void* quick_oat_code =
-        class_linker->GetQuickOatCodeFor(patch->GetDexFile(),
-                                         patch->GetReferrerClassDefIdx(),
-                                         patch->GetReferrerMethodIdx());
-      if (is_quick_offset) {
-        // If its a quick offset it means that we are doing a relative patch from the class linker
-        // oat_file to the elf_patcher oat_file so we need to adjust the quick oat code to be the
-        // one in the output oat_file (ie where it is actually going to be loaded).
-        quick_code = PointerToLowMemUInt32(reinterpret_cast<void*>(oat_data_addr + code_offset));
-        quick_oat_code =
-            reinterpret_cast<const void*>(reinterpret_cast<uintptr_t>(quick_oat_code) +
-                oat_data_addr - code_base);
-      }
-      uintptr_t base = reinterpret_cast<uintptr_t>(quick_oat_code);
-      uintptr_t patch_location = base + patch->GetLiteralOffset();
-      value = quick_code - patch_location + patch->RelativeOffset();
-    } else if (code_offset != 0) {
-      value = PointerToLowMemUInt32(reinterpret_cast<void*>(oat_data_addr + code_offset));
-    } else {
-      value = 0;
-    }
-    SetPatchLocation(patch, value);
-  }
-
-  const CallPatches& methods_to_patch = compiler_driver_->GetMethodsToPatch();
-  for (size_t i = 0; i < methods_to_patch.size(); i++) {
-    const CompilerDriver::CallPatchInformation* patch = methods_to_patch[i];
-    mirror::ArtMethod* target = GetTargetMethod(patch);
-    SetPatchLocation(patch, PointerToLowMemUInt32(get_image_address_(cb_data_, target)));
-  }
-
-  const std::vector<const CompilerDriver::TypePatchInformation*>& classes_to_patch =
-      compiler_driver_->GetClassesToPatch();
-  for (size_t i = 0; i < classes_to_patch.size(); i++) {
-    const CompilerDriver::TypePatchInformation* patch = classes_to_patch[i];
-    mirror::Class* target = GetTargetType(patch);
-    SetPatchLocation(patch, PointerToLowMemUInt32(get_image_address_(cb_data_, target)));
-  }
-
-  if (write_patches_) {
-    return WriteOutPatchData();
-  }
-  return true;
-}
-
-bool ElfPatcher::WriteOutPatchData() {
-  Elf32_Shdr* shdr = elf_file_->FindSectionByName(".oat_patches");
-  if (shdr != nullptr) {
-    CHECK_EQ(shdr, elf_file_->FindSectionByType(SHT_OAT_PATCH))
-        << "Incorrect type for .oat_patches section";
-    CHECK_LE(patches_.size() * sizeof(uintptr_t), shdr->sh_size)
-        << "We got more patches than anticipated";
-    CHECK_LE(reinterpret_cast<uintptr_t>(elf_file_->Begin()) + shdr->sh_offset + shdr->sh_size,
-              reinterpret_cast<uintptr_t>(elf_file_->End())) << "section is too large";
-    CHECK(shdr == elf_file_->GetSectionHeader(elf_file_->GetSectionHeaderNum() - 1) ||
-          shdr->sh_offset + shdr->sh_size <= (shdr + 1)->sh_offset)
-        << "Section overlaps onto next section";
-    // It's mmap'd so we can just memcpy.
-    memcpy(elf_file_->Begin() + shdr->sh_offset, patches_.data(),
-           patches_.size() * sizeof(uintptr_t));
-    // TODO We should fill in the newly empty space between the last patch and
-    // the start of the next section by moving the following sections down if
-    // possible.
-    shdr->sh_size = patches_.size() * sizeof(uintptr_t);
-    return true;
-  } else {
-    LOG(ERROR) << "Unable to find section header for SHT_OAT_PATCH";
-    *error_msg_ = "Unable to find section to write patch information to in ";
-    *error_msg_ += elf_file_->GetFile().GetPath();
-    return false;
-  }
-}
-
-}  // namespace art
diff --git a/compiler/elf_patcher.h b/compiler/elf_patcher.h
deleted file mode 100644
index 0a9f0a01..0000000
--- a/compiler/elf_patcher.h
+++ /dev/null
@@ -1,132 +0,0 @@
-/*
- * 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_ELF_PATCHER_H_
-#define ART_COMPILER_ELF_PATCHER_H_
-
-#include "base/mutex.h"
-#include "driver/compiler_driver.h"
-#include "elf_file.h"
-#include "mirror/art_method.h"
-#include "mirror/class.h"
-#include "mirror/object.h"
-#include "oat_file.h"
-#include "oat.h"
-#include "os.h"
-
-namespace art {
-
-class ElfPatcher {
- public:
-  typedef void* (*ImageAddressCallback)(void* data, mirror::Object* obj);
-
-  static bool Patch(const CompilerDriver* driver, ElfFile* elf_file,
-                    const std::string& oat_location,
-                    ImageAddressCallback cb, void* cb_data,
-                    std::string* error_msg)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-  static bool Patch(const CompilerDriver* driver, ElfFile* elf_file,
-                    const OatFile* oat_file, uintptr_t oat_data_begin,
-                    ImageAddressCallback cb, void* cb_data,
-                    std::string* error_msg)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-  static bool Patch(const CompilerDriver* driver, ElfFile* elf_file,
-                    const std::string& oat_location,
-                    std::string* error_msg)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    return ElfPatcher::Patch(driver, elf_file, oat_location,
-                             DefaultImageAddressCallback, nullptr, error_msg);
-  }
-
-  static bool Patch(const CompilerDriver* driver, ElfFile* elf_file,
-                    const OatFile* oat_file, uintptr_t oat_data_begin,
-                    std::string* error_msg)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    return ElfPatcher::Patch(driver, elf_file, oat_file, oat_data_begin,
-                             DefaultImageAddressCallback, nullptr, error_msg);
-  }
-
- private:
-  ElfPatcher(const CompilerDriver* driver, ElfFile* elf_file, const OatFile* oat_file,
-             OatHeader* oat_header, uintptr_t oat_data_begin,
-             ImageAddressCallback cb, void* cb_data, std::string* error_msg)
-      : compiler_driver_(driver), elf_file_(elf_file), oat_file_(oat_file),
-        oat_header_(oat_header), oat_data_begin_(oat_data_begin), get_image_address_(cb),
-        cb_data_(cb_data), error_msg_(error_msg),
-        write_patches_(compiler_driver_->GetCompilerOptions().GetIncludePatchInformation()) {}
-  ~ElfPatcher() {}
-
-  static void* DefaultImageAddressCallback(void* data_unused, mirror::Object* obj) {
-    return static_cast<void*>(obj);
-  }
-
-  bool PatchElf()
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-  mirror::ArtMethod* GetTargetMethod(const CompilerDriver::CallPatchInformation* patch)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-  mirror::Class* GetTargetType(const CompilerDriver::TypePatchInformation* patch)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-  void AddPatch(uintptr_t off);
-
-  void SetPatchLocation(const CompilerDriver::PatchInformation* patch, uint32_t value)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-  // Takes the pointer into the oat_file_ and get the pointer in to the ElfFile.
-  uint32_t* GetPatchLocation(uintptr_t patch_ptr);
-
-  bool WriteOutPatchData();
-
-  uintptr_t GetBaseAddressFor(const OatFile* f) {
-    if (f == oat_file_) {
-      return oat_data_begin_;
-    } else {
-      return reinterpret_cast<uintptr_t>(f->Begin());
-    }
-  }
-
-  const CompilerDriver* compiler_driver_;
-
-  // The elf_file containing the oat_data we are patching up
-  ElfFile* elf_file_;
-
-  // The oat_file that is actually loaded.
-  const OatFile* oat_file_;
-
-  // The oat_header_ within the elf_file_
-  OatHeader* oat_header_;
-
-  // Where the elf_file will be loaded during normal runs.
-  uintptr_t oat_data_begin_;
-
-  // Callback to get image addresses.
-  ImageAddressCallback get_image_address_;
-  void* cb_data_;
-
-  std::string* error_msg_;
-  std::vector<uintptr_t> patches_;
-  std::set<uintptr_t> patches_set_;
-  bool write_patches_;
-
-  DISALLOW_COPY_AND_ASSIGN(ElfPatcher);
-};
-
-}  // namespace art
-#endif  // ART_COMPILER_ELF_PATCHER_H_
diff --git a/compiler/elf_writer_mclinker.cc b/compiler/elf_writer_mclinker.cc
index 3dba426..f017641 100644
--- a/compiler/elf_writer_mclinker.cc
+++ b/compiler/elf_writer_mclinker.cc
@@ -67,19 +67,40 @@
                               bool is_host) {
   std::vector<uint8_t> oat_contents;
   oat_contents.reserve(oat_writer->GetSize());
-  VectorOutputStream output_stream("oat contents", oat_contents);
-  CHECK(oat_writer->Write(&output_stream));
-  CHECK_EQ(oat_writer->GetSize(), oat_contents.size());
 
   Init();
-  AddOatInput(oat_contents);
+  mcld::LDSection* oat_section = AddOatInput(oat_writer, &oat_contents);
   if (kUsePortableCompiler) {
     AddMethodInputs(dex_files);
     AddRuntimeInputs(android_root, is_host);
   }
-  if (!Link()) {
+
+  // link inputs
+  if (!linker_->link(*module_.get(), *ir_builder_.get())) {
+    LOG(ERROR) << "Failed to link " << elf_file_->GetPath();
     return false;
   }
+
+  // Fill oat_contents.
+  VectorOutputStream output_stream("oat contents", oat_contents);
+  oat_writer->SetOatDataOffset(oat_section->offset());
+  CHECK(oat_writer->Write(&output_stream));
+  CHECK_EQ(oat_writer->GetSize(), oat_contents.size());
+
+  // emit linked output
+  // TODO: avoid dup of fd by fixing Linker::emit to not close the argument fd.
+  int fd = dup(elf_file_->Fd());
+  if (fd == -1) {
+    PLOG(ERROR) << "Failed to dup file descriptor for " << elf_file_->GetPath();
+    return false;
+  }
+  if (!linker_->emit(*module_.get(), fd)) {
+    LOG(ERROR) << "Failed to emit " << elf_file_->GetPath();
+    return false;
+  }
+  mcld::Finalize();
+  LOG(INFO) << "ELF file written successfully: " << elf_file_->GetPath();
+
   oat_contents.clear();
   if (kUsePortableCompiler) {
     FixupOatMethodOffsets(dex_files);
@@ -156,16 +177,13 @@
   linker_->emulate(*linker_script_.get(), *linker_config_.get());
 }
 
-void ElfWriterMclinker::AddOatInput(std::vector<uint8_t>& oat_contents) {
-  // Add an artificial memory input. Based on LinkerTest.
-  std::string error_msg;
-  std::unique_ptr<OatFile> oat_file(OatFile::OpenMemory(oat_contents, elf_file_->GetPath(), &error_msg));
-  CHECK(oat_file.get() != NULL) << elf_file_->GetPath() << ": " << error_msg;
-
-  const char* oat_data_start = reinterpret_cast<const char*>(&oat_file->GetOatHeader());
-  const size_t oat_data_length = oat_file->GetOatHeader().GetExecutableOffset();
+mcld::LDSection* ElfWriterMclinker::AddOatInput(OatWriter* oat_writer,
+                                                std::vector<uint8_t>* oat_contents) {
+  // NOTE: oat_contents has sufficient reserved space but it doesn't contain the data yet.
+  const char* oat_data_start = reinterpret_cast<const char*>(&(*oat_contents)[0]);
+  const size_t oat_data_length = oat_writer->GetOatHeader().GetExecutableOffset();
   const char* oat_code_start = oat_data_start + oat_data_length;
-  const size_t oat_code_length = oat_file->Size() - oat_data_length;
+  const size_t oat_code_length = oat_writer->GetSize() - oat_data_length;
 
   // TODO: ownership of oat_input?
   oat_input_ = ir_builder_->CreateInput("oat contents",
@@ -205,7 +223,7 @@
 
   // TODO: why does IRBuilder::CreateRegion take a non-const pointer?
   mcld::Fragment* text_fragment = ir_builder_->CreateRegion(const_cast<char*>(oat_data_start),
-                                                            oat_file->Size());
+                                                            oat_writer->GetSize());
   CHECK(text_fragment != NULL);
   ir_builder_->AppendFragment(*text_fragment, *text_sectiondata);
 
@@ -236,6 +254,8 @@
                          // subtract a word so symbol is within section
                          (oat_data_length + oat_code_length) - sizeof(uint32_t),  // offset
                          text_section);
+
+  return text_section;
 }
 
 void ElfWriterMclinker::AddMethodInputs(const std::vector<const DexFile*>& dex_files) {
@@ -322,29 +342,6 @@
   CHECK(libm_lib_input_input != NULL);
 }
 
-bool ElfWriterMclinker::Link() {
-  // link inputs
-  if (!linker_->link(*module_.get(), *ir_builder_.get())) {
-    LOG(ERROR) << "Failed to link " << elf_file_->GetPath();
-    return false;
-  }
-
-  // emit linked output
-  // TODO: avoid dup of fd by fixing Linker::emit to not close the argument fd.
-  int fd = dup(elf_file_->Fd());
-  if (fd == -1) {
-    PLOG(ERROR) << "Failed to dup file descriptor for " << elf_file_->GetPath();
-    return false;
-  }
-  if (!linker_->emit(*module_.get(), fd)) {
-    LOG(ERROR) << "Failed to emit " << elf_file_->GetPath();
-    return false;
-  }
-  mcld::Finalize();
-  LOG(INFO) << "ELF file written successfully: " << elf_file_->GetPath();
-  return true;
-}
-
 void ElfWriterMclinker::FixupOatMethodOffsets(const std::vector<const DexFile*>& dex_files) {
   std::string error_msg;
   std::unique_ptr<ElfFile> elf_file(ElfFile::Open(elf_file_, true, false, &error_msg));
diff --git a/compiler/elf_writer_mclinker.h b/compiler/elf_writer_mclinker.h
index 955e5d2..489fefb 100644
--- a/compiler/elf_writer_mclinker.h
+++ b/compiler/elf_writer_mclinker.h
@@ -61,11 +61,10 @@
   ~ElfWriterMclinker();
 
   void Init();
-  void AddOatInput(std::vector<uint8_t>& oat_contents);
+  mcld::LDSection* AddOatInput(OatWriter* oat_writer, std::vector<uint8_t>* oat_contents);
   void AddMethodInputs(const std::vector<const DexFile*>& dex_files);
   void AddCompiledCodeInput(const CompiledCode& compiled_code);
   void AddRuntimeInputs(const std::string& android_root, bool is_host);
-  bool Link();
   void FixupOatMethodOffsets(const std::vector<const DexFile*>& dex_files)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   uint32_t FixupCompiledCodeOffset(ElfFile& elf_file,
diff --git a/compiler/elf_writer_quick.cc b/compiler/elf_writer_quick.cc
index dbd3a37..e661324 100644
--- a/compiler/elf_writer_quick.cc
+++ b/compiler/elf_writer_quick.cc
@@ -85,26 +85,6 @@
   return elf_writer.Write(oat_writer, dex_files, android_root, is_host);
 }
 
-// Add patch information to this section. Each patch is a Elf_Word that
-// identifies an offset from the start of the text section
-static void ReservePatchSpace(const CompilerDriver* compiler_driver, std::vector<uint8_t>* buffer,
-                              bool debug) {
-  size_t size =
-      compiler_driver->GetCodeToPatch().size() +
-      compiler_driver->GetMethodsToPatch().size() +
-      compiler_driver->GetClassesToPatch().size();
-  if (size == 0) {
-    if (debug) {
-      LOG(INFO) << "No patches to record";
-    }
-    return;
-  }
-  buffer->resize(size * sizeof(uintptr_t));
-  if (debug) {
-    LOG(INFO) << "Patches reserved for " << size;
-  }
-}
-
 std::vector<uint8_t>* ConstructCIEFrameX86(bool is_x86_64) {
   std::vector<uint8_t>* cfi_info = new std::vector<uint8_t>;
 
@@ -219,6 +199,9 @@
  public:
   explicit OatWriterWrapper(OatWriter* oat_writer) : oat_writer_(oat_writer) {}
 
+  void SetCodeOffset(size_t offset) {
+    oat_writer_->SetOatDataOffset(offset);
+  }
   bool Write(OutputStream* out) OVERRIDE {
     return oat_writer_->Write(out);
   }
@@ -274,7 +257,13 @@
   if (compiler_driver_->GetCompilerOptions().GetIncludePatchInformation()) {
     ElfRawSectionBuilder<Elf_Word, Elf_Sword, Elf_Shdr> oat_patches(
         ".oat_patches", SHT_OAT_PATCH, 0, NULL, 0, sizeof(uintptr_t), sizeof(uintptr_t));
-    ReservePatchSpace(compiler_driver_, oat_patches.GetBuffer(), debug);
+    const std::vector<uintptr_t>& locations = oat_writer->GetAbsolutePatchLocations();
+    const uint8_t* begin = reinterpret_cast<const uint8_t*>(&locations[0]);
+    const uint8_t* end = begin + locations.size() * sizeof(locations[0]);
+    oat_patches.GetBuffer()->assign(begin, end);
+    if (debug) {
+      LOG(INFO) << "Prepared .oat_patches for " << locations.size() << " patches.";
+    }
     builder->RegisterRawSection(oat_patches);
   }
 
diff --git a/compiler/image_test.cc b/compiler/image_test.cc
index f2a16e5..2a37049 100644
--- a/compiler/image_test.cc
+++ b/compiler/image_test.cc
@@ -62,6 +62,8 @@
   oat_filename += "oat";
   ScratchFile oat_file(OS::CreateEmptyFile(oat_filename.c_str()));
 
+  const uintptr_t requested_image_base = ART_BASE_ADDRESS;
+  ImageWriter writer(*compiler_driver_, requested_image_base);
   {
     {
       jobject class_loader = NULL;
@@ -79,15 +81,15 @@
       compiler_driver_->CompileAll(class_loader, class_linker->GetBootClassPath(), &timings);
 
       t.NewTiming("WriteElf");
-      ScopedObjectAccess soa(Thread::Current());
       SafeMap<std::string, std::string> key_value_store;
-      OatWriter oat_writer(class_linker->GetBootClassPath(), 0, 0, 0, compiler_driver_.get(), &timings,
-                           &key_value_store);
-      bool success = compiler_driver_->WriteElf(GetTestAndroidRoot(),
-                                                !kIsTargetBuild,
-                                                class_linker->GetBootClassPath(),
-                                                &oat_writer,
-                                                oat_file.GetFile());
+      OatWriter oat_writer(class_linker->GetBootClassPath(), 0, 0, 0, compiler_driver_.get(),
+                           &writer, &timings, &key_value_store);
+      bool success = writer.PrepareImageAddressSpace() &&
+          compiler_driver_->WriteElf(GetTestAndroidRoot(),
+                                     !kIsTargetBuild,
+                                     class_linker->GetBootClassPath(),
+                                     &oat_writer,
+                                     oat_file.GetFile());
       ASSERT_TRUE(success);
     }
   }
@@ -95,11 +97,9 @@
   std::unique_ptr<File> dup_oat(OS::OpenFileReadWrite(oat_file.GetFilename().c_str()));
   ASSERT_TRUE(dup_oat.get() != NULL);
 
-  const uintptr_t requested_image_base = ART_BASE_ADDRESS;
   {
-    ImageWriter writer(*compiler_driver_.get());
-    bool success_image = writer.Write(image_file.GetFilename(), requested_image_base,
-                                      dup_oat->GetPath(), dup_oat->GetPath());
+    bool success_image =
+        writer.Write(image_file.GetFilename(), dup_oat->GetPath(), dup_oat->GetPath());
     ASSERT_TRUE(success_image);
     bool success_fixup = ElfFixup::Fixup(dup_oat.get(), writer.GetOatDataBegin());
     ASSERT_TRUE(success_fixup);
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index c08d3bd..1c8b8d5 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -29,7 +29,6 @@
 #include "driver/compiler_driver.h"
 #include "elf_file.h"
 #include "elf_utils.h"
-#include "elf_patcher.h"
 #include "elf_writer.h"
 #include "gc/accounting/card_table-inl.h"
 #include "gc/accounting/heap_bitmap.h"
@@ -68,15 +67,38 @@
 
 namespace art {
 
+bool ImageWriter::PrepareImageAddressSpace() {
+  {
+    Thread::Current()->TransitionFromSuspendedToRunnable();
+    PruneNonImageClasses();  // Remove junk
+    ComputeLazyFieldsForImageClasses();  // Add useful information
+    ComputeEagerResolvedStrings();
+    Thread::Current()->TransitionFromRunnableToSuspended(kNative);
+  }
+  gc::Heap* heap = Runtime::Current()->GetHeap();
+  heap->CollectGarbage(false);  // Remove garbage.
+
+  if (!AllocMemory()) {
+    return false;
+  }
+
+  if (kIsDebugBuild) {
+    ScopedObjectAccess soa(Thread::Current());
+    CheckNonImageClassesRemoved();
+  }
+
+  Thread::Current()->TransitionFromSuspendedToRunnable();
+  CalculateNewObjectOffsets();
+  Thread::Current()->TransitionFromRunnableToSuspended(kNative);
+
+  return true;
+}
+
 bool ImageWriter::Write(const std::string& image_filename,
-                        uintptr_t image_begin,
                         const std::string& oat_filename,
                         const std::string& oat_location) {
   CHECK(!image_filename.empty());
 
-  CHECK_NE(image_begin, 0U);
-  image_begin_ = reinterpret_cast<byte*>(image_begin);
-
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
 
   std::unique_ptr<File> oat_file(OS::OpenFileReadWrite(oat_filename.c_str()));
@@ -115,35 +137,18 @@
       oat_file_->GetOatHeader().GetQuickResolutionTrampolineOffset();
   quick_to_interpreter_bridge_offset_ =
       oat_file_->GetOatHeader().GetQuickToInterpreterBridgeOffset();
-  {
-    Thread::Current()->TransitionFromSuspendedToRunnable();
-    PruneNonImageClasses();  // Remove junk
-    ComputeLazyFieldsForImageClasses();  // Add useful information
-    ComputeEagerResolvedStrings();
-    Thread::Current()->TransitionFromRunnableToSuspended(kNative);
-  }
-  gc::Heap* heap = Runtime::Current()->GetHeap();
-  heap->CollectGarbage(false);  // Remove garbage.
 
-  if (!AllocMemory()) {
-    return false;
-  }
-
-  if (kIsDebugBuild) {
-    ScopedObjectAccess soa(Thread::Current());
-    CheckNonImageClassesRemoved();
-  }
-
-  Thread::Current()->TransitionFromSuspendedToRunnable();
   size_t oat_loaded_size = 0;
   size_t oat_data_offset = 0;
   ElfWriter::GetOatElfInformation(oat_file.get(), oat_loaded_size, oat_data_offset);
-  CalculateNewObjectOffsets(oat_loaded_size, oat_data_offset);
-  CopyAndFixupObjects();
 
-  PatchOatCodeAndMethods(oat_file.get());
+  Thread::Current()->TransitionFromSuspendedToRunnable();
+  CreateHeader(oat_loaded_size, oat_data_offset);
+  CopyAndFixupObjects();
   Thread::Current()->TransitionFromRunnableToSuspended(kNative);
 
+  SetOatChecksumFromElfFile(oat_file.get());
+
   std::unique_ptr<File> image_file(OS::CreateEmptyFile(image_filename.c_str()));
   ImageHeader* image_header = reinterpret_cast<ImageHeader*>(image_->Begin());
   if (image_file.get() == NULL) {
@@ -527,8 +532,7 @@
   writer->WalkFieldsInOrder(obj);
 }
 
-void ImageWriter::CalculateNewObjectOffsets(size_t oat_loaded_size, size_t oat_data_offset) {
-  CHECK_NE(0U, oat_loaded_size);
+void ImageWriter::CalculateNewObjectOffsets() {
   Thread* self = Thread::Current();
   StackHandleScope<1> hs(self);
   Handle<ObjectArray<Object>> image_roots(hs.NewHandle(CreateImageRoots()));
@@ -548,7 +552,14 @@
     heap->VisitObjects(WalkFieldsCallback, this);
   }
 
-  const byte* oat_file_begin = image_begin_ + RoundUp(image_end_, kPageSize);
+  image_roots_address_ = PointerToLowMemUInt32(GetImageAddress(image_roots.Get()));
+
+  // Note that image_end_ is left at end of used space
+}
+
+void ImageWriter::CreateHeader(size_t oat_loaded_size, size_t oat_data_offset) {
+  CHECK_NE(0U, oat_loaded_size);
+  const byte* oat_file_begin = GetOatFileBegin();
   const byte* oat_file_end = oat_file_begin + oat_loaded_size;
   oat_data_begin_ = oat_file_begin + oat_data_offset;
   const byte* oat_data_end = oat_data_begin_ + oat_file_->Size();
@@ -558,21 +569,19 @@
   const size_t heap_bytes_per_bitmap_byte = kBitsPerByte * kObjectAlignment;
   const size_t bitmap_bytes = RoundUp(image_end_, heap_bytes_per_bitmap_byte) /
       heap_bytes_per_bitmap_byte;
-  ImageHeader image_header(PointerToLowMemUInt32(image_begin_),
-                           static_cast<uint32_t>(image_end_),
-                           RoundUp(image_end_, kPageSize),
-                           RoundUp(bitmap_bytes, kPageSize),
-                           PointerToLowMemUInt32(GetImageAddress(image_roots.Get())),
-                           oat_file_->GetOatHeader().GetChecksum(),
-                           PointerToLowMemUInt32(oat_file_begin),
-                           PointerToLowMemUInt32(oat_data_begin_),
-                           PointerToLowMemUInt32(oat_data_end),
-                           PointerToLowMemUInt32(oat_file_end));
-  memcpy(image_->Begin(), &image_header, sizeof(image_header));
-
-  // Note that image_end_ is left at end of used space
+  new (image_->Begin()) ImageHeader(PointerToLowMemUInt32(image_begin_),
+                                    static_cast<uint32_t>(image_end_),
+                                    RoundUp(image_end_, kPageSize),
+                                    RoundUp(bitmap_bytes, kPageSize),
+                                    image_roots_address_,
+                                    oat_file_->GetOatHeader().GetChecksum(),
+                                    PointerToLowMemUInt32(oat_file_begin),
+                                    PointerToLowMemUInt32(oat_data_begin_),
+                                    PointerToLowMemUInt32(oat_data_end),
+                                    PointerToLowMemUInt32(oat_file_end));
 }
 
+
 void ImageWriter::CopyAndFixupObjects()
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   ScopedAssertNoThreadSuspension ants(Thread::Current(), "ImageWriter");
@@ -809,19 +818,12 @@
   return reinterpret_cast<OatHeader*>(elf->Begin() + data_sec->sh_offset);
 }
 
-void ImageWriter::PatchOatCodeAndMethods(File* elf_file) {
+void ImageWriter::SetOatChecksumFromElfFile(File* elf_file) {
   std::string error_msg;
   std::unique_ptr<ElfFile> elf(ElfFile::Open(elf_file, PROT_READ|PROT_WRITE,
                                              MAP_SHARED, &error_msg));
   if (elf.get() == nullptr) {
-    LOG(FATAL) << "Unable patch oat file: " << error_msg;
-    return;
-  }
-  if (!ElfPatcher::Patch(&compiler_driver_, elf.get(), oat_file_,
-                         reinterpret_cast<uintptr_t>(oat_data_begin_),
-                         GetImageAddressCallback, reinterpret_cast<void*>(this),
-                         &error_msg)) {
-    LOG(FATAL) << "unable to patch oat file: " << error_msg;
+    LOG(FATAL) << "Unable open oat file: " << error_msg;
     return;
   }
   OatHeader* oat_header = GetOatHeaderFromElf(elf.get());
diff --git a/compiler/image_writer.h b/compiler/image_writer.h
index e8bcf7f..bdf0614 100644
--- a/compiler/image_writer.h
+++ b/compiler/image_writer.h
@@ -37,17 +37,39 @@
 // Write a Space built during compilation for use during execution.
 class ImageWriter {
  public:
-  explicit ImageWriter(const CompilerDriver& compiler_driver)
-      : compiler_driver_(compiler_driver), oat_file_(NULL), image_end_(0), image_begin_(NULL),
+  ImageWriter(const CompilerDriver& compiler_driver, uintptr_t image_begin)
+      : compiler_driver_(compiler_driver), image_begin_(reinterpret_cast<byte*>(image_begin)),
+        image_end_(0), image_roots_address_(0), oat_file_(NULL),
         oat_data_begin_(NULL), interpreter_to_interpreter_bridge_offset_(0),
-        interpreter_to_compiled_code_bridge_offset_(0), portable_imt_conflict_trampoline_offset_(0),
-        portable_resolution_trampoline_offset_(0), quick_generic_jni_trampoline_offset_(0),
-        quick_imt_conflict_trampoline_offset_(0), quick_resolution_trampoline_offset_(0) {}
+        interpreter_to_compiled_code_bridge_offset_(0), jni_dlsym_lookup_offset_(0),
+        portable_imt_conflict_trampoline_offset_(0), portable_resolution_trampoline_offset_(0),
+        portable_to_interpreter_bridge_offset_(0), quick_generic_jni_trampoline_offset_(0),
+        quick_imt_conflict_trampoline_offset_(0), quick_resolution_trampoline_offset_(0),
+        quick_to_interpreter_bridge_offset_(0) {
+    CHECK_NE(image_begin, 0U);
+  }
 
   ~ImageWriter() {}
 
+  bool PrepareImageAddressSpace();
+
+  bool IsImageAddressSpaceReady() const {
+    return image_roots_address_ != 0u;
+  }
+
+  mirror::Object* GetImageAddress(mirror::Object* object) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (object == NULL) {
+      return NULL;
+    }
+    return reinterpret_cast<mirror::Object*>(image_begin_ + GetImageOffset(object));
+  }
+
+  byte* GetOatFileBegin() const {
+    return image_begin_ + RoundUp(image_end_, kPageSize);
+  }
+
   bool Write(const std::string& image_filename,
-             uintptr_t image_begin,
              const std::string& oat_filename,
              const std::string& oat_location)
       LOCKS_EXCLUDED(Locks::mutator_lock_);
@@ -75,14 +97,6 @@
     return reinterpret_cast<ImageWriter*>(writer)->GetImageAddress(obj);
   }
 
-  mirror::Object* GetImageAddress(mirror::Object* object) const
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    if (object == NULL) {
-      return NULL;
-    }
-    return reinterpret_cast<mirror::Object*>(image_begin_ + GetImageOffset(object));
-  }
-
   mirror::Object* GetLocalAddress(mirror::Object* object) const
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     size_t offset = GetImageOffset(object);
@@ -131,7 +145,9 @@
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   // Lays out where the image objects will be at runtime.
-  void CalculateNewObjectOffsets(size_t oat_loaded_size, size_t oat_data_offset)
+  void CalculateNewObjectOffsets()
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void CreateHeader(size_t oat_loaded_size, size_t oat_data_offset)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   mirror::ObjectArray<mirror::Object>* CreateImageRoots() const
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -162,23 +178,25 @@
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   // Patches references in OatFile to expect runtime addresses.
-  void PatchOatCodeAndMethods(File* elf_file)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void SetOatChecksumFromElfFile(File* elf_file);
 
   const CompilerDriver& compiler_driver_;
 
+  // Beginning target image address for the output image.
+  byte* image_begin_;
+
+  // Offset to the free space in image_.
+  size_t image_end_;
+
+  // The image roots address in the image.
+  uint32_t image_roots_address_;
+
   // oat file with code for this image
   OatFile* oat_file_;
 
   // Memory mapped for generating the image.
   std::unique_ptr<MemMap> image_;
 
-  // Offset to the free space in image_.
-  size_t image_end_;
-
-  // Beginning target image address for the output image.
-  byte* image_begin_;
-
   // Saved hashes (objects are inside of the image so that they don't move).
   std::vector<std::pair<mirror::Object*, uint32_t>> saved_hashes_;
 
diff --git a/compiler/oat_test.cc b/compiler/oat_test.cc
index 80d7b98..0b1f9e2 100644
--- a/compiler/oat_test.cc
+++ b/compiler/oat_test.cc
@@ -114,7 +114,6 @@
     compiler_driver_->CompileAll(class_loader, class_linker->GetBootClassPath(), &timings);
   }
 
-  ScopedObjectAccess soa(Thread::Current());
   ScratchFile tmp;
   SafeMap<std::string, std::string> key_value_store;
   key_value_store.Put(OatHeader::kImageLocationKey, "lue.art");
@@ -123,6 +122,7 @@
                        4096U,
                        0,
                        compiler_driver_.get(),
+                       nullptr,
                        &timings,
                        &key_value_store);
   bool success = compiler_driver_->WriteElf(GetTestAndroidRoot(),
@@ -152,6 +152,7 @@
                                                                     &dex_file_checksum);
   ASSERT_TRUE(oat_dex_file != nullptr);
   CHECK_EQ(dex_file->GetLocationChecksum(), oat_dex_file->GetDexFileLocationChecksum());
+  ScopedObjectAccess soa(Thread::Current());
   for (size_t i = 0; i < dex_file->NumClassDefs(); i++) {
     const DexFile::ClassDef& class_def = dex_file->GetClassDef(i);
     const byte* class_data = dex_file->GetClassData(class_def);
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index e74d6de..dd64368 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -27,6 +27,7 @@
 #include "dex_file-inl.h"
 #include "dex/verification_results.h"
 #include "gc/space/space.h"
+#include "image_writer.h"
 #include "mirror/art_method-inl.h"
 #include "mirror/array.h"
 #include "mirror/class_loader.h"
@@ -36,10 +37,270 @@
 #include "safe_map.h"
 #include "scoped_thread_state_change.h"
 #include "handle_scope-inl.h"
+#include "utils/arm/assembler_thumb2.h"
 #include "verifier/method_verifier.h"
 
 namespace art {
 
+class OatWriter::RelativeCallPatcher {
+ public:
+  virtual ~RelativeCallPatcher() { }
+
+  // Reserve space for relative call thunks if needed, return adjusted offset.
+  // After all methods have been processed it's call one last time with compiled_method == nullptr.
+  virtual uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method) = 0;
+
+  // Write relative call thunks if needed, return adjusted offset.
+  virtual uint32_t WriteThunks(OutputStream* out, uint32_t offset) = 0;
+
+  // Patch method code. The input displacement is relative to the patched location,
+  // the patcher may need to adjust it if the correct base is different.
+  virtual void Patch(std::vector<uint8_t>* code, uint32_t literal_offset, uint32_t patch_offset,
+                     uint32_t target_offset) = 0;
+
+ protected:
+  RelativeCallPatcher() { }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(RelativeCallPatcher);
+};
+
+class OatWriter::NoRelativeCallPatcher FINAL : public RelativeCallPatcher {
+ public:
+  NoRelativeCallPatcher() { }
+
+  uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method) OVERRIDE {
+    return offset;  // No space reserved; no patches expected.
+  }
+
+  uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE {
+    return offset;  // No thunks added; no patches expected.
+  }
+
+  void Patch(std::vector<uint8_t>* code, uint32_t literal_offset, uint32_t patch_offset,
+             uint32_t target_offset) OVERRIDE {
+    LOG(FATAL) << "Unexpected relative patch.";
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(NoRelativeCallPatcher);
+};
+
+class OatWriter::X86RelativeCallPatcher FINAL : public RelativeCallPatcher {
+ public:
+  X86RelativeCallPatcher() { }
+
+  uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method) OVERRIDE {
+    return offset;  // No space reserved; no limit on relative call distance.
+  }
+
+  uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE {
+    return offset;  // No thunks added; no limit on relative call distance.
+  }
+
+  void Patch(std::vector<uint8_t>* code, uint32_t literal_offset, uint32_t patch_offset,
+             uint32_t target_offset) OVERRIDE {
+    DCHECK_LE(literal_offset + 4u, code->size());
+    // Unsigned arithmetic with its well-defined overflow behavior is just fine here.
+    uint32_t displacement = target_offset - patch_offset;
+    displacement -= kPcDisplacement;  // The base PC is at the end of the 4-byte patch.
+
+    typedef __attribute__((__aligned__(1))) int32_t unaligned_int32_t;
+    reinterpret_cast<unaligned_int32_t*>(&(*code)[literal_offset])[0] = displacement;
+  }
+
+ private:
+  // PC displacement from patch location; x86 PC for relative calls points to the next
+  // instruction and the patch location is 4 bytes earlier.
+  static constexpr int32_t kPcDisplacement = 4;
+
+  DISALLOW_COPY_AND_ASSIGN(X86RelativeCallPatcher);
+};
+
+class OatWriter::Thumb2RelativeCallPatcher FINAL : public RelativeCallPatcher {
+ public:
+  explicit Thumb2RelativeCallPatcher(OatWriter* writer)
+      : writer_(writer), thunk_code_(CompileThunkCode()),
+        thunk_locations_(), current_thunk_to_write_(0u), unprocessed_patches_() {
+  }
+
+  uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method) OVERRIDE {
+    // NOTE: The final thunk can be reserved from InitCodeMethodVisitor::EndClass() while it
+    // may be written early by WriteCodeMethodVisitor::VisitMethod() for a deduplicated chunk
+    // of code. To avoid any alignment discrepancies for the final chunk, we always align the
+    // offset after reserving of writing any chunk.
+    if (UNLIKELY(compiled_method == nullptr)) {
+      uint32_t aligned_offset = CompiledMethod::AlignCode(offset, kThumb2);
+      bool needs_thunk = ReserveSpaceProcessPatches(aligned_offset);
+      if (needs_thunk) {
+        thunk_locations_.push_back(aligned_offset);
+        offset = CompiledMethod::AlignCode(aligned_offset + thunk_code_.size(), kThumb2);
+      }
+      return offset;
+    }
+    DCHECK(compiled_method->GetQuickCode() != nullptr);
+    uint32_t quick_code_size = compiled_method->GetQuickCode()->size();
+    uint32_t quick_code_offset = compiled_method->AlignCode(offset) + sizeof(OatQuickMethodHeader);
+    uint32_t next_aligned_offset = compiled_method->AlignCode(quick_code_offset + quick_code_size);
+    if (!unprocessed_patches_.empty() &&
+        next_aligned_offset - unprocessed_patches_.front().second > kMaxPositiveDisplacement) {
+      bool needs_thunk = ReserveSpaceProcessPatches(next_aligned_offset);
+      if (needs_thunk) {
+        // A single thunk will cover all pending patches.
+        unprocessed_patches_.clear();
+        uint32_t thunk_location = compiled_method->AlignCode(offset);
+        thunk_locations_.push_back(thunk_location);
+        offset = CompiledMethod::AlignCode(thunk_location + thunk_code_.size(), kThumb2);
+      }
+    }
+    for (const LinkerPatch& patch : compiled_method->GetPatches()) {
+      if (patch.Type() == kLinkerPatchCallRelative) {
+        unprocessed_patches_.emplace_back(patch.TargetMethod(),
+                                          quick_code_offset + patch.LiteralOffset());
+      }
+    }
+    return offset;
+  }
+
+  uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE {
+    if (current_thunk_to_write_ == thunk_locations_.size()) {
+      return offset;
+    }
+    uint32_t aligned_offset = CompiledMethod::AlignCode(offset, kThumb2);
+    if (UNLIKELY(aligned_offset == thunk_locations_[current_thunk_to_write_])) {
+      ++current_thunk_to_write_;
+      uint32_t aligned_code_delta = aligned_offset - offset;
+      if (aligned_code_delta != 0u && !writer_->WriteCodeAlignment(out, aligned_code_delta)) {
+        return 0u;
+      }
+      if (!out->WriteFully(thunk_code_.data(), thunk_code_.size())) {
+        return 0u;
+      }
+      writer_->size_relative_call_thunks_ += thunk_code_.size();
+      uint32_t thunk_end_offset = aligned_offset + thunk_code_.size();
+      // Align after writing chunk, see the ReserveSpace() above.
+      offset = CompiledMethod::AlignCode(thunk_end_offset, kThumb2);
+      aligned_code_delta = offset - thunk_end_offset;
+      if (aligned_code_delta != 0u && !writer_->WriteCodeAlignment(out, aligned_code_delta)) {
+        return 0u;
+      }
+    }
+    return offset;
+  }
+
+  void Patch(std::vector<uint8_t>* code, uint32_t literal_offset, uint32_t patch_offset,
+             uint32_t target_offset) OVERRIDE {
+    DCHECK_LE(literal_offset + 4u, code->size());
+    DCHECK_EQ(literal_offset & 1u, 0u);
+    DCHECK_EQ(patch_offset & 1u, 0u);
+    DCHECK_EQ(target_offset & 1u, 1u);  // Thumb2 mode bit.
+    // Unsigned arithmetic with its well-defined overflow behavior is just fine here.
+    uint32_t displacement = target_offset - 1u - patch_offset;
+    // NOTE: With unsigned arithmetic we do mean to use && rather than || below.
+    if (displacement > kMaxPositiveDisplacement && displacement < -kMaxNegativeDisplacement) {
+      // Unwritten thunks have higher offsets, check if it's within range.
+      DCHECK(current_thunk_to_write_ == thunk_locations_.size() ||
+             thunk_locations_[current_thunk_to_write_] > patch_offset);
+      if (current_thunk_to_write_ != thunk_locations_.size() &&
+          thunk_locations_[current_thunk_to_write_] - patch_offset < kMaxPositiveDisplacement) {
+        displacement = thunk_locations_[current_thunk_to_write_] - patch_offset;
+      } else {
+        // We must have a previous thunk then.
+        DCHECK_NE(current_thunk_to_write_, 0u);
+        DCHECK_LT(thunk_locations_[current_thunk_to_write_ - 1], patch_offset);
+        displacement = thunk_locations_[current_thunk_to_write_ - 1] - patch_offset;
+        DCHECK(displacement >= -kMaxNegativeDisplacement);
+      }
+    }
+    displacement -= kPcDisplacement;  // The base PC is at the end of the 4-byte patch.
+    DCHECK_EQ(displacement & 1u, 0u);
+    DCHECK((displacement >> 24) == 0u || (displacement >> 24) == 255u);  // 25-bit signed.
+    uint32_t signbit = (displacement >> 31) & 0x1;
+    uint32_t i1 = (displacement >> 23) & 0x1;
+    uint32_t i2 = (displacement >> 22) & 0x1;
+    uint32_t imm10 = (displacement >> 12) & 0x03ff;
+    uint32_t imm11 = (displacement >> 1) & 0x07ff;
+    uint32_t j1 = i1 ^ (signbit ^ 1);
+    uint32_t j2 = i2 ^ (signbit ^ 1);
+    uint32_t value = (signbit << 26) | (j1 << 13) | (j2 << 11) | (imm10 << 16) | imm11;
+    value |= 0xf000d000;  // BL
+
+    uint8_t* addr = &(*code)[literal_offset];
+    // Check that we're just overwriting an existing BL.
+    DCHECK_EQ(addr[1] & 0xf8, 0xf0);
+    DCHECK_EQ(addr[3] & 0xd0, 0xd0);
+    // Write the new BL.
+    addr[0] = (value >> 16) & 0xff;
+    addr[1] = (value >> 24) & 0xff;
+    addr[2] = (value >> 0) & 0xff;
+    addr[3] = (value >> 8) & 0xff;
+  }
+
+ private:
+  bool ReserveSpaceProcessPatches(uint32_t next_aligned_offset) {
+    // Process as many patches as possible, stop only on unresolved targets or calls too far back.
+    while (!unprocessed_patches_.empty()) {
+      uint32_t patch_offset = unprocessed_patches_.front().second;
+      auto it = writer_->method_offset_map_.find(unprocessed_patches_.front().first);
+      if (it == writer_->method_offset_map_.end()) {
+        // If still unresolved, check if we have a thunk within range.
+        DCHECK(thunk_locations_.empty() || thunk_locations_.back() <= patch_offset);
+        if (thunk_locations_.empty() ||
+            patch_offset - thunk_locations_.back() > kMaxNegativeDisplacement) {
+          return next_aligned_offset - patch_offset > kMaxPositiveDisplacement;
+        }
+      } else if (it->second >= patch_offset) {
+        DCHECK_LE(it->second - patch_offset, kMaxPositiveDisplacement);
+      } else {
+        // When calling back, check if we have a thunk that's closer than the actual target.
+        uint32_t target_offset = (thunk_locations_.empty() || it->second > thunk_locations_.back())
+            ? it->second
+            : thunk_locations_.back();
+        DCHECK_GT(patch_offset, target_offset);
+        if (patch_offset - target_offset > kMaxNegativeDisplacement) {
+          return true;
+        }
+      }
+      unprocessed_patches_.pop_front();
+    }
+    return false;
+  }
+
+  static std::vector<uint8_t> CompileThunkCode() {
+    // The thunk just uses the entry point in the ArtMethod. This works even for calls
+    // to the generic JNI and interpreter trampolines.
+    arm::Thumb2Assembler assembler;
+    assembler.LoadFromOffset(
+        arm::kLoadWord, arm::PC, arm::R0,
+        mirror::ArtMethod::EntryPointFromQuickCompiledCodeOffset().Int32Value());
+    assembler.bkpt(0);
+    std::vector<uint8_t> thunk_code(assembler.CodeSize());
+    MemoryRegion code(thunk_code.data(), thunk_code.size());
+    assembler.FinalizeInstructions(code);
+    return thunk_code;
+  }
+
+  // PC displacement from patch location; Thumb2 PC is always at instruction address + 4.
+  static constexpr int32_t kPcDisplacement = 4;
+
+  // Maximum positive and negative displacement measured from the patch location.
+  // (Signed 25 bit displacement with the last bit 0 has range [-2^24, 2^24-2] measured from
+  // the Thumb2 PC pointing right after the BL, i.e. 4 bytes later than the patch location.)
+  static constexpr uint32_t kMaxPositiveDisplacement = (1u << 24) - 2 + kPcDisplacement;
+  static constexpr uint32_t kMaxNegativeDisplacement = (1u << 24) - kPcDisplacement;
+
+  OatWriter* const writer_;
+  const std::vector<uint8_t> thunk_code_;
+  std::vector<uint32_t> thunk_locations_;
+  size_t current_thunk_to_write_;
+
+  // ReserveSpace() tracks unprocessed patches.
+  typedef std::pair<MethodReference, uint32_t> UnprocessedPatch;
+  std::deque<UnprocessedPatch> unprocessed_patches_;
+
+  DISALLOW_COPY_AND_ASSIGN(Thumb2RelativeCallPatcher);
+};
+
 #define DCHECK_OFFSET() \
   DCHECK_EQ(static_cast<off_t>(file_offset + relative_offset), out->Seek(0, kSeekCurrent)) \
     << "file_offset=" << file_offset << " relative_offset=" << relative_offset
@@ -53,10 +314,14 @@
                      uintptr_t image_file_location_oat_begin,
                      int32_t image_patch_delta,
                      const CompilerDriver* compiler,
+                     ImageWriter* image_writer,
                      TimingLogger* timings,
                      SafeMap<std::string, std::string>* key_value_store)
   : compiler_driver_(compiler),
+    image_writer_(image_writer),
     dex_files_(&dex_files),
+    size_(0u),
+    oat_data_offset_(0u),
     image_file_location_oat_checksum_(image_file_location_oat_checksum),
     image_file_location_oat_begin_(image_file_location_oat_begin),
     image_patch_delta_(image_patch_delta),
@@ -81,6 +346,7 @@
     size_method_header_(0),
     size_code_(0),
     size_code_alignment_(0),
+    size_relative_call_thunks_(0),
     size_mapping_table_(0),
     size_vmap_table_(0),
     size_gc_map_(0),
@@ -92,9 +358,27 @@
     size_oat_class_type_(0),
     size_oat_class_status_(0),
     size_oat_class_method_bitmaps_(0),
-    size_oat_class_method_offsets_(0) {
+    size_oat_class_method_offsets_(0),
+    method_offset_map_() {
   CHECK(key_value_store != nullptr);
 
+  switch (compiler_driver_->GetInstructionSet()) {
+    case kX86:
+    case kX86_64:
+      relative_call_patcher_.reset(new X86RelativeCallPatcher);
+      break;
+    case kArm:
+      // Fall through: we generate Thumb2 code for "arm".
+    case kThumb2:
+      relative_call_patcher_.reset(new Thumb2RelativeCallPatcher(this));
+      break;
+    case kArm64:
+      // TODO: Implement relative calls for arm64.
+    default:
+      relative_call_patcher_.reset(new NoRelativeCallPatcher);
+      break;
+  }
+
   size_t offset;
   {
     TimingLogger::ScopedTiming split("InitOatHeader", timings);
@@ -127,6 +411,7 @@
   size_ = offset;
 
   CHECK_EQ(dex_files_->size(), oat_dex_files_.size());
+  CHECK_EQ(compiler->IsImage(), image_writer_ != nullptr);
   CHECK_EQ(compiler->IsImage(),
            key_value_store_->find(OatHeader::kImageLocationKey) == key_value_store_->end());
   CHECK_ALIGNED(image_patch_delta_, kPageSize);
@@ -316,6 +601,7 @@
     OatClass* oat_class = new OatClass(offset_, compiled_methods_,
                                        num_non_null_compiled_methods_, status);
     writer_->oat_classes_.push_back(oat_class);
+    oat_class->UpdateChecksum(writer_->oat_header_);
     offset_ += oat_class->SizeOf();
     return DexMethodVisitor::EndClass();
   }
@@ -329,6 +615,16 @@
  public:
   InitCodeMethodVisitor(OatWriter* writer, size_t offset)
     : OatDexMethodVisitor(writer, offset) {
+    writer_->absolute_patch_locations_.reserve(
+        writer_->compiler_driver_->GetNonRelativeLinkerPatchCount());
+  }
+
+  bool EndClass() {
+    OatDexMethodVisitor::EndClass();
+    if (oat_class_index_ == writer_->oat_classes_.size()) {
+      offset_ = writer_->relative_call_patcher_->ReserveSpace(offset_, nullptr);
+    }
+    return true;
   }
 
   bool VisitMethod(size_t class_def_method_index, const ClassDataItemIterator& it)
@@ -350,6 +646,7 @@
             oat_method_offsets_offset + OFFSETOF_MEMBER(OatMethodOffsets, code_offset_));
       } else {
         CHECK(quick_code != nullptr);
+        offset_ = writer_->relative_call_patcher_->ReserveSpace(offset_, compiled_method);
         offset_ = compiled_method->AlignCode(offset_);
         DCHECK_ALIGNED_PARAM(offset_,
                              GetInstructionSetAlignment(compiled_method->GetInstructionSet()));
@@ -369,6 +666,18 @@
           dedupe_map_.PutBefore(lb, compiled_method, quick_code_offset);
         }
 
+        MethodReference method_ref(dex_file_, it.GetMemberIndex());
+        auto method_lb = writer_->method_offset_map_.lower_bound(method_ref);
+        if (method_lb != writer_->method_offset_map_.end() &&
+            !writer_->method_offset_map_.key_comp()(method_ref, method_lb->first)) {
+          // TODO: Should this be a hard failure?
+          LOG(WARNING) << "Multiple definitions of "
+              << PrettyMethod(method_ref.dex_method_index, *method_ref.dex_file)
+              << ((method_lb->second != quick_code_offset) ? "; OFFSET MISMATCH" : "");
+        } else {
+          writer_->method_offset_map_.PutBefore(method_lb, method_ref, quick_code_offset);
+        }
+
         // Update quick method header.
         DCHECK_LT(method_offsets_index_, oat_class->method_headers_.size());
         OatQuickMethodHeader* method_header = &oat_class->method_headers_[method_offsets_index_];
@@ -392,12 +701,19 @@
                                               frame_size_in_bytes, core_spill_mask, fp_spill_mask,
                                               code_size);
 
-        // Update checksum if this wasn't a duplicate.
         if (!deduped) {
-          writer_->oat_header_->UpdateChecksum(method_header, sizeof(*method_header));
+          // Update offsets. (Checksum is updated when writing.)
           offset_ += sizeof(*method_header);  // Method header is prepended before code.
-          writer_->oat_header_->UpdateChecksum(&(*quick_code)[0], code_size);
           offset_ += code_size;
+          // Record absolute patch locations.
+          if (!compiled_method->GetPatches().empty()) {
+            uintptr_t base_loc = offset_ - code_size - writer_->oat_header_->GetExecutableOffset();
+            for (const LinkerPatch& patch : compiled_method->GetPatches()) {
+              if (patch.Type() != kLinkerPatchCallRelative) {
+                writer_->absolute_patch_locations_.push_back(base_loc + patch.LiteralOffset());
+              }
+            }
+          }
         }
 
         if (writer_->compiler_driver_->GetCompilerOptions().GetIncludeDebugSymbols()) {
@@ -548,13 +864,51 @@
 class OatWriter::WriteCodeMethodVisitor : public OatDexMethodVisitor {
  public:
   WriteCodeMethodVisitor(OatWriter* writer, OutputStream* out, const size_t file_offset,
-                             size_t relative_offset)
+                         size_t relative_offset) SHARED_LOCK_FUNCTION(Locks::mutator_lock_)
     : OatDexMethodVisitor(writer, relative_offset),
       out_(out),
-      file_offset_(file_offset) {
+      file_offset_(file_offset),
+      self_(Thread::Current()),
+      old_no_thread_suspension_cause_(self_->StartAssertNoThreadSuspension("OatWriter patching")),
+      class_linker_(Runtime::Current()->GetClassLinker()),
+      dex_cache_(nullptr) {
+    if (writer_->image_writer_ != nullptr) {
+      // If we're creating the image, the address space must be ready so that we can apply patches.
+      CHECK(writer_->image_writer_->IsImageAddressSpaceReady());
+      patched_code_.reserve(16 * KB);
+    }
+    self_->TransitionFromSuspendedToRunnable();
   }
 
-  bool VisitMethod(size_t class_def_method_index, const ClassDataItemIterator& it) {
+  ~WriteCodeMethodVisitor() UNLOCK_FUNCTION(Locks::mutator_lock_) {
+    self_->EndAssertNoThreadSuspension(old_no_thread_suspension_cause_);
+    self_->TransitionFromRunnableToSuspended(kNative);
+  }
+
+  bool StartClass(const DexFile* dex_file, size_t class_def_index)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    OatDexMethodVisitor::StartClass(dex_file, class_def_index);
+    if (dex_cache_ == nullptr || dex_cache_->GetDexFile() != dex_file) {
+      dex_cache_ = class_linker_->FindDexCache(*dex_file);
+    }
+    return true;
+  }
+
+  bool EndClass() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    bool result = OatDexMethodVisitor::EndClass();
+    if (oat_class_index_ == writer_->oat_classes_.size()) {
+      DCHECK(result);  // OatDexMethodVisitor::EndClass() never fails.
+      offset_ = writer_->relative_call_patcher_->WriteThunks(out_, offset_);
+      if (UNLIKELY(offset_ == 0u)) {
+        PLOG(ERROR) << "Failed to write final relative call thunks";
+        result = false;
+      }
+    }
+    return result;
+  }
+
+  bool VisitMethod(size_t class_def_method_index, const ClassDataItemIterator& it)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     OatClass* oat_class = writer_->oat_classes_[oat_class_index_];
     const CompiledMethod* compiled_method = oat_class->GetCompiledMethod(class_def_method_index);
 
@@ -565,18 +919,18 @@
       const std::vector<uint8_t>* quick_code = compiled_method->GetQuickCode();
       if (quick_code != nullptr) {
         CHECK(compiled_method->GetPortableCode() == nullptr);
+        offset_ = writer_->relative_call_patcher_->WriteThunks(out, offset_);
+        if (offset_ == 0u) {
+          ReportWriteFailure("relative call thunk", it);
+          return false;
+        }
         uint32_t aligned_offset = compiled_method->AlignCode(offset_);
         uint32_t aligned_code_delta = aligned_offset - offset_;
         if (aligned_code_delta != 0) {
-          static const uint8_t kPadding[] = {
-              0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u
-          };
-          DCHECK_LE(aligned_code_delta, sizeof(kPadding));
-          if (UNLIKELY(!out->WriteFully(kPadding, aligned_code_delta))) {
+          if (!writer_->WriteCodeAlignment(out, aligned_code_delta)) {
             ReportWriteFailure("code alignment padding", it);
             return false;
           }
-          writer_->size_code_alignment_ += aligned_code_delta;
           offset_ += aligned_code_delta;
           DCHECK_OFFSET_();
         }
@@ -591,7 +945,9 @@
                    offset_ + sizeof(OatQuickMethodHeader) + compiled_method->CodeDelta())
             << PrettyMethod(it.GetMemberIndex(), *dex_file_);
         if (method_offsets.code_offset_ >= offset_) {
-          const OatQuickMethodHeader& method_header = oat_class->method_headers_[method_offsets_index_];
+          const OatQuickMethodHeader& method_header =
+              oat_class->method_headers_[method_offsets_index_];
+          writer_->oat_header_->UpdateChecksum(&method_header, sizeof(method_header));
           if (!out->WriteFully(&method_header, sizeof(method_header))) {
             ReportWriteFailure("method header", it);
             return false;
@@ -599,6 +955,31 @@
           writer_->size_method_header_ += sizeof(method_header);
           offset_ += sizeof(method_header);
           DCHECK_OFFSET_();
+
+          if (!compiled_method->GetPatches().empty()) {
+            patched_code_ =  *quick_code;
+            quick_code = &patched_code_;
+            for (const LinkerPatch& patch : compiled_method->GetPatches()) {
+              if (patch.Type() == kLinkerPatchCallRelative) {
+                // NOTE: Relative calls across oat files are not supported.
+                uint32_t target_offset = GetTargetOffset(patch);
+                uint32_t literal_offset = patch.LiteralOffset();
+                writer_->relative_call_patcher_->Patch(&patched_code_, literal_offset,
+                                                       offset_ + literal_offset, target_offset);
+              } else if (patch.Type() == kLinkerPatchCall) {
+                uint32_t target_offset = GetTargetOffset(patch);
+                PatchCodeAddress(&patched_code_, patch.LiteralOffset(), target_offset);
+              } else if (patch.Type() == kLinkerPatchMethod) {
+                mirror::ArtMethod* method = GetTargetMethod(patch);
+                PatchObjectAddress(&patched_code_, patch.LiteralOffset(), method);
+              } else if (patch.Type() == kLinkerPatchType) {
+                mirror::Class* type = GetTargetType(patch);
+                PatchObjectAddress(&patched_code_, patch.LiteralOffset(), type);
+              }
+            }
+          }
+
+          writer_->oat_header_->UpdateChecksum(&(*quick_code)[0], code_size);
           if (!out->WriteFully(&(*quick_code)[0], code_size)) {
             ReportWriteFailure("method code", it);
             return false;
@@ -617,11 +998,81 @@
  private:
   OutputStream* const out_;
   size_t const file_offset_;
+  Thread* const self_;
+  const char* const old_no_thread_suspension_cause_;  // TODO: Use ScopedAssertNoThreadSuspension.
+  ClassLinker* const class_linker_;
+  mirror::DexCache* dex_cache_;
+  std::vector<uint8_t> patched_code_;
 
   void ReportWriteFailure(const char* what, const ClassDataItemIterator& it) {
     PLOG(ERROR) << "Failed to write " << what << " for "
         << PrettyMethod(it.GetMemberIndex(), *dex_file_) << " to " << out_->GetLocation();
   }
+
+  mirror::ArtMethod* GetTargetMethod(const LinkerPatch& patch)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    MethodReference ref = patch.TargetMethod();
+    mirror::DexCache* dex_cache =
+        (dex_file_ == ref.dex_file) ? dex_cache_ : class_linker_->FindDexCache(*ref.dex_file);
+    mirror::ArtMethod* method = dex_cache->GetResolvedMethod(ref.dex_method_index);
+    CHECK(method != nullptr);
+    return method;
+  }
+
+  uint32_t GetTargetOffset(const LinkerPatch& patch) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    auto target_it = writer_->method_offset_map_.find(patch.TargetMethod());
+    uint32_t target_offset =
+        (target_it != writer_->method_offset_map_.end()) ? target_it->second : 0u;
+    // If there's no compiled code, point to the correct trampoline.
+    if (UNLIKELY(target_offset == 0)) {
+      mirror::ArtMethod* target = GetTargetMethod(patch);
+      DCHECK(target != nullptr);
+      DCHECK_EQ(target->GetQuickOatCodeOffset(), 0u);
+      target_offset = target->IsNative()
+          ? writer_->oat_header_->GetQuickGenericJniTrampolineOffset()
+          : writer_->oat_header_->GetQuickToInterpreterBridgeOffset();
+    }
+    return target_offset;
+  }
+
+  mirror::Class* GetTargetType(const LinkerPatch& patch)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    mirror::DexCache* dex_cache = (dex_file_ == patch.TargetTypeDexFile())
+        ? dex_cache_ : class_linker_->FindDexCache(*patch.TargetTypeDexFile());
+    mirror::Class* type = dex_cache->GetResolvedType(patch.TargetTypeIndex());
+    CHECK(type != nullptr);
+    return type;
+  }
+
+  void PatchObjectAddress(std::vector<uint8_t>* code, uint32_t offset, mirror::Object* object)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    // NOTE: Direct method pointers across oat files don't use linker patches. However, direct
+    // type pointers across oat files do. (TODO: Investigate why.)
+    if (writer_->image_writer_ != nullptr) {
+      object = writer_->image_writer_->GetImageAddress(object);
+    }
+    uint32_t address = PointerToLowMemUInt32(object);
+    DCHECK_LE(offset + 4, code->size());
+    uint8_t* data = &(*code)[offset];
+    data[0] = address & 0xffu;
+    data[1] = (address >> 8) & 0xffu;
+    data[2] = (address >> 16) & 0xffu;
+    data[3] = (address >> 24) & 0xffu;
+  }
+
+  void PatchCodeAddress(std::vector<uint8_t>* code, uint32_t offset, uint32_t target_offset)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    // NOTE: Direct calls across oat files don't use linker patches.
+    DCHECK(writer_->image_writer_ != nullptr);
+    uint32_t address = PointerToLowMemUInt32(writer_->image_writer_->GetOatFileBegin() +
+                                             writer_->oat_data_offset_ + target_offset);
+    DCHECK_LE(offset + 4, code->size());
+    uint8_t* data = &(*code)[offset];
+    data[0] = address & 0xffu;
+    data[1] = (address >> 8) & 0xffu;
+    data[2] = (address >> 16) & 0xffu;
+    data[3] = (address >> 24) & 0xffu;
+  }
 };
 
 template <typename DataAccess>
@@ -863,11 +1314,17 @@
 }
 
 bool OatWriter::Write(OutputStream* out) {
-  const size_t file_offset = out->Seek(0, kSeekCurrent);
+  const off_t raw_file_offset = out->Seek(0, kSeekCurrent);
+  if (raw_file_offset == (off_t) -1) {
+    LOG(ERROR) << "Failed to get file offset in " << out->GetLocation();
+    return false;
+  }
+  const size_t file_offset = static_cast<size_t>(raw_file_offset);
 
+  // Reserve space for header. It will be written last - after updating the checksum.
   size_t header_size = oat_header_->GetHeaderSize();
-  if (!out->WriteFully(oat_header_, header_size)) {
-    PLOG(ERROR) << "Failed to write oat header to " << out->GetLocation();
+  if (out->Seek(header_size, kSeekCurrent) == (off_t) -1) {
+    PLOG(ERROR) << "Failed to reserve space for oat header in " << out->GetLocation();
     return false;
   }
   size_oat_header_ += sizeof(OatHeader);
@@ -878,7 +1335,12 @@
     return false;
   }
 
-  size_t relative_offset = out->Seek(0, kSeekCurrent) - file_offset;
+  off_t tables_end_offset = out->Seek(0, kSeekCurrent);
+  if (tables_end_offset == (off_t) -1) {
+    LOG(ERROR) << "Failed to seek to oat code position in " << out->GetLocation();
+    return false;
+  }
+  size_t relative_offset = static_cast<size_t>(tables_end_offset) - file_offset;
   relative_offset = WriteMaps(out, file_offset, relative_offset);
   if (relative_offset == 0) {
     LOG(ERROR) << "Failed to write oat code to " << out->GetLocation();
@@ -897,6 +1359,12 @@
     return false;
   }
 
+  const off_t oat_end_file_offset = out->Seek(0, kSeekCurrent);
+  if (oat_end_file_offset == (off_t) -1) {
+    LOG(ERROR) << "Failed to get oat end file offset in " << out->GetLocation();
+    return false;
+  }
+
   if (kIsDebugBuild) {
     uint32_t size_total = 0;
     #define DO_STAT(x) \
@@ -922,6 +1390,7 @@
     DO_STAT(size_method_header_);
     DO_STAT(size_code_);
     DO_STAT(size_code_alignment_);
+    DO_STAT(size_relative_call_thunks_);
     DO_STAT(size_mapping_table_);
     DO_STAT(size_vmap_table_);
     DO_STAT(size_gc_map_);
@@ -937,13 +1406,29 @@
     #undef DO_STAT
 
     VLOG(compiler) << "size_total=" << PrettySize(size_total) << " (" << size_total << "B)"; \
-    CHECK_EQ(file_offset + size_total, static_cast<uint32_t>(out->Seek(0, kSeekCurrent)));
+    CHECK_EQ(file_offset + size_total, static_cast<size_t>(oat_end_file_offset));
     CHECK_EQ(size_, size_total);
   }
 
-  CHECK_EQ(file_offset + size_, static_cast<uint32_t>(out->Seek(0, kSeekCurrent)));
+  CHECK_EQ(file_offset + size_, static_cast<size_t>(oat_end_file_offset));
   CHECK_EQ(size_, relative_offset);
 
+  // Write the header now that the checksum is final.
+  if (out->Seek(file_offset, kSeekSet) == (off_t) -1) {
+    PLOG(ERROR) << "Failed to seek to oat header position in " << out->GetLocation();
+    return false;
+  }
+  DCHECK_EQ(raw_file_offset, out->Seek(0, kSeekCurrent));
+  if (!out->WriteFully(oat_header_, header_size)) {
+    PLOG(ERROR) << "Failed to write oat header to " << out->GetLocation();
+    return false;
+  }
+  if (out->Seek(oat_end_file_offset, kSeekSet) == (off_t) -1) {
+    PLOG(ERROR) << "Failed to seek to end after writing oat header to " << out->GetLocation();
+    return false;
+  }
+  DCHECK_EQ(oat_end_file_offset, out->Seek(0, kSeekCurrent));
+
   return true;
 }
 
@@ -1070,6 +1555,18 @@
   return relative_offset;
 }
 
+bool OatWriter::WriteCodeAlignment(OutputStream* out, uint32_t aligned_code_delta) {
+  static const uint8_t kPadding[] = {
+      0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u
+  };
+  DCHECK_LE(aligned_code_delta, sizeof(kPadding));
+  if (UNLIKELY(!out->WriteFully(kPadding, aligned_code_delta))) {
+    return false;
+  }
+  size_code_alignment_ += aligned_code_delta;
+  return true;
+}
+
 OatWriter::OatDexFile::OatDexFile(size_t offset, const DexFile& dex_file) {
   offset_ = offset;
   const std::string& location(dex_file.GetLocation());
diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h
index 11f8bff..5545ba8 100644
--- a/compiler/oat_writer.h
+++ b/compiler/oat_writer.h
@@ -23,6 +23,7 @@
 
 #include "driver/compiler_driver.h"
 #include "mem_map.h"
+#include "method_reference.h"
 #include "oat.h"
 #include "mirror/class.h"
 #include "safe_map.h"
@@ -31,6 +32,7 @@
 
 class BitVector;
 class CompiledMethod;
+class ImageWriter;
 class OutputStream;
 
 // OatHeader         variable length with count of D OatDexFiles
@@ -82,6 +84,7 @@
             uintptr_t image_file_location_oat_begin,
             int32_t image_patch_delta,
             const CompilerDriver* compiler,
+            ImageWriter* image_writer,
             TimingLogger* timings,
             SafeMap<std::string, std::string>* key_value_store);
 
@@ -93,6 +96,14 @@
     return size_;
   }
 
+  const std::vector<uintptr_t>& GetAbsolutePatchLocations() const {
+    return absolute_patch_locations_;
+  }
+
+  void SetOatDataOffset(size_t oat_data_offset) {
+    oat_data_offset_ = oat_data_offset;
+  }
+
   bool Write(OutputStream* out);
 
   ~OatWriter();
@@ -160,6 +171,8 @@
   size_t WriteCode(OutputStream* out, const size_t file_offset, size_t relative_offset);
   size_t WriteCodeDexFiles(OutputStream* out, const size_t file_offset, size_t relative_offset);
 
+  bool WriteCodeAlignment(OutputStream* out, uint32_t aligned_code_delta);
+
   class OatDexFile {
    public:
     explicit OatDexFile(size_t offset, const DexFile& dex_file);
@@ -248,6 +261,7 @@
   std::vector<DebugInfo> method_info_;
 
   const CompilerDriver* const compiler_driver_;
+  ImageWriter* const image_writer_;
 
   // note OatFile does not take ownership of the DexFiles
   const std::vector<const DexFile*>* dex_files_;
@@ -255,6 +269,9 @@
   // Size required for Oat data structures.
   size_t size_;
 
+  // Offset of the oat data from the start of the mmapped region of the elf file.
+  size_t oat_data_offset_;
+
   // dependencies on the image.
   uint32_t image_file_location_oat_checksum_;
   uintptr_t image_file_location_oat_begin_;
@@ -296,6 +313,7 @@
   uint32_t size_method_header_;
   uint32_t size_code_;
   uint32_t size_code_alignment_;
+  uint32_t size_relative_call_thunks_;
   uint32_t size_mapping_table_;
   uint32_t size_vmap_table_;
   uint32_t size_gc_map_;
@@ -309,6 +327,18 @@
   uint32_t size_oat_class_method_bitmaps_;
   uint32_t size_oat_class_method_offsets_;
 
+  class RelativeCallPatcher;
+  class NoRelativeCallPatcher;
+  class X86RelativeCallPatcher;
+  class Thumb2RelativeCallPatcher;
+
+  std::unique_ptr<RelativeCallPatcher> relative_call_patcher_;
+
+  // The locations of absolute patches relative to the start of the executable section.
+  std::vector<uintptr_t> absolute_patch_locations_;
+
+  SafeMap<MethodReference, uint32_t, MethodReferenceComparator> method_offset_map_;
+
   struct CodeOffsetsKeyComparator {
     bool operator()(const CompiledMethod* lhs, const CompiledMethod* rhs) const {
       if (lhs->GetQuickCode() != rhs->GetQuickCode()) {
@@ -321,6 +351,18 @@
       if (UNLIKELY(&lhs->GetVmapTable() != &rhs->GetVmapTable())) {
         return &lhs->GetVmapTable() < &rhs->GetVmapTable();
       }
+      const auto& lhs_patches = lhs->GetPatches();
+      const auto& rhs_patches = rhs->GetPatches();
+      if (UNLIKELY(lhs_patches.size() != rhs_patches.size())) {
+        return lhs_patches.size() < rhs_patches.size();
+      }
+      auto rit = rhs_patches.begin();
+      for (const LinkerPatch& lpatch : lhs_patches) {
+        if (UNLIKELY(!(lpatch == *rit))) {
+          return lpatch < *rit;
+        }
+        ++rit;
+      }
       return false;
     }
   };
diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h
index 2d70b7d..e6b4a6a 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -82,12 +82,13 @@
       : array_(array), size_(size) {
   }
 
-  explicit ArrayRef(std::vector<T>& v)
+  template <typename Alloc>
+  explicit ArrayRef(std::vector<T, Alloc>& v)
       : array_(v.data()), size_(v.size()) {
   }
 
-  template <typename U>
-  ArrayRef(const std::vector<U>& v,
+  template <typename U, typename Alloc>
+  ArrayRef(const std::vector<U, Alloc>& v,
            typename std::enable_if<std::is_same<T, const U>::value, tag>::tag t = tag())
       : array_(v.data()), size_(v.size()) {
   }
@@ -167,6 +168,16 @@
   size_t size_;
 };
 
+template <typename T>
+bool operator==(const ArrayRef<T>& lhs, const ArrayRef<T>& rhs) {
+  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+}
+
+template <typename T>
+bool operator!=(const ArrayRef<T>& lhs, const ArrayRef<T>& rhs) {
+  return !(lhs == rhs);
+}
+
 }  // namespace art
 
 
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index 9e6e958..09825e2 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -45,7 +45,6 @@
 #include "driver/compiler_driver.h"
 #include "driver/compiler_options.h"
 #include "elf_fixup.h"
-#include "elf_patcher.h"
 #include "elf_stripper.h"
 #include "gc/space/image_space.h"
 #include "gc/space/space-inl.h"
@@ -261,12 +260,12 @@
     CHECK(verification_results != nullptr);
     CHECK(method_inliner_map != nullptr);
     std::unique_ptr<Dex2Oat> dex2oat(new Dex2Oat(&compiler_options,
-                                           compiler_kind,
-                                           instruction_set,
-                                           instruction_set_features,
-                                           verification_results,
-                                           method_inliner_map,
-                                           thread_count));
+                                                 compiler_kind,
+                                                 instruction_set,
+                                                 instruction_set_features,
+                                                 verification_results,
+                                                 method_inliner_map,
+                                                 thread_count));
     if (!dex2oat->CreateRuntime(runtime_options, instruction_set)) {
       *p_dex2oat = nullptr;
       return false;
@@ -341,39 +340,16 @@
     return ReadImageClasses(image_classes_stream);
   }
 
-  bool PatchOatCode(const CompilerDriver* compiler_driver, File* oat_file,
-                    const std::string& oat_location, std::string* error_msg) {
-    // We asked to include patch information but we are not making an image. We need to fix
-    // everything up manually.
-    std::unique_ptr<ElfFile> elf_file(ElfFile::Open(oat_file, PROT_READ|PROT_WRITE,
-                                                    MAP_SHARED, error_msg));
-    if (elf_file.get() == NULL) {
-      LOG(ERROR) << error_msg;
-      return false;
-    }
-    {
-      ReaderMutexLock mu(Thread::Current(), *Locks::mutator_lock_);
-      return ElfPatcher::Patch(compiler_driver, elf_file.get(), oat_location, error_msg);
-    }
-  }
-
-  const CompilerDriver* CreateOatFile(const std::string& boot_image_option,
-                                      const std::string& android_root,
-                                      bool is_host,
-                                      const std::vector<const DexFile*>& dex_files,
-                                      File* oat_file,
-                                      const std::string& oat_location,
-                                      const std::string& bitcode_filename,
-                                      bool image,
-                                      std::unique_ptr<std::set<std::string>>& image_classes,
-                                      bool dump_stats,
-                                      bool dump_passes,
-                                      TimingLogger& timings,
-                                      CumulativeLogger& compiler_phases_timings,
-                                      std::string profile_file,
-                                      SafeMap<std::string, std::string>* key_value_store) {
-    CHECK(key_value_store != nullptr);
-
+  void Compile(const std::string& boot_image_option,
+               const std::vector<const DexFile*>& dex_files,
+               const std::string& bitcode_filename,
+               bool image,
+               std::unique_ptr<std::set<std::string>>& image_classes,
+               bool dump_stats,
+               bool dump_passes,
+               TimingLogger* timings,
+               CumulativeLogger* compiler_phases_timings,
+               const std::string& profile_file) {
     // Handle and ClassLoader creation needs to come after Runtime::Create
     jobject class_loader = nullptr;
     Thread* self = Thread::Current();
@@ -392,31 +368,45 @@
       Runtime::Current()->SetCompileTimeClassPath(class_loader, class_path_files);
     }
 
-    std::unique_ptr<CompilerDriver> driver(new CompilerDriver(compiler_options_,
-                                                              verification_results_,
-                                                              method_inliner_map_,
-                                                              compiler_kind_,
-                                                              instruction_set_,
-                                                              instruction_set_features_,
-                                                              image,
-                                                              image_classes.release(),
-                                                              thread_count_,
-                                                              dump_stats,
-                                                              dump_passes,
-                                                              &compiler_phases_timings,
-                                                              profile_file));
+    driver_.reset(new CompilerDriver(compiler_options_,
+                                     verification_results_,
+                                     method_inliner_map_,
+                                     compiler_kind_,
+                                     instruction_set_,
+                                     instruction_set_features_,
+                                     image,
+                                     image_classes.release(),
+                                     thread_count_,
+                                     dump_stats,
+                                     dump_passes,
+                                     compiler_phases_timings,
+                                     profile_file));
 
-    driver->GetCompiler()->SetBitcodeFileName(*driver.get(), bitcode_filename);
+    driver_->GetCompiler()->SetBitcodeFileName(*driver_, bitcode_filename);
 
-    driver->CompileAll(class_loader, dex_files, &timings);
+    driver_->CompileAll(class_loader, dex_files, timings);
+  }
 
-    TimingLogger::ScopedTiming t2("dex2oat OatWriter", &timings);
+  void PrepareImageWriter(uintptr_t image_base) {
+    image_writer_.reset(new ImageWriter(*driver_, image_base));
+  }
+
+  bool CreateOatFile(const std::vector<const DexFile*>& dex_files,
+                     const std::string& android_root,
+                     bool is_host,
+                     File* oat_file,
+                     const std::string& oat_location,
+                     TimingLogger* timings,
+                     SafeMap<std::string, std::string>* key_value_store) {
+    CHECK(key_value_store != nullptr);
+
+    TimingLogger::ScopedTiming t2("dex2oat OatWriter", timings);
     std::string image_file_location;
     uint32_t image_file_location_oat_checksum = 0;
     uintptr_t image_file_location_oat_data_begin = 0;
     int32_t image_patch_delta = 0;
-    if (!driver->IsImage()) {
-      TimingLogger::ScopedTiming t3("Loading image checksum", &timings);
+    if (!driver_->IsImage()) {
+      TimingLogger::ScopedTiming t3("Loading image checksum", timings);
       gc::space::ImageSpace* image_space = Runtime::Current()->GetHeap()->GetImageSpace();
       image_file_location_oat_checksum = image_space->GetImageHeader().GetOatChecksum();
       image_file_location_oat_data_begin =
@@ -432,49 +422,50 @@
     OatWriter oat_writer(dex_files, image_file_location_oat_checksum,
                          image_file_location_oat_data_begin,
                          image_patch_delta,
-                         driver.get(),
-                         &timings,
+                         driver_.get(),
+                         image_writer_.get(),
+                         timings,
                          key_value_store);
 
-    t2.NewTiming("Writing ELF");
-    if (!driver->WriteElf(android_root, is_host, dex_files, &oat_writer, oat_file)) {
-      LOG(ERROR) << "Failed to write ELF file " << oat_file->GetPath();
-      return nullptr;
-    }
-
-    // Flush result to disk. Patching code will re-open the file (mmap), so ensure that our view
-    // of the file already made it there and won't be re-ordered with writes from PatchOat or
-    // image patching.
-    oat_file->Flush();
-
-    if (!driver->IsImage() && driver->GetCompilerOptions().GetIncludePatchInformation()) {
-      t2.NewTiming("Patching ELF");
-      std::string error_msg;
-      if (!PatchOatCode(driver.get(), oat_file, oat_location, &error_msg)) {
-        LOG(ERROR) << "Failed to fixup ELF file " << oat_file->GetPath() << ": " << error_msg;
-        return nullptr;
+    if (driver_->IsImage()) {
+      // The OatWriter constructor has already updated offsets in methods and we need to
+      // prepare method offsets in the image address space for direct method patching.
+      t2.NewTiming("Preparing image address space");
+      if (!image_writer_->PrepareImageAddressSpace()) {
+        LOG(ERROR) << "Failed to prepare image address space.";
+        return false;
       }
     }
 
-    return driver.release();
+    t2.NewTiming("Writing ELF");
+    if (!driver_->WriteElf(android_root, is_host, dex_files, &oat_writer, oat_file)) {
+      LOG(ERROR) << "Failed to write ELF file " << oat_file->GetPath();
+      return false;
+    }
+
+    // Flush result to disk.
+    t2.NewTiming("Flushing ELF");
+    if (oat_file->Flush() != 0) {
+      LOG(ERROR) << "Failed to flush ELF file " << oat_file->GetPath();
+      return false;
+    }
+
+    return true;
   }
 
   bool CreateImageFile(const std::string& image_filename,
-                       uintptr_t image_base,
                        const std::string& oat_filename,
-                       const std::string& oat_location,
-                       const CompilerDriver& compiler)
+                       const std::string& oat_location)
       LOCKS_EXCLUDED(Locks::mutator_lock_) {
-    uintptr_t oat_data_begin;
-    {
-      // ImageWriter is scoped so it can free memory before doing FixupElf
-      ImageWriter image_writer(compiler);
-      if (!image_writer.Write(image_filename, image_base, oat_filename, oat_location)) {
-        LOG(ERROR) << "Failed to create image file " << image_filename;
-        return false;
-      }
-      oat_data_begin = image_writer.GetOatDataBegin();
+    CHECK(image_writer_ != nullptr);
+    if (!image_writer_->Write(image_filename, oat_filename, oat_location)) {
+      LOG(ERROR) << "Failed to create image file " << image_filename;
+      return false;
     }
+    uintptr_t oat_data_begin = image_writer_->GetOatDataBegin();
+
+    // Destroy ImageWriter before doing FixupElf.
+    image_writer_.reset();
 
     std::unique_ptr<File> oat_file(OS::OpenFileReadWrite(oat_filename.c_str()));
     if (oat_file.get() == nullptr) {
@@ -504,7 +495,9 @@
         method_inliner_map_(method_inliner_map),
         runtime_(nullptr),
         thread_count_(thread_count),
-        start_ns_(NanoTime()) {
+        start_ns_(NanoTime()),
+        driver_(nullptr),
+        image_writer_(nullptr) {
     CHECK(compiler_options != nullptr);
     CHECK(verification_results != nullptr);
     CHECK(method_inliner_map != nullptr);
@@ -571,6 +564,8 @@
   Runtime* runtime_;
   size_t thread_count_;
   uint64_t start_ns_;
+  std::unique_ptr<CompilerDriver> driver_;
+  std::unique_ptr<ImageWriter> image_writer_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(Dex2Oat);
 };
@@ -1421,22 +1416,28 @@
   oss << kRuntimeISA;
   key_value_store->Put(OatHeader::kDex2OatHostKey, oss.str());
 
-  std::unique_ptr<const CompilerDriver> compiler(dex2oat->CreateOatFile(boot_image_option,
-                                                                        android_root,
-                                                                        is_host,
-                                                                        dex_files,
-                                                                        oat_file.get(),
-                                                                        oat_location,
-                                                                        bitcode_filename,
-                                                                        image,
-                                                                        image_classes,
-                                                                        dump_stats,
-                                                                        dump_passes,
-                                                                        timings,
-                                                                        compiler_phases_timings,
-                                                                        profile_file,
-                                                                        key_value_store.get()));
-  if (compiler.get() == nullptr) {
+  dex2oat->Compile(boot_image_option,
+                   dex_files,
+                   bitcode_filename,
+                   image,
+                   image_classes,
+                   dump_stats,
+                   dump_passes,
+                   &timings,
+                   &compiler_phases_timings,
+                   profile_file);
+
+  if (image) {
+    dex2oat->PrepareImageWriter(image_base);
+  }
+
+  if (!dex2oat->CreateOatFile(dex_files,
+                              android_root,
+                              is_host,
+                              oat_file.get(),
+                              oat_location,
+                              &timings,
+                              key_value_store.get())) {
     LOG(ERROR) << "Failed to create oat file: " << oat_location;
     return EXIT_FAILURE;
   }
@@ -1472,34 +1473,43 @@
   //
   // To get this all correct, we go through several steps.
   //
-  // 1. We have already created that oat file above with
-  // CreateOatFile. Originally this was just our own proprietary file
-  // but now it is contained within an ELF dynamic object (aka an .so
-  // file). The Compiler returned by CreateOatFile provides
-  // PatchInformation for references to oat code and Methods that need
-  // to be update once we know where the oat file will be located
-  // after the image.
+  // 1. We prepare offsets for all data in the oat file and calculate
+  // the oat data size and code size. During this stage, we also set
+  // oat code offsets in methods for use by the image writer.
   //
-  // 2. We create the image file. It needs to know where the oat file
+  // 2. We prepare offsets for the objects in the image and calculate
+  // the image size.
+  //
+  // 3. We create the oat file. Originally this was just our own proprietary
+  // file but now it is contained within an ELF dynamic object (aka an .so
+  // file). Since we know the image size and oat data size and code size we
+  // can prepare the ELF headers and we then know the ELF memory segment
+  // layout and we can now resolve all references. The compiler provides
+  // LinkerPatch information in each CompiledMethod and we resolve these,
+  // using the layout information and image object locations provided by
+  // image writer, as we're writing the method code.
+  //
+  // 4. We create the image file. It needs to know where the oat file
   // will be loaded after itself. Originally when oat file was simply
   // memory mapped so we could predict where its contents were based
   // on the file size. Now that it is an ELF file, we need to inspect
   // the ELF file to understand the in memory segment layout including
-  // where the oat header is located within. ElfPatcher's Patch method
-  // uses the PatchInformation from the Compiler to touch up absolute
-  // references in the oat file.
+  // where the oat header is located within.
+  // TODO: We could just remember this information from step 3.
   //
-  // 3. We fixup the ELF program headers so that dlopen will try to
+  // 5. We fixup the ELF program headers so that dlopen will try to
   // load the .so at the desired location at runtime by offsetting the
   // Elf32_Phdr.p_vaddr values by the desired base address.
+  // TODO: Do this in step 3. We already know the layout there.
+  //
+  // Steps 1.-3. are done by the CreateOatFile() above, steps 4.-5.
+  // are done by the CreateImageFile() below.
   //
   if (image) {
     TimingLogger::ScopedTiming t("dex2oat ImageWriter", &timings);
     bool image_creation_success = dex2oat->CreateImageFile(image_filename,
-                                                           image_base,
                                                            oat_unstripped,
-                                                           oat_location,
-                                                           *compiler.get());
+                                                           oat_location);
     if (!image_creation_success) {
       return EXIT_FAILURE;
     }
@@ -1512,7 +1522,7 @@
       LOG(INFO) << Dumpable<TimingLogger>(timings);
     }
     if (dump_passes) {
-      LOG(INFO) << Dumpable<CumulativeLogger>(*compiler.get()->GetTimingsLogger());
+      LOG(INFO) << Dumpable<CumulativeLogger>(compiler_phases_timings);
     }
     return EXIT_SUCCESS;
   }
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index 888f2d2..d5e766f 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -315,6 +315,11 @@
     }
   }
 
+  // Set oat data offset. Required by ElfBuilder/CodeOutput.
+  void SetCodeOffset(size_t offset) {
+    // Nothing to do.
+  }
+
   // Write oat code. Required by ElfBuilder/CodeOutput.
   bool Write(OutputStream* out) {
     return out->WriteFully(oat_file_->Begin(), oat_file_->End() - oat_file_->Begin());
diff --git a/runtime/oat.cc b/runtime/oat.cc
index 43173ca..fc0ccb1 100644
--- a/runtime/oat.cc
+++ b/runtime/oat.cc
@@ -23,7 +23,7 @@
 namespace art {
 
 const uint8_t OatHeader::kOatMagic[] = { 'o', 'a', 't', '\n' };
-const uint8_t OatHeader::kOatVersion[] = { '0', '4', '0', '\0' };
+const uint8_t OatHeader::kOatVersion[] = { '0', '4', '1', '\0' };
 
 static size_t ComputeOatHeaderSize(const SafeMap<std::string, std::string>* variable_data) {
   size_t estimate = 0U;