公开(公告)号：CA2453777A1

公开(公告)日：2005-06-19

申请号：CA2453777

申请日：2003-12-19

Applicant: IBM CANADA

Inventor： TAL ARIE ,  BLAINEY ROBERT J

IPC: G06F7/00 ,  G06F9/44

Abstract: There is disclosed a method and system for determining the bounds of generat ed software loops, where the relationships between split points and loop bounds are not known, or only partly known, at compile time. A "sub-range tree" is built with a root node representing the original software loop. Each sub-node represents a sub-range of the original software loop split by one or more split points. Each edge between nodes of the sub-range tree is marked with either a "then" (T) or "else" (E) marker, according to a predetermined scheme. Once the sub- range tree is built, a "path-from-root" is analyzed for each leaf node of the sub-range tree, and "dead" inductive control flow branches are identified and folded. The growth of software loop code based on the sub-range tree may be restricted by a predetermined code growth limit.

公开(公告)号：CA2392122A1

公开(公告)日：2003-12-28

申请号：CA2392122

申请日：2002-06-28

Applicant: IBM CANADA

Inventor： TAL ARIE ,  BLAINEY ROBERT J

IPC: G06F9/30 ,  G06F9/45

Abstract: The present invention is directed to a transformation technique for nested loops. A virtual iteration space may be determined based on an unroll factor (UF). The virtua l iteration space, which includes the actual iteration space, is formed such that, the virtual iteration space may be evenly divided by a selected UF. Once the virtual iteration space has been calculat ed or determined, the virtual iteration space is "cut" into regular portions by one or more unroll factors. Portions of the actual iteration space which do not fill the cut portions of the virtual iteration space or which fall outside these cuts which have been evenly divided by the unroll factor form a residue which is calculated. The portions of the actual iteration space which remain are also evenly divided by the unroll factor(s). An outer loop for this remaining portion of the actual iteration space is then unrolled. This unrolled portion forms a perfect nested loop. Accordingly, th e operations for the unrolled remaining portion of the actual iteration space when combined with the operations for the residue of the actual iteration space which was not evenly divided by the unroll factor is, in appropriate situations, semantically equivalent to the original nested loops . Aspects of the invention are applicable to rectangular andtriangular loop nests, and combinations thereof. Moreover, the invention is applicable to loops having n-dimensions.