Patent ID: 8826256
Filing Date: 2014-09-02
Classification: G06F

Abstract:
1. A computer-implemented method for performing object collocation on a computer comprising a memory, the method comprising steps performed by the computer of: analyzing, by the computer, a sequence of computer instructions for object allocations and uses of the allocated objects; creating, by the computer, an allocation interference graph of object allocation nodes with edges indicating pairs of allocations to be omitted from collocation; coloring, by the computer, the allocation interference graph such that adjacent nodes are assigned different colors; creating, by the computer, an object allocation at a program point prior to allocations of a selected color from the allocation interference graph; storing, by the computer, an address associated with the created object allocation in a collocation pointer maintained in the memory; replacing, by the computer, a use of each allocation of the selected color with a use of the collocation pointer to collocate multiple objects; computing, by the computer, may-point-to information for the sequence of computer instructions, indicating a set of allocations to which each pointer may point when the sequence of computer instructions is executed; inspecting, by the computer, the sequence of computer instructions and the may-point-to information to determine which allocations interfere; and removing, by the computer, self-interfering allocations from the allocation interference graph, wherein creating the allocation interference graph of object allocation nodes further comprises: indicating an interference at each allocation instruction between an associated allocation and one or more other allocations that may be pointed to as identified using the may-point-to information; indicating an interference at each field store instruction through a pointer between objects that the pointer may point to and one or more allocations that may be pointed to by other pointers, as identified using the may-point-to information at each field store instruction; indicating an interference at each comparison of a pair of live pointers between one or more objects that the pair of live pointers may point to; and indicating an interference at each method call between one or more objects that may be pointed to by arguments of each method.