Closed Bug 498807 Opened 15 years ago Closed 14 years ago

TM: make insGuard() less confusing

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Platform:
x86
Linux
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED WONTFIX

People

(Reporter: n.nethercote, Assigned: n.nethercote)

References

Details

Attachments

(1 file)

patch splitting insGuard() into three
17.81 KB, patch
edwsmith
: review+
Details | Diff | Splinter Review 
jstracer.cpp has this code in TraceRecorder::emitNativeCall, around line 7808:

        // Tell nanojit not to discard or defer stack writes before this call.
        LIns* guardRec = createGuardRecord(exit);
        lir->insGuard(LIR_xbarrier, guardRec, guardRec);

'guardRec' is a LIR_skip instruction whose payload contains a GuardRecord.  It's used as the 3rd arg to insGuard(), which makes sense, but also as the second (cond) arg.

I see etwo possibilities:
- It's a bug.
- It's not a bug, but it should have a comment explaining why it is able to be different to pretty much all other insGuard() calls, which all take boolean expressions or integer expressions as their 2nd arg.  (If the argument doesn't matter then something like NULL, along with a comment, would be better.)
Also, TraceRecorder::createGuardRecord() has this comment:

     * Creates an instruction whose payload is a GuardRecord for the given exit.
     * The instruction is suitable for use as the final argument of a single
     * call to LirBuffer::insGuard; do not reuse the returned value.

which lends more weight to the idea that it's a bug.
Actually(In reply to comment #1)
> Also, TraceRecorder::createGuardRecord() has this comment:
> 
>      * Creates an instruction whose payload is a GuardRecord for the given
> exit.
>      * The instruction is suitable for use as the final argument of a single
>      * call to LirBuffer::insGuard; do not reuse the returned value.
> 
> which lends more weight to the idea that it's a bug.

Actually, that comment used to be there but was removed recently.  Hmm.
(In reply to comment #2)
>
> Actually, that comment used to be there but was removed recently.  Hmm.

Argh, it wasn't removed;  it's present on the declaration in jstracer.h, I was incorrectly looking at the definition in jstracer.cpp when I thought that.  Ignore comment #2.
The comment is a red herring; I added it by way of explaining what the function did, but the behavior itself predated that checkin, and I was more concerned with warding off the behavior in error that the corresponding push fixed than about determining exactly what that line's function was.
The first argument of x, xbarrier, loop is not used. It can't be NULL. We usually set it to imm(1). Setting it to the guard record itself is pretty poor taste, but otherwise fairly inconsequential.
Why does it take two arguments at all, then?
Probably to be able to treat xt/xf and x/loop/xbarrier the same in filters.
(In reply to comment #5)
> The first argument of x, xbarrier, loop is not used. It can't be NULL. We
> usually set it to imm(1). Setting it to the guard record itself is pretty poor
> taste, but otherwise fairly inconsequential.

If it can't be NULL, then it must be used somehow -- can you explain how?  I find the chains of insGuard() calls confusing.  (Actually, in the patch for bug 495734 I did set it to 0 with no noticeable effect.)

As for setting the cond for x/xbarrier/loop to imm(1) -- doesn't that create an unnecessary instruction in the buffer?  I think it would be better to require that this arg be NULL for x/xbarrier/loop, and check this is so.  Or something like that;  having the arg just be ignored in some cases makes me nervous.
I am in no way defending the way the code was originally written. I am just trying to report from memory why we had to insert imm(1) there and why I think tamarin's original code was written the way it was. I definitively remember running into a null pointer bug if we passed NULL there. The source of that bug might be gone by now. I am not arguing to stick with imm(1). I am just saying be very careful removing it. It used to be there for a reason.
Blocks: 495158
Summary: TM: GuardRecord used as a condition, bug? → TM: make insGuard() less confusing
To clarify how insGuard() works:

- for xt/xf, the 2nd arg is the condition, the 3rd is the GuardRecord
- for loop/xbarrier/x, likewise, but the condition is always insImm(1)
- for xtbl, the 2nd arg is the "diff" (something to do with the jump table),
  the 3rd is the GuardRecord

Thus there are three distinct cases that insGuard() is covering.

In this patch I split it into three:
- insCondGuard()            // like insGuard()
- insUnCondGuard()          // lacks the condition
- insSwitchGuard()          // lacks the opcode, because it's always xtbl

In terms of the representation, they all end up calling ins2();  for unconditional guards the first operand gets set to NULL, but it's never 
inspected.  I'll change this to avoid the wasted words once variable-width LIR
(bug 492866) is implemented, it'll be easier then.

With respect to comment #7, as it happens the filters that implement
insGuard() (in class ExprFilter and class CseFilter) only modify xt/xf, all the other guards passed through unchanged.  So I was able to change those insGuard() functions simply to insCondGuard();  for insUncondGuard() and insSwitchGuard() the defaults (which do nothing) are fine.

I also fixed the operand count for xbarrier in LIRopcode.tbl;  it should be
0 like LIR_loop and LIR_x.  This partly fixes bug 495158 but it seemed
suitable to include here.

The main advantage of the change is that things are much clearer.  It also
saves a little bit of space by avoiding all the insImm(1) instructions for
unconditional guards -- for trace-test.js the number of calls to makeRoom()
(which is close to the number of LIR insns) dropped from 810,210 to 805,994.
That's about 0.5% which isn't a lot but better than nothing.
Assignee: general → nnethercote
Status: NEW → ASSIGNED
Attachment #383843 - Flags: review?(gal)
Blocks: 495734
Gal: ping?

Actually, after talking to Julian about this I realised that "guard" is entirely the wrong word for all these things.  A guard is a boolean expression controlling whether something gets executed (eg. see http://en.wikipedia.org/wiki/Guard_(computing)).  So what I've called "CondGuard" matches that meaning, but UncondGuard and SwitchGuard do not.

Really, x/xt/xf/xtbl are kinds of exits, loop is sort of an exit (albeit to the start of the same block, I think?) and xbarrier is something else again (which raises another question:  should xbarrier have a GuardRecord?).

Furthermore, I wonder what isGuard() means and how it is used... I suspect it's used to check "does state needs to be flushed here?"

All of which suggests a possible new naming scheme:

- CondGuard   -> CondExit
- UncondGuard -> UncondExit
- SwitchGuard -> Switch
- isGuard()   -> requiresFlush()

With this naming scheme there isn't a single word to cover all six instructions, but maybe that's not a bad thing.

Thoughts?  Some of you might be thinking "pedantry!" but I figure grouping several things under a name that incorrectly describes them is a recipe for confusion;  it's certainly been confusing for me.
Heh.

"Pedantry" is not the only issue at work; history and some technical details figure in. It turns out we you're missing a distinction still. There is an exit *instruction* -- xt, xf, x, xtbl -- and then there is an exit *path*. The exit instruction (what we're currently calling the "guard") is translated to a jump to the exit path, and this jump can be patched later to be a jump to another fragment if the tree gets extended. The exit *path* -- the part the exit instruction jumps to initially -- is the code that "definitely exits the trace", flushes writes and whatnot, and it is emitted off the main trace.

So we *used* to call both the exit path and the xt/xf/x/xtbl jump instruction "an exit", and this was the source of previous confusion. After much pedantic deliberation in a former bug, I whined enough and someone (I believe Waldo?) landed a patch untangling the terminology to its current state, where the condition, the jump instruction and the exit path at least all have independent, short, punchy names that can be used as stems in variables in the code: "cond", "guard" and "exit".

I agree that "guard" in the CSP-guarded-receive / ML-and-Haskell-guarded-pattern-match sense most likely familiar is the boolean expression. But to make this argument airtight, you need to find a couple nice, short, distinct words for the jump-part and the extended-code-part of the exit. Exits have two parts.

("Exit" and "epilogue" spring to mind, but maybe there's something sharper sounding? It would be good to stick with a word that retains its meaning *after* the jump is patched to no longer mean "exit the trace", but rather branch to a sub-tree. And note that there is a family of LIR_j* instructions that have already gobbled up the word "jump". Sigh.)
I also have found the current terminology confusing.

> I agree that "guard" in the CSP-guarded-receive /
> ML-and-Haskell-guarded-pattern-match sense most likely familiar [...]

Never mind ML and Haskell.  It's more important to be consistent with
terminology in the compiler literature to do with trace scheduling, from
the wonderful world of VLIWs.

 Current      Suggested           What it is
 cond         guard               the condition determining whether to exit
 guard        exit                the actual exit branch
 exit         compensation code   insns that the exit branches to

I'm not sure about the first two.  But certainly the use of "compensation
code" to be the block holding off-trace instructions and branch fixup stuff
(sp adjustments etc) is well established in the literature.

So perhaps "guard", "exit" and "comp" ?

There's a nice presentation introducing the trace scheduling idea at
http://altair.snu.ac.kr/newhome/kr/course/advanced-compiler/2006/Hyperblock%20Scheduling.ppt
You can see some uses of the terms "exit" and "compensation code" in it.
Hmm, "comp" isn't very suggestive of what it's for.  Perhaps "link"
or "linkblock" ?
As a further distinction, we call exit points in the native code guards, and points in the interpreter bytecode stream we return to side exits. Several guards can point to the same side exits.

I agree that some of the terminology is a bit unique and not necessarily completely inline with the literature, what is really the value in completely changing the established nanojit terminology? It might make nanojit slightly more accessible to readers who have never worked for it before, but it will require a fair amount of code reshuffling and renaming on our end, and will cause some initial confusion for existing users. I am a bit on the fence whether such a massive renaming for the sake of renaming is worth it. Nicely documenting and defining terms might be the less invasive approach, imo.
Attachment #383843 - Flags: review?(gal) → review?(edwsmith)
Comment on attachment 383843 [details] [diff] [review]
patch splitting insGuard() into three

To be honest, I don't much like this change because it increases the amount of filter methods a filter has to implement. Many filters do relatively similar things to all guards (i.e. look at the guard record). This leads to some code duplication in the filter, and makes it easy to forget about one of the cases. I agree the uniform interface has its drawbacks with the unused arguments and what not, but its there and it works and more documentation and asserts might do the trick just as well.

In Hotpath we used multi-level dispatch to address this problem. The default implementation of insCondGuard defers to insGuard which defers to ins(). That way one can pick what level of abstraction to overwrite. However, the constant dispatching around is pretty slow and I wouldn't want to use it here.

I am not going to deny review here because I wouldn't really drop dead if we end up doing this change, but I could live without it. Deferring to Ed for his opinion.
> (From update of attachment 383843 [details] [diff] [review])
> To be honest, I don't much like this change because it increases the amount of
> filter methods a filter has to implement. Many filters do relatively similar
> things to all guards (i.e. look at the guard record).

Can you give an example of these "many filters"?  I see four filters: SoftFloatFilter, FuncFilter, CseFilter and ExprFilter.  The first two don't touch guards and so are unaffected.  For the latter two, in both cases insGuard() was converted to insCondGuard().  There is no code duplication in those two filters, but they are easier to understand because you don't have to work out which subsets of guards they cover.

There's also the space saving to be gained by avoiding the unnecessary argument on the UncondGuards -- I thought you would have liked that.
As indicated above, there are some valid arguments to be made for the split. However, looking at the overall design of the filter base class, it clearly aims for minimality:

        virtual LInsp ins0(LOpcode v) {
        virtual LInsp ins1(LOpcode v, LIns* a) {
        virtual LInsp ins2(LOpcode v, LIns* a, LIns* b) {
        virtual LInsp insGuard(LOpcode v, LIns *c, LIns *x) {
        virtual LInsp insBranch(LOpcode v, LInsp condition, LInsp to) {
        virtual LInsp insParam(int32_t arg, int32_t kind) {
        virtual LInsp insImm(int32_t imm) {
        virtual LInsp insImmq(uint64_t imm) {
        virtual LInsp insLoad(LOpcode op, LIns* base, LIns* d) {
        virtual LInsp insStorei(LIns* value, LIns* base, int32_t d) {
        virtual LInsp insCall(const CallInfo *call, LInsp args[]) {
        virtual LInsp insAlloc(int32_t size) {
        virtual LInsp insSkip(size_t size) {

I simply don't think that splitting up guards into individual virtual methods fits in here, nor do I see a really strongly needed. We don't have insAdd and insSub either, just ins2. Yet I don't see a proposal to add 128 additional virtual methods to make sure nobody accidentally uses ins2(LIR_add). We solve that issue with a bunch of asserts, and some documentation.

Again, I am not strongly opposed, just not convinced this change really gets us much. Its a valid alternative view point, which is about as good or bad as the previous design, which different strength and weaknesses.

We have a bunch of convenience functions in the same class, btw, which are not part of the interface (ins_chose, ins_eq0, etc). If you feel strongly about hiding the extra NULL arguments, maybe that would work?
(In reply to comment #18)
> 
> I simply don't think that splitting up guards into individual virtual methods
> fits in here, nor do I see a really strongly needed. We don't have insAdd and
> insSub either, just ins2.

LIR_add and LIR_sub have the same number of arguments, the arguments have the same types, the arguments have the same meanings, and the instruction layout in memory is identical.  That is not true (or need not be true, in the layout case) for the 6 guard kinds, as comment 10 states.

The patch slightly simplifies ExprFilter and CseFilter, avoids some dead arguments, avoids potential confusion caused by grouping together non-similar things, allows for more compact representation of some instructions, and avoids the need for unused imm(1) instructions.  The cost is two very simple extra methods in LirWriter, LirBufWriter, and VerboseWriter.

Anyway, we're clearly on different wavelengths here, so let's see what Ed (and anyone else) thinks.

On the terminology issue, ideally I'd like something like comment 13, but I can see that this could cause TM vs. Tamarin difficulties.  So I'll be happy to stick with the {Uncond,Cond,Switch}Guard terminology, plus add a few explanatory comments.
Comment on attachment 383843 [details] [diff] [review]
patch splitting insGuard() into three

Tamarin doesn't use guards (currently) so i don't know if I'm qualified to be the tiebreaker here.

however, it does use branches and the kinds of branches exactly match the kinds of guards.

jump, branch, and switch each have different concerns, just like the guard equivalents.

the strongest argument against this patch would be if we had filters that treated all 3 flavors (uncond, cond, switch) uniformly... and i don't think we do.

so, the extra methods eliminate branching in the previously-single insGuard function.

would a similar patch make sense for insBranch()?  if so, it backs up my R+.  if not, lets drill into why branches and guards would be treated differently.
Attachment #383843 - Flags: review?(edwsmith) → review+
(In reply to comment #20)
> 
> the strongest argument against this patch would be if we had filters that
> treated all 3 flavors (uncond, cond, switch) uniformly... and i don't think we
> do.

That's right;  all the filters I'm aware of only do something interesting in the cond case, and the uncond and switch cases are never touched.

> so, the extra methods eliminate branching in the previously-single insGuard
> function.
> 
> would a similar patch make sense for insBranch()?  if so, it backs up my R+. 
> if not, lets drill into why branches and guards would be treated differently.

It would make sense.  TM seems to not use LIR_j, but tamarin-redux has this:

    branchIns(LIR_j, 0, targetpc_off); // will be patched

The 0 is required because there's no condition.  That's actually much better than the corresponding TM code for x/loop/xbarrier -- there's no insImm(1) so it's clearer that the condition is unused, and no LIR buffer space is wasted.

A compromise would be to use 0 for the 2nd argument for x/loop/xbarrier in TM, and not split insCondGuard()/insUncondGuard().  I'd still want xtbl (and jtbl if it's introduced) to be handled separately via insSwitchGuard() because in that case the argument is an offset rather than a condition and so using the same ins() function is really confusing.
#21: I am trying to move away from LIR_loop and use LIR_j instead. It requires some heavy shuffling around of the way we maintain the frame state between recompilation, but its definitively on the agenda. If we make that work LIR_loop can go away altogether, so its just x and xbarrier then (xtbl is totally different as you mentioned and should be treated differently for sure).
Bug 504705 has a patch that gets rid of the unnecessary imm(1) instructions, because they were blocking some work I am doing on the CseFilter.  If that patch lands, this patch will need some rejigging.
Given the disagreement, I don't see this bug ever eventuating.
Status: ASSIGNED → RESOLVED
Closed: 14 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: