Show simple item record

dc.contributor.authorHorton, Michael Robert
dc.date.accessioned2020-08-28T10:49:35Z
dc.date.created2020-05
dc.date.issued2020-06-18
dc.date.submitted2020
dc.identifier.citationHorton, Michael Robert. 2020. Register Allocation by Pseudo-Boolean Optimization. Bachelor's thesis, Harvard College.
dc.identifier.urihttps://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364763*
dc.description.abstractRegister Allocation is a part of the compilation process in which virtual registers are mapped to a physical memory location. This problem is NP-hard yet also an integral part of the compilation process which has led to the development of various efficient heuristics for achieving near optimal allocations. These heuristics are used in modern compilers such as gcc and clang. In this thesis, we investigate register allocation via the solving a pseudo-Boolean optimization (PBO) problem. We develop a suitable encoding of Register Allocation as a PBO Problem. This PBO Problem has constraints relating to virtual and physical register liveness and a cost model developed to find not just a correct register allocation, but the optimal register allocation with respect to number of spills and expected program execution. We allow the PBO Solver to run for a specified amount of time (the longest trial being 6 hours per function) before the most optimal solution to the PBO problem found is used to perform register allocation. We find that the heuristics are able to outperform the PBO Register Allocator. However, we find optimal solutions to 81% of functions in under 65 seconds and have runtimes within 3% of industry strength register allocation methods. Further work will add live-range splitting to the PBO Register Allocator which should improve performance against the heuristics.
dc.description.sponsorshipComputer Science
dc.description.sponsorshipComputer Science
dc.format.mimetypeapplication/pdf
dc.language.isoen
dash.licenseLAA
dc.titleRegister Allocation by Pseudo-Boolean Optimization
dc.typeThesis or Dissertation
dash.depositing.authorHorton, Michael Robert
dc.date.available2020-08-28T10:49:35Z
thesis.degree.date2020
thesis.degree.grantorHarvard College
thesis.degree.grantorHarvard College
thesis.degree.levelUndergraduate
thesis.degree.levelUndergraduate
thesis.degree.nameAB
thesis.degree.nameAB
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.departmentComputer Science
dash.identifier.vireo
dash.author.emailhorton.mrf@gmail.com


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record