Patent ID: 8601459
Filing Date: 2013-12-03
Classification: G06F

Abstract:
1. A method for discovering a set of possible iterative sequences for a given loop in a program, the method comprising: partitioning the loop into a plurality of portions based on control flow in the loop, each of the plurality of portions representing multiple paths in the control flow; associating labels with the portions, loop iterations being abstracted as a finite state automaton over the labels; constructing an initial loop automaton in memory storage that represents the loop iterations as a regular language over the labels corresponding to the portions in the program; analyzing subsequences of the labels to determine infeasibility of the subsequences permitted in the automaton; and refining the loop automaton by removing all infeasible subsequences to discover a set of possible iteration sequences, wherein partitioning the loop into a plurality of portions includes partitioning the loop using splitting criteria including one or more of outcome of branches in the loop, back edges traversed by an iteration, and induction variable updates.