src/share/vm/code/dependencies.cpp
Index Unified diffs Context diffs Sdiffs Patch New Old Previous File Next File JDK-7194669 Cdiff src/share/vm/code/dependencies.cpp

src/share/vm/code/dependencies.cpp

Print this page

        

*** 678,687 **** --- 678,695 ---- assert(result == NULL || result->is_klass() || result->is_method(), "must be"); return result; } + uintptr_t Dependencies::DepStream::get_identity_hash(int i) { + if (has_oop_argument()) { + return argument_oop(i)->identity_hash(); + } else { + return argument(i)->identity_hash(); + } + } + oop Dependencies::DepStream::argument_oop(int i) { oop result = recorded_oop_at(argument_index(i)); assert(result == NULL || result->is_oop(), "must be"); return result; }
*** 713,722 **** --- 721,844 ---- // And some dependencies don't have a context type at all, // e.g. evol_method. return NULL; } + // ----------------- DependencySignatureBuffer -------------------------------------- + DependencySignatureBuffer::DependencySignatureBuffer(Dependencies::DepType type) { + _type = type; + _root = NULL; + } + + /** + * Search binary tree recursively. The key is the identity hash of the first or the second dependency + * argument. + */ + DependencySignature* DependencySignatureBuffer::tree_search(DependencySignature* current_node, uintptr_t key) { + if (current_node == NULL || key == current_node->key()) { + return current_node; + } + if (key < current_node->key()) { + return tree_search(current_node->left(), key); + } else { + return tree_search(current_node->right(), key); + } + } + + /** + * Returns a buffer that contains the dependency signatures of a particular dependency type. + */ + DependencySignatureBuffer* DependencySignatureBuffer::buffer(GrowableArray<DependencySignatureBuffer*>* signature_buffers, + Dependencies::DepType type) { + for (int i = 0; i < signature_buffers->length(); i++) { + DependencySignatureBuffer* current = signature_buffers->at(i); + if (current->type() == type) { + return current; + } + } + + DependencySignatureBuffer* new_buffer = new DependencySignatureBuffer(type); + signature_buffers->append(new_buffer); + return new_buffer; + } + + /** + * To remember already checked dependencies, dependencies are represented as dependency + * signatures. A dependency signature consists (i) a type and (ii) the identity hashes + * of all arguments. + * There is a DependencySignatureBuffer object for each dependency type. As a result, + * the lookup that is performed by this function does not have to consider the dependency + * type. + * Dependency signatures are stored in a binary tree where the key is either the identity hash + * of the first argument or the identity hash of the second argument of the dependency. Since + * dependencies can have more than one argument, each element of the tree (DependencySignature) + * maintains a linked list in which dependency signatures that have the same key but different + * argument identity hashes are stored. + */ + bool DependencySignatureBuffer::contains(DependencySignature* sig) { + // Search binary tree + DependencySignature* found = tree_search(_root, sig->key()); + // Search linked list + while (found != NULL) { + // Check if arguments are identical. Two dependency signatures are considered + // identical, if the type as well as all identity hashes of all arguments are + // identical. + const int args_count = sig->args_count(); + int identical_args = 0; + for (int i = 0; i < sig->args_count(); i++) { + if (sig->arg(i) == found->arg(i)) { + identical_args++; + } + } + if (identical_args == args_count) { + return true; + } + found = found->next(); + } + return false; + } + + /** + * Adds element to the binary tree if the binary tree does not contain an element with the specified + * key. If the binary tree contains an element of the same key as the element that will be added, the + * new dependency signature is appended to the end of a linked list. + */ + void DependencySignatureBuffer::add(DependencySignature* to_add) { + DependencySignature* y = NULL; + DependencySignature* x = _root; + DependencySignature* z = new DependencySignature(to_add); + + // Insert into binary search tree + while (x != NULL) { + y = x; + // Found key; add to linked list + if (z->key() == x->key()) { + // Append to end of linked list + while (x->next() != NULL) { + x = x->next(); + } + x->set_next(z); + return; + } else if (z->key() < x->key()) { + x = x->left(); + } else { + x = x->right(); + } + } + // The dependency signature was not found in the tree. Set links of new element. + z->set_parent(y); + + if (y == NULL) { + _root = z; // tree was empty + } else if (z->key() < y->key()) { + y->set_left(z); + } else { + y->set_right(z); + } + } + + /// Checking dependencies: // This hierarchy walker inspects subtypes of a given type, // trying to find a "bad" class which breaks a dependency. // Such a class is called a "witness" to the broken dependency.
src/share/vm/code/dependencies.cpp
Index Unified diffs Context diffs Sdiffs Patch New Old Previous File Next File