nathan binkert wrote: >> I'd still really encourage you to work on cutting out the middleman >> and find a way to go straight from raw bytes to StaticInsts via a >> cache. I really don't see any long-term benefit to doing this in two >> stages. I agree that we don't want a proliferation of code paths or >> scenarios, so once we find a way to make it work for x86 the next step >> is to see how we can take the same approach and streamline it to work >> efficiently for the other ISAs, then use that to completely replace >> the current ExtMachInst->StaticInst cache. >> > > Random thought: one way to implement a caching mechanism for a > variable length instruction set is to implement it as a radix tree. > If each level of the tree were for a one byte word (yes, that is a > pretty high branching factor, but if we just implemented each node as > an array of 256 pointers, it's actually not bad at all in terms of > traversal time), then as soon as you get to a terminal node, you > should hit a valid instruction. For fixed length instructions, you'd > always hit a leaf at the same level, but for an ISA like x86, you > wouldn't. This of course only works if it is never ambiguous whether > or not there are more bytes in your instruction given a certain > prefix. I can't imagine that not being the case in any ISA. > > Make sense? > > Nate > _______________________________________________ > m5-dev mailing list > [email protected] > http://m5sim.org/mailman/listinfo/m5-dev > What do you mean by "given a certain prefix"? X86's encoding is fairly amorphous, and it's not always possible to tell early on how big an instruction will be. It's possible in general of course, so it depends on what you actually mean there. Would chasing through linked lists like that slow things down a lot with memory dependencies, caching, etc.? We would have to find some way of keeping the bytes around at least to reprocess with the predecoder on a miss, and it might be easiest to do that byte by byte since the alignment is arbitrary. The way I hash the ExtMachInst right now is just to pack all the fields together into same lengthed chunks, xor those, and then hash the result, and that may just not be a very good hash function. By putting things into a tree we might avoid the entire issue of wonky roll-your-own hash functions. All in all I'm not sure the tree idea would work, but it's definitely at least good to consider.
Gabe _______________________________________________ m5-dev mailing list [email protected] http://m5sim.org/mailman/listinfo/m5-dev
