|
From: Anne R. <am...@cs...> - 2007-07-05 20:43:54
|
I have been trying to build a branch predictor based on
valgrind for quite some time. Every time I think I have it
working, I find some new oddity in the way valgrind
works. My most recent problem is that valgrind
flips the sense of some tests (even with vex-ir-level=0
and vex_guest_chase_threshold=0). For example,
The instruction:
80483cc: 7d 09 jge 80483d7 <iter+0x17>
gets translated into:
------ IMark(0x80483CC, 2) ------
PUT(60) = 0x80483CC:I32
t19 = GET:I32(32)
t20 = GET:I32(36)
t21 = GET:I32(40)
t22 = GET:I32(44)
t23 = x86g_calculate_condition[mcx=0x13]{0x38097a40}
(0xC:I32,t19,t20,t21,t22\
):I32
t18 = 32to1(t23)
if (t18) goto {Boring} 0x80483CE:I32
goto {Boring} 0x80483D7:I32
}
So, the destination of the instruction appears to be the
true fall through address, whereas the fall through ends
up being the true destination.
Unfortunately, it does not always make this swap. For example,
this instruction:
804832d: 74 05 je 8048334 <call_gmon_start
+0x20>
turns into these vex instructions:
------ IMark(0x804832D, 2) ------
PUT(60) = 0x804832D:I32
t24 = GET:I32(32)
t25 = GET:I32(36)
t26 = GET:I32(40)
t27 = GET:I32(44)
t28 = x86g_calculate_condition[mcx=0x13]{0x38097a40}
(0x4:I32,t24,t25,t26,t27\
):I32
t23 = 32to1(t28)
if (t23) goto {Boring} 0x8048334:I32
goto {Boring} 0x804832F:I32
}
The dst is the true dst and the fall through is the true fall through.
Is this anyway around this problem? Has anyone written tool that
correctly identifies branchs? (And calls and returns.)
-Anne Rogers
|
|
From: Julian S. <js...@ac...> - 2007-07-05 21:05:28
|
> The dst is the true dst and the fall through is the true fall through. Yes. There's nothing that mandates, for an IR Exit statement, that the fallthrough IR corresponds to the fallthrough guest instruction it was derived from. Various parts of the IR compilation pipeline switch around the sense of the exits from time to time. > Is this anyway around this problem? Has anyone written tool that > correctly identifies branchs? (And calls and returns.) Yes, Yes, and Not really. Reliably identifying all calls and returns is a very hard problem, and Josef W (Callgrind's author) is the person to ask. As far as the immediate problem goes: a couple months ago I extended cachegrind to do branch prediction simulation, and so had to solve this exact problem. It's not in the 3.2.X series but it is in the current trunk. svn co svn://svn.valgrind.org/valgrind/trunk and look at cg_main.c around line 1020, specifically the 'case Ist_Exit:' ... stuff. The branch events are fed through to the simulator in cg_branchpred.c. It probably has a fairly high level of bogosity. Comments, feedback, welcomed. J |
|
From: Nicholas N. <nj...@cs...> - 2007-07-05 21:53:18
|
On Thu, 5 Jul 2007, Julian Seward wrote: > As far as the immediate problem goes: a couple months ago I extended > cachegrind to do branch prediction simulation, and so had to solve this > exact problem. It's not in the 3.2.X series but it is in the current > trunk. svn co svn://svn.valgrind.org/valgrind/trunk and look at cg_main.c > around line 1020, specifically the 'case Ist_Exit:' ... stuff. > > The branch events are fed through to the simulator in cg_branchpred.c. > It probably has a fairly high level of bogosity. I think "It" in that last sentence refers to the branch simulation, rather than the rest of the tool -- ie. it identifies the branches ok. However, Daniel Jimenez did say it was a reasonable basic simulator, although some of the parameters could be tweaked. Nick |
|
From: Anne R. <am...@cs...> - 2007-07-05 22:04:06
|
Thank you very much. I now see how to fix my problem. -anne ps. I understood that the antecedent of "it" was the predictor not the branch event finder. On Jul 5, 2007, at 4:53 PM, Nicholas Nethercote wrote: > On Thu, 5 Jul 2007, Julian Seward wrote: > >> As far as the immediate problem goes: a couple months ago I extended >> cachegrind to do branch prediction simulation, and so had to solve >> this >> exact problem. It's not in the 3.2.X series but it is in the current >> trunk. svn co svn://svn.valgrind.org/valgrind/trunk and look at >> cg_main.c >> around line 1020, specifically the 'case Ist_Exit:' ... stuff. >> >> The branch events are fed through to the simulator in >> cg_branchpred.c. >> It probably has a fairly high level of bogosity. > > I think "It" in that last sentence refers to the branch simulation, > rather > than the rest of the tool -- ie. it identifies the branches ok. > However, > Daniel Jimenez did say it was a reasonable basic simulator, > although some of > the parameters could be tweaked. > > Nick > > ---------------------------------------------------------------------- > --- > This SF.net email is sponsored by DB2 Express > Download DB2 Express C - the FREE version of DB2 express and take > control of your XML. No limits. Just data. Click to get it now. > http://sourceforge.net/powerbar/db2/ > _______________________________________________ > Valgrind-users mailing list > Val...@li... > https://lists.sourceforge.net/lists/listinfo/valgrind-users > |