llvm dev - Aug 2018 - 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):

----------------------------------------------------------------------
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.

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;
----------------------------------------------------------------------

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.

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.

Thank you for your help.

Kind regards,
Phillip Raffeck
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ARMConstantIslandPass.patch
Type: text/x-patch
Size: 1910 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180811/61da7b51/attachment.bin>

On 8/11/2018 9:16 AM, Phillip Raffeck via llvm-dev
wrote:
> 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

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

On Mon, 13 Aug 2018 11:46:45 -0700
"Friedman, Eli" <efriedma at codeaurora.org> wrote:
> On 8/11/2018 9:16 AM, Phillip Raffeck via llvm-dev wrote:
> > 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.
Thank you for your kind feedback. I'll look into creating a testcase and
putting the patch up for review.

Kind regards
Phillip Raffeck