llvm dev - Jul 2009 - [LLVMdev] patch for llc/ARM: added mechanism to move switch tables from .text -> .data; also cleanup and documentation

On Tue, Jul 14, 2009 at 6:48 PM, Bob Wilson <bob.wilson at apple.com>
wrote:
>
> On Jul 2, 2009, at 10:48 AM, robert muth wrote:
>
> I spend over a day trying to follow your suggestion. In the end I was not
> successful. Here is what Iearned:
>
> After setting
>
> ARMJITInfo::hasCustomJumpTables -> true
> setOperationAction for ISD::BR_JT -> Expand
>
> I needed to add a "brind" definition to ARMInstrInfo.td
> I picked "bx" but to do a proper job one would have to take older
> architectures
> into account..
> The next thing was to to set
>  setOperationAction for ISD::JumpTable -> Custom
> and implement the corresponding code.
> This code is very similar to my "outline" code as it has to
materialize
> the table start address.
>
>  I never quite got this  to work, though.
>
>
> Sorry for the slow response.  Since it wasn't clear what problems you
ran
> into, and since I wasn't very familiar with LLVM's handling of jump
tables,
> I wanted to have a look at it myself to see what the issues were.
>
> I was able to make it work after fixing one problem: the branch folder
> removes "dead" jump tables and it doesn't scan the constant
pool for jump
> table references.  I had to add some code to the branch folder and the
> MachineConstantPoolValue class to fix that.  I haven't yet done much
testing
> of this but it looks like it's basically working.
>
> Since I had to write the code to try this out, I'm sending my revised
patch
> back to you.  There are still a few issues to sort out before committing
> this:
>
> * I followed your lead and added a "brind" pattern using
"bx".  I think
> this works on older architectures, too.  What issue were you thinking of
> with regard to supporting older architectures?  I didn't even look at
Thumb
> or Thumb2, but we'll need something for them.
>
> * I saw some earlier discussion about the command-line option name.  You
> had "outline-jumptables" and Evan had suggested
"OutOfLine".  I don't
> particularly like either one (sorry, Evan).  How about
> "no-inline-jumptables"?  I prefer that because it captures the
sense that
> this option is disabling an ARM-specific feature (the inline jumptables)
and
> changing back to the default.
>
> * I didn't look at the JIT code emitter at all.  That will need to be
> fixed.
>
> * It would be great to change the testcase to use the new FileCheck format.
>
> I've attached my revised patch to show you how I made this work. 
I've also
> attached a copy of your last patch with embedded comments (search for
> "bob>").  Let me know what you think and if you can take a
look at
> addressing some of the open issues above.
>
> Presumably what the generic code generator
> would to is to use this table start multiple the "switch index"
by 4 load
> the target address and jump there. Not a very  big saving in my mind.
> And it is offset by having to touch ARMInstrInfo.td.
> Also note, that the generic code generator must make some assumptions
> about the format of each jumptable entry (e.g. 32bit absolute addresses) so
> this cannot be changed easily afterwards.
>
> Having the default jumtables and the out of line version diverge too much
> and have different code path may also not be such a good idea.
>
>
> I'm not so much concerned about savings in the quantity of code as I am
in
> keeping the ARM backend from diverging too far from the other LLVM
backends.
>  Sometimes we have to do that but it is an ongoing maintenance
> burden, and in this case, it seems like we can easily avoid it.
>
>
> It also helps leverage the existing code.  For example, I didn't look
too closely, but with my patch, compiling with -relocation-model=pic seemed to
do the right thing.
>
>
>> Why did you change the default value for JumpTableDataSection?  Jump
>> tables really should not go into .data.  That is a security hole.  They
>> should be read-only.
>>
>
> I changed that too so the data goes into the default .rodata now.
> I am not sure where .rodata lives. if it lives in the text *segment*
> you get better protection but the code wont be PIC if .rodata
> goes into the data segment it is the other way round.
>
>
> If you compile with -relocation-model=pic, then the jump table contains
> offsets relative to the start of the table.  The tables live in .rodata (or
> even in .text itself, but not inline in the code) which is in the same
> segment as .text and thus the code is still PIC.
>


Bob:

Thanks for cleaning this up. I like the new patch much better than the old
one.
Teaching the (abstract) ConstantValue class about jumptable indices is a
little
bit ugly but I do not see any better solution without massive refactoring.
I have added TODOs  here and elsewhere and plan to address them in future
patches. I also added a test and pcleaned up a few things.

The new patch is attached.
I also uploaded it to

 http://codereview.appspot.com/96065/show

which is more convenient for browsing.
(you will have to register with an arbitrary pair
of email address and password --if you have a gmail
account you can use that)
Cheers,

Robert

>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090723/eba18605/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: j.patch
Type: text/x-diff
Size: 16583 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090723/eba18605/attachment.patch>

On Jul 23, 2009, at 12:10 PM, robert muth wrote:
> Bob:
>
> Thanks for cleaning this up. I like the new patch much better than  
> the old one.
> Teaching the (abstract) ConstantValue class about jumptable indices  
> is a little
> bit ugly but I do not see any better solution without massive  
> refactoring.
> I have added TODOs  here and elsewhere and plan to address them in  
> future
> patches. I also added a test and pcleaned up a few things.

Maybe I'm missing something but it looks like this is basically the  
same as the sample code that I sent back to you.  Aside from the TODO  
comments, it looks like all you changed was to move the new code in  
BranchFolding into a new UpdateLiveSetUsingConstantPoolAndMapIndices  
function, and I don't particularly like that change -- the new code is  
not that big and it is essentially the same code as in the preceding  
loop.  If anything, maybe it would be possible to refactor those two  
loops to share some code?  I don't see the point in just moving one of  
them out to a separate function with a big name.

As I wrote before, there are a few things that need to be addressed  
before we can take the patch.  I'll repeat them here for clarity:

* It needs to work on Thumb and Thumb2.  I'm not even sure if the  
"brind" pattern I added is the right thing for ARM mode.

* The JIT code emitter is definitely broken with this.  Unless there  
is a fundamental reason why this is hard, it should be fixed.

* The testcase should use the new FileCheck format.  (I think I  
phrased this as a suggestion before, but upon looking more closely at  
the test, it seems like the sort of test that is not well-suited to  
using grep.)

You didn't respond to my comment about the command-line option name.   
What do you think of "no-inline-jumptables"?

How do you plan to test this?  The simple testcase is a good start.   
Beyond that, I'd like to see you (temporarily) enable this by default  
and run through the llvm testsuite.

I also see you added a comment: "TODO: this does not currently work  
for PIC mode: the code works correctly but the table still ends up in  
the .text section."  I don't remember seeing that behavior, but maybe  
I missed it.  Please investigate why this is happening.

Thanks!

Bob:

a new patch is attached. I also uploaded it to

 http://codereview.appspot.com/96065/show

more info inline

On Mon, Jul 27, 2009 at 2:24 PM, Bob Wilson <bob.wilson at apple.com>
wrote:
>
> On Jul 23, 2009, at 12:10 PM, robert muth wrote:
> > Bob:
> >
> > Thanks for cleaning this up. I like the new patch much better than
> > the old one.
> > Teaching the (abstract) ConstantValue class about jumptable indices
> > is a little
> > bit ugly but I do not see any better solution without massive
> > refactoring.
> > I have added TODOs  here and elsewhere and plan to address them in
> > future
> > patches. I also added a test and pcleaned up a few things.
>
>
> Maybe I'm missing something but it looks like this is basically the
> same as the sample code that I sent back to you.  Aside from the TODO
> comments, it looks like all you changed was to move the new code in
> BranchFolding into a new UpdateLiveSetUsingConstantPoolAndMapIndices
> function, and I don't particularly like that change -- the new code is
> not that big and it is essentially the same code as in the preceding
> loop.  If anything, maybe it would be possible to refactor those two

* undid my refactoring.

>
> loops to share some code?  I don't see the point in just moving one of
> them out to a separate function with a big name.
>
> As I wrote before, there are a few things that need to be addressed
> before we can take the patch.  I'll repeat them here for clarity:
>
> * It needs to work on Thumb and Thumb2.  I'm not even sure if the
> "brind" pattern I added is the right thing for ARM mode.
>
added a brind instruction for thumb, but it seems that jump tables are
broken
on thumb even with "inlined tables"

>
> * The JIT code emitter is definitely broken with this.  Unless there
> is a fundamental reason why this is hard, it should be fixed.
>
as per our private conversation did not address this
>
> * The testcase should use the new FileCheck format.  (I think I
> phrased this as a suggestion before, but upon looking more closely at
> the test, it seems like the sort of test that is not well-suited to
> using grep.)
>
I made small change to look for "section" rather than
"rodata" to make the
test more portable.
As per our private conversation did not switch to "FileCheck format"
because
it does
not seem to support multiple passes over the same file.

>
> You didn't respond to my comment about the command-line option name.
> What do you think of "no-inline-jumptables"?
>
* command line naming is following  your proposal
>
> How do you plan to test this?  The simple testcase is a good start.
> Beyond that, I'd like to see you (temporarily) enable this by default
> and run through the llvm testsuite.
>
* did a *lot* testing using gnu torture test, overall I ran 3x1000 small c
programs on qemu

> I also see you added a comment: "TODO: this does not currently work
> for PIC mode: the code works correctly but the table still ends up in
> the .text section."  I don't remember seeing that behavior, but
maybe
> I missed it.  Please investigate why this is happening.
>
* reworded this but it seems to agree with your initial findings.

> Thanks!
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090806/db005de1/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: llvm-jt.patch
Type: text/x-diff
Size: 17913 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090806/db005de1/attachment.patch>