[llvm-dev] Strange behaviour of post-legalising optimisations(?)

[Joan Lluch via llvm-dev]

Hi Tim,

Thank you for your reply. It actually helped a lot to narrow the issue, as previously I didn’t even know where to look.

I have been following the code in the debugger, specially the LSRInstance::SolveRecurse function. This function traverses recursively all possible ‘Formulae’, and determines the best instruction combination for the loop generation, based on minimal cost. The SolveRecurse function uses Cost::RateFormula as the basis for the cost computation. 

I found that the RateFormula function does not return the what-would-be best values for my architecture. In particular, my understanding is that the whole implementation kind of assumes that all architectures will have post-increment addressing modes, even if they don’t. For example, consider the following formulas:

reg({%dest,+,1}<nsw><%for.cond>) 
reg(%dest) + 1*reg({0,+,1}<nuw><nsw><%for.cond>)

The RateFormula function returns ‘1 instruction’ for either of them, however, in my case, the first one will require an explicit add instruction (post increment is not supported), which should account for an instruction count of 2 instead of just 1. The count should be 2 because this additional add can not be folded with other instructions, as it’s exclusively to increment the pointer.

So the problem is that in most situations, llvm choses the first form rather than the second one due to the register overhead in the second one, in spite that in my architecture it would be much better to chose the second (which would happen if the first one resulted in a 2 instruction count).

At this point, I advanced significantly on the understanding of the problem, but I got stuck at a more concrete problem. It seems to me that there’s no way to instruct LLVM to adopt a more costly result for the first form, as it would be necessary for my architecture, unless I’m missing something (?).

(As a side note: I implemented “isLegalAddressingMode”, but it turned to be virtually identical to the default one except for the smaller immediate sizes, so I think it doesn’t make much difference. Post/Pre increment addressing mode is not supported in my architecture so this is reflected, and I haven’t either added the setIndexedLoadAction calls to my TargetLowering constructor. I also created my own TargetTransformInfo implementation based on the ARM code, which works fine as the functions get diligently called, but I found that it’s not of much help because it doesn’t have the necessary hooks to solve this issue)

So any additional help would be appreciated.

Joan Lluch


> On 5 Jun 2019, at 19:33, Tim Northover <t.p.northover at gmail.com> wrote:
> 
> Hi Joan,
> 
> On Wed, 5 Jun 2019 at 08:58, Joan Lluch via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> Any ideas about why this happens?. Particularly, what could cause this change of behaviour just by adding an ‘if’ before the ‘for’?  Note that the IR code for the for ‘for’ body is IDENTICAL in both cases, so this is definitely a LLVM thing.
> 
> If you run "llc -print-after-all" you should be able to see which pass
> first introduces the behaviour you don't like. In this case it seems
> to be "Loop Strength Reduction", in
> lib/Transforms/Scalar/LoopStrengthReduce.cpp. It makes use of a lot of
> hooks in TargetTransformInfo (search for "TTI.") when making its
> decisions and if you haven't implemented versions of those matching
> your target its heuristics are going to get this kind of thing wrong.
> 
> Beyond that I'm just guessing, but isLegalAddressingMode looks like it
> could be a critical one for your case (it's the only thing you've
> mentioned being able to do neatly).
> 
> Cheers.
> 
> Tim.