MachineInstr sizes for ARM jumptables

Hi llvm developers,

I might be overlooking something, but I think the ARMConstantIsland
pass uses the wrong size for the MachineInstrs representing jump
tables: Currently, there is the following calculation in
doInitialJumpTablePlacement
(lib/Target/ARM/ARMConstantIslandPass.cpp:588):

ARMConstantIslandPass.patch (1.87 KB)

Hi llvm developers,

I might be overlooking something, but I think the ARMConstantIsland
pass uses the wrong size for the MachineInstrs representing jump
tables: Currently, there is the following calculation in
doInitialJumpTablePlacement
(lib/Target/ARM/ARMConstantIslandPass.cpp:588):

----------------------------------------------------------------------
unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
----------------------------------------------------------------------

Obviously, a size of 4 bytes per entry is incorrect for jump tables
consisting of byte or halfword entries.

IIRC we never generate TBB or TBH before ARMConstantIslands::optimizeThumb2JumpTables runs anyway, so that doesn't actually make a difference... but either way, it should be cleaned up.

Additionally, when trying to optimize for table size later in
optimizeThumb2JumpTables, the opcode is updated without updating the
size (lib/Target/ARM/ARMConstantIslandPass.cpp:2229):

----------------------------------------------------------------------
unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
----------------------------------------------------------------------

That looks like a bug, yes.

It seems to me, that the size of that MachineInstr is not used in any
critical calculations (or at all), so it maybe has no consequences
observable in the produced binary. I am however using an analysis
toolkit, which kind of relies on these sizes being correct.

The ARM backend is relatively sensitive to the sizes of instructions because Thumb1 branches have extremely small offsets: if the computed size of an instruction is smaller than the actual size, we won't lay out the function correctly, and the result will fail to assemble in edge cases.

That said, if the computed size is larger than the actual size, there isn't much consequence except that the generated code will be less efficient in some cases.

I have attached a diff for better clarification of what I'm talking
about and what I think would be a solution. I will happily contribute
these changes, so if you can confirm my observations, please point me
to what would be the next steps.

Should be possible to write a testcase: in Thumb1 mode, if you have a loop with a jumptable, and we overestimate the size of the jump table, the backedge branch will be "bl" when it could be "b". Or something like that; maybe needs to be an MIR testcase to reliably get the right block layout.

If you're interested, see http://llvm.org/docs/DeveloperPolicy.html and http://llvm.org/docs/MIRLangRef.html#mir-testing-guide . Otherwise, I'll look into cleaning it up your patch and submitting it in the right form.

-Eli

Thank you for your kind feedback. I'll look into creating a testcase and
putting the patch up for review.

Kind regards
Phillip Raffeck

I've created https://reviews.llvm.org/D50800 .

I'm not really satisfied with revisiting far branches afterwards, but
resizing jump tables before constant placement and branch fixup
interferes greatly with constant placement: As for tTBB and tTBH jump
tables have to be placed directly after the instruction, there is no
space between them for constant islands, leaving less room for constant
placement than with tBR_JT instructions. This might lead to splitting of
basic blocks and introduction of additional jumps, so I decided to
leave the order as it is and check afterwards if all far branches are
really necessary.

While creating the patch and testcase I also noticed that the full
range of branches is apparently not used for back egdes. If I'm not
mistaken, branches on ARM always range from -(X+2) to X, while the
ConstantIslandPass just uses the range -X to X. Is this intentional?

I have also written a testcase triggering that behaviour, but I wasn't
sure if uploading a patch only consisting of a testcase (which is
failing right now) to reviews.llvm.org is okay.

Regards
Phillip