No patents on CC elim in emulators

Doug Kwan (ctkwan@csd.hku.hk) asks,
> Does anyone know if there is a patent on the use of dataflow
> analysis to eliminate unnecessary condition code evaluation in
> instruction set simulators?


No, there are no (valid) patents on the use of static dataflow analysis
techniques to eliminate unneeded condition-code computations in
translations from object code. In July 1989, Hunter Systems Software
of Mountain View, California applied for a patent (appl
PCT/US89/02994) for the techniques they used in their XDOS 8086
emulator for Unix systems, but there's lots of prior art to invalidate
that patent. XDOS was described in the article "DOS at RISC" in the
November 1989 issue of BYTE. Hunter Systems has since been acquired
by Multiport Inc of Mountain View.


Hewlett Packard used and published all these object-code-translation
techniques earlier, in their emulation of HP3000 stack machine code on
their commercial version of their PA-RISC machines. They publicly
described these nicely in the Dec 1987 Hewlett-Packard Journal article
"HP 3000 Emulation on HP Precision Architecture Computers". They
apparently did not seek any patent on this; this was in the period
when software-based patent applications were routinely rejected.


If you cannot locate that HP Journal issue, you can read about a very
similar implementation we did at Tandem Computers, described in my
article "Migrating a CISC Computer Family onto RISC via Object Code
Translation" by K. Andrews and D. Sand, in the 1992 ASPLOS-V
conference (SIPLAN Notices Vol 27, Num 9, Sept 1992, also printed as
SIGARCH Comp. Arch News Vol 20, Oct 1992 and SIGOPS Op Systems Review
Vol 26, Oct 1992). An even more available article is "Binary
Translation" by R.Sites et al in Feb 1993 Comm ACM, describing the
very similar implementation by DEC for VAX-->Alpha migration.


HP could not have patented CC elimination anyhow. The article
"Automatic Assembler Source Translation from the Z80 to the MC6809" by
M.F.Smith and B.E.Luff in the April 1984 issue of IEEE Computer,
describes a macro-like instruction-by-instruction translation from Z80
opcode and register semantics to MC6809 opcodes and registers. They
describe an extension they did not implement, of using context to
remove unnecessary "flag simulations". They in turn refer to the
article "Upward Migration -- Part 1: Translators" by R. Taylor and P.
Lemmons in the June 1982 issue of Byte, Vol 7, Num. 6, for the idea of
use context to reduce translation overheads. I haven't dredged up
that article to see what it actually said.


Somewhat later, at about the time HP was completing their work,
there were two other public descriptions of these techniques:


    "Emulating a Complex Instruction Set Computer with a Reduced
      Instruction Set Computer" by K.J.McNeley and V.M.Milutinovic,
      in Feb 1987 issue of IEEE Micro.


    "MIMIC: A Fast System/370 Simulator" by C.May, in SIGPLAN 1987
      Symposium on Interpreters and Interpretive Techniques, June 1987.


I think it is likely that most of these techniques were invented,
used, and then forgotten back in the 60's, when various emulation
techniques were invented to move programs from 1401 and 7090-era
machines onto System/360 etc.


In the early to mid 1970's, there was work at Univ California at
Irvine, in porting programs from one minicomputer to another at the
assembly language level. Greg Hopwood (?) wrote a UCI PhD thesis on
it, but I don't have an exact reference. I believe it did some
trivial local optimizations. The only significant difference between
that and the recent static-translation work by HP, Hunter, Tandem,
Echo Logic, and DEC is that Hopwood used textual assembly input rather
than binary machine code, and didn't have a way to dynamically handle
unknown branch paths.


The other interesting idea, of doing simulators by caching dynamic
translations of code fragments, goes way back too; early 70's at least.


Finally, there have been no patent claims against Tandem in this
area, and probably none against HP or DEC.


              Duane Sand, Tandem Computers
              sand_duane@tandem.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.