--- a/hotspot/src/share/vm/code/codeCache.cpp	Tue Jan 14 14:51:47 2014 +0100
+++ b/hotspot/src/share/vm/code/codeCache.cpp	Wed Jan 15 06:16:55 2014 +0100
@@ -596,20 +596,13 @@
 }
 
 #ifndef PRODUCT
-// used to keep track of how much time is spent in mark_for_deoptimization
+// Keeps track of time spent for checking dependencies
 static elapsedTimer dependentCheckTime;
-static int dependentCheckCount = 0;
-#endif // PRODUCT
+#endif
 
 
 int CodeCache::mark_for_deoptimization(DepChange& changes) {
   MutexLockerEx mu(CodeCache_lock, Mutex::_no_safepoint_check_flag);
-
-#ifndef PRODUCT
-  dependentCheckTime.start();
-  dependentCheckCount++;
-#endif // PRODUCT
-
   int number_of_marked_CodeBlobs = 0;
 
   // search the hierarchy looking for nmethods which are affected by the loading of this class
@@ -617,32 +610,23 @@
   // then search the interfaces this class implements looking for nmethods
   // which might be dependent of the fact that an interface only had one
   // implementor.
-
-  { No_Safepoint_Verifier nsv;
-    for (DepChange::ContextStream str(changes, nsv); str.next(); ) {
-      Klass* d = str.klass();
-      number_of_marked_CodeBlobs += InstanceKlass::cast(d)->mark_dependent_nmethods(changes);
-    }
-  }
-
-  if (VerifyDependencies) {
-    // Turn off dependency tracing while actually testing deps.
-    NOT_PRODUCT( FlagSetting fs(TraceDependencies, false) );
-    FOR_ALL_ALIVE_NMETHODS(nm) {
-      if (!nm->is_marked_for_deoptimization() &&
-          nm->check_all_dependencies()) {
-        ResourceMark rm;
-        tty->print_cr("Should have been marked for deoptimization:");
-        changes.print();
-        nm->print();
-        nm->print_dependencies();
-      }
-    }
+  // nmethod::check_all_dependencies works only correctly, if no safepoint
+  // can happen
+  No_Safepoint_Verifier nsv;
+  for (DepChange::ContextStream str(changes, nsv); str.next(); ) {
+    Klass* d = str.klass();
+    number_of_marked_CodeBlobs += InstanceKlass::cast(d)->mark_dependent_nmethods(changes);
   }
 
 #ifndef PRODUCT
-  dependentCheckTime.stop();
-#endif // PRODUCT
+  if (VerifyDependencies) {
+    // Object pointers are used as unique identifiers for dependency arguments. This
+    // is only possible if no safepoint, i.e., GC occurs during the verification code.
+    dependentCheckTime.start();
+    nmethod::check_all_dependencies(changes);
+    dependentCheckTime.stop();
+  }
+#endif
 
   return number_of_marked_CodeBlobs;
 }
@@ -899,9 +883,7 @@
   }
 
   tty->print_cr("CodeCache:");
-
-  tty->print_cr("nmethod dependency checking time %f", dependentCheckTime.seconds(),
-                dependentCheckTime.seconds() / dependentCheckCount);
+  tty->print_cr("nmethod dependency checking time %fs", dependentCheckTime.seconds());
 
   if (!live.is_empty()) {
     live.print("live");

--- a/hotspot/src/share/vm/code/dependencies.cpp	Tue Jan 14 14:51:47 2014 +0100
+++ b/hotspot/src/share/vm/code/dependencies.cpp	Wed Jan 15 06:16:55 2014 +0100
@@ -680,6 +680,17 @@
   return result;
 }
 
+/**
+ * Returns a unique identifier for each dependency argument.
+ */
+uintptr_t Dependencies::DepStream::get_identifier(int i) {
+  if (has_oop_argument()) {
+    return (uintptr_t)(oopDesc*)argument_oop(i);
+  } else {
+    return (uintptr_t)argument(i);
+  }
+}
+
 oop Dependencies::DepStream::argument_oop(int i) {
   oop result = recorded_oop_at(argument_index(i));
   assert(result == NULL || result->is_oop(), "must be");
@@ -715,6 +726,57 @@
   return NULL;
 }
 
+// ----------------- DependencySignature --------------------------------------
+bool DependencySignature::equals(const DependencySignature& sig) const {
+  if (type() != sig.type()) {
+    return false;
+  }
+
+  if (args_count() != sig.args_count()) {
+    return false;
+  }
+
+  for (int i = 0; i < sig.args_count(); i++) {
+    if (arg(i) != sig.arg(i)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+// ----------------- DependencySignatureBuffer --------------------------------------
+DependencySignatureBuffer::DependencySignatureBuffer() {
+  _signatures = NEW_RESOURCE_ARRAY(GrowableArray<DependencySignature*>*, Dependencies::TYPE_LIMIT);
+  memset(_signatures, 0, sizeof(DependencySignature*) * Dependencies::TYPE_LIMIT);
+}
+
+/* Check if arguments are identical. Two dependency signatures are considered
+ * identical, if the type as well as all argument identifiers are identical.
+ * If the dependency has not already been checked, the dependency signature is
+ * added to the checked dependencies of the same type. The function returns
+ * false, which causes the dependency to be checked in the caller.
+ */
+bool DependencySignatureBuffer::add_if_missing(const DependencySignature& sig) {
+  const int index = sig.type();
+  GrowableArray<DependencySignature*>* buffer = _signatures[index];
+  if (buffer == NULL) {
+    buffer = new GrowableArray<DependencySignature*>();
+    _signatures[index] = buffer;
+  }
+
+  // Check if we have already checked the dependency
+  for (int i = 0; i < buffer->length(); i++) {
+    DependencySignature* checked_signature = buffer->at(i);
+    if (checked_signature->equals(sig)) {
+      return true;
+    }
+  }
+  buffer->append((DependencySignature*)&sig);
+  return false;
+}
+
+
 /// Checking dependencies:
 
 // This hierarchy walker inspects subtypes of a given type,

--- a/hotspot/src/share/vm/code/dependencies.hpp	Tue Jan 14 14:51:47 2014 +0100
+++ b/hotspot/src/share/vm/code/dependencies.hpp	Wed Jan 15 06:16:55 2014 +0100
@@ -480,6 +480,9 @@
     bool next();
 
     DepType type()               { return _type; }
+    bool has_oop_argument()      { return type() == call_site_target_value; }
+    uintptr_t get_identifier(int i);
+
     int argument_count()         { return dep_args(type()); }
     int argument_index(int i)    { assert(0 <= i && i < argument_count(), "oob");
                                    return _xi[i]; }
@@ -523,6 +526,38 @@
 };
 
 
+class DependencySignature : public ResourceObj {
+ private:
+  int                   _args_count;
+  uintptr_t             _argument_hash[Dependencies::max_arg_count];
+  Dependencies::DepType _type;
+
+
+ public:
+  DependencySignature(Dependencies::DepStream& dep) {
+    _args_count = dep.argument_count();
+    _type = dep.type();
+    for (int i = 0; i < _args_count; i++) {
+      _argument_hash[i] = dep.get_identifier(i);
+    }
+  }
+
+  bool equals(const DependencySignature& sig) const;
+
+  int args_count()             const { return _args_count; }
+  uintptr_t arg(int idx)       const { return _argument_hash[idx]; }
+  Dependencies::DepType type() const { return _type; }
+};
+
+class DependencySignatureBuffer : public StackObj {
+ private:
+  GrowableArray<DependencySignature*>**  _signatures;
+
+ public:
+  DependencySignatureBuffer();
+  bool add_if_missing(const DependencySignature& sig);
+};
+
 // Every particular DepChange is a sub-class of this class.
 class DepChange : public StackObj {
  public:

--- a/hotspot/src/share/vm/code/nmethod.cpp	Tue Jan 14 14:51:47 2014 +0100
+++ b/hotspot/src/share/vm/code/nmethod.cpp	Wed Jan 15 06:16:55 2014 +0100
@@ -2161,16 +2161,41 @@
 }
 
 
-bool nmethod::check_all_dependencies() {
-  bool found_check = false;
-  // wholesale check of all dependencies
-  for (Dependencies::DepStream deps(this); deps.next(); ) {
-    if (deps.check_dependency() != NULL) {
-      found_check = true;
-      NOT_DEBUG(break);
+void nmethod::check_all_dependencies(DepChange& changes) {
+  // Checked dependencies are allocated into this ResourceMark
+  ResourceMark rm;
+
+  // Turn off dependency tracing while actually testing dependencies.
+  NOT_PRODUCT( FlagSetting fs(TraceDependencies, false) );
+
+  // 'dep_signature_buffers' caches already checked dependencies.
+  DependencySignatureBuffer dep_signature_buffers;
+
+  // Iterate over live nmethods and check dependencies of all nmethods that are not
+  // marked for deoptimization. A particular dependency is only checked once.
+  for(nmethod* nm = CodeCache::alive_nmethod(CodeCache::first()); nm != NULL; nm = CodeCache::alive_nmethod(CodeCache::next(nm))) {
+    if (!nm->is_marked_for_deoptimization()) {
+      for (Dependencies::DepStream deps(nm); deps.next(); ) {
+        // Construct abstraction of a dependency.
+        const DependencySignature* current_sig = new DependencySignature(deps);
+        // Determine if 'deps' is already checked. If it is not checked,
+        // 'add_if_missing()' adds the dependency signature and returns
+        // false.
+        if (!dep_signature_buffers.add_if_missing(*current_sig)) {
+          if (deps.check_dependency() != NULL) {
+            // Dependency checking failed. Print out information about the failed
+            // dependency and finally fail with an assert. We can fail here, since
+            // dependency checking is never done in a product build.
+            ResourceMark rm;
+            changes.print();
+            nm->print();
+            nm->print_dependencies();
+            assert(false, "Should have been marked for deoptimization");
+          }
+        }
+      }
     }
   }
-  return found_check;  // tell caller if we found anything
 }
 
 bool nmethod::check_dependency_on(DepChange& changes) {

--- a/hotspot/src/share/vm/code/nmethod.hpp	Tue Jan 14 14:51:47 2014 +0100
+++ b/hotspot/src/share/vm/code/nmethod.hpp	Wed Jan 15 06:16:55 2014 +0100
@@ -679,7 +679,7 @@
 
   // tells if any of this method's dependencies have been invalidated
   // (this is expensive!)
-  bool check_all_dependencies();
+  static void check_all_dependencies(DepChange& changes);
 
   // tells if this compiled method is dependent on the given changes,
   // and the changes have invalidated it