Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Merging Sequential Comparisons of Contiguous Memory

IP.com Disclosure Number: IPCOM000241992D
Publication Date: 2015-Jun-12
Document File: 6 page(s) / 56K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is an algorithm that addresses the need to improve code sequences in the compiler. The novel algorithm starts with a tight set of restrictions for when compare and branch sequences can be merged; the method can also relax some of the restrictions without changing the correctness of the generated code.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 26% of the total text.

Page 01 of 6

Merging Sequential Comparisons of Contiguous Memory

Compilers often generate code to compare objects, member by member, generating a sequence of compare and branch pairs. It is sometimes possible to combine such sequences into a single, larger, compare and branch.

Consider the computer source code to see if objects X and Y of class Z, in differing locations in memory, have the same contents:

class Z

{

int a;

long b;

} X, Y;

if (X.a == Y.a && X.b == Y.b)

...

The user cannot simply write X == Y to compare the values of the contents, as that only compares the addresses; it misses the cases in which the contents are the same. For the source code above, a naive pseudo code implementation is:

Compare X.a to Y.a


If they are unequal, jump to LABEL1
Compare X.b to Y.b
If they are unequal, jump to LABEL1
Code executed if all items compared are equal
Jump to LABEL2
LABEL1: Code executed if any comparisons fail
...

LABEL2: Common point for both paths to continue execution

This code might have performance drawbacks. The branch prediction unit in the hardware might make an incorrect choice on any of the branches, leading to performance degradation. In addition, the straightforward sequence ties up multiple location-dependent branch prediction resources. No current methods exist to improve this code sequence in the compiler.

1


Page 02 of 6

The novel algorithm starts with a tight set of restrictions for when compare and branch sequences can be merged . Some of the restrictions can be relaxed without changing the correctness of the generated code.

The algorithm groups comparisons of sequential locations in memory into one larger comparison and one branch instruction . This uses fewer branch prediction resources and offers the branch prediction hardware fewer opportunities to make mistakes . First, the algorithm identifies a series of comparisons and branches without intervening instructions and sorts an in -memory representation of the instructions. For each comparison, the method re-orders the operands, so that the operand with the lowest address is always first; this is safe to do because a != b produces the same result as b != a. The approach sorts comparisons such that the comparison with the lowest memory address of either operand comes first. From the sorted list, the algorithm combines each block of sequential comparisons and branches into one compare and branch .

Using the algorithm, the pseudo code sequence above can be reduced to the following:

Compare X.aX.b to Y.aY.b


If they are unequal, jump to LABEL1
Code executed if all items compared are equal
Jump to LABEL2
LABEL1: Code executed if any comparisons fail
...

LABEL2: Common point for both paths to continue execution

The algorithm can only be used if the all the following conditions are met:


1. Each branch goes to the same location; otherwise, using a single branch instruction produces incorrect behavior


2. Each comparison is a comparison for inequality (e.g., if a != b then branch)

A. Ordered...