Issue 11 in jitasm: Crash in ControlFlowGraph::Build()

[jit...@googlecode.com]

Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 11 by just.ser...@gmail.com: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

While investigating a crashdump (from another guy) I found that the
block_idx variable in ControlFlowGraph::Build() is equal to blocks_.size()
which I guess could be a reason of his crash.

Shouldn't be there a check like block_idx_ < blocks_.size() or something?

I'm using jitasm fron trunk.

[jit...@googlecode.com]

Updates:
Owner: aki.yamasaki

Comment #1 on issue 11 by hikaruk...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

(No comment was entered for this change.)

[jit...@googlecode.com]

Comment #2 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

I have looked into ControlFlowGraph::Build() but I have no idea at this
time. Could you make reproducible small code?

[jit...@googlecode.com]

Comment #3 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

ControlFlowGraph::Build() is buggy. Working on a mips 2 x86-64 recompiler
using jitasm, I added a dot generator to be able to track what is wrong.
There are cases where CFG fails to split a basic block at the right place
and then it messes up the flow as a result, making my generated code being
wrong when trying to allocate x86-64 registers for each basic block. In the
attached pdf file, if you look at the end of basic block 'node_193', you'll
see a 'jle' instruction is not terminating this block as it should be. As a
result, I have some weird nodes like 'node_44' or badly linked nodes
appearing afterwards due to this bug. I've spent so many weeks to
understand why my recompiler didn't work because of that buggy CFG builder
I thought it could be trusted.


Attachments:
cfg_sb_0xA3FB0800.pdf 47.1 KB

--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[jit...@googlecode.com]

Comment #4 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Could you give me the debug trace which is outputted by JITASM_DEBUG_DUMP
define? The reproducible small code is most helpful.

[jit...@googlecode.com]

Comment #5 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

well no because I heavily changed jitasm for the recompiler needs, included
JITASM_DEBUG_DUMP. But I can tell what I changed to make it work. The issue
is about variable "block_idx" which is used as an obviously wrong
optimization to avoid fetch ing which basic block index has the instruction
residing at instr_idx. Attached is the function with my changes.







Attachments:
Compiler.cpp 1.9 KB

[jit...@googlecode.com]

Comment #6 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Btw, it may also explain why I had some asserts being false in another
project where I mostly use your jitasm version.

[jit...@googlecode.com]

Updates:
Status: Fixed

Comment #7 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

I have fixed this issue. Thank you for your report!

[jit...@googlecode.com]

Comment #8 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

I applied your fix to my ControlFlowGraph::Build() and I still have the
same issue as before your fix about a I_JCC going backward to another
block. If I simplify, the test case might be the following:

L("0");
mov(eax, 2);
mov(edx, 1);
cmp(eax, 0);
jle("1");
dec(edx);
L("1");
dec(eax);
jne("0");
...

I don't use symbolic registers at all (have my own register allocator which
deals with a register context as a place holder and not stack placeholder)
but I force the call to this function so I can have the CFG.

Attachments:
Compiler_Cfg_20140818.cpp 2.7 KB

[jit...@googlecode.com]

Comment #9 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Attached is a 7z archive with four files:

with your fix: sb_0xA3FB0840.wrong.gv and sb_0xA3FB0840.wrong.gv.pdf

with mine: sb_0xA3FB0840.right.gv and sb_0xA3FB0840.right.gv

Use a diff between .gv files and you'll see one basic block is not ending
with a jump-like instruction.

Attachments:
cfg_20140818.7z 101 KB

[jit...@googlecode.com]

Updates:
Status: Started

Comment #10 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

I'm looking into it again.

[jit...@googlecode.com]

Comment #11 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Thanks. By the way, "node_#/Node #" means # is the number of last Instr
instance in the associated basic block.

[jit...@googlecode.com]

Comment #12 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Thanks. By the way, "node#/Node #" means that # is the index of an
instruction in f.instrs which is the last (and terminating) instruction in

[jit...@googlecode.com]

Comment #13 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

FYI, if you wonder why some instructions changes whereas I just switch
between your fix and mine, it is because I have my own RewriteIntructions
which transforms some instructions.

For instance:

MIPS: ADDIU v0, v0, -1

is always generated into X86-46:

MOV(MIPS_GPR(v0), MIPS_GPR(v0));
DEC(MIPS_GPR(v0));
MOV(MIPS_GPR(v0), MIPS_GPR(v0));

where MIPS_GPR() defines a mips context register (equivalent to symbolic
register in your case)

CFG is always building with those three instructions so there is no
consequence on the way CFG builds at this stage.

After CFG building, register allocator will replace instances of
MIPS_GPR(vreg) in each instructions by an allocated physical register or by
a memory reference like dword_ptr[rsi + 4*vreg] where rsi is the base of
the mips registers context. I modified stuff like EncodeMOV so a pattern
like: mov(X,X) is never output.

So depending on the basic block and the register usage of vreg beforehand
or afterward I may have:

1) vreg is used before and after the mips ADDIU instruction in this basic
block:

dec(reg);

2) vreg is used before but not after the mips ADDIU instruction in this
basic block:

dec(reg); mov(dword_ptr[rsi+4*vreg], reg)

3) vreg is used after but not before the mips ADDIU instruction in this
basic block:

mov(reg, dword_ptr[rsi+4*vreg]); dec(reg);

4) vreg is used only by the mips ADDIU instruction in this basic block:

dec(dword_ptr[rsi+4*vreg]);

[jit...@googlecode.com]

Updates:
Status: Fixed

Comment #14 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Fixed!

[jit...@googlecode.com]

Comment #15 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

The MIPS to x86 recompiler is interesting, hlide.

I wonder why you use your own register allocator instead of the jitasm
register allocator? I believe jitasm register allocator is more efficient.

[jit...@googlecode.com]

Comment #16 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

There are several reasons:

1) In early times, whenever I tried to use symbolic registers, I had very
bad code (too many mov or xchg because of registers rotation probably) and
a lot of asserts being false as well. Maybe the buggy CFG was the culprit.
And several of my fellows told me the same thing: code seems too bloated.

2) Context registers (registers mapped into a memory structure representing
mips registers) and symbolic registers (registers spilled into a stack)
have radically different purposes. Symbolic registers are used as local
variables whereas context registers are used as global and
persistent "variables". I need them to be read when entering the function
and be saved in the context at the end of the function, which is not how a
local variable works (a local variables is always written the first time
and doesn't need to be saved back in the spill slot when leaving the
function). When executing a "call rdi" (mips syscall emulation), it's very
important to get all registers back in the context (that's why I consider
I_CALL always terminates a basic block).

3) The most important part is the ability to issue fastest direct or
indirect branching/jumping across the program and not the efficiency of the
register allocation. It leads to a huger execution speed while the use of
allocated registers brings a very marginal speed gain and less bytes for
the generated superblock.
With a true interpreter, I have a frame period of 5.0-5.3 ms for a demo.
Using the recompiler in interpreter-like mode (each basic block is created
per one instruction or two if there is a delayslot), I have a frame period
of 1.1-1.2 ms. In full mode, I have a frame period of 1 ms with or without
register allocation.

4) The strategy I choose for register allocation is different too. While I
can have up to 12 registers (RAX, RDX, RCX, RBX, R8-R15), I want to
allocate one if and only if it leads to more than 2 instructions to
read/write in the register context and reuse registers if there is no
overlaps. Besides, I also remap the allocated registers, so the most
referenced mips registers will be associated to the most prioritized
registers in this order (RAX, RDX, RCX, RBX, R8, ..., R15) since it helps
to reduce the generated bytes (less prefixes because of use of R8-R15). I
also plan to add a constant propagation to reduce the register pressure and
merge several instructions into one (ex: lui reg, 0xXXXX; ori reg, reg,
0xYYYY ---> mov(GPR(vreg), 0xXXXX0000); or(GPR(vreg), 0x0000YYYY); --->
mov(GPR(vreg), 0xXXXXYYYY)) which are not infrequent in mips.

While I do understand why you says jitasm register allocator is more
efficient - because it can generate intermediate blocks to help to keep
only registers in a loop (no need to save/restore context registers), it
tends to use too many registers and to issue too many mov or xchg
instructions and it doesn't scope well with the purpose of a context
register (vs. symbolic register). So it isn't top in my priority list. But
yeah, when a lot of other stuff are done, I may reconsiderate an adapted
version of jitasm register allocator so I can avoid flushing registers
inside a loop.

[jit...@googlecode.com]

Comment #17 on issue 11 by aki.yamasaki: Crash in ControlFlowGraph::Build()
http://code.google.com/p/jitasm/issues/detail?id=11

Thank you for your explanation. They are very interesting. I agree that
jitasm generates too many mov, xchg and jump code. I want to improve it,
though I have no good idea at this time.

[jit...@googlecode.com]

Comment #18 on issue 11 by hlide.de...@gmail.com: Crash in
ControlFlowGraph::Build()
https://code.google.com/p/jitasm/issues/detail?id=11

You could also have a look at that :
http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html.
They switch from a linear scan register allocator to this allocator for the
reasons they explain in this link. Wonder if it could be interesting for
jitasm as well.