[llvm-dev] MachineInstr sizes for ARM jumptables

[Phillip Raffeck via llvm-dev]

On Tue, 14 Aug 2018 10:38:05 +0200
Phillip Raffeck via llvm-dev <llvm-dev at lists.llvm.org> wrote:

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

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