Method and apparatus for efficient multiple-pattern based matching and transformation of intermediate language expression trees
AssigneeInternational Business Machines Corporation
InventorArie Tal
Life of this patent
Estimating the term…
Abstract
A computer implemented method, system and computer program product for efficient multiple-pattern based matching and transformation of intermediate language expression trees in a compiler. Such an approach includes three constructs of pattern matchers namely a registry, a mapped registry and a registry instance for constructing multiple patterns and for enabling a matching and transformation process. These constructs narrow the number of relevant patterns applied against input expressions without repeatedly implementing an algorithm and also significantly reduce memory footprint and compilation time.
Claims20
A computer-implementable method, comprising:
- creating a mapped registry from a registry associated with at least one pattern, said registry capable of managing and dynamically adding said at least one pattern to said registry
- generating an array of bit vectors with respect to a plurality of keys associated with said at least one pattern thereby setting bits in said array of bit vectors to a value relevant to said plurality of keys associated with said at least one pattern;
- performing a matching process by matching an input expression tree associated with said plurality of keys with said at least one pattern, wherein said at least one pattern contains a bit associated with said array of bit vectors, said bit set to said value, thereby significantly increasing a speed of said matching process and a compile time thereof;
- and
- performing a transformation process for a matched input in order to generate an output expression utilizing said mapped registry to thereby provide for an efficient multiple-pattern-based matching and transformation of intermediate language expression trees in a compiler.
A system, comprising:
- a processor;
- a data bus coupled to said processor;
- and
- a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for:
- creating a mapped registry from a registry associated with at least one pattern, said registry capable of managing and dynamically adding said at least one pattern to said registry;
- generating an array of bit vectors with respect to a plurality of keys associated with said at least one pattern thereby setting bits in said array of bit vectors to a value relevant to said plurality of keys associated with said at least one pattern;
- performing a matching process by matching an input expression tree associated with said plurality of keys with said at least one pattern, wherein said at least one pattern contains a bit associated with said array of bit vectors, said bit set to said value, thereby significantly increasing a speed of said matching process and a compile time thereof;
- and
- performing a transformation process for a matched input in order to generate an output expression utilizing said mapped registry to thereby provide for an efficient multiple-pattern-based matching and transformation of intermediate language expression trees in a compiler.
A computer-usable medium embodying computer program code, said computer program code comprising computer executable instructions configured for:
- creating a mapped registry from a registry associated with at least one pattern, said registry capable of managing and dynamically adding said at least one pattern to said registry
- generating an array of bit vectors with respect to a plurality of keys associated with said at least one pattern thereby setting bits in said array of bit vectors to a value relevant to said plurality of keys associated with said at least one pattern;
- performing a matching process by matching an input expression tree associated with said plurality of keys with said at least one pattern, wherein said at least one pattern contains a bit associated with said array of bit vectors, said bit set to said value, thereby significantly increasing a speed of said matching process and a compile time thereof;
- and
- performing a transformation process for a matched input in order to generate an output expression utilizing said mapped registry to thereby provide for an efficient multiple-pattern-based matching and transformation of intermediate language expression trees in a compiler.
Dependencies are inferred from the claim text.