Feedback-Directed Switch-Case Statement Optimization

  • Author(s) / Creator(s)
  • Technical report TR04-26. Switch-case statements provide a concise way to express multi-way branching control flow semantics. Switch-cases are common in programs, including script parsers, compilers and virtual machines. Because they occur in widely used programs, optimization for switch-cases has been studied since the 1970's. This paper presents two new techniques: hot default case promotion (DP) and switch-case statement partitioning (SP). DP improves case dispatch performance while SP simplifies case dispatch, improves instruction layout and enables further inlining. Both DP and SP are guided by runtime feedback information. An extensive experimental study compares the runtime performance of existent switch-case transformations and these new techniques. The effectiveness of these switch-case transformations depends on how these statements are used in a program. For benchmarks that heavily use switch-case statements, we observed overall execution time improvements of up to 4.96% when compared with a straightforward jump table approach. A micro-architecture level performance study provides insights on the basis for this performance improvement. | TRID-ID TR04-26

  • Date created
  • Subjects / Keywords
  • Type of Item
  • DOI
  • License
    Attribution 3.0 International