Strange behaviour of post-legalising optimisations(?)

I come across a situation that I am having a hard time to understand.

When I compile the following code :

char *tst( char *dest, const char *src, unsigned int len )
{
for (int i=0 ; i<len ; i++) {
dest[i] = src[i];
}
return dest;
}

Clang generates this for the ‘for’ body:

for.body: ; preds = %for.cond
%arrayidx = getelementptr inbounds i8, i8* %src, i16 %i.0
%0 = load i8, i8* %arrayidx, align 1, !tbaa !2
%arrayidx1 = getelementptr inbounds i8, i8* %dest, i16 %i.0
store i8 %0, i8* %arrayidx1, align 1, !tbaa !2
%inc = add nuw nsw i16 %i.0, 1
br label %for.cond

This gets converted into this by llc:

Creating new node: t2: i16,ch = CopyFromReg t0, Register:i16 %3
Creating new node: t4: i16,ch = CopyFromReg t0, Register:i16 %0
Creating new node: t5: i16 = add t2, t4
Creating constant: t6: i16 = Constant<0>
Creating new node: t7: i16 = undef
Creating new node: t8: i8,ch = load<(load 1 from %ir.scevgep1, !tbaa !2)> t0, t5, undef:i16
Creating new node: t10: i16,ch = CopyFromReg t0, Register:i16 %2
Creating new node: t11: i16 = add t10, t4
Creating new node: t12: ch = store<(store 1 into %ir.scevgep, !tbaa !2)> t8:1, t8, t11, undef:i16
Creating constant: t13: i16 = Constant<1>
Creating new node: t14: i16 = add nuw nsw t4, Constant:i16<1>
Creating new node: t16: ch = CopyToReg t0, Register:i16 %1, t14
Creating new node: t17: ch = TokenFactor t16, t12
Creating new node: t19: ch = br t17, BasicBlock:ch<for.cond 0x10983ff38>
Initial selection DAG: %bb.3 'tst:for.body’
SelectionDAG has 20 nodes:
t0: ch = EntryToken
t4: i16,ch = CopyFromReg t0, Register:i16 %0
t6: i16 = Constant<0>
t2: i16,ch = CopyFromReg t0, Register:i16 %3
t5: i16 = add t2, t4
t8: i8,ch = load<(load 1 from %ir.scevgep1, !tbaa !2)> t0, t5, undef:i16
t14: i16 = add nuw nsw t4, Constant:i16<1>
t16: ch = CopyToReg t0, Register:i16 %1, t14
t10: i16,ch = CopyFromReg t0, Register:i16 %2
t11: i16 = add t10, t4
t12: ch = store<(store 1 into %ir.scevgep, !tbaa !2)> t8:1, t8, t11, undef:i16
t17: ch = TokenFactor t16, t12
t19: ch = br t17, BasicBlock:ch<for.cond 0x10983ff38>

This is ok:
The array indexes get replaced by ‘add’ instructions (see t5 and t11) that later on can be folded into appropriate load/store addressing modes.
So far so good.

However, if I replace the original code by this:

char *tst( char *dest, const char *src, unsigned int len )
{
if ( dest ) {
for (int i=0 ; i<len ; i++) {
dest[i] = src[i];
}
}

return dest;
}

I get IDENTICAL output from Clang for the ‘for’ body

But totally different code from llc:

Total amount of phi nodes to update: 0
Creating new node: t2: i16,ch = CopyFromReg t0, Register:i16 %1
Creating constant: t3: i16 = Constant<0>
Creating new node: t4: i16 = undef
Creating new node: t5: i8,ch = load<(load 1 from %ir.lsr.iv1, !tbaa !2)> t0, t2, undef:i16
Creating new node: t7: i16,ch = CopyFromReg t0, Register:i16 %2
Creating new node: t8: ch = store<(store 1 into %ir.lsr.iv, !tbaa !2)> t5:1, t5, t7, undef:i16
Creating constant: t9: i16 = Constant<1>
Creating new node: t10: i16 = add t7, Constant:i16<1>
Creating new node: t12: ch = CopyToReg t0, Register:i16 %3, t10
Creating new node: t13: i16 = add t2, Constant:i16<1>
Creating new node: t15: ch = CopyToReg t0, Register:i16 %4, t13
Creating new node: t17: i16,ch = CopyFromReg t0, Register:i16 %0
Creating constant: t18: i16 = Constant<-1>
Creating new node: t19: i16 = add t17, Constant:i16<-1>
Creating new node: t21: ch = CopyToReg t0, Register:i16 %5, t19
Creating new node: t22: ch = TokenFactor t12, t15, t21, t8
Creating new node: t24: ch = br t22, BasicBlock:ch<for.cond 0x10985e000>
Initial selection DAG: %bb.3 'tst:for.body’
SelectionDAG has 25 nodes:
t0: ch = EntryToken
t2: i16,ch = CopyFromReg t0, Register:i16 %1
t3: i16 = Constant<0>
t5: i8,ch = load<(load 1 from %ir.lsr.iv1, !tbaa !2)> t0, t2, undef:i16
t7: i16,ch = CopyFromReg t0, Register:i16 %2
t10: i16 = add t7, Constant:i16<1>
t12: ch = CopyToReg t0, Register:i16 %3, t10
t13: i16 = add t2, Constant:i16<1>
t15: ch = CopyToReg t0, Register:i16 %4, t13
t17: i16,ch = CopyFromReg t0, Register:i16 %0
t19: i16 = add t17, Constant:i16<-1>
t21: ch = CopyToReg t0, Register:i16 %5, t19
t8: ch = store<(store 1 into %ir.lsr.iv, !tbaa !2)> t5:1, t5, t7, undef:i16
t22: ch = TokenFactor t12, t15, t21, t8
t24: ch = br t22, BasicBlock:ch<for.cond 0x10985e000>

Now, instead of using array indexes with ‘add’ instructions (which can be folded later on into load/store addressing modes), LLVM choses to directly increment the pointers!. This is suboptimal -at least on my architecture- because at this point it’s impossible to select optimal addressing modes. Instead, the pointers must be explicitly incremented with additional instructions as llvm dictates.

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.

Joan Lluch

Hi Joan,

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.

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

Hi,

Hi Tim,

After studying the x86 backend I got it working !

What happens is that considering the following formulas:

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

the RateFormula function is designed to not increment the instruction counter when the second form appears more than once. This is what it gives it some cost advantage over the first form, as I wanted. Now, the x86 takes advantage of this by implementing an unique isLSRCostLess function on its TargetTransformInfo. The isLSRCostLess function compares costs for the Loop Strength Reduction algorithm and there’s a hook to custom implement it. The particular implementation of x86 is the only one (along with the SystemZ) that takes the number of instructions into account and puts that as main cost. All the other targets just rely on the default isLSRCostLess implementation that takes number of registers as priority. So that was it.

So thanks for all your pointers!

Joan Lluch

Hi Joan,