The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jun. 17, 2008
Filed:
Feb. 18, 2003
Karim T. Farouki, Seattle, WA (US);
James J. Radigan, Redmond, WA (US);
Karim T. Farouki, Seattle, WA (US);
James J. Radigan, Redmond, WA (US);
Microsoft Corporation, Redmond, WA (US);
Abstract
The construction of Static Single Assignment form (SSA) is used as a dynamic conflict graph so that while constructing SSA in linear time, the program being analyzed is simultaneously register allocated. When allocating a register for the symbol, the conflict set is examined so that the register chosen for the symbol is not used by a symbol in the conflict set. When a symbol is register-allocated, the symbol is added to all the conflict set of all live symbols. A live symbol is determined by keeping two counters, called herein a use counter and a use threshold counter. Both counters are initialized when a definition of a symbol is encountered in a block. Both counters are incremented when a use of the symbol is encountered when traversing a block in a depth-first downward traversal. The use count is decremented when a use is detected when traversing the block in an upward traversal. A symbol is live when the use count is less than the use count threshold and the use count is greater than zero when a register is allocated. The register-allocated symbol is added to the conflict set of all live symbols.