This is an archive of the discontinued LLVM Phabricator instance.

[ARM] ARMCodeGenPrepare backend pass
ClosedPublic

Authored by samparker on Jul 2 2018, 8:06 AM.

Details

Summary

Arm specific codegen prepare is implemented to perform type promotion
on icmp operands, which can enable the removal of uxtb and uxth
(unsigned extend) instructions. This is possible because performing
type promotion before ISel alleviates this duty from the DAG builder,
which has to perform legalisation, but has a limited view on data
ranges.

The pass visits any instruction operand of an icmp and creates a
worklist to traverse the use-def tree to determine whether the values
can simply be promoted. Our concern is values in the registers
overflowing the narrow (i8, i16) data range, so instructions marked
with nuw can be promoted easily. For add and sub instructions, we are
able to use the parallel dsp instructions to operate on scalar data
types and avoid overflowing bits. Underflowing adds and subs are also
permitted when the result is only used by an unsigned icmp.

Diff Detail

Event Timeline

samparker created this revision.Jul 2 2018, 8:06 AM
eastig added a subscriber: eastig.Jul 2 2018, 9:04 AM
javed.absar added inline comments.Jul 2 2018, 12:15 PM
lib/Target/ARM/ARMCodeGenPrepare.cpp
10

It may be good to copy the description you have of the algorithm in the commit message to here (or something similar)

134

nitpick. Typo or missing word "Some instructions can 8- and 16 .."

198

Typo : "is the given.." => "if the given.."

220

Typo "will" => "we"

269

typo - "performed"

test/CodeGen/ARM/arm-cgp-signed.ll
1

Please add a line to describe overall what this test is about

Not a complete review, but a quick first pass.

On a sort of related note, I ran into an issue recently with a testcase like the following: "void a(short *x, void f()) { if (*x == -3) f(); }". We generate an extra instruction because we treat the loaded value as unsigned. Not sure if that's in scope for the sort of thing you want to fix with this IR pass.

lib/Target/ARM/ARMCodeGenPrepare.cpp
113

Please add a comment explaining what it means for an instruction to be "signed".

280

Is it safe to generate calls to uadd? It writes to the GE bits, and user code could potentially read them.

441

Do we need to check we have Thumb2, if we're in Thumb mode?

Also a quick first pass, see comments inline.

lib/Target/ARM/ARMCodeGenPrepare.cpp
49

Can you comment what this exactly does? Looks like that deep down in the logic that checks for candidares, in ARMCodeGenPrepare::isNarrowInstSupported(Instruction *I), this prevents the transformation from triggering. So checking DisableDSP can be done a lot earlier, or perhaps you want to put a TODO somewhere if you plan on supporting this later? Also, this one does not seem to be covered by tests (arm-disable-scalar-dsp-imms is covered).

184

I learned a trick the other day: the IR pattern matcher. ;-) Looks like you can simply things, and don't need the check and cast above and can immediately do something like:

if (match(V, m_Store(m_Value(), m_Value())) || isa<TerminatorInst>(V))
  return false;

Looks like you can actually use the pattern matcher at more places, like e.g. the function below.

@efriedma what was the extra instruction that you're generating in your example? I'm seeing code that looks okay to me:

ldrh	r0, [r0]
movw	r2, #65533
cmp	r0, r2
lib/Target/ARM/ARMCodeGenPrepare.cpp
49

It's to control the generation of the DSP instructions which, as Eli points out, could be unsafe. I only want to check at that point because the transformation could happen without the need for those intrinsics.

I'll add some tests, and I'm going to change the default of this to 'true' to stay on the safe side.

280

Currently intrinsics are the only way to read and write the GE flag, but no it doesn't mean its safe. Is there a way to query the function/module for the intrinsics used? If there's no sel intrinsic being used, we are okay to use these instructions. Either way, I'll change the default to disable the generation of these instructions.

samparker added inline comments.Jul 3 2018, 2:15 AM
lib/Target/ARM/ARMCodeGenPrepare.cpp
441

I thought DSP should cover it since they're only available in Thumb2, but an explicit check wouldn't hurt.

samparker added inline comments.Jul 3 2018, 3:19 AM
lib/Target/ARM/ARMCodeGenPrepare.cpp
184

I don't see how the match function is better than isa<> here. The cases below are mainly concerned with checking the number of uses, can the pattern matching framework help there?

samparker updated this revision to Diff 153891.Jul 3 2018, 3:25 AM

Changes:

  • fixed typos,
  • changed the names and default setting of the options, the generation of uadd and usub are now disabled by default.
  • moved icmp handling code out of isSigned and into isPromotedResultSafe.
  • added another target to test the default command line options.

what was the extra instruction that you're generating in your example

The movw. We should generate ldrsh+cmn, like we do for "*x < -3".

lib/Target/ARM/ARMCodeGenPrepare.cpp
280

You can call use_empty() on any particular intrinsic, but that probably isn't what you want; either we assume GE is clobbered across function calls (in which case we only want to check the current function), or we assume it's preserved across function calls (in which case checking the current module isn't sufficient).

441

"hasDSP()" is essentially just the "dsp" subtarget feature, which is whether the target CPU supports DSP instructions in either ARM or Thumb mode. This makes perfect sense from the perspective of subtarget features (since whether a function is in Thumb mode is independent of the target CPU), but it's a little confusing in this context.

john.brawn added inline comments.Jul 5 2018, 8:49 AM
lib/Target/ARM/ARMCodeGenPrepare.cpp
90

This is unused.

520

OrigTy is only used in this function, so should be a local variable.

532

CurrentVisited is only used in this function, and cleared before being used, so it would make more sense as a local variable.

618

M isn't used outside of this function, so you can get rid of it.

619

ExtTy is never changed and only passed to IRPromoter::Mutate, so it looks like it would make more sense for it to be just a local variable in IRPRomoter::Mutate.

628

Why IfAvailable? Why not define ARMCodeGenPrepare::getAnalysisUsage and require it there so it's always available?

632

As far as I can tell F isn't used outside of this function, so you can get rid of it.

samparker updated this revision to Diff 154361.Jul 6 2018, 12:13 AM

Cheers John! Moved, removed or localised variables and implemented getAnalysisUsage.

I studied the test cases, which make sense. So this is a nit: I think it would be good if you take the reader by the hand here, and explicitly state why and what corner cases you're testing.

samparker updated this revision to Diff 154961.Jul 11 2018, 3:44 AM

Added comments to describe the purpose of some of the tests.

Hi Sam, I took your patch, and ran some C/C++ language conformance tests with it. Did not come back entirely clean. Here's a first reproducer that throws this compile error:

LLVM ERROR: Broken function found, compilation aborted!

Input code:

unsigned char unsigned_char_data[42];
short short_data[42];
short short1;
int foo(void) {
  short1 = (short)unsigned_char_data[2];
  return short1 == short_data[2];
}

And its corresponding IR that should show this problem:

@d_uch = hidden local_unnamed_addr global [16 x i8] zeroinitializer, align 1
@sh1 = hidden local_unnamed_addr global i16 0, align 2
@d_sh = hidden local_unnamed_addr global [16 x i16] zeroinitializer, align 2

define hidden arm_aapcs_vfpcc i32 @foo() local_unnamed_addr #0 {
entry:
  %0 = load i8, i8* getelementptr inbounds ([16 x i8], [16 x i8]* @d_uch, i32 0, i32 2), align 1, !tbaa !5
  %conv = zext i8 %0 to i16
  store i16 %conv, i16* @sh1, align 2, !tbaa !8
  %conv1 = zext i8 %0 to i32
  %1 = load i16, i16* getelementptr inbounds ([16 x i16], [16 x i16]* @d_sh, i32 0, i32 2), align 2, !tbaa !8
  %conv2 = sext i16 %1 to i32
  %cmp = icmp eq i32 %conv1, %conv2
  %conv3 = zext i1 %cmp to i32
  ret i32 %conv3
}
SjoerdMeijer added a comment.EditedJul 12 2018, 1:09 AM

We also have a few miscompilations. Here's a reproducer for which we produce the wrong result:

short short1, short2, short3;                                                                                    
                                                                                                    
int main() {                                                                                          
  short2 = 5;                                                                                         
  short3 = -6;                                                                                       
  assert((short1 = ~short2) == short3);                                                              
}

Many thanks for those!

samparker updated this revision to Diff 155655.Jul 16 2018, 5:58 AM

Hi Sjoerd,

Hopefully the changes address the two problems that you found. I still need to write a couple of other tests to convince myself there isn't still an issue similar the one you reported with the aborted compilation.

Most of the changes are code movement, the functional changes are that I now handle negative immediates in all cases, not just the special cased icmp. The mutation of 'roots' has also been tweaked to fix the other issue.

cheers,

SjoerdMeijer added a comment.EditedJul 16 2018, 7:26 AM

We are down to 3 errors, compared to 14 before. Before we had 2 issues: the backend compile error was responsible for 12 errors, the miscompilation for 2. The build error disappeared, so we have only the miscompilations remaining. The first miscompilation is also resolved, but we have some new ones (the tests progress further now). The first one I looked at is very similar to the one I reported earlier:

assert((short1 = ~short2) == short3);

but now the operator is different (of course the variables have different values):

(short *= short2) == short3

This test file is doing similar checks, testing operators += and -= and /= and %= and &= and |= and ^=. Perhaps you can see if you can explain these failures. Otherwise, let me know if you need full reproducers. Looks like these patterns are responsible for 2 test failures.

The 3rd failure is an assertion failure:

lib/IR/Instructions.cpp:2463: static llvm::CastInst* llvm::CastInst::Create(llvm::Instruction::CastOps, llvm::Value*, llvm::Type*, const llvm::Twine&, llvm::Instruction*): Assertion `castIsValid(op, S, Ty) && "Invalid cast!"' failed

This is conversion issue from small ints to long long. I think this should be enough to trigger it:

unsigned char uc = 42;
long long LL;
void foo() {
  LL = uc;
  assert(LL == 42ll);
}
samparker updated this revision to Diff 155842.Jul 17 2018, 4:03 AM
  • Fixed the really bad typo that was allowing wrapping instructions, quite confused that this wasn't caught by my existing tests... so added more of them.
  • Added more type checking so we can catch the i64 issue
  • Added a couple more tests to show the current limitation too
samparker updated this revision to Diff 155874.Jul 17 2018, 6:53 AM

Moved a couple of functions into lambdas and added a couple of checks to reject ConstantExprs.

samparker updated this revision to Diff 155890.Jul 17 2018, 8:06 AM

Now explicitly stating what values and opcodes we support. Also added some debug code around and removed the ShouldIgnore function.

Is the pass running at any optimisation level? Or should this for example only be at -O3?

samparker updated this revision to Diff 156042.Jul 18 2018, 4:04 AM

Fixed a couple of bugs around the truncating of values into the root users. Also added explicit checks to reject signed compares.

samparker updated this revision to Diff 156084.Jul 18 2018, 8:26 AM

Fixed support for handling switch instructions and added another test.

SjoerdMeijer accepted this revision.Jul 18 2018, 9:02 AM

I have been running language conformance tests in different configurations with your latest patches, targeting different targets, and I have also been running fuzzers. Your latest fixes solves all earlier reported issues. Everything is green, and also the 4% performance improvement in a benchmarks is a nice one! :-)

So this looks good to me.

One nit: we probably want to skip running this pass for CodeGenOpt::None?

This revision is now accepted and ready to land.Jul 18 2018, 9:02 AM
samparker updated this revision to Diff 156735.Jul 23 2018, 3:40 AM

Now disabled at -O0

samparker updated this revision to Diff 156753.Jul 23 2018, 5:07 AM

Added another test

This revision was automatically updated to reflect the committed changes.