Re: Help needed: Code generation for CASE/SWITCH statements

|William A. Barath wrote:
|> How so? If the code is called repeatedly (iterative model, one which
|> is _worth_ optimising) then the CPU's instruction cache is very likely
|> to keep all the relevant data cached, and branch instructions can be
|> executed in 1 clock or less.


On 17 Dec 1997, Raymond Hayes wrote:
|The problem isn't the cache, it's predicting the branch. Assuming
|everything is in the caches, if the branch can't be predicted or is
|mispredicted, the pipe needs to be flushed and ifetch needs to be
|redirected.


Pipeline flush is generally irrelevant in a situation where program
flow is concerned, because the pipeline would have been stalled to an
empty state pending resolution of the next fetch address. The
prediction at least had a chance of keeping all the pipelines full
(superscalar processor: the original reply was from someone stressing
'*modern* *high-speed*' targets.) On the other hand, a table lookup
stalls all the pipelines 100 percent of the time- while the data load
hazard affects the program counter (jump insn.) the fetch address is
invalid and hence no instructions can be loaded into the pipeline(s).


The cache concern is more important than you might think. Most
operating systems are now multitasking and running multithreaded
programs. 1 Meg of cache is fine for a large number of jumptables
under DOS, but on a system with 50+ users logged in and over one
hundred tasks running I wouldn't bet on the chances of sparse tables
staying cached from one iteration to the next. Note that I am saying
sparse tables. I've never argued against the value of lookup tables
for selecting between dense case nodes.


Wil Barath, aka WseM : "I feel as though I see my pen to write"
Author of VPM, EDITPLN, and other VGA Planets support programs
--

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