diff --git a/compiler/driver/compiler_options.cc b/compiler/driver/compiler_options.cc
index 34ad1c5..a0c0a2a 100644
--- a/compiler/driver/compiler_options.cc
+++ b/compiler/driver/compiler_options.cc
@@ -27,7 +27,6 @@
       small_method_threshold_(kDefaultSmallMethodThreshold),
       tiny_method_threshold_(kDefaultTinyMethodThreshold),
       num_dex_methods_threshold_(kDefaultNumDexMethodsThreshold),
-      inline_depth_limit_(kUnsetInlineDepthLimit),
       inline_max_code_units_(kUnsetInlineMaxCodeUnits),
       no_inline_from_(nullptr),
       boot_image_(false),
@@ -62,7 +61,6 @@
                                  size_t small_method_threshold,
                                  size_t tiny_method_threshold,
                                  size_t num_dex_methods_threshold,
-                                 size_t inline_depth_limit,
                                  size_t inline_max_code_units,
                                  const std::vector<const DexFile*>* no_inline_from,
                                  double top_k_profile_threshold,
@@ -86,7 +84,6 @@
       small_method_threshold_(small_method_threshold),
       tiny_method_threshold_(tiny_method_threshold),
       num_dex_methods_threshold_(num_dex_methods_threshold),
-      inline_depth_limit_(inline_depth_limit),
       inline_max_code_units_(inline_max_code_units),
       no_inline_from_(no_inline_from),
       boot_image_(false),
@@ -130,10 +127,6 @@
   ParseUintOption(option, "--num-dex-methods", &num_dex_methods_threshold_, Usage);
 }
 
-void CompilerOptions::ParseInlineDepthLimit(const StringPiece& option, UsageFn Usage) {
-  ParseUintOption(option, "--inline-depth-limit", &inline_depth_limit_, Usage);
-}
-
 void CompilerOptions::ParseInlineMaxCodeUnits(const StringPiece& option, UsageFn Usage) {
   ParseUintOption(option, "--inline-max-code-units", &inline_max_code_units_, Usage);
 }
@@ -183,8 +176,6 @@
     ParseTinyMethodMax(option, Usage);
   } else if (option.starts_with("--num-dex-methods=")) {
     ParseNumDexMethods(option, Usage);
-  } else if (option.starts_with("--inline-depth-limit=")) {
-    ParseInlineDepthLimit(option, Usage);
   } else if (option.starts_with("--inline-max-code-units=")) {
     ParseInlineMaxCodeUnits(option, Usage);
   } else if (option == "--generate-debug-info" || option == "-g") {
diff --git a/compiler/driver/compiler_options.h b/compiler/driver/compiler_options.h
index 2e3e55f..2376fbf 100644
--- a/compiler/driver/compiler_options.h
+++ b/compiler/driver/compiler_options.h
@@ -46,15 +46,9 @@
   static constexpr double kDefaultTopKProfileThreshold = 90.0;
   static const bool kDefaultGenerateDebugInfo = false;
   static const bool kDefaultGenerateMiniDebugInfo = false;
-  static const size_t kDefaultInlineDepthLimit = 3;
   static const size_t kDefaultInlineMaxCodeUnits = 32;
-  static constexpr size_t kUnsetInlineDepthLimit = -1;
   static constexpr size_t kUnsetInlineMaxCodeUnits = -1;
 
-  // Default inlining settings when the space filter is used.
-  static constexpr size_t kSpaceFilterInlineDepthLimit = 3;
-  static constexpr size_t kSpaceFilterInlineMaxCodeUnits = 10;
-
   CompilerOptions();
   ~CompilerOptions();
 
@@ -64,7 +58,6 @@
                   size_t small_method_threshold,
                   size_t tiny_method_threshold,
                   size_t num_dex_methods_threshold,
-                  size_t inline_depth_limit,
                   size_t inline_max_code_units,
                   const std::vector<const DexFile*>* no_inline_from,
                   double top_k_profile_threshold,
@@ -155,13 +148,6 @@
     return num_dex_methods_threshold_;
   }
 
-  size_t GetInlineDepthLimit() const {
-    return inline_depth_limit_;
-  }
-  void SetInlineDepthLimit(size_t limit) {
-    inline_depth_limit_ = limit;
-  }
-
   size_t GetInlineMaxCodeUnits() const {
     return inline_max_code_units_;
   }
@@ -275,7 +261,6 @@
   void ParseDumpInitFailures(const StringPiece& option, UsageFn Usage);
   void ParseDumpCfgPasses(const StringPiece& option, UsageFn Usage);
   void ParseInlineMaxCodeUnits(const StringPiece& option, UsageFn Usage);
-  void ParseInlineDepthLimit(const StringPiece& option, UsageFn Usage);
   void ParseNumDexMethods(const StringPiece& option, UsageFn Usage);
   void ParseTinyMethodMax(const StringPiece& option, UsageFn Usage);
   void ParseSmallMethodMax(const StringPiece& option, UsageFn Usage);
@@ -289,7 +274,6 @@
   size_t small_method_threshold_;
   size_t tiny_method_threshold_;
   size_t num_dex_methods_threshold_;
-  size_t inline_depth_limit_;
   size_t inline_max_code_units_;
 
   // Dex files from which we should not inline code.
diff --git a/compiler/image_test.cc b/compiler/image_test.cc
index 7ee494a..897d819 100644
--- a/compiler/image_test.cc
+++ b/compiler/image_test.cc
@@ -363,7 +363,6 @@
   }
   CreateCompilerDriver(Compiler::kOptimizing, kRuntimeISA, kIsTargetBuild ? 2U : 16U);
   // Set inline filter values.
-  compiler_options_->SetInlineDepthLimit(CompilerOptions::kDefaultInlineDepthLimit);
   compiler_options_->SetInlineMaxCodeUnits(CompilerOptions::kDefaultInlineMaxCodeUnits);
   image_classes_.clear();
   if (!extra_dex.empty()) {
diff --git a/compiler/jit/jit_compiler.cc b/compiler/jit/jit_compiler.cc
index 3ae7974..ad951bc 100644
--- a/compiler/jit/jit_compiler.cc
+++ b/compiler/jit/jit_compiler.cc
@@ -97,7 +97,6 @@
       CompilerOptions::kDefaultSmallMethodThreshold,
       CompilerOptions::kDefaultTinyMethodThreshold,
       CompilerOptions::kDefaultNumDexMethodsThreshold,
-      CompilerOptions::kDefaultInlineDepthLimit,
       CompilerOptions::kDefaultInlineMaxCodeUnits,
       /* no_inline_from */ nullptr,
       CompilerOptions::kDefaultTopKProfileThreshold,
@@ -177,10 +176,6 @@
     jit_logger_.reset(new JitLogger());
     jit_logger_->OpenLog();
   }
-
-  size_t inline_depth_limit = compiler_driver_->GetCompilerOptions().GetInlineDepthLimit();
-  DCHECK_LT(thread_count * inline_depth_limit, std::numeric_limits<uint16_t>::max())
-      << "ProfilingInfo's inline counter can potentially overflow";
 }
 
 JitCompiler::~JitCompiler() {
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 62f5114..eda26f1 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -46,32 +46,100 @@
 
 namespace art {
 
-static constexpr size_t kMaximumNumberOfHInstructions = 32;
+// Instruction limit to control memory.
+static constexpr size_t kMaximumNumberOfTotalInstructions = 1024;
+
+// Maximum number of instructions for considering a method small,
+// which we will always try to inline if the other non-instruction limits
+// are not reached.
+static constexpr size_t kMaximumNumberOfInstructionsForSmallMethod = 3;
 
 // Limit the number of dex registers that we accumulate while inlining
 // to avoid creating large amount of nested environments.
 static constexpr size_t kMaximumNumberOfCumulatedDexRegisters = 64;
 
-// Avoid inlining within a huge method due to memory pressure.
-static constexpr size_t kMaximumCodeUnitSize = 4096;
+// Limit recursive call inlining, which do not benefit from too
+// much inlining compared to code locality.
+static constexpr size_t kMaximumNumberOfRecursiveCalls = 4;
 
 // Controls the use of inline caches in AOT mode.
 static constexpr bool kUseAOTInlineCaches = false;
 
+// We check for line numbers to make sure the DepthString implementation
+// aligns the output nicely.
+#define LOG_INTERNAL(msg) \
+  static_assert(__LINE__ > 10, "Unhandled line number"); \
+  static_assert(__LINE__ < 10000, "Unhandled line number"); \
+  VLOG(compiler) << DepthString(__LINE__) << msg
+
+#define LOG_TRY() LOG_INTERNAL("Try inlinining call: ")
+#define LOG_NOTE() LOG_INTERNAL("Note: ")
+#define LOG_SUCCESS() LOG_INTERNAL("Success: ")
+#define LOG_FAIL(stat) MaybeRecordStat(stat); LOG_INTERNAL("Fail: ")
+#define LOG_FAIL_NO_STAT() LOG_INTERNAL("Fail: ")
+
+std::string HInliner::DepthString(int line) const {
+  std::string value;
+  // Indent according to the inlining depth.
+  size_t count = depth_;
+  // Line numbers get printed in the log, so add a space if the log's line is less
+  // than 1000, and two if less than 100. 10 cannot be reached as it's the copyright.
+  if (!kIsTargetBuild) {
+    if (line < 100) {
+      value += " ";
+    }
+    if (line < 1000) {
+      value += " ";
+    }
+    // Safeguard if this file reaches more than 10000 lines.
+    DCHECK_LT(line, 10000);
+  }
+  for (size_t i = 0; i < count; ++i) {
+    value += "  ";
+  }
+  return value;
+}
+
+static size_t CountNumberOfInstructions(HGraph* graph) {
+  size_t number_of_instructions = 0;
+  for (HBasicBlock* block : graph->GetReversePostOrderSkipEntryBlock()) {
+    for (HInstructionIterator instr_it(block->GetInstructions());
+         !instr_it.Done();
+         instr_it.Advance()) {
+      ++number_of_instructions;
+    }
+  }
+  return number_of_instructions;
+}
+
+void HInliner::UpdateInliningBudget() {
+  if (total_number_of_instructions_ >= kMaximumNumberOfTotalInstructions) {
+    // Always try to inline small methods.
+    inlining_budget_ = kMaximumNumberOfInstructionsForSmallMethod;
+  } else {
+    inlining_budget_ = std::max(
+        kMaximumNumberOfInstructionsForSmallMethod,
+        kMaximumNumberOfTotalInstructions - total_number_of_instructions_);
+  }
+}
+
 void HInliner::Run() {
-  const CompilerOptions& compiler_options = compiler_driver_->GetCompilerOptions();
-  if ((compiler_options.GetInlineDepthLimit() == 0)
-      || (compiler_options.GetInlineMaxCodeUnits() == 0)) {
-    return;
-  }
-  if (caller_compilation_unit_.GetCodeItem()->insns_size_in_code_units_ > kMaximumCodeUnitSize) {
-    return;
-  }
   if (graph_->IsDebuggable()) {
     // For simplicity, we currently never inline when the graph is debuggable. This avoids
     // doing some logic in the runtime to discover if a method could have been inlined.
     return;
   }
+
+  // Initialize the number of instructions for the method being compiled. Recursive calls
+  // to HInliner::Run have already updated the instruction count.
+  if (outermost_graph_ == graph_) {
+    total_number_of_instructions_ = CountNumberOfInstructions(graph_);
+  }
+
+  UpdateInliningBudget();
+  DCHECK_NE(total_number_of_instructions_, 0u);
+  DCHECK_NE(inlining_budget_, 0u);
+
   // Keep a copy of all blocks when starting the visit.
   ArenaVector<HBasicBlock*> blocks = graph_->GetReversePostOrder();
   DCHECK(!blocks.empty());
@@ -305,17 +373,18 @@
   ScopedObjectAccess soa(Thread::Current());
   uint32_t method_index = invoke_instruction->GetDexMethodIndex();
   const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
-  VLOG(compiler) << "Try inlining " << caller_dex_file.PrettyMethod(method_index);
+  LOG_TRY() << caller_dex_file.PrettyMethod(method_index);
 
-  // We can query the dex cache directly. The verifier has populated it already.
   ArtMethod* resolved_method = invoke_instruction->GetResolvedMethod();
-  ArtMethod* actual_method = nullptr;
   if (resolved_method == nullptr) {
     DCHECK(invoke_instruction->IsInvokeStaticOrDirect());
     DCHECK(invoke_instruction->AsInvokeStaticOrDirect()->IsStringInit());
-    VLOG(compiler) << "Not inlining a String.<init> method";
+    LOG_FAIL_NO_STAT() << "Not inlining a String.<init> method";
     return false;
-  } else if (invoke_instruction->IsInvokeStaticOrDirect()) {
+  }
+  ArtMethod* actual_method = nullptr;
+
+  if (invoke_instruction->IsInvokeStaticOrDirect()) {
     actual_method = resolved_method;
   } else {
     // Check if we can statically find the method.
@@ -328,6 +397,7 @@
     if (method != nullptr) {
       cha_devirtualize = true;
       actual_method = method;
+      LOG_NOTE() << "Try CHA-based inlining of " << actual_method->PrettyMethod();
     }
   }
 
@@ -390,16 +460,23 @@
       : GetInlineCacheJIT(invoke_instruction, &hs, &inline_cache);
 
   switch (inline_cache_type) {
-    case kInlineCacheNoData:
-      break;
-
-    case kInlineCacheUninitialized:
-      VLOG(compiler) << "Interface or virtual call to "
-                     << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
-                     << " is not hit and not inlined";
+    case kInlineCacheNoData: {
+      LOG_FAIL_NO_STAT()
+          << "Interface or virtual call to "
+          << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
+          << " could not be statically determined";
       return false;
+    }
 
-    case kInlineCacheMonomorphic:
+    case kInlineCacheUninitialized: {
+      LOG_FAIL_NO_STAT()
+          << "Interface or virtual call to "
+          << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
+          << " is not hit and not inlined";
+      return false;
+    }
+
+    case kInlineCacheMonomorphic: {
       MaybeRecordStat(kMonomorphicCall);
       if (outermost_graph_->IsCompilingOsr()) {
         // If we are compiling OSR, we pretend this call is polymorphic, as we may come from the
@@ -408,23 +485,29 @@
       } else {
         return TryInlineMonomorphicCall(invoke_instruction, resolved_method, inline_cache);
       }
+    }
 
-    case kInlineCachePolymorphic:
+    case kInlineCachePolymorphic: {
       MaybeRecordStat(kPolymorphicCall);
       return TryInlinePolymorphicCall(invoke_instruction, resolved_method, inline_cache);
+    }
 
-    case kInlineCacheMegamorphic:
-      VLOG(compiler) << "Interface or virtual call to "
-                     << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
-                     << " is megamorphic and not inlined";
+    case kInlineCacheMegamorphic: {
+      LOG_FAIL_NO_STAT()
+          << "Interface or virtual call to "
+          << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
+          << " is megamorphic and not inlined";
       MaybeRecordStat(kMegamorphicCall);
       return false;
+    }
 
-    case kInlineCacheMissingTypes:
-      VLOG(compiler) << "Interface or virtual call to "
-                     << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
-                     << " is missing types and not inlined";
+    case kInlineCacheMissingTypes: {
+      LOG_FAIL_NO_STAT()
+          << "Interface or virtual call to "
+          << caller_dex_file.PrettyMethod(invoke_instruction->GetDexMethodIndex())
+          << " is missing types and not inlined";
       return false;
+    }
   }
   UNREACHABLE();
 }
@@ -587,9 +670,10 @@
   dex::TypeIndex class_index = FindClassIndexIn(
       GetMonomorphicType(classes), caller_compilation_unit_);
   if (!class_index.IsValid()) {
-    VLOG(compiler) << "Call to " << ArtMethod::PrettyMethod(resolved_method)
-                   << " from inline cache is not inlined because its class is not"
-                   << " accessible to the caller";
+    LOG_FAIL(kNotInlinedDexCache)
+        << "Call to " << ArtMethod::PrettyMethod(resolved_method)
+        << " from inline cache is not inlined because its class is not"
+        << " accessible to the caller";
     return false;
   }
 
@@ -603,6 +687,7 @@
     resolved_method = GetMonomorphicType(classes)->FindVirtualMethodForVirtual(
         resolved_method, pointer_size);
   }
+  LOG_NOTE() << "Try inline monomorphic call to " << resolved_method->PrettyMethod();
   DCHECK(resolved_method != nullptr);
   HInstruction* receiver = invoke_instruction->InputAt(0);
   HInstruction* cursor = invoke_instruction->GetPrevious();
@@ -752,6 +837,7 @@
 
     dex::TypeIndex class_index = FindClassIndexIn(handle.Get(), caller_compilation_unit_);
     HInstruction* return_replacement = nullptr;
+    LOG_NOTE() << "Try inline polymorphic call to " << method->PrettyMethod();
     if (!class_index.IsValid() ||
         !TryBuildAndInline(invoke_instruction,
                            method,
@@ -761,8 +847,8 @@
     } else {
       one_target_inlined = true;
 
-      VLOG(compiler) << "Polymorphic call to " << ArtMethod::PrettyMethod(resolved_method)
-                     << " has inlined " << ArtMethod::PrettyMethod(method);
+      LOG_SUCCESS() << "Polymorphic call to " << ArtMethod::PrettyMethod(resolved_method)
+                    << " has inlined " << ArtMethod::PrettyMethod(method);
 
       // If we have inlined all targets before, and this receiver is the last seen,
       // we deoptimize instead of keeping the original invoke instruction.
@@ -796,9 +882,10 @@
   }
 
   if (!one_target_inlined) {
-    VLOG(compiler) << "Call to " << ArtMethod::PrettyMethod(resolved_method)
-                   << " from inline cache is not inlined because none"
-                   << " of its targets could be inlined";
+    LOG_FAIL_NO_STAT()
+        << "Call to " << ArtMethod::PrettyMethod(resolved_method)
+        << " from inline cache is not inlined because none"
+        << " of its targets could be inlined";
     return false;
   }
 
@@ -932,9 +1019,6 @@
       actual_method = new_method;
     } else if (actual_method != new_method) {
       // Different methods, bailout.
-      VLOG(compiler) << "Call to " << ArtMethod::PrettyMethod(resolved_method)
-                     << " from inline cache is not inlined because it resolves"
-                     << " to different methods";
       return false;
     }
   }
@@ -1007,6 +1091,7 @@
 
   MaybeRecordStat(kInlinedPolymorphicCall);
 
+  LOG_SUCCESS() << "Inlined same polymorphic target " << actual_method->PrettyMethod();
   return true;
 }
 
@@ -1076,13 +1161,34 @@
   return true;
 }
 
+size_t HInliner::CountRecursiveCallsOf(ArtMethod* method) const {
+  const HInliner* current = this;
+  size_t count = 0;
+  do {
+    if (current->graph_->GetArtMethod() == method) {
+      ++count;
+    }
+    current = current->parent_;
+  } while (current != nullptr);
+  return count;
+}
+
 bool HInliner::TryBuildAndInline(HInvoke* invoke_instruction,
                                  ArtMethod* method,
                                  ReferenceTypeInfo receiver_type,
                                  HInstruction** return_replacement) {
   if (method->IsProxyMethod()) {
-    VLOG(compiler) << "Method " << method->PrettyMethod()
-                   << " is not inlined because of unimplemented inline support for proxy methods.";
+    LOG_FAIL(kNotInlinedProxy)
+        << "Method " << method->PrettyMethod()
+        << " is not inlined because of unimplemented inline support for proxy methods.";
+    return false;
+  }
+
+  if (CountRecursiveCallsOf(method) > kMaximumNumberOfRecursiveCalls) {
+    LOG_FAIL(kNotInlinedRecursiveBudget)
+        << "Method "
+        << method->PrettyMethod()
+        << " is not inlined because it has reached its recursive call budget.";
     return false;
   }
 
@@ -1091,15 +1197,16 @@
   if (!compiler_driver_->MayInline(method->GetDexFile(),
                                    outer_compilation_unit_.GetDexFile())) {
     if (TryPatternSubstitution(invoke_instruction, method, return_replacement)) {
-      VLOG(compiler) << "Successfully replaced pattern of invoke "
-                     << method->PrettyMethod();
+      LOG_SUCCESS() << "Successfully replaced pattern of invoke "
+                    << method->PrettyMethod();
       MaybeRecordStat(kReplacedInvokeWithSimplePattern);
       return true;
     }
-    VLOG(compiler) << "Won't inline " << method->PrettyMethod() << " in "
-                   << outer_compilation_unit_.GetDexFile()->GetLocation() << " ("
-                   << caller_compilation_unit_.GetDexFile()->GetLocation() << ") from "
-                   << method->GetDexFile()->GetLocation();
+    LOG_FAIL(kNotInlinedWont)
+        << "Won't inline " << method->PrettyMethod() << " in "
+        << outer_compilation_unit_.GetDexFile()->GetLocation() << " ("
+        << caller_compilation_unit_.GetDexFile()->GetLocation() << ") from "
+        << method->GetDexFile()->GetLocation();
     return false;
   }
 
@@ -1108,30 +1215,32 @@
   const DexFile::CodeItem* code_item = method->GetCodeItem();
 
   if (code_item == nullptr) {
-    VLOG(compiler) << "Method " << method->PrettyMethod()
-                   << " is not inlined because it is native";
+    LOG_FAIL_NO_STAT()
+        << "Method " << method->PrettyMethod() << " is not inlined because it is native";
     return false;
   }
 
   size_t inline_max_code_units = compiler_driver_->GetCompilerOptions().GetInlineMaxCodeUnits();
   if (code_item->insns_size_in_code_units_ > inline_max_code_units) {
-    VLOG(compiler) << "Method " << method->PrettyMethod()
-                   << " is too big to inline: "
-                   << code_item->insns_size_in_code_units_
-                   << " > "
-                   << inline_max_code_units;
+    LOG_FAIL(kNotInlinedCodeItem)
+        << "Method " << method->PrettyMethod()
+        << " is not inlined because its code item is too big: "
+        << code_item->insns_size_in_code_units_
+        << " > "
+        << inline_max_code_units;
     return false;
   }
 
   if (code_item->tries_size_ != 0) {
-    VLOG(compiler) << "Method " << method->PrettyMethod()
-                   << " is not inlined because of try block";
+    LOG_FAIL(kNotInlinedTryCatch)
+        << "Method " << method->PrettyMethod() << " is not inlined because of try block";
     return false;
   }
 
   if (!method->IsCompilable()) {
-    VLOG(compiler) << "Method " << method->PrettyMethod()
-                   << " has soft failures un-handled by the compiler, so it cannot be inlined";
+    LOG_FAIL(kNotInlinedNotVerified)
+        << "Method " << method->PrettyMethod()
+        << " has soft failures un-handled by the compiler, so it cannot be inlined";
   }
 
   if (!method->GetDeclaringClass()->IsVerified()) {
@@ -1139,8 +1248,9 @@
     if (Runtime::Current()->UseJitCompilation() ||
         !compiler_driver_->IsMethodVerifiedWithoutFailures(
             method->GetDexMethodIndex(), class_def_idx, *method->GetDexFile())) {
-      VLOG(compiler) << "Method " << method->PrettyMethod()
-                     << " couldn't be verified, so it cannot be inlined";
+      LOG_FAIL(kNotInlinedNotVerified)
+          << "Method " << method->PrettyMethod()
+          << " couldn't be verified, so it cannot be inlined";
       return false;
     }
   }
@@ -1149,9 +1259,9 @@
       invoke_instruction->AsInvokeStaticOrDirect()->IsStaticWithImplicitClinitCheck()) {
     // Case of a static method that cannot be inlined because it implicitly
     // requires an initialization check of its declaring class.
-    VLOG(compiler) << "Method " << method->PrettyMethod()
-                   << " is not inlined because it is static and requires a clinit"
-                   << " check that cannot be emitted due to Dex cache limitations";
+    LOG_FAIL(kNotInlinedDexCache) << "Method " << method->PrettyMethod()
+             << " is not inlined because it is static and requires a clinit"
+             << " check that cannot be emitted due to Dex cache limitations";
     return false;
   }
 
@@ -1160,7 +1270,7 @@
     return false;
   }
 
-  VLOG(compiler) << "Successfully inlined " << method->PrettyMethod();
+  LOG_SUCCESS() << method->PrettyMethod();
   MaybeRecordStat(kInlinedInvoke);
   return true;
 }
@@ -1448,15 +1558,17 @@
                         handles_);
 
   if (builder.BuildGraph() != kAnalysisSuccess) {
-    VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                   << " could not be built, so cannot be inlined";
+    LOG_FAIL(kNotInlinedCannotBuild)
+        << "Method " << callee_dex_file.PrettyMethod(method_index)
+        << " could not be built, so cannot be inlined";
     return false;
   }
 
   if (!RegisterAllocator::CanAllocateRegistersFor(*callee_graph,
                                                   compiler_driver_->GetInstructionSet())) {
-    VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                   << " cannot be inlined because of the register allocator";
+    LOG_FAIL(kNotInlinedRegisterAllocator)
+        << "Method " << callee_dex_file.PrettyMethod(method_index)
+        << " cannot be inlined because of the register allocator";
     return false;
   }
 
@@ -1503,15 +1615,13 @@
                              /* is_first_run */ false).Run();
   }
 
-  size_t number_of_instructions_budget = kMaximumNumberOfHInstructions;
-  size_t number_of_inlined_instructions =
-      RunOptimizations(callee_graph, code_item, dex_compilation_unit);
-  number_of_instructions_budget += number_of_inlined_instructions;
+  RunOptimizations(callee_graph, code_item, dex_compilation_unit);
 
   HBasicBlock* exit_block = callee_graph->GetExitBlock();
   if (exit_block == nullptr) {
-    VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                   << " could not be inlined because it has an infinite loop";
+    LOG_FAIL(kNotInlinedInfiniteLoop)
+        << "Method " << callee_dex_file.PrettyMethod(method_index)
+        << " could not be inlined because it has an infinite loop";
     return false;
   }
 
@@ -1520,15 +1630,17 @@
     if (predecessor->GetLastInstruction()->IsThrow()) {
       if (invoke_instruction->GetBlock()->IsTryBlock()) {
         // TODO(ngeoffray): Support adding HTryBoundary in Hgraph::InlineInto.
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because one branch always throws and"
-                       << " caller is in a try/catch block";
+        LOG_FAIL(kNotInlinedTryCatch)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because one branch always throws and"
+            << " caller is in a try/catch block";
         return false;
       } else if (graph_->GetExitBlock() == nullptr) {
         // TODO(ngeoffray): Support adding HExit in the caller graph.
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because one branch always throws and"
-                       << " caller does not have an exit block";
+        LOG_FAIL(kNotInlinedInfiniteLoop)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because one branch always throws and"
+            << " caller does not have an exit block";
         return false;
       } else if (graph_->HasIrreducibleLoops()) {
         // TODO(ngeoffray): Support re-computing loop information to graphs with
@@ -1544,32 +1656,31 @@
   }
 
   if (!has_one_return) {
-    VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                   << " could not be inlined because it always throws";
+    LOG_FAIL(kNotInlinedAlwaysThrows)
+        << "Method " << callee_dex_file.PrettyMethod(method_index)
+        << " could not be inlined because it always throws";
     return false;
   }
 
   size_t number_of_instructions = 0;
-
-  bool can_inline_environment =
-      total_number_of_dex_registers_ < kMaximumNumberOfCumulatedDexRegisters;
-
   // Skip the entry block, it does not contain instructions that prevent inlining.
   for (HBasicBlock* block : callee_graph->GetReversePostOrderSkipEntryBlock()) {
     if (block->IsLoopHeader()) {
       if (block->GetLoopInformation()->IsIrreducible()) {
         // Don't inline methods with irreducible loops, they could prevent some
         // optimizations to run.
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because it contains an irreducible loop";
+        LOG_FAIL(kNotInlinedIrreducibleLoop)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because it contains an irreducible loop";
         return false;
       }
       if (!block->GetLoopInformation()->HasExitEdge()) {
         // Don't inline methods with loops without exit, since they cause the
         // loop information to be computed incorrectly when updating after
         // inlining.
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because it contains a loop with no exit";
+        LOG_FAIL(kNotInlinedLoopWithoutExit)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because it contains a loop with no exit";
         return false;
       }
     }
@@ -1577,34 +1688,39 @@
     for (HInstructionIterator instr_it(block->GetInstructions());
          !instr_it.Done();
          instr_it.Advance()) {
-      if (number_of_instructions++ == number_of_instructions_budget) {
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " is not inlined because its caller has reached"
-                       << " its instruction budget limit.";
+      if (++number_of_instructions >= inlining_budget_) {
+        LOG_FAIL(kNotInlinedInstructionBudget)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " is not inlined because the outer method has reached"
+            << " its instruction budget limit.";
         return false;
       }
       HInstruction* current = instr_it.Current();
-      if (!can_inline_environment && current->NeedsEnvironment()) {
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " is not inlined because its caller has reached"
-                       << " its environment budget limit.";
+      if (current->NeedsEnvironment() &&
+          (total_number_of_dex_registers_ >= kMaximumNumberOfCumulatedDexRegisters)) {
+        LOG_FAIL(kNotInlinedEnvironmentBudget)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " is not inlined because its caller has reached"
+            << " its environment budget limit.";
         return false;
       }
 
       if (current->NeedsEnvironment() &&
           !CanEncodeInlinedMethodInStackMap(*caller_compilation_unit_.GetDexFile(),
                                             resolved_method)) {
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because " << current->DebugName()
-                       << " needs an environment, is in a different dex file"
-                       << ", and cannot be encoded in the stack maps.";
+        LOG_FAIL(kNotInlinedStackMaps)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because " << current->DebugName()
+            << " needs an environment, is in a different dex file"
+            << ", and cannot be encoded in the stack maps.";
         return false;
       }
 
       if (!same_dex_file && current->NeedsDexCacheOfDeclaringClass()) {
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because " << current->DebugName()
-                       << " it is in a different dex file and requires access to the dex cache";
+        LOG_FAIL(kNotInlinedDexCache)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because " << current->DebugName()
+            << " it is in a different dex file and requires access to the dex cache";
         return false;
       }
 
@@ -1613,21 +1729,24 @@
           current->IsUnresolvedStaticFieldSet() ||
           current->IsUnresolvedInstanceFieldSet()) {
         // Entrypoint for unresolved fields does not handle inlined frames.
-        VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
-                       << " could not be inlined because it is using an unresolved"
-                       << " entrypoint";
+        LOG_FAIL(kNotInlinedUnresolvedEntrypoint)
+            << "Method " << callee_dex_file.PrettyMethod(method_index)
+            << " could not be inlined because it is using an unresolved"
+            << " entrypoint";
         return false;
       }
     }
   }
-  number_of_inlined_instructions_ += number_of_instructions;
-
   DCHECK_EQ(caller_instruction_counter, graph_->GetCurrentInstructionId())
       << "No instructions can be added to the outer graph while inner graph is being built";
 
+  // Inline the callee graph inside the caller graph.
   const int32_t callee_instruction_counter = callee_graph->GetCurrentInstructionId();
   graph_->SetCurrentInstructionId(callee_instruction_counter);
   *return_replacement = callee_graph->InlineInto(graph_, invoke_instruction);
+  // Update our budget for other inlining attempts in `caller_graph`.
+  total_number_of_instructions_ += number_of_instructions;
+  UpdateInliningBudget();
 
   DCHECK_EQ(callee_instruction_counter, callee_graph->GetCurrentInstructionId())
       << "No instructions can be added to the inner graph during inlining into the outer graph";
@@ -1640,9 +1759,9 @@
   return true;
 }
 
-size_t HInliner::RunOptimizations(HGraph* callee_graph,
-                                  const DexFile::CodeItem* code_item,
-                                  const DexCompilationUnit& dex_compilation_unit) {
+void HInliner::RunOptimizations(HGraph* callee_graph,
+                                const DexFile::CodeItem* code_item,
+                                const DexCompilationUnit& dex_compilation_unit) {
   // Note: if the outermost_graph_ is being compiled OSR, we should not run any
   // optimization that could lead to a HDeoptimize. The following optimizations do not.
   HDeadCodeElimination dce(callee_graph, inline_stats_, "dead_code_elimination$inliner");
@@ -1664,23 +1783,37 @@
     optimization->Run();
   }
 
-  size_t number_of_inlined_instructions = 0u;
-  if (depth_ + 1 < compiler_driver_->GetCompilerOptions().GetInlineDepthLimit()) {
-    HInliner inliner(callee_graph,
-                     outermost_graph_,
-                     codegen_,
-                     outer_compilation_unit_,
-                     dex_compilation_unit,
-                     compiler_driver_,
-                     handles_,
-                     inline_stats_,
-                     total_number_of_dex_registers_ + code_item->registers_size_,
-                     depth_ + 1);
-    inliner.Run();
-    number_of_inlined_instructions += inliner.number_of_inlined_instructions_;
+  // Bail early for pathological cases on the environment (for example recursive calls,
+  // or too large environment).
+  if (total_number_of_dex_registers_ >= kMaximumNumberOfCumulatedDexRegisters) {
+    LOG_NOTE() << "Calls in " << callee_graph->GetArtMethod()->PrettyMethod()
+             << " will not be inlined because the outer method has reached"
+             << " its environment budget limit.";
+    return;
   }
 
-  return number_of_inlined_instructions;
+  // Bail early if we know we already are over the limit.
+  size_t number_of_instructions = CountNumberOfInstructions(callee_graph);
+  if (number_of_instructions > inlining_budget_) {
+    LOG_NOTE() << "Calls in " << callee_graph->GetArtMethod()->PrettyMethod()
+             << " will not be inlined because the outer method has reached"
+             << " its instruction budget limit. " << number_of_instructions;
+    return;
+  }
+
+  HInliner inliner(callee_graph,
+                   outermost_graph_,
+                   codegen_,
+                   outer_compilation_unit_,
+                   dex_compilation_unit,
+                   compiler_driver_,
+                   handles_,
+                   inline_stats_,
+                   total_number_of_dex_registers_ + code_item->registers_size_,
+                   total_number_of_instructions_ + number_of_instructions,
+                   this,
+                   depth_ + 1);
+  inliner.Run();
 }
 
 static bool IsReferenceTypeRefinement(ReferenceTypeInfo declared_rti,
diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h
index a032042..9e4685c 100644
--- a/compiler/optimizing/inliner.h
+++ b/compiler/optimizing/inliner.h
@@ -42,7 +42,9 @@
            VariableSizedHandleScope* handles,
            OptimizingCompilerStats* stats,
            size_t total_number_of_dex_registers,
-           size_t depth)
+           size_t total_number_of_instructions,
+           HInliner* parent,
+           size_t depth = 0)
       : HOptimization(outer_graph, kInlinerPassName, stats),
         outermost_graph_(outermost_graph),
         outer_compilation_unit_(outer_compilation_unit),
@@ -50,8 +52,10 @@
         codegen_(codegen),
         compiler_driver_(compiler_driver),
         total_number_of_dex_registers_(total_number_of_dex_registers),
+        total_number_of_instructions_(total_number_of_instructions),
+        parent_(parent),
         depth_(depth),
-        number_of_inlined_instructions_(0),
+        inlining_budget_(0),
         handles_(handles),
         inline_stats_(nullptr) {}
 
@@ -95,10 +99,10 @@
                                HInstruction** return_replacement);
 
   // Run simple optimizations on `callee_graph`.
-  // Returns the number of inlined instructions.
-  size_t RunOptimizations(HGraph* callee_graph,
-                          const DexFile::CodeItem* code_item,
-                          const DexCompilationUnit& dex_compilation_unit);
+  void RunOptimizations(HGraph* callee_graph,
+                        const DexFile::CodeItem* code_item,
+                        const DexCompilationUnit& dex_compilation_unit)
+    REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Try to recognize known simple patterns and replace invoke call with appropriate instructions.
   bool TryPatternSubstitution(HInvoke* invoke_instruction,
@@ -259,14 +263,30 @@
                                                 HInstruction* return_replacement,
                                                 HInstruction* invoke_instruction);
 
+  // Update the inlining budget based on `total_number_of_instructions_`.
+  void UpdateInliningBudget();
+
+  // Count the number of calls of `method` being inlined recursively.
+  size_t CountRecursiveCallsOf(ArtMethod* method) const;
+
+  // Pretty-print for spaces during logging.
+  std::string DepthString(int line) const;
+
   HGraph* const outermost_graph_;
   const DexCompilationUnit& outer_compilation_unit_;
   const DexCompilationUnit& caller_compilation_unit_;
   CodeGenerator* const codegen_;
   CompilerDriver* const compiler_driver_;
   const size_t total_number_of_dex_registers_;
+  size_t total_number_of_instructions_;
+
+  // The 'parent' inliner, that means the inlinigng optimization that requested
+  // `graph_` to be inlined.
+  const HInliner* const parent_;
   const size_t depth_;
-  size_t number_of_inlined_instructions_;
+
+  // The budget left for inlining, in number of instructions.
+  size_t inlining_budget_;
   VariableSizedHandleScope* const handles_;
 
   // Used to record stats about optimizations on the inlined graph.
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 23ccd9e..3c6d2d6 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -499,7 +499,8 @@
                                 handles,
                                 stats,
                                 number_of_dex_registers,
-                                /* depth */ 0);
+                                /* total_number_of_instructions */ 0,
+                                /* parent */ nullptr);
   } else if (opt_name == HSharpening::kSharpeningPassName) {
     return new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver, handles);
   } else if (opt_name == HSelectGenerator::kSelectGeneratorPassName) {
@@ -607,8 +608,7 @@
                                          VariableSizedHandleScope* handles) const {
   OptimizingCompilerStats* stats = compilation_stats_.get();
   const CompilerOptions& compiler_options = driver->GetCompilerOptions();
-  bool should_inline = (compiler_options.GetInlineDepthLimit() > 0)
-      && (compiler_options.GetInlineMaxCodeUnits() > 0);
+  bool should_inline = (compiler_options.GetInlineMaxCodeUnits() > 0);
   if (!should_inline) {
     return;
   }
@@ -623,7 +623,8 @@
       handles,
       stats,
       number_of_dex_registers,
-      /* depth */ 0);
+      /* total_number_of_instructions */ 0,
+      /* parent */ nullptr);
   HOptimization* optimizations[] = { inliner };
 
   RunOptimizations(optimizations, arraysize(optimizations), pass_observer);
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index ae9a811..a211c54 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -69,6 +69,23 @@
   kExplicitNullCheckGenerated,
   kSimplifyIf,
   kInstructionSunk,
+  kNotInlinedUnresolvedEntrypoint,
+  kNotInlinedDexCache,
+  kNotInlinedStackMaps,
+  kNotInlinedEnvironmentBudget,
+  kNotInlinedInstructionBudget,
+  kNotInlinedLoopWithoutExit,
+  kNotInlinedIrreducibleLoop,
+  kNotInlinedAlwaysThrows,
+  kNotInlinedInfiniteLoop,
+  kNotInlinedTryCatch,
+  kNotInlinedRegisterAllocator,
+  kNotInlinedCannotBuild,
+  kNotInlinedNotVerified,
+  kNotInlinedCodeItem,
+  kNotInlinedWont,
+  kNotInlinedRecursiveBudget,
+  kNotInlinedProxy,
   kLastStat
 };
 
@@ -168,6 +185,23 @@
       case kExplicitNullCheckGenerated: name = "ExplicitNullCheckGenerated"; break;
       case kSimplifyIf: name = "SimplifyIf"; break;
       case kInstructionSunk: name = "InstructionSunk"; break;
+      case kNotInlinedUnresolvedEntrypoint: name = "NotInlinedUnresolvedEntrypoint"; break;
+      case kNotInlinedDexCache: name = "NotInlinedDexCache"; break;
+      case kNotInlinedStackMaps: name = "NotInlinedStackMaps"; break;
+      case kNotInlinedEnvironmentBudget: name = "NotInlinedEnvironmentBudget"; break;
+      case kNotInlinedInstructionBudget: name = "NotInlinedInstructionBudget"; break;
+      case kNotInlinedLoopWithoutExit: name = "NotInlinedLoopWithoutExit"; break;
+      case kNotInlinedIrreducibleLoop: name = "NotInlinedIrreducibleLoop"; break;
+      case kNotInlinedAlwaysThrows: name = "NotInlinedAlwaysThrows"; break;
+      case kNotInlinedInfiniteLoop: name = "NotInlinedInfiniteLoop"; break;
+      case kNotInlinedTryCatch: name = "NotInlinedTryCatch"; break;
+      case kNotInlinedRegisterAllocator: name = "NotInlinedRegisterAllocator"; break;
+      case kNotInlinedCannotBuild: name = "NotInlinedCannotBuild"; break;
+      case kNotInlinedNotVerified: name = "NotInlinedNotVerified"; break;
+      case kNotInlinedCodeItem: name = "NotInlinedCodeItem"; break;
+      case kNotInlinedWont: name = "NotInlinedWont"; break;
+      case kNotInlinedRecursiveBudget: name = "NotInlinedRecursiveBudget"; break;
+      case kNotInlinedProxy: name = "NotInlinedProxy"; break;
 
       case kLastStat:
         LOG(FATAL) << "invalid stat "
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index e80be81..b4ea20b 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -312,13 +312,6 @@
   UsageError("      Example: --num-dex-method=%d", CompilerOptions::kDefaultNumDexMethodsThreshold);
   UsageError("      Default: %d", CompilerOptions::kDefaultNumDexMethodsThreshold);
   UsageError("");
-  UsageError("  --inline-depth-limit=<depth-limit>: the depth limit of inlining for fine tuning");
-  UsageError("      the compiler. A zero value will disable inlining. Honored only by Optimizing.");
-  UsageError("      Has priority over the --compiler-filter option. Intended for ");
-  UsageError("      development/experimental use.");
-  UsageError("      Example: --inline-depth-limit=%d", CompilerOptions::kDefaultInlineDepthLimit);
-  UsageError("      Default: %d", CompilerOptions::kDefaultInlineDepthLimit);
-  UsageError("");
   UsageError("  --inline-max-code-units=<code-units-count>: the maximum code units that a method");
   UsageError("      can have to be considered for inlining. A zero value will disable inlining.");
   UsageError("      Honored only by Optimizing. Has priority over the --compiler-filter option.");
@@ -870,22 +863,8 @@
       }
     }
 
-    // It they are not set, use default values for inlining settings.
-    // TODO: We should rethink the compiler filter. We mostly save
-    // time here, which is orthogonal to space.
-    if (compiler_options_->inline_depth_limit_ == CompilerOptions::kUnsetInlineDepthLimit) {
-      compiler_options_->inline_depth_limit_ =
-          (compiler_options_->compiler_filter_ == CompilerFilter::kSpace)
-          // Implementation of the space filter: limit inlining depth.
-          ? CompilerOptions::kSpaceFilterInlineDepthLimit
-          : CompilerOptions::kDefaultInlineDepthLimit;
-    }
     if (compiler_options_->inline_max_code_units_ == CompilerOptions::kUnsetInlineMaxCodeUnits) {
-      compiler_options_->inline_max_code_units_ =
-          (compiler_options_->compiler_filter_ == CompilerFilter::kSpace)
-          // Implementation of the space filter: limit inlining max code units.
-          ? CompilerOptions::kSpaceFilterInlineMaxCodeUnits
-          : CompilerOptions::kDefaultInlineMaxCodeUnits;
+      compiler_options_->inline_max_code_units_ = CompilerOptions::kDefaultInlineMaxCodeUnits;
     }
 
     // Checks are all explicit until we know the architecture.
diff --git a/runtime/jit/jit_code_cache.cc b/runtime/jit/jit_code_cache.cc
index fc41f94..e9a5ae5 100644
--- a/runtime/jit/jit_code_cache.cc
+++ b/runtime/jit/jit_code_cache.cc
@@ -1366,7 +1366,10 @@
   MutexLock mu(self, lock_);
   ProfilingInfo* info = method->GetProfilingInfo(kRuntimePointerSize);
   if (info != nullptr) {
-    info->IncrementInlineUse();
+    if (!info->IncrementInlineUse()) {
+      // Overflow of inlining uses, just bail.
+      return nullptr;
+    }
   }
   return info;
 }
diff --git a/runtime/jit/profiling_info.h b/runtime/jit/profiling_info.h
index f42a8da..d6881aa 100644
--- a/runtime/jit/profiling_info.h
+++ b/runtime/jit/profiling_info.h
@@ -108,9 +108,15 @@
     }
   }
 
-  void IncrementInlineUse() {
-    DCHECK_NE(current_inline_uses_, std::numeric_limits<uint16_t>::max());
+  // Increments the number of times this method is currently being inlined.
+  // Returns whether it was successful, that is it could increment without
+  // overflowing.
+  bool IncrementInlineUse() {
+    if (current_inline_uses_ == std::numeric_limits<uint16_t>::max()) {
+      return false;
+    }
     current_inline_uses_++;
+    return true;
   }
 
   void DecrementInlineUse() {