Search-based Optimization for Compiler Machine-code Generation

dc.contributor.advisorWilson, Christopheren_US
dc.contributor.authorClauson, Aranen_US
dc.date.accessioned2013-10-10T23:20:00Z
dc.date.available2013-10-10T23:20:00Z
dc.date.issued2013-10-10
dc.description.abstractCompilation encompasses many steps. Parsing turns the input program into a more manageable syntax tree. Verification ensures that the program makes some semblance of sense. Finally, code generation transforms the internal abstract program representation into an executable program. Compilers strive to produce the best possible programs. Optimizations are applied at nearly every level of compilation. Instruction Scheduling is one of the last compilation tasks. It is part of code generation. Instruction Scheduling replaces the internal graph representation of the program with an instruction sequence. The scheduler should produce some sequence that the hardware can execute quickly. Considering that Instruction Scheduling is an NP-Complete optimization problem, it is interesting that schedules are usually generated by a greedy, heuristic algorithm called List Scheduling. Given search-based algorithms' successes in other NP-Complete optimization domains, we ask whether search-based algorithms can be applied to Instruction Scheduling to generate superior schedules without unacceptably increasing compilation time. To answer this question, we formulate a problem description that captures practical scheduling constraints. We show that this problem is NP-Complete given modest requirements on the actual hardware. We adapt three different search algorithms to Instruction Scheduling in order to show that search is an effective Instruction Scheduling technique. The schedules generated by our algorithms are generally shorter than those generated by List Scheduling. Search-based scheduling does take more time, but the increases are acceptable for some compilation domains.en_US
dc.identifier.urihttps://hdl.handle.net/1794/13433
dc.language.isoen_USen_US
dc.publisherUniversity of Oregonen_US
dc.rightsAll Rights Reserved.en_US
dc.subjectCode-generationen_US
dc.subjectCompileren_US
dc.subjectSearchen_US
dc.titleSearch-based Optimization for Compiler Machine-code Generationen_US
dc.typeElectronic Thesis or Dissertationen_US
thesis.degree.disciplineDepartment of Computer and Information Scienceen_US
thesis.degree.grantorUniversity of Oregonen_US
thesis.degree.leveldoctoralen_US
thesis.degree.namePh.D.en_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Clauson_oregon_0171A_10818.pdf
Size:
6.8 MB
Format:
Adobe Portable Document Format