Daytripper

daytripper analyzes and rewrites binaries to better take advantage of Intel's Loop Stream Detector (LSD). The result hopes to realize power savings (by reducing the amount of computation performed, and allowing the frontend to be powered down) and some performance benefit (due to avoiding instruction fetch limitations). The 2010-03 edition of Intel's Optimization Reference Manual claims the following benefits:

• No loss of bandwidth due to taken branches
• No loss of bandwidth due to misaligned instructions
• No Length-Changing Prefix penalties, as the pre-decode stage has already been passed
• Reduced front end power consumption, because the instruction cache, BPU and predecode unit can be idle

Loop Stream Detector

• Introduced in Conroe, improved in Nehalem
• Located following instruction fetch in Conroe and decode in Nehalem
• Caches 18 fetched instructions in Conroe, and 28 decoded μops in Nehalem
• Lives in the branch prediction unit
• LSD.UOPS: performance counter providing the number of μops delivered by the LSD (introduced on Core i7)
• David Kanter had some excellent insight:

  One of the most interesting things to note about Nehalem is that the LSD is conceptually very similar to a trace cache. The goal of the trace cache was to store decoded uops in dynamic program order, instead of the static compiler ordered x86 instructions stored in the instruction cache, thereby removing the decoder and branch predictor from the critical path and enabling multiple basic blocks to be fetched at once. The problem with the trace cache in the P4 was that it was extremely fragile; when the trace cache missed, it would decode instructions one by one. The hit rate for a normal instruction cache is well above 90%. The trace cache hit rate was extraordinarily low by those standards, rarely exceeding 80% and easily getting as low as 50-60%. In other words, 40-50% of the time, the P4 was behaving exactly like a single issue microprocessor, rather than taking full advantage of [its] execution resources. The LSD buffer achieves almost all the same goals as a trace cache, and when it doesn’t work (i.e. the loop is too big) there are no extremely painful downsides as there were with the P4's trace cache.

Constraints

The Loop Stream Detector requires a number of properties from any loop hoping to be cached...

Pre-Nehalem

• No more than 18 instructions, none of which is a CALL
• Requires no more than 4 decoder fetches (16 bytes each)
• No more than 4 branches
• Executed more than 64 times

Nehalem

• No more than 28 μops

Methodology

• Start with innermost loops only, though the approach ought work for all loops.
• An innermost loop might not be a basic block. Exits in media res and oddly-encoded loop conditionals might violate the single-exit condition.
• Furthermore, jumps/branches elsewhere might violate the single-entry condition.
• The presence of indirect branches greatly complicates matters.
• Look for LCP stalls; these will be eliminated by Nehalem's LSD, making the optimization particularly effective. These include:
  • operand size prefix (0x66)
  • address size prefix (0x67)

History

• daytripper began as a project for Nate Clark's spring 2010 CS8803DC, "Dynamic Translation and Virtual Runtimes" at the Georgia Institute of Technology.
• some early notes on binary translation

See Also

• Real World Technologies article, "Inside Nehalem: Intel's Future Processor and System". 2008-04-02.
• Intel 64 and IA-32 Architectures Optimization Reference Manual (Order № 248966-018), March 2009. §2.1.2.3 and 3.4.2.4.