TransmetaTM CrusoeTM Hardware, Software, and Development

                                                        David Keppel amas-bt-2009@xsim.com

Abstract                                                                             The only programs running directly on the VLIW host
                                                                           are simulators, called “code morphing software” or CMS.

Transmeta was founded to build simple VLIW microproces- CMSes are substantially patterned after Shade, using a main sors with high clock speed, short pipeline, and enough issue dispatch loop and cached and chained translations. Where width for high performance. Crusoe is the first Transmeta Shade was simple, CMS is complex, supporting user and product. The only programs it runs are simulators, which kernel modes; x86 segmentation and stack floating-point; in turn run operating systems and applications. This paper optimizations to run CMS quickly; optimizers so gener- briefly describes Crusoe’s hardware, software, tools, and ated translations run quickly; and multiple implementation development process. strategies to run a wide range of user, system, and BIOS codes with consistent performance.

1. Introduction As important as the final product, are tools used to build, run, and debug Crusoe. Example tools are reference x86

Transmeta1 was founded on several observations: past simulators and corner-case tests; a fast simulator and fault- VLIW projects gave good performance but had compati- isolating debugger used to run CMS both while hardware bility problems; the Shade [CK94, CK95] simulator some- was in development and also long after hardware was for times gave performance close to one host instruction exe- sale to the public; and a highly automated test farm and test cuted per target instruction simulated, suggesting simula- generators. tion as a compatibility solution; and, for the time being, x86 was the industry standard ABI. The goal was to build a 2. Hardware low-cost, high-performance microprocessor with 100% x86 compatibility. The first product was the Crusoe micropro- Crusoe’s conventional VLIW issue includes two integer cessor. ALUs, an SSE-style FPU, memory load/store, branch, and Crusoe is2 a traditional VLIW, plus simulation sup- special register access. Up to four types may issue in one port [CDE+00, DGB+03]. One kind of support is for sim- VLIW instruction, but only in some combinations. Indi- ulating any machine. As example, Crusoe has transactional vidual operations in an instruction may be suppressed un- commit/abort. Code is over-optimized, with safety checks; der software control, allowing an individual operation to on failure, pending work is aborted, then re-run with lower be simulated or suppressed, without affecting or needing to optimization. A second kind of support is specifically for simulate the others [CDS03]. Long-running operations are x86. For example, a special hardware flags register com- typically interlocked, but short-running operations are not, putes flags using x86 rules. x86 simulators thus have x86 using software scheduling instead [DGB+03]. flags “for free”, while non-x86 simulators must compute x86 registers may be used as two 1-byte registers, a 2- flags in software. byte register, or a 4-byte register. The VLIW has 64 flat Notably absent is hardware support for decoding simu- 4-byte integer registers, with narrow 2-byte and 1-byte op- lated instructions. Instead, software does all target instruc- erations that do not sign extend. 32 80-bit FP registers tion decoding. Crusoe thus truly simulates all instructions, match the x87 FPU, with 32-bit and 64-bit operations so and can run arbitrary instruction sets, given a suitable simu- MMX/SSE operations do not get excess precision. lator. Transmeta’s first public demonstration showed a ma- chine simultaneously running both native x86 and native Pi- Branches have no delay slot, but indirect branches may coJava bytecodes. Quake compiled to PicoJava ran as fast stall to a pipe depth of 5 cycles. Indirect host branches as it did compiled to x86. are used commonly in interpretation and in some transla- tions. An indirect branch pipe allows branch targets to be 1Code Morphing, Crusoe, Efficeon, Intel, Microsoft, Microsoft Win- pre-loaded into the pipe. If the preload is at least 5 cy- dows, MMX, and Transmeta are trademarks of their respective owners.2 cles ahead, a branch-to-pipe instruction executes without For simplicity, this paper uses “is” instead of “was”. Transmeta delay [BCH03]. A branch pipe is generally difficult to use, stopped selling microprocessors in 2007 [Shi97] and was sold in 2008. The term “x86” refers to generic members of the Intel 8086 family, includ- but a few stylized uses are practical and show substantial ing IA-32. speedup.

1

A departure from conventional processors is commit and counters implement a superset of x86 counters, and are used abort, which implement a transactional model. Crusoe has both to implement x86 performance counters and internally two main structures for commit/abort: shadowed registers by CMS [CKB01]. and a gated store buffer [KW99, WD00]. Shadowed reg- The TLB has both generic simulation support and x86- isters are implemented as a pair of registers. On a register specific support. It has the same page size and basic pro- write, only the “working” register is updated. On a commit, tection controls as an x86, although the underlying organi- all working registers are copied to corresponding “commit- zation is different. The TLB is software-invalidated. CMS ted” registers; on abort, committed registers are copied to must detect instruction space changes, as x86 uses implicit working, thus erasing any changes since the last commit. rather than explicit instruction/data consistency [Kep09]. Shadowed registers include some integer, FP, and special Thus, the TLB has two write-protect bits, one for x86, registers. Shadowing only some simplifies hardware, and and one set during translation from a page, so subse- gives a place to store “why” state when a transaction is quent page writes fault and CMS can invalidate transla- aborted. tions [KCW96, KCW00], and the TLB is used even when The gated store buffer is conceptually similar to a regular x86 paging is disabled. Later Crusoes have a small cache of store buffer, but only entries which have passed a commit- sub-page write-protect bits used sometimes when code and ted “gate” are allowed to drain. On a store, the working gate data share a page [BAG+01]. register is advanced. Working and committed gate values The TLB also has four bits that compare against a spe- are handled as with other shadowed registers. On loads, the cial “match” register. x86-level TLB invalidations typically whole store buffer is snooped, whether or not committed. increment the match register, rather than performing a full The gated store buffer is conceptually simple, but has subtle invalidation. The TLB is 4-way associative and sectored, complexity. First, it is large, because translation size is of- with a valid bit per sector. ten limited by the number of stores, and using smaller trans- An x86 has three kinds of I/O. Memory-Mapped IO, or lations hurts performance. Second, some snooping corner MMIO, uses ordinary “memory” loads and stores. When cases must be resolvable without draining the store buffer, they “miss” RAM, they perform device reads and writes in because draining implies commit. a 32-bit address space (36 bits with PAE). Direct Memory Physical memory is divided into a CMS-only section and Access, or DMA, allows devices to asynchronously read a target-only section. CMS memory holds the simulator and write RAM in the same address space as MMIO. In- code, translations, and simulator data structures. The target Out I/O, or IOIO, uses in and out instructions that read and section contains committed target memory state. Pending write devices in a separate 16-bit address space. uncommitted stores are never released from the store buffer Various details complicate I/O. One device may be con- until committed. A third, on-chip “local” memory is small nected to both address spaces. A portion of the low and has guaranteed fast access and is accessed with short megabyte of address space is mapped to a legacy video instructions. Local memory holds frequently-used state that device and never to RAM. Another portion has reads and is not so frequent it deserves fixed allocation in VLIW reg- writes steered separately. One use is an x86 BIOS copy isters. Local memory holds both CMS and target state. loop that does simply “read X; write X” to copy from a More support for general simulation is provided by “alias memory-mapped ROM to RAM, while executing from the registers” [WK99, Kla00, RDP06]. Each holds the address same page that holds the data being copied. Crusoe has spe- of a memory operation and is tied to a comparator that cial steering hardware for just these addresses; it is unused signals an exception if it overlaps with a memory opera- for other targets. tion. CMS may then arbitrarily reorder memory operations DMA is conventionally performed by an asynchronous within a translation, saving dependencies in alias registers. copy engine, but on Crusoe that introduces coherency prob- If a reordered memory reference overlaps another, the trans- lems for translated code. Crusoe uses a DMA interrupt and lation is aborted and retranslated at lower optimization. In CMS performs all DMA and checks for translation invali- practice, most loads and stores can be reordered. dation [BKK+03]. Software DMA serializes DMA and re- Target-specific simulation support includes condition moves benefits of concurrent computation and communica- code flags mentioned above. A second set of condition tion, but early workload studies showed DMA was rarely codes is used by CMS, and avoids multiplexing a single used. DMA is common in newer workloads, and Cru- condition code register [CK93]. soe’s successor, Efficeon, uses a simple DMA engine which The first VLIW design used no segmentation hardware, handshakes with CMS to ensure DMA writes do not overlap but after better workload analysis, hardware segmentation translations, but allows asynchronous DMA otherwise. support was added for certain common cases. Although Ordinary memory can be read multiple times without segmentation support mimics some usual x86 segmentation side-effects, which in turn allows speculative operations. functionality, the bit-level layout is distinct. Performance Memory-mapped I/O, however, must be read exactly once

    2

for each target read request. This is complicated to sim- than 90%: many workloads spend substantial time blocked ulate, as any memory reference, including an instruction on memory, and memory typically stays at 100%. Thus, fetch, can go either to real memory or to memory-mapped cache misses are effectively faster when the CPU is slowed. I/O. To make translation practical, VLIW loads and stores use two address space identifiers, or ASIs: “normal” (#n) LongRun complicates characterization and binning be- and “abnormal” (#a). RAM is accessed only with #n. A cause transistors are not precisely linear, so transistors may load or store to an MMIO address with a #n ASI causes a “bin” differently depending on the specific voltage and fre- “normal assumed” exception. Similarly, MMIO uses only quency setting. Yields are improved by using higher volt- #a. These ASIs enable translation optimizations for RAM ages, but at the expense of higher power consumption. Dif- accesses, while ensuring correct behavior on MMIO. Large ferent settings could have been allowed for each part, but at objects, such as 80-bit FP and multiword x86 complex data, intolerable manufacturing expense to manage multiple V/F are implemented using multiple VLIW loads and stores. To mappings for each part. ensure “all or nothing” behavior, a sequence of check in- structions precede and protect large loads and stores. Check VLIW registers allow software to choose higher or lower instructions fault if the corresponding load or store would power/performance settings, then request a level change. fault [KSD03]. The request briefly stops all execution while hardware The PC architecture extends beyond the x86 instruction changes power supply voltage, frequency multiplier, resyn- set, and includes bridges for memory and external devices. chronizes the PLL, then restarts execution. Some care is Crusoe uses a memory controller integrated with the CPU. needed to ensure the power supply does not glitch during The North Bridge, which is closest to the CPU, is imple- voltage changes. Since no work is done during changes, mented in software, with underlying VLIW CPU support LongRun software must balance what V/F settings to use, for memory control registers, etc. x86 bootstrapping with when to change, and how often to change. an integrated memory controller is somewhat complicated, as RAM is checked by CMS before the first x86 instruction All exceptions go to a common trap vector. Exception runs, but x86 software can reconfigure RAM. The South types include usual processor exceptions plus “special” ex- Bridge is a commodity part, as used with other x86 CPUs. ceptions to support simulation. Exceptions are typically ser- Older x86es use the PCI bus for graphics. AGP became viced two ways. One is “fix up and continue.” For example, popular during Crusoe development and offers much higher on a TLB miss fault, a simulation routine reads target page performance via a faster bus and RAM-like behavior. AGP tables, loads the hardware TLB, then restarts the faulting is not included in Crusoe hardware, limiting both graphics instruction. Another example is to simulate a faulting oper- performance and GPU compatibility. Crusoe’s successor, ation, then restart the faulting instruction with the relevant Efficeon, has AGP. pipe disabled [CK04]. A second service category is “abort Crusoe power management includes LongRun [Kla00, and go to main loop.” For example, if the store buffer over- HAC+06, RHK07]. LongRun allows the processor to flows from too many uncommitted stores, the current trans- quickly stop, adjust clock speed and voltage up or down, lation is aborted and the simulator creates a new translation and restart. CMS controls LongRun, increasing speed when with fewer stores between commits. (The number of stores the processor is continuously busy, and decreasing it when is often not known during translation, see §3.) x86 inter- the processor is mostly idle over some interval. rupts, including DMA, are also handled via abort to ensure Savings are substantial because lower frequencies al- handling when x86 state is precise. low proportionally lower voltages, and dynamic power con- sumption is roughly proportional to V 2F and leakage is Exceptions set a “fault” bit in hardware, and return from roughly proportional to V 2. Thus, running at 90% fre- exception clears the bit. If another fault occurs while the quency uses roughly 70% static and 80% leakage power bit is set, control vectors to a special “double fault” location compared to running at full speed. LongRun2, introduced in the exception vector, whose handler carefully services the with Efficeon, extends the V 2F observation, using an ad- nested fault [AK04]. Nested faults are dynamically rare, but justable substrate bias to cut both static (leakage) and dy- there are many corner cases that can give rise to them. For namic (switching) power, and to increase switching speed. example, placing page tables in video memory causes TLB Actual energy use varies, as a slower processor takes longer miss handling to take a normal-assumed fault; the transla- to complete work and thus spends less time in deeper power tion is aborted, then during interpretation the miss handler’s management states, but in practice CPU energy savings are #n load is promoted to #a. Nested fault handlers increase often substantial; and in a typical laptop, the CPU is the software complexity because there are multiple handlers for second biggest energy user, after the display backlight. each fault type, but nesting speeds common-case handlers, Performance at 90% clock speed is also typically better e.g., by allowing a dedicated temporary register or by ignor- ing uncommon cases and letting them double fault.

    3

3. Simulator: CMS virtual and physical addresses: the same code at a differ- Crusoe hardware runs only one application: CMS. At a high ent virtual address may need to be translated differently, as level, CMS is a “traditional” translator like Shade [CK94], not all code is PC-relative; and mapping the same virtual with data structures holding the target state (TS), and sim- address to a different physical address may reference differ- ulation code and data including a main loop, translator, ent code. The V-to-P check uses the TLB and so also per- translation cache (TC), and a translation map (TM) used forms needed protection checks. CMS also matches saved to find a suitable translation given the current virtual state. information called “context” [KCB01]. For example, an In addition, CMS keeps potentially extensive information instruction may execute differently in real mode than pro- for each translation (TCinfo), and CMS uses an inter- tected mode. Rather than generate one general translation preter: it interprets instructions several times before trans- that works for both modes, CMS generates a streamlined lating them, and interprets to handle certain corner-case translation for each situation. behaviors. Other components include “out of line” sub- Other approaches are possible, such as TM invalidation routines called from translations or the interpreter, called on each mode transition. But using context allows fine- “OOLs”; dynamically-generated repeat string OOLs called grained choices. For example, the user/kernel mode is in “DROOLs”, an exception-handling kernel called the “nu- the context, and mode checks are performed at translation cleus”, a simulated “virtual north bridge”, LongRun, power- time rather than during execution. The context risks dupli- on reset, and cross-debugger support. cating translations, but what goes in the context is chosen Target state is held principally in four places. First, target so in practice most code is executed in only one context. memory is stored in a target-only part of host RAM. Sec- A problematic case was emulating the mapping from x87 ond, ordinary integer and floating-point/media (FP) target stack to VLIW registers. Most code executes a given FP in- registers are allocated to shadowed VLIW registers. Third, struction with only one mapping, but non-FP code is often complex non-memory target state is held in local memory run with many FP mappings. This was solved by moving and cached in VLIW registers as needed. Targets with many FP stack mapping to hardware [RDD+04]. registers allocate target registers to VLIW local memory The main loop has various entry points: translations may and cache them in VLIW registers on demand. For the x86, return to the main loop in various ways depending on their hard allocation to VLIW registers simplifies bookkeeping, status. The interpreter also branches to the main loop. And especially given the x86’s asymmetric treatment of regis- while nucleus aborts largely sanitizes x86 state, there is sim- ters. Finally, target device state is held in target devices: ulator state which merits special treatment on exceptions. CMS state exists only in the processor, RAM, and ROM, For example, “store buffer overflow” is handled by retrans- and no target devices besides ROM and RAM are assumed lating with more frequent commits; “x86 page fault” is han- or required. dled by executing instructions one-at-a-time until the fault On entry to the main loop, CMS looks for a translation reoccurs, then by branching to code which simulates page that matches the current program counter (PC) and context fault delivery then resumes x86 execution [TK01]. (described below). If no translation is found, the main loop A goal of CMS is to minimize trips through the main calls the interpreter, which updates instruction and branch loop and instead branch directly to suitable code. Examples counters as it runs [TA05]. When a given instruction is ex- of this include translation chaining, retranslating to avoid ecuted a few tens of times, the interpreter returns, and in- speculation exceptions, and so on. A case which is com- structions are translated using the branch statistics to guide mon and difficult to avoid is indirect target branches, which translation. may go to any address. Where branches are dynamically Interpretation costs on the order of 100 VLIW instruc- predictable, a flavor of receiver caching [DS84] is efficient. tions per simulated target instruction, where translations are However, many indirect branches are unpredictable. For typically under 1 VLIW instruction per simulated target in- example, return from a procedure such as strlen(), which struction. However, interpreting avoids translating rarely- often has many callers. For unpredictable branches, CMS used instructions, which may cost 10,000 VLIW instruc- uses a fast lookup in a small cache of recent lookups, falling tions per translated target instruction. And, interpretation back on misses to a general TM lookup. Early Crusoe collects profile data that greatly improves performance of uses a software cache; late Crusoe uses a small hardware many translations. The interpreter also implements precise cache [BCT+03]. x86 semantics and computes exact x86 state at every in- A translator for a Shade-like simulator is straightfor- struction boundary. The interpreter is thus used for deliver- ward: for each target instruction, emit a “canned” sequence ing faults and for handling corner cases that are too rare or of host instructions, and repeat until a branch, until some expensive to handle in translations. threshold is reached, or until an especially tricky case is CMS finds translations by hashing the current target pro- reached. In contrast, the CMS translator is an optimiz- gram counter (PC) to subscript the TM. CMS matches both ing compiler whose source language is decoded x86 in-

    4
   

structions, and whose optimization strategies include con- are a multiple of page size.) ventional things like common subexpression elimination, VLIW instruction scheduling typically schedules the VLIW-specific instruction scheduling, and unconventional longest path then fills available slots where possible. Alias things like alias protection for speculative code motion. registers and the corresponding load/store motion often The translator first reads x86 instructions and decodes makes translations significantly shorter. Alias speculation them to an intermediate representation (IR). The transla- occasionally fails and requires retranslation. Failure is rare, tor typically reads instructions that have already been in- so for nearly all applications it is at least a slight win, and terpreted, but may read new instructions and thus must for some nearly doubles performance [DGB+03]. perform all usual fetch-time checks. The interpreter col- Register allocation is somewhat complicated, as some lects conditional branch profiles, and the translator fol- registers are dedicated to target state and so are live on entry lows branches but often avoids branch-to-self to avoid store and cannot be renamed on exit. With many registers, mod- buffer overflow – Crusoe translations are single-entry mul- est issue width and a short pipe, register pressure is not typi- tiple exit, and while they may contain embedded loops, cally a problem. The x86 flags register is set by most x86 in- they tend to be more like DAGs rather than full sub- teger instructions, and some x86 instructions set only some graphs [DS84, May87]. Once a translation is generated, it is flags leaving others with their earlier values. Thus, analysis sometimes retranslated into several simpler translations, but is needed to safely remove flags operations and keep flags translations are not merged [May87] except for chaining. calculations from being a bottleneck. TM lookup performs a page protection check on the first Crusoe also simulates x87 FP, whose architecture in- instruction in the translation. When a translation spans cludes eight FP registers, a “valid” bit per register, and a pages, the translator generates checks for other pages in the “top of stack” (TOS) register, often used to treat the reg- translation [BKB05]. Chaining to a translation on a differ- isters as a stack. FP instructions contain offsets which are ent page goes by way of a page protection check called an added to TOS, mod eight, to form absolute register num- “interpage prologue” or IPP [BKB05]. bers. fadd is a two-operand add, where one operand is off- CMS optimizations include “traditional” compiler opti- set zero. faddp also increments TOS; in typical use, the mizations as well as simulation-specific and Crusoe-specific second operand has offset one, so faddp has the effect of optimizations. All optimizations would ideally provide popping the first register and making the second register the good translation speedup with little translation-time cost. new top of stack, which the next instruction accesses with However, choosing optimizations is tricky, as benefit varies offset zero. Crusoe uses a hardware TOS (but see §5). widely with the workload, and even cost varies some with Each x87 register also has a valid bit. Reading an invalid the workload. register or overwriting a valid register causes an exception. It is the nature of machine code that translations often In typical use, valid bits are set for register numbers TOS contain redundant subexpressions, especially for memory and higher, and clear for lower-numbered registers. CMS addressing. Constant folding and propagation are also use- detects this and only simulates valid bits explicitly when ful. Translations often speculate branches based on inter- they follow a different pattern. preter profiles, and commit and branch to another transla- The x87 has deferred errors, where state about each FP tion for the not-predicted path. Thus, translations typically instruction is saved internally, and executing a later FP in- have few internal branches, and various loop optimizations struction delivers pending errors. The saved state is: the are of less value. Short target subroutines may be inlined code segment, PC, opcode, data segment, and operand off- in a translation – being sure to push and pop the target PC. set in the data segment. Saving that state substantially com- Translations do, however, have branches to call OOLs. plicates and slows simulation. However, target FP instruc- The VLIW has eight alias registers, which allows loads tions are often clustered, so a single translation has only one and stores to be moved speculatively. If they overlap, an “last” FP instruction that is complicated to simulate. Most alias exception is delivered, but except for memory refer- but not all FP instructions check for pending errors; errors ences that “obviously” overlap, most do not overlap, so the may be ignored or delivered; and errors may be delivered compiler often does a good job choosing non-overlapping as exceptions or interrupts, optionally routed through off- operands. The compiler avoids using alias registers where chip logic, and optionally cause the x86 to stall until a non- it can: one translation often has tens of loads and stores, maskable or non-masked interrupt. making alias registers a scarce resource. Some cases are The VLIW store buffer is 32 entries, but translation typi- amenable to translation-time analysis, for example adjacent cally stops at fewer than 32 x86 stores. Many stores take up offsets from the stack pointer within 4096 bytes never over- more than one store buffer entry because misaligned stores lap, even if adjacent stack pages map to the same physical may span store buffer entries and because x86 memory ac- page. (In real mode, segments can be arbitrary sizes, but cesses cause implicit “accessed” or “dirty” bit writes to the segment wrap only occurs with full-size segments, which page tables, again using store buffer space. Some CMS state

    5

writes use buffered stores. A few x86 instructions use more compiles DROOLs tailored to particular calls. Although than 32 entries. For example, fnsave directly uses 29 to 37 there are many rep cases, many programs dynamically use store buffer entries, depending on the size and alignment of just a few. Thus, performance is improved at low space cost. the operand – plus any used implicitly for TLB accessed and User-level simulators use the host to handle most excep- dirty bits. CMS does not directly translate large cases but tions. Exceptions that are simulated typically poll whether instead the translation calls an OOL. The OOL pre-checks an exception is needed. System-level simulators typically all stores for possible faults; if all are safe, stores are com- simulate all checks needed for delivery. CMS relies on the mitted incrementally. underlying VLIW to deliver most exceptions and interrupts, Translation also stops for other reasons. One reason is which are vectored through a “mini OS” called the nucleus. target instructions that make pervasive state changes, mak- CMS also simulates some checks, and also typically vectors ing further translation difficult. For example, state loaded them through the nucleus with a “conditional trap” instruc- from target memory that changes the context. Translation tion, which is smaller than a conditional branch and also also typically stops soon after MMIO loads, because many reduces contention for the VLIW condition codes. translated operations handle corner cases by aborting, and As an example of nucleus operation, consider a store in- MMIO loads cannot be aborted and may not be repeated. struction to the #n ASI which takes a “normal assumed” Translation need not stop immediately, but many instruc- exception because the store actually goes to MMIO. If the tions cannot follow “tricky” instructions, and these are usu- faulting instruction was translated – that is, is in the TC – ally encountered soon enough. the nucleus aborts and branches to the main loop, indicating To reduce duplication, translation sometimes stops on “retranslate abnormal assumed”. Static code typically does x86 instructions that are already translated. Translation also not have “abnormal” variants, as that would roughly double stops after at most 200 x86 instructions [DGB+03]. the size of OOLs and the interpreter, yet still leave tricky Finally, translation may stop due to adaptive retransla- corner cases such as a page-spanning read or write that tion: CMS records when and why a translation fails, so touches both RAM and MMIO. Instead, the nucleus copies retranslation can create better code for the situation. As the faulting VLIW memory operation, changes the ASI in an example, when a particular x86 instruction faults fre- the copy to #a, executes the copy, then restarts the except- quently, CMS may generate a new optimized translation ing VLIW instruction with that memory pipe suppressed, so that ends just before the faulting instruction, followed by the original load or store is not reexecuted. Page-spanning a translation that branches directly to the interpreter to han- loads and stores are split as needed, and MMIO byte lanes dle faults [DGB+03]. Adaptive retranslation is also used to masked. Any MMIO, once performed, must not be in- deoptimize when speculation is too aggressive, though this terrupted or aborted, so the interpreter and interpreter-like does not necessarily shorten translations [DGB+03]. OOLs execute each instruction under lock, and all static Translations are stored in a conventional TC. Shade-like code in the interpreter or callable from the interpreter fol- translators typically fill the TC then invalidate it completely. lows certain rules to ensure aborts are never needed once a CMS translation is expensive, typically thousands of VLIW #n load or store is promoted to #a. instructions per translated x86 instruction, so CMS reclaims Note that a copied instruction may itself take an excep- TC space incrementally to save retranslation overhead. The tion, for example due to a TLB miss or page table dirty bit TM matches virtual address, physical address, and context. write. In that case, the nucleus takes a doublefault exception The interpreter and translations both call OOLs. OOLs and carefully saves state so the nested exception handler typically perform rare or expensive operations that would does not step on the first-level handler. The nested fault is otherwise bloat translations without performance gain. Ex- serviced, then state is restored and the first-level exception amples include simulation of call gates, segmentation resumed. On a dirty write, the store buffer may overflow, changes, north bridge simulation, and so on. Some OOLs causing the doublefault handler to be invoked recursively, return to the caller and do not commit; other OOLs change called a triple fault. Store buffer overflow and other such state in a way that makes chaining tricky and so commit cases cause an abort, so interpreter code is constructed to then return to the main loop. avoid cases that can give rise to overflow. As example, fn- A special case is x86 rep instructions, which repeatedly save checks all permissions before performing any memory scan or move bytes in memory. For example, “scan for the operation, then commits stores incrementally to avoid store byte value B” or “move N words”. There are many rep buffer overflow. variants, and some combinations of alignment and transfer x86 and DMA interrupts are also vectored through the size are much faster with special-case CMS code. rep code nucleus. The nucleus aborts and branches to the main loop. is large enough it is best to avoid inlining it in translations, All of CMS must therefore be built so all nonshadowed ac- but like BitBlt [Loc87], there are many special cases, and cesses are safe against interrupts. As example, a nonshad- static specialization would bloat CMS. Thus, CMS demand- owed register may be read and then written between com-

    6

mits only if interrupts are locked out. Similarly, all memory 16 bytes of instructions, or after a serializing instruction. references that use the ASI #a or which might be promoted Thus, some checking must be done late in the translation, by the nucleus to #a are locked, stay locked until the next after any possible writes. commit, and must not abort. When only immediate fields are changing, translations Simulation of self-modifying x86 code is problematic can fetch the values from the x86 instructions, being sure to in part because the x86 relies on hardware instruction/data skip immediates in checks [DGB+03]. Where instructions coherency, where most other processors have a software change but only to a few “stylized” patterns, CMS keeps mechanism to indicate I/D changes. “Self-modifying” code a list of previously-generated translations and checks if any takes many forms, including paging (code pages are reused have become valid again [DGB+03]. Finally, CMS can gen- to hold different code), dynamic compilation at various erate a translation which simply calls the interpreter, thus grain sizes and reuse rates, one-time instruction patching avoiding further overhead to “rediscover” where interpreta- such as used by some dynamic linkers, and patching of in- tion is needed. dividual bits or fields in some instructions [Kep09]. CMS is also heavily involved in power management. To respond with good performance, CMS uses several Longrun manages two types of state transitions. When mechanisms. In most cases, the primary goal is to avoid an x86 is idle, the OS executes a HALT. LongRun tracks frequent retranslation, as that is the highest cost, often two these and slows the CPU the more often it is idle. At idle, orders of magnitude slower than interpretation. LongRun also sets a countdown timer; when there is no By default, code pages are write-protected during trans- idle time the timer expires, signaling LongRun to increase lation. The VLIW TLB has a second write-protect bit called speed. At top speed, no timer is needed, so LongRun has no the “T” (translate) bit. For each page translated, CMS sets a overhead. bit in a simulator data structure and invalidates TLB entries CMS bootstrapping is different than most simulators: At if the bit was clear. On TLB miss, the TLB’s T bit is loaded power on, CMS runs – slowly! – from the system ROM. It from the data structure. copies code to local memory, executes from local memory Write faults invalidate all translations for the page, so ex- to configure RAM, then copies CMS to the CMS part of ecuting from a modified page forces retranslation. If fault RAM, initializes the x86 state to power-on-reset then starts rates for a page are high, CMS uses a variety of strate- executing the BIOS. gies that are asymptotically slower but also less sensitive CMS is stored in a programmable ROM along with a to change. backup “fail safe” CMS. CMS changes are cryptographi- “Self-revalidating” translations use a VLIW structure cally protected against downloading arbitrary code, and the that divides a page in to subpages and keeps a bit per sub- backup ensures that even a power failure during reprogram- page. On a first write, a write fault handler marks the sub- ming is recoverable. Primary and backup CMS versions page as writable but not executable; subsequent writes do are in isolated physical parts of the ROM so power failure not fault. Special translations for these pages check the during CMS write cannot corrupt the backup CMS. CMS corresponding bits for all subpages used by the translation. also has a fixed-format configuration table at a well-known When all subpages are executable, the translation simply address, used to hold configuration data such as CMS and executes. If a subpage is marked writable, the translation LongRun tuning parameters. It is not writable by users, but compares current x86 memory against bytes saved at trans- supports vendor configuration for each platform. lation time. If all match, the bits are marked executable, and 32-bit x86 was the only Crusoe released publically. x86- further uses of the translations do not need to re-check. If 64 was implemented on Crusoe hardware [KF03]. It had any mismatch, the translation is invalid and CMS uses an- about 100x lower performance, due partly to multiplexing other strategy. This strategy efficiently handles most cases 64-bit operations on 32-bit hardware, but due mostly to in- where code and data are on the same page and code rarely terpreting only – no translation. Though incomplete, the changes. Although the VLIW structure is small, applica- x86-64 implementation passed all existing validation tests tions rarely have many pages sharing code and writable and could boot and run OSes and applications. It was prob- data [BAG+01, DGB+03]. ably the first hardware x86-64 processor, predating even “Self-checking” translations use unprotected pages: ev- FPGA implementations. ery time a translation is invoked, it compares the current and saved bytes [BAB+03]. Self-checking translations are thus 4. Supporting Software slower than self-revalidating translations, but can compare only those bytes used for the translation itself, rather than CMS exists only because of supporting software: reference a whole subpage, and they eliminate write faults and state simulators, a fast VLIW simulator, error detection and iso- ping-ponging of self-revalidating translations [DGB+03]. lation tools, bug and source code management tools, build The x86 assures coherency after a branch, after executing and debug tools, test generation and test suites, test and

    7

farm management, and performance monitoring, visualiza- played after “undo”. tion and navigation tools. The VLIW simulator’s commit/abort mechanism is ex- One part of building “an x86” is discovering and defining tended to save total machine state, called a “checkpoint.” “what is an x86”, then committing that to a reference sim- Reloading an earlier checkpoint restarts execution from ear- ulator. A reference simulator is a standard for comparison lier in the execution. Checkpoints include an I/O log, so to find bugs in the product. There are many problems dis- even interactive sessions with live input can restart from an covering what is an x86: there are multiple standards, stan- earlier checkpoint and replay I/O, thus reproducing execu- dards sometimes conflict, x86 implementations sometimes tion exactly. disagree with standards, and some applications, including The reference simulator also supports checkpoint and OSes, depend on nonstandard behavior. Parts of some op- restart. In principle, adding checkpoint and restart to any erations are undefined and vary from implementation to im- simulator consists of saving and restoring target state and plementation. Applications may depend on combinations logging target I/O for replay. In practice, simulators tend of behaviors that are nominally independent; such applica- to cache target state in various tricky ways. For example, tions are arguably buggy, but some have historically been a translating simulator may cache translations based on a supported anyway. bit in a target register, and moving to a different check- For all these reasons, the reference simulator changes point may change the bit. Thus, a simple bit copy of target continually to reflect newfound understanding of the x86. state may be insufficient. However, an “official” interface Further, the reference simulator is also used to simulate var- to change the bit may perform consistency checks, so us- ious non-product x86es to diagnose changes between exe- ing it to restore state may signal an error, even though state cution on the product x86 and a non-product x86. Thus, will be consistent again when checkpoint restore finishes. the reference simulator needs to be easy to change, config- In addition, the simulator may keep non-target state such as urable, reliable, and fast enough to not be a serious bottle- pipeline state and profiles, and that state should be updated neck. In practice, execution speed is typically over 100 host at each checkpoint change. instructions per simulated target instruction. Checkpoints are large – the size of the target state – so CMS development started years before working VLIW frequent checkpoints and restarts are expensive due to both hardware. Development uses a fast VLIW simulator that the direct cost of copying state, and because restart often uses dynamic translation and runs on an x86. It typically needs to load a checkpoint from secondary storage. Op- runs about 30 host instructions per simulated target instruc- timizations such as asynchrounous writes speed up check- tion. As CMS matured and approached 1:1 x86:VLIW, pointing considerably, but it is often inconvenient to store overall performance under the VLIW simulator was so good checkpoints in a format they can be resumed via demand it could boot and run x86 operating systems in something paging. For a simple restart, performance is rarely annoy- approaching real time – visibly slow, but still fast enough to ing, but binary searches during fault isolation (see below) enable many kinds of work that would have been infeasible occasionally take a long time. on a slower simulator. Checkpoints may be loaded by different debugger ses- Even with VLIW hardware available, fast simulation is sions. Automated farm testing executes long-running tests still vital. At first, only a few systems are available, they to find bugs, then leaves checkpoints so humans can quickly are in high demand, and are potentially flaky. As systems get to the point of failure found by automation. Checkpoints are more widely deployed, the superior environment in sim- are also an easy way to hand off debugging sessions be- ulation still makes it preferable for many tasks. Finally, as tween developers. hardware is revised, simulation is again available before re- Each simulated VLIW instruction is given a virtual vised hardware, allowing development, testing, and mea- timestamp called a “vtick”. Each simulated target x86 in- surement to proceed with workarounds removed and new struction executed is given a virtual timestamp called an features added. “xtick”, whose name has stuck even for non-x86 targets. The VLIW simulator is itself a study in simulator con- CMS calculates the xticks performed by a translation and struction: the host x86 has few registers, and the target tells the simulator using a specially-coded VLIW NOP. The VLIW often shadows resources to speed up simulation, so simulator can stop at a given vtick; since xticks advance the fast VLIW simulator needs to simulate both sets of re- in chunks, it can sometimes only stop near a given xtick. sources. For example, the fast VLIW simulator keeps an Restart from checkpoint is wrapped in a command go- “undo” log. When writing a shadowed resource, it copies tov V or gotox X that loads from the most recent check- the old value and address into the undo log. On commit, the point before V or X, then executes forward until the tick is undo log is discarded. On abort, undo log values are written reached. Finally, the simulator saves checkpoints automati- back to memory. However, nonshadowed values can also cally, so developers never “see” checkpoints, instead think- be clobbered, so there is also an “undo-redo” log that is re- ing in terms of executing to a specified tick. This facility is

    8

called “reverse execution.” pers. Fortunately, most blocks of code are relatively inde- The reference simulator and fast simulator both have pendent – building a specific version of CMS may require checkpoint and restart facilities, and are run together un- a specific version of build and simulation tools, but such der an execution control framework called the “nexus”. In dependencies are usually simple. Branches are used fre- simple form, the nexus tells CMS to execute one translation quently but with frequent merges against the trunk, or with then stop, then advances the reference simulator to the same an explicit plan to never merge. xtick, then compares all of registers and memory, halting if Custom build tools are used to generate VLIW object there are differences [KBK99]. Paired execution is called code. Much of CMS is written in C with selected exten- “cosimulation.” Stopping every few instructions to compare sions. Some extensions give access to special VLIW hard- millions of bytes of memory is expensive, so in practice the ware, for example special registers in the VLIW. Many ex- simulators are advanced by thousands to billions of x86 in- tensions control compiler behavior. For example, some structions. In this way, reference comparison costs are kept code is checked using PC ranges, so it is vital an inline to a small part of the total simulation cost. function really is inlined; a compiler directive causes com- When an error is found, it could be anywhere since the pilation failure if the routine is not inlined. Similarly, tail last comparison. An early and vital feature of the nexus is recursion and other properties can be assured. “narrowing”: the nexus backs up to the last agreeing com- A fast build system is useful for all development, but vi- parison, then executes forward half the number of ticks to tal for a code base with frequent checkins and loose checkin the failure. If comparison fails, the error is in the first half; requirements. The build system uses both incremental and if not, it is in the second half. This repeats until the nexus “from scratch” build servers for CMS. Incremental builds arrives at the first xtick past failure. Thus, errors are isolated sometimes give false failures due to bad dependencies, but to a specific failing translation, often in a few seconds. can validate or refute a checkin in just a few minutes. The The debugger runs the nexus. It also looks in the “guts” full build server is more reliable, but can take many tens of of CMS. For example, the debugger prints VLIW registers minutes. Often, errors are fixed and checked in well before along with the x86 registers they represent. Thus, with a the first full build reports failure. A fast build system is a few keystrokes it is possible to land at an error, examine the mixed blessing, in that it encourages sloppy checkins. On host and target code, back up to the last agreeing xtick, set the other hand, fixes and features by one developer can be breakpoints or single step, watch values changing, and even available to all in minutes. Especially in early development, examine low-level state, such as uncommitted entries in the the ability to request a fix or feature and everybody have it store buffer. five minutes later is a great win. Although some errors are subtle, many are “obvious” Like the nexus, the build system does failure narrowing. and easy to repair. Given the reference simulator and nexus, If there are five checkins while build #123 is running, the the time from failure to repair is often just a few minutes. build server next builds #129. If that fails, the build server Once VLIW hardware was available, the simulator was both reports failure and starts a binary search for which extended, where possible, to provide the same views. For checkin triggered the failure. example, much VLIW internal state is available via special Once code passes rudimentary testing and checkin, it machine registers. The VLIW simulator was extended to goes through escalating tests. The first tests are simple ones track even state that is not essential for VLIW simulation. that have often failed before [Cla91]. Better and better can- On hardware, the debugger also gives access to state that is didates are run on longer and longer suites, some running not simulated, such as cache tags and contents. Such state for weeks. The best candidates, are subjected to human can be queried interactively and can also be downloaded testing, and some difficult or risky changes are also human- for automated analysis – which sometimes proved vital in tested. The fast VLIW simulator means human testing can diagnosing errors. begin long before hardware is ready; and starting human Many early bugs were simply found and fixed. Later testing early means increased maturity when hardware is bugs are often more complicated and have several people available. working together to discover, diagnose, and repair. Bug Testing uses both VLIW and x86 suites. Tests include tracking is largely done using Gnats, though customer- instruction-level tests and system level tests including per- facing groups use a tool with work flow. Gnats works formance tests. VLIW tests are all written in-house, while well for developers in part because it runs “cleanly enough” x86 tests include both in-house and external tests. External within GNU Emacs, which is preferred by most software tests include those bought from other companies, industry- developers and used frequently by others. standard tests, applications and OSes used as tests, and CVS with wrappers is used to manage CMS source code, acceptance suites used by individual makers. Note that as well as sources for most tools. CVS has various well- “test” implies an acceptance or rejection criteria. Some known limitations, some of which are solved by the wrap- benchmarks have a checkable results file, but many do not.

    9

Nonetheless, “crashes” and “fails to complete” are under- developing tools to pattern match the video output. This stood to be a checkable failure. So while a benchmark sometimes yielded false failures, so video frames were kept may silently (uncheckably) compute wrong answers, some for human review. outcomes are easily recognized as failures. And although Hardware is always in high demand and limited supply. benchmarks are not designed for fault isolation, some fail- Even with processors in volume production, the in-house ures are easy to diagnose and can expose bugs not found by debug systems are in limited supply and often need rework. any other test. Thus, it is valuable to at least triage these In-house farm hardware and software allow automated ini- failures. tialization of CMS, the BIOS, and the hard disk drive. This Several automatic instruction-level and system-level test in turn allows any machine to be used for any purpose. A generators are used for both VLIW and x86 testing, in ad- machine can be allocated, configured, and used for remote dition to traditional hand-written tests and real workloads. interactive debugging. Then, no matter what it’s state, it Automated tests are used for both hardware and software can, without human intervention, be reallocated and recon- development, and for both finding and diagnosing failures. figured for another use, such as batch testing, with any de- Automated test generators produce tests which are compli- sired versions of CMS, BIOS, and disk image. cated enough to find failures not found by simple tests, and A small remote debugger stub is built in to CMS. On are often simpler to diagnose than failures in real work- CMS boot, the stub queries a special debug connector and loads. Once bugs are discovered, the test generator can if “live”, downloads a larger debug stub before proceeding. be constrained to exclude or emphasize certain features in The stub provides general access, and the debugger’s user order to help find small and easy-to-debug test cases. Al- interface is the same for simulation and hardware, as much though “narrowing” is often time-consuming, it can be auto- as possible, so a developer’s experience is nearly the same mated to a degree, and can proceed in parallel with diagno- for debugging on both simulator and hardware. With effort, sis of test cases so far. In practice automated tests find both even cosimulation of hardware against a reference simula- hardware and software bugs including tricky corner cases tor is possible, though the lack of reverse execution on hard- missed by hand-written tests. ware is a serious shortcoming! Debugging short instruction sequences from test genera- Debugger code is integrated with CMS bootstrap code. tors “should” be straightforward, but often “easy” bugs have On reset, vital pre-reset machine state is saved. Thus, even already been found with hand-written directed tests, leaving after hard crashes, much state at the time of the crash is difficult-to-debug race conditions and the like. In contrast, available for postmortem analysis, and the debugger allows longer-running system tests less often find races and more downloading of the crash-time state. Then, as debugging often find state bugs that span multiple translations. State proceeds, one can go back to the postmortem dump and an- bugs can sometimes be reproduced in simulation making swer more detailed questions about the crash. them easier to reproduce. Further, system tests can option- A static theorem prover, the “Static Program Analysis ally pause occasionally and “settle” to help isolate failures, Machine” (SPAM), walks a user-supplied predicate over and can record their progress to simplify reconstruction of CMS machine code, ensuring the predicate is true. For ex- the state leading up to failure. That said, there were an un- ample, it is usually an error to write a nonshadowed register, fortunate number of VLIW races and system tests some- abort, then read the register, since it is nonshadowed and times found them. thus contains a value from the future. A predicate to find A traditional problem with hand-written tests is the au- violations is write X ; abort; read X for all nonshadowed thor “knows” certain cases are unimportant and so skips X. A complication is no translations exist statically, so there them and misses bugs. A traditional problem with psuedo- are paths with unknown code. The solution is to annotate random test generators is they generate many “boring” cases entry and exit to dynamically-generated code, including ex- for each interesting case. A technique used with good suc- ception paths, and claim behavior of the as-yet nonexistent cess is biased random number generation. For example, code. rather than testing a case with two arbitrary inputs, test with Performance work also uses many in-house tools. The inputs whose bit pattern is usually mostly ones or mostly fast simulator collects low-level metrics, and hardware has zeros. This allows the test generator author to provide guid- performance counters [CKB01]. Hardware is accurate, but ance towards cases which are likely to be problems, but has only a few counters and has run-to-run variations. Sim- since the inputs are only guided, not firmly constrained, the ulation is less accurate, but collects data as fine-grained as random machinery still tests some cases the author thinks per-instruction, and is repeatable. Fine-grained data is yet are “boring”. another reason the fast simulator was used heavily even long At the time Crusoe was being developed, some industry- after hardware was available. standard tests relied on a human reading a report screen. Performance visualization includes traditional plots of Thus, automation was hard. One part of automation was bulk statistics, but it was quickly apparent detailed behavior

    10

of individual dynamically-generated translations was sig- that does not run on the simulator. This “less than 100%” nificant. A set of tools instrument translator and translations implementation requires some care, but avoids simulating to collect translation-level behavior and also save both tar- tricky corner cases just for CMS boot, yet allows CMS boot get code and the generated translation. Instrumented code code development in the simulation environment. is usually almost as fast as uninstrumented code, yet saves In many situations, CMS works around hardware bugs. enough detail a developer can start with a screen summariz- For example, a pair of symmetrical hardware instructions ing the whole execution, then quickly zoom in to much nar- were implemented asymmetrically. Until hardware was rower “windows” of execution. Although statistical analy- fixed, software simulated the faulty VLIW instruction. Al- sis of bulk data is often important for an overall understand- though simulation was much slower, it allowed CMS to run ing of “why is this slow”, actual diagnosis and repair often on hardware, and reduced the “push” to finish the next tape- depends on data from individual translations. out as soon as possible – thus increasing the number of bugs that could be found, the number of fixes in the next tapeout, 5. Some Development Experiences and thus the rate of progress of each tapeout. Software is also used to work around timing bugs. For Preceding sections describe hardware and software. This example, hardware uses a “cancel” signal shared by most section describes some development experiences, especially functional units. A new functional unit was added without those different than might be expected in conventional suitable timing analysis. If a unit at one end of the wire projects. applied a signal, and the unit at the other end had an in-flight Much of early software development is test-driven. That operation, the in-flight operation missed the signal and the is, the goal is to implement enough to execute the first in- operation was not cancelled. The static compiler and CMS struction of the first test. Once that works, development translator were changed to avoid scheduling operations in moves to the next instruction, even if the first instruction’s the same VLIW instruction if they were at opposite ends of implementation is incomplete and may fail on other tests. the wire. This approach keeps development very focused. Produc- Software changes are also used as a diagnostic tool: tivity relies heavily on the reference simulator, reverse ex- given a hypothesis “the problem is due to X combined with ecution, and the nexus. In a conventional environment, a Y”, software can be changed to avoid that combination. A developer knows only a test has failed, and is responsible variety of diagnostic features were developed and controlled for analyzing why. The nexus, however, reports “register X with flags. In addition, many control flags introduced dur- diverged at tick Y” and stops, showing total state and allow- ing development were left in for diagnostic use. Thus, many ing the developer to back up one instruction and “watch” the diagnostic changes are as simple as changing a few flags. incorrect value being generated. Diagnostic changes may spuriously cause a symptom to go Hardware development is more traditional, but still has away, but if a symptom continues, that shows a hypothesis unusual features. For example, there were three proposals false. Flag changes are also used by people with no CMS for how to implement a particular operation. All would hurt, internals knowledge to work around bugs without needing though in different ways. We dropped the operation and to wait for a fix. Thus, while some bugs are still show- did it all in software, as cheaper overall than any proposed stoppers, other serious problems are discovered and worked hardware solution. A hardware developer smiled broadly – around in just a few minutes, with diagnosis and repair sep- “This is the first project I have worked on where instructions arated from other work. have been removed during development!” Another diagnostic tool is instrumenting CMS. One way Keeping the fast VLIW simulator consistent with real to instrument is debugger scripts run at debugger break- hardware is a potential nightmare, especially since CMS is points. Another is editing CMS. Some diagnostics are suf- built around the fast simulator’s behavior. There could have ficiently useful they are checked in to the code base. Or, been terrible problems, but in practice problems are few and a “framework” may be checked in – for example, certain minor. A big reason is the fast simulator and development bytes of local memory are allocated for logging data about environment are so useful, hardware verification also uses the last N exceptions. The trap code to do the logging is it for development, thus errors are corrected even before a not checked in, as what to log varies, but reserving local suitable verification test exists or hardware implementation memory ensures certain offsets are always the same. of that feature is started. There is always competition for what stays in the code That said, some hardware features appeared in the fast base. On one hand, adding instrumentation is error-prone. simulator late or not at all. For example, the fast simula- For example, one failure we reduced to one of two signa- tor implements enough bootstrap-specific behaviors that a tures that occurred with roughly equal frequency. It turned CMS boot sequence runs on both simulator and hardware, out one signature was due to my errors in adding excep- but it is also possible to write a correct VLIW boot sequence tion logging code. On the other hand, checked-in diagnostic

    11

code makes real code harder to understand, thus introducing few more pages of low memory have “steering” bits, called bugs; and, diagnostics sometimes makes code slower. One A20M, that control reads and writes separately. A typical compromise is a library of code that is not checked in the use is to copy a word from address X to address X – where main code base, but which can be patched in at less effort the read comes from ROM and the write goes to RAM. and with fewer errors than writing it from scratch. This sort of use brings up all sorts of issues. One is what Hardware and software designs changed substantially happens when a single instruction spans a page boundary, during development. For example, an early design of alias part in RAM – and thus translatable – and part in ROM, hardware was difficult to use, even in the original situa- so it must be fetched exactly once each time it is executed. tions for which it was devised. Thus, alias hardware was Our initial conclusion was nobody would ever write code unused when hardware first became available. A different with one instruction in both RAM and MMIO, but doing design was implemented in a later hardware revision, where so must not crash or corrupt CMS. CMS uses #n fetches it “met up” with the CMS implementation which was devel- in the translator and promotes normal-assumed instruction oped in simulation but until then was disabled when running fetch faults to the interpreter. Interpreting is slow, but ROM on hardware. fetches are even slower and are mandatory. Imagine our sur- Most FP instructions are invoked with a single TOS prise to discover OS/2 boot has an instruction that executes value, so early versions of Crusoe used a flat FP regis- from both RAM and video memory! Our guess is RAM ter file and simulated x87 indirection by putting TOS in was exhausted and somebody said “Why not execute a few the context. However, non-FP code is often invoked with instructions from video memory?” It could also have been many TOS values, which caused context mismatches and an accident that was never noticed because it “just works”. duplicate translations. For example, most kernel code is The gated store buffer implements memory store com- invoked with many TOS values. All shipping versions of mit/abort. It has 32 entries, so it might seem CMS can use Crusoe have a hardware TOS value that is added, mod 8, to up to 32 stores between commits. However, a suitably mis- the VLIW instruction’s register numbers to form the VLIW aligned store uses two store buffer entries. Further, a store hardware’s register number. CR0’s TS (task switched) and may implicitly write page table “accessed” and “dirty” bits, EM (emulate math) bits are also checked by x87 FP instruc- while a page-crossing store can write accessed and dirty bits tions; early versions of Crusoe included these in the context, for two pages. (x86 80-bit floating-point stores can touch 3 but shipping versions explicitly load and test the flags as pages; they are implemented with a pair of VLIW 16- and needed. 80-bit stores.) Software changes were pervasive. Most of the world’s Stores that are misaligned or which change page table fast simulator experts worked at Transmeta during Crusoe A and D bits are common enough translations are typically development, but it was a learning experience for all. Much limited to around 28 VLIW stores, including stores in OOLs of CMS was implemented twice – which Brooks would say called by the translation. Thus, a few “unfortunate” stores is a good thing [Bro75]. Some code that shipped after being do not cause overflow. Even so, store buffer overflow is not implemented only once, had a comment saying it needed to rare. Store buffer overflow is handled by retranslating with be rewritten. smaller translations and thus fewer stores between commits. Some learning was about fast simulation; some about the Transmeta’s goal is 100% x86 compatibility. In many x86 target; and some about how applications ran on that tar- cases there is a wide range of “legal” behaviors, and even get. For example, the x86 has several segmentation modes. “legal” differences risk incompatibility for a system that de- “Real” mode supports segments with byte-grain size, but pends on a behavior that is not guaranteed but is nonetheless they must be small. “Protected” mode supports large seg- common. ments but the size must be a multiple of the page size. Dur- One example of “legal but different” is page table “page ing Microsoft Windows boot, a CMS assertion tripped on a accessed” and “page dirty” bits. Most x86 processors write real-mode reference to an oversize segment. The reference them whether or not the instruction completes. Crusoe simulator showed the same reference, yet it ran Microsoft writes them using commit/abort logic, so they are written Windows. It turns out switching to real mode does not al- only if the instruction completes. Crusoe meets the specifi- ter or invalidate sizes too large to have been established in cation, but is different. Would x86 code rely on this subtle real mode. Operating this way is sometimes called “unreal” difference? Crusoe could write them unconditionally, but mode [Aga91]. While not part of the ISA, all x86es support at higher complexity (consider page tables in MMIO) and it. higher execution cost in the common case. We know of no Another education was how RAM and MMIO pages are case where this difference led to problems, but it does reflect interleaved. The simple model is RAM is low addresses, details that, at every step, take time and effort to resolve. and everything else is high addresses. However, a few Even where features agree individually with conven- pages of low memory are dedicated for legacy video, and a tional x86es, it is hard to exactly emulate any one x86. Cru-

    12

soe has a unique combination of feature flags. In principle, ior defined in at least two places. DROOLs (§3) were added a system looks at each flag independently, so the combina- to make a more careful tradeoff between optimization and tion is unimportant. In practice, Microsoft Windows does instruction cache pressure. The many approaches to han- not examine flags individually, but instead looks for com- dling self-modifying code (§3) follow poor performance of binations seen in real processors, and defaults to a minimal simpler approaches. x86 otherwise. Limiting feature combinations helps limit On CPU-bound work, Crusoe performance is compara- user’s exposure to bugs. But it also means that since Crusoe ble to contemporary processors using much more power. was missing one feature, Microsoft Windows was not using On typical work, performance suffers due to various bot- any features until Crusoe systems were made available for tlenecks, including comparatively poor performance of the Microsoft to test that specific combination. memory subsystem, and serialization of DMA and compu- Even where Crusoe is bit-for-bit compatible, the timing tation (§2). Even where long-term average performance is differs. Since there are many x86 implementations, most good, short-term slowness is sometimes visible to users. time-sensitive code uses wallclock time rather than instruc- Memory performance suffers more when interpretation or tion counts. One Linux Ethernet driver failed, however, be- translation is frequent, since x86 instructions are read as cause it self-timed a loop; the initial timing run was inter- data and so increase data cache pressure. During transla- preted, and thus slow; and normal execution was translated, tion, VLIW instructions are first written to the data cache and thus fast. Similarly, translator pauses caused a soft mo- then flushed to memory, then read to the instruction cache. dem to fail during real-time negotiation. The second try Further hardware changes could have boosted Crusoe’s always succeeded, as the code was now compiled. performance, but would have required major modifications A problem reported with early dynamic translators is and thus greatly delayed delivery. Efficeon fixes many of user-visible jerkiness during compilation. Although Crusoe Crusoe’s performance problems, including better memory also has compilation pauses, and although Crusoe’s opti- performance, and overlapped compute and I/O. Efficeon has mizing compiler is more expensive, the higher performance much higher overall performance, even factoring in changes of modern processors – 1GHz vs. 10MHz – and Crusoe’s in transistor size and speed. interleaved interpretation makes the UI smooth, even when “x86 compatible” includes both the instruction set and overall execution speed is slowed. the PC platform. An early decision was to use the same Overall execution speed is slowest when translation and RAM chips for both CMS and target memory. CMS boot- interpretation rates are high and translation execution rates strap code configures memory for CMS, then CMS runs the are low, usually OS and application startup. Tuning can BIOS, which configures memory. Thus, some memory con- improve worst-case performance. For example, interpret- figuration done by the BIOS needs to be skipped or ignored. ing more and translating less can avoid translation of low- The BIOS still has some memory “knobs” and is allowed reuse code. However, tuning for one case tends to hurt to use those where doing so does not misconfigure CMS. others. For example, one Microsoft Windows certification As described above, one development strategy is com- grade requires boot in a minute or less. Crusoe is tuned to paring CMS against a reference simulator. Another is com- boot in under a minute, even though the tuning hurts per- paring two CMSes, running with different configuration pa- formance on some applications, including some important rameters. CMS on the fast VLIW simulator is faster than the benchmarks. reference simulator, and the nexus stops on any divergence Crusoe performance improved during development due between the two simulators, no matter which one made the to both VLIW and CMS changes. One VLIW change is error. Thus, CMS vs. CMS runs a suite of configurations limited support for segmentation (§2); with better workload more quickly than running against the reference. It is, how- analysis, it might have been added earlier. A pipelined indi- ever, no substitute for execution against a reference simula- rect branch (§2) and limited support for x87 FP simulation tor, as CMS vs. CMS misses bugs that appear in both. (§5) followed several iterations of CMS development and Hardware emulation was planned from the start. FPGA workload analysis. The original VLIW included alias hard- emulators have limited gate counts, but Crusoe is simple ware, but it was changed due to problems with the original enough to emulate the whole core. The emulator is in prin- design (§5). ciple built from the same sources as real hardware, but in CMS performance changes continued through develop- practice it is a lot of work to excise the core and to build ment. The original design was based on translation with- an emulator framework to run it. Several emulator systems out interpretation, with single-instruction translations as were purchased, one because an earlier vendor was acquired needed. Translation was more expensive than expected, and that emulator line was abandoned. The emulation effort and an interpreter collects profile data that significantly im- was then restarted on a new system. Also, emulation was a proves subsequent translation. Interpretation yields better second-tier priority, and it was only after Crusoe shipped performance, but means each x86 instruction has its behav- there was a person dedicated to emulation. Thus, the emu-

    13

lator finally ran Crusoe only after hardware shipped, and it after almost 24 hours, the translation was flushed and the found only a few bugs. However, the effort was worthwhile code generator ran again, this time with interrupts enabled. as it made emulation available early in Efficeon develop- A “zero-cycle” interrupt checker was added to SPAM. ment, where it found difficult and critical bugs. A third bug appeared during testing of an isolated Development was helped greatly by adding debugger change. Ad-hoc testing repeatedly led to a hard crash during features aggressively. Adding them as needed is too late! launch of an ordinary program. Study showed the failure You want them already working and debugged when you was after a triple-nested nucleus fault that was not related are staring at an error, especially errors which are time- to the change or application, but happened when starting consuming to reproduce, or which appear erratically. For the test in a certain time window after OS boot. Most triple example, downloading cache contents and tags was added faults abort the current translation. This case resumed the before it was needed. One hard-to-reproduce failure was faulting instruction, and an error in triple-nested fault han- positively identified as a hardware bug by dumping and ex- dling led to corrupted target state and a crash. Two people amining cache tags, noting no sequence of valid instructions studying the failure found three distinct cut-and-paste errors could give rise to the observed state, and noting the cache in 20 lines of assembly that had been stable for months. One download code was simple and regular, thus unlikely to person found one error by stepping with the debugger and have bugs. This was a key to isolating the failure. We never noting a value saved was different than the value restored – saw the “must be hardware” corruption again, so had we yes, the debugger can single-step through nested fault han- added cache dumping only as needed, it might have taken dlers. The other person inspected the code and found two weeks more to encounter another definitive case. more errors. A few debugging stories may be of interest. One bug These last two bugs might have been found by inspec- caused crashes roughly once a day per machine. A week tion. Software inspection has been studied widely and con- of experimenting showed a corner case that failed within 5 sistently beats other strategies for finding bugs at the low- minutes about 30% of the time. Crash analysis suggested est cost. However, inspection is not used heavily at Trans- the failure was related to an exception, but the failure case meta, in part because it is not directly automatable. But was during program start when exceptions were frequent. despite the great success of automated testing, various “in- Unfortunately, we did not have application or OS sources, spectable” bugs still survived long enough to demand ar- so could not readily study or instrument failing target code. duous debugging. Programmers often resist classic inspec- We concluded it was a hardware bug, most likely in one of tion due to meetings and because it gates and thus delays two units, but studying the circuits showed no errors. Fur- checkin. However, inspection via e-mail is now common ther study showed a particular register had a value equal to and has shown good results; and much as debug testing af- another register – with no copy between them, but always ter checkin is common practice, inspection after checkin is a restarted chain pull when duplication occurred. Further also reasonable. hardware study showed the two units treated a shared bus It is always fun to demonstrate virtualization. signal differently: in some cases there was a one-cycle win- Shade [CK95] was once used to run nested Shades. dow where one unit was reading the signal, but the other For example, a SPARC running a Shade that was running was not driving it! There was only slow progress between Shade that was running Shade that was running Shade initial discovery of the 5-minute test case and the final dis- that was running a “Hello world” program (slowly). At covery of the mis-copied value. That discovery led within Transmeta, various similar configurations were run using 60 minutes to positive identification of the bug’s root cause. CMS and the fast VLIW simulator. For example, an x86 Another error caused failures about 15 minutes before running the fast VLIW simulator running CMS running the the end of a 24-hour stress test. Unfortunately, no “fast” fast VLIW simulator running CMS booting an OS (slowly). case was discovered. Application and OS sources were Or, real VLIW hardware running CMS running the fast not available. After about two weeks of study – about a simulator, running CMS, booting an OS (also slowly). dozen runs per machine – evidence pointed to CMS code that seemed common to all failures. Inspection revealed a 6. Conclusion bug where interrupts were supposed to be disabled across a sequence, but the disable was handed off between two inter- Transmeta’s Crusoe seamlessly runs nearly all workloads, rupt disable mechanisms, and a bug reenabled interrupts be- and demonstrates a CPU based on dynamic translation is tween two instructions. A pending interrupt aborted execu- practical. Crusoe’s hardware is small and simple, using tion to deliver the interrupt, leaving inconsistent state. Why software for corner cases. This combination allowed a small did it fail only after 24 hours? The race was in a special- team to produce a reliable x86-compatible CPU in just a few purpose code generator; the first time it ran was during OS years. This paper briefly summarizes some of the designs, boot when interrupts were also disabled at the x86 level; experiences, and lessons of development.

    14

Acknowledgments [CK95] R. Cmelik, D. Keppel, Shade: a fast instruction-set sim- ulator for execution profiling. Chapter 1, “Fast simulation of Thanks to Bob Cmelik, Ron Maeder, and Stephen Russell computer architectures”, T. Conte & C. Gimarc eds. Kluwer, for reviewing and improving earlier drafts of this paper and 1995. to Bob Cmelik for research assistance. Thanks also to Jim [CDS03] B. Coon, G. D’Souza, P. Serris. Pipeline replay support Hunt for reviewing a near-final draft. for multi-cycle operations wherein all VLIW instructions are flushed upon detection of a multi-cycle atom operation in a References VLIW instruction. U.S. Pat. 6,604,188, issued 2003. [CKB01] B. Coon, D. Keppel, C. Price. Programmable event [Aga91] R. K. Agarwal. 80x86 architecture & programming, Vol- counter system. WIPO #WO 01/27873, issued 2001. Also as ume II: architecture reference. Prentice Hall, 1991. U.S. Pat. 6,356,615, issued 2002. [AK04] H. P. Anvin, D. Keppel. Method and apparatus for han- [CK04] B. Coon, D. Keppel. Use of enable bits to control execu- dling nested faults. U.S. Pat. 6,829,719, issued 2004. tion of selected instructions. U.S. Pat. 6,738,892, issued 2004. [BAB+03] J. Banning, H. P. Anvin, R. Bedichek, G. Rozas, A. [DGB+03] J. Dehnert, B. Grant, J. Banning, R. Johnson, T. Shaw, L. Torvalds, J. Wilson. Translation consistency check- Kistler, A. Klaiber, J. Mattson. The Transmeta code morphing ing for modified target instructions by comparing to original software: using speculation, recovery, and adaptive retransla- copy. U.S. Pat. 6,594,821, issued 2003. tion to address real-life challenges. CGO 2003, pg. 15-24. [BAG+01] J. Banning, H. P. Anvin, B. Gribstad, D. Keppel, A. [DS84] L. P. Deutsch, A. M. Schiffman, Efficient implementation Klaiber, P. Serris. Fine grain translation discrimination. WIPO of the Smalltalk-80 system. POPL 1984, pg. 297–302. #WO 01/027743, issued 2001. Also as U.S. Pat. 6,363,336, [KF03] M. Kanellos, M. J. Foley. Transmeta to help AMD push issued 2002. into servers. CNET News.com 2001/01/03. [BCH03] J. Banning, B. Coon, E. Hao. Link pipe system for stor- [KCW96] E. Kelly, R. Cmelik, M. Wing. Memory controller for age and retrieval of sequences of branch addresses. U.S. Pat. a microprocessor for detecting a failure of speculation on the 6,640,297, issued 2003. physical nature of a component being addressed. U.S. Pat. [BCT+03] J. Banning, B. Coon, L. Torvalds, B. Choy, M. Wing, 5,832,205, issued 1998. P. Gainer. Fast look-up of indirect branch destination in a dy- [KCW00] E. Kelly, R. Cmelik, M. Wing. Translated memory pro- namic translation system. 6,615,300, issued 2003. tection apparatus for an advanced microprocessor. U.S. Pat. [BKK+03] P. Boyle, D. Keppel, A. Klaiber, E. Kelly. Software 6,199,152, Issued March 2001. direct memory access. U.S. Pat. 6,668,287, issued 2003. [KW99] E. Kelly, M. Wing. Host microprocessor with appara- [BKB05] R. Bedichek, D. Keppel, J. Banning. Interpage prologue tus for temporarily holding target processor state. U.S. Pat. to protect virtual address mappings. U.S. Pat. 6,845,353, is- 5,958,061, issued 1999. sued 2005. [KCB01] D. Keppel, R. Cmelik, R. Bedichek. Method and appa- [Bro75] F. Brooks. The mythical man-month. Addison-Wesley, ratus for maintaining context while executing translated in- 1975. structions. WIPO #WO 01/27741, issued 2001. Also as U.S. Pat. 6,415,379, issued 2002. [CDE+00] R. Cmelik, D. Ditzel, E. Kelly, C. Hunter, D. Laird, [Kep09] D. Keppel. How to detect self-modifying code during M. Wing, G. Zyner. Combining hardware and software to pro- instruction-set simulation. 2009 workshop on architectural vide an improved microprocessor. U.S. Pat. 6,031,992, issued and microarchitectural support for binary translation, 36th 2000. annual international symposium on computer architecture. [Cla91] D. W. Clark. Large-scale hardware simulation: model- Austin, TX. ing and verification strategies. Chapter 9, “CMU computer [KSD03] D. Keppel, P. Serris, G. D’Souza. Check instruction and science: a 25th anniversary commemorative”, R. Rashid, ed. method. U.S. Pat. 6,513,110, issued 2003. ACM Press/Addison-Wesley, 1991, pp. 219-234 [KBK99] A. Klaiber, R. Bedichek, D. Keppel. Method and ap- [CK93] R. Cmelik, D. Keppel, Shade: a fast instruction-set simu- paratus for correcting errors in computer systems. U.S. Pat. lator for execution profiling. Sun Microsystems Laboratories, 5,905,855, issued 1999. Inc. TR SMLI 93-12; also University of Washington Depart- ment of Computer Science & Engineering TR 93-06-06. [Kla00] A. Klaiber. The technology behind Crusoe pro- cessors, 2001/01. From archive.org as of 2009/03, for [CK94] R. Cmelik, D. Keppel, Shade: a fast instruction-set simu- www.transmeta.com/crusoe/download/pdf/crusoetechwp.pdf lator for execution profiling, SIGMETRICS 1994. as of 2001/06.

 15

[HAC+06] S. Halepete, H. P. Anvin, Z. Chen, G. D’Souza, M. Fleischmann, K. Klayman, T. Lawrence, A. Read. Adaptive Power Control. U.S. Pat. 7,100,061, issued 2006.

[Loc87] B. Locanthi, Fast BitBlt with asm() and CPP. European Unix Users Group Conference, 1987/09.

[May87] C. May. Mimic: a fast System/370 simulator. SIGPLAN ’87 Symposium on Interpreters and Interpretive Techniques. 1987/06.

[RHK07] A. Read, S. Halepete, K Klayman. Saving power when in or transitioning to a static mode of a processor. U.S. Pat. 7,260,731, issued 2007.

  [RDD+04] G. Rozas, D. Dunn, D. Dobrikin, A. Klaiber, D.
Nelsen. Method and apparatus for emulating a floating point
stack in a translation process. U.S. Pat. 6,725,361, issued
2004.

[RDP06] G. Rozas, G. D’Souza, C. Price, P. Serris. Method and apparatus for enhancing scheduling in an advanced micropro- cessor U.S. Pat. 7,089,404, issued 2006.

[Shi97] A. Shilov, “Transmeta quits        microprocessor
business”,    Xibt Laboratories, 2007/07/02,         from
http://www.xbitlabs.com/news/cpu/display/20070207230938.html
as of 2009/05.

[TA05] L. Torvalds, H. P. Anvin. Method of determining a mode of code generation. U.S. Pat. 6,880,152, issued 2005.

[TK01] L. Torvalds, D. Keppel. Controlling instruction trans- lation using dynamic feedback. WIPO #WO 01/27767 A1, issued 2001. Also as “System for using rate of exception event generation during execution of translated instructions to control optimization of the translated instruction”. U.S. Pat. 6,714,904, issued 2004.

[WD00] M. Wing, G. D’Souza. Gated store buffer for an ad-
vanced microprocessor. U.S. Pat. 6,011,908, issued 2000.

[WK99] M. Wing, E. Kelly. Method and apparatus for alias-
ing memory data in an advanced microprocessor. U.S. Pat.
5,926,832, issued 1996.










16