Missed pattern 0 modulo/div/mul N in phi

[davidbolvansky]

Bugzilla Link	38479
Version	trunk
OS	Linux
CC	@efriedma-quic,@LebedevRI,@RKSimon,@rotateright

Extended Description

unsigned int hash_function(const char *str, unsigned hash_tab_size) {
unsigned int h = 0;
const unsigned char *p;
for (p = (const unsigned char *) str; *p != '\0'; p++)
h = 65599 * h + *p;
return h % hash_tab_size;
// return h / hash_tab_size;
// return h * hash_tab_size;
// similar code generation
}

Lets say p[0] is \0 -> .LBB0_1

Latest trunk, O3:
hash_function(char const*, unsigned int): # @​hash_function(char const*, unsigned int)
mov cl, byte ptr [rdi]
test cl, cl
je .LBB0_1
add rdi, 1
xor eax, eax
.LBB0_3: # =>This Inner Loop Header: Depth=1
movzx ecx, cl
imul eax, eax, 65599
add eax, ecx
movzx ecx, byte ptr [rdi]
add rdi, 1
test cl, cl
jne .LBB0_3
xor edx, edx
div esi
mov eax, edx
ret
.LBB0_1:
xor eax, eax
xor edx, edx
div esi // useless
mov

I believe these are important lines in the IR:
%16 = phi i32 [ 0, %2 ], [ %11, %5 ]
%17 = urem i32 %16, %1
ret i32 %17

In this case we should expand/simplify phi and remove "0 urem %1"

[davidbolvansky]

This might be a bigger optimization opportunity for phis

%16 = phi i32 [ 0, %2 ], [ %11, %5 ]
%17 = urem i32 %16, %1

Now create "urem i32 0, %1" and "urem i32 %11, %1". Then call SimplifyInstruction on them. If simplified, update phi.

---->

%15 = urem i32 %11, %1
%16 = phi i32 [ 0, %2 ], [ %15, %5 ]

Thoughts?

[rotateright]

This might be a bigger optimization opportunity for phis

%16 = phi i32 [ 0, %2 ], [ %11, %5 ]
%17 = urem i32 %16, %1

Now create "urem i32 0, %1" and "urem i32 %11, %1". Then call
SimplifyInstruction on them. If simplified, update phi.

---->

%15 = urem i32 %11, %1
%16 = phi i32 [ 0, %2 ], [ %15, %5 ]

Thoughts?

Not sure if that's desirable in general or even possible in this case.

1. Hoisting the binop would mean it's in the loop rather than after the loop?

2. div/rem are not speculatable, so I don't think it's safe to move those ahead of a phi.

[davidbolvansky]

If not the general case, I would like to solve at least the original case I reported.

[efriedma-quic]

instcombine has foldOpIntoPhi which usually does this sort of transform. InstCombiner::commonIDivTransforms calls it when the RHS of the divide is constant. Not sure we currently call it at all for remainder, but it would be easy to handle a constant remainder.

foldOpIntoPhi currently only triggers code when there isn't a critical edge, so it won't hoist into a loop or anything like that. (I think this is more for performance, not correctness, but it does what we want anyway.) I think we run instcombine on loops in loop-simplify form at some point, which doesn't have the critical edge in question, so it's probably not important. Or we could do the transform somewhere else that's allowed to break critical edges.

foldOpIntoPhi does not have a strong check to ensure it isn't introducing instructions which might not execute otherwise, though: it doesn't check for control flow, or for calls which might trap. So it would need some changes to handle a remainder with a non-constant RHS.

[davidbolvansky]

It needs to be general somehow..
%16 = phi i32 [ 0, %2 ], [ %11, %5 ]
%17 = add i32 %16, %1

We need to check if phi value is bin op identity constant to fold it away.

"2. div/rem are not speculatable, so I don't think it's safe to move those ahead of a phi."

So for e.g. add is this allowed transformation?

%16 = add i32 %15, %1
%17 = phi i32 [ 0, %2 ], [ %16, %5 ]

For div/rem (not speculatable) what optimized IR should look like?

[efriedma-quic]

We need to check if phi value is bin op identity constant to fold it away.

We can call SimplifyBinOp.

[davidbolvansky]

Sadly, for motivating case - "hash_function" it really means to hoist binop to the loop :/

Not sure how this could be solved on generic IR level.. Only solution is to solve it on Machine IR level?

[davidbolvansky]

Seems like we miss 0 rem/div X folds in DAG.

https://godbolt.org/z/XoJBo4

After we "expand" phi, maybe the new DAG folds would handle it.. I will check it.

[davidbolvansky]

https://reviews.llvm.org/D52504

But sadly it does not help here.

[efriedma-quic]

Sadly, for motivating case - "hash_function" it really means to hoist binop
to the loop :/

Is there a critical edge here? Should be possible to break it at some point.

[davidbolvansky]

In the end, we don't have any critical edges since Simplify CFG removes them.

*** IR Dump After Loop Invariant Code Motion ***
; Preheader:
for.body.lr.ph: ; preds = %entry
br label %for.body

; Loop:
for.body: ; preds = %for.body.lr.ph, %for.body
%1 = phi i8 [ %0, %for.body.lr.ph ], [ %2, %for.body ]
%p.09 = phi i8* [ %str, %for.body.lr.ph ], [ %incdec.ptr, %for.body ]
%h.08 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
%conv = zext i8 %1 to i32
%mul = mul i32 %h.08, 65599
%add = add i32 %conv, %mul
%incdec.ptr = getelementptr inbounds i8, i8* %p.09, i64 1
%2 = load i8, i8* %incdec.ptr, align 1, !tbaa !​2
%cmp = icmp eq i8 %2, 0
br i1 %cmp, label %for.cond.for.end_crit_edge, label %for.body

; Exit blocks
for.cond.for.end_crit_edge: ; preds = %for.body
%split = phi i32 [ %add, %for.body ]
br label %for.end
*** IR Dump After Unswitch loops ***
; Preheader:
for.body.lr.ph: ; preds = %entry
br label %for.body

; Loop:
for.body: ; preds = %for.body.lr.ph, %for.body
%1 = phi i8 [ %0, %for.body.lr.ph ], [ %2, %for.body ]
%p.09 = phi i8* [ %str, %for.body.lr.ph ], [ %incdec.ptr, %for.body ]
%h.08 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
%conv = zext i8 %1 to i32
%mul = mul i32 %h.08, 65599
%add = add i32 %conv, %mul
%incdec.ptr = getelementptr inbounds i8, i8* %p.09, i64 1
%2 = load i8, i8* %incdec.ptr, align 1, !tbaa !​2
%cmp = icmp eq i8 %2, 0
br i1 %cmp, label %for.cond.for.end_crit_edge, label %for.body

; Exit blocks
for.cond.for.end_crit_edge: ; preds = %for.body
%split = phi i32 [ %add, %for.body ]
br label %for.end

*** IR Dump After Simplify the CFG ***
; Function Attrs: norecurse nounwind readonly uwtable
define dso_local i32 @​hash_function(i8* nocapture readonly %str, i32 %hash_tab_size) local_unnamed_addr #​0 {
entry:
%0 = load i8, i8* %str, align 1, !tbaa !​2
%cmp7 = icmp eq i8 %0, 0
br i1 %cmp7, label %for.end, label %for.body

for.body: ; preds = %entry, %for.body
%1 = phi i8 [ %2, %for.body ], [ %0, %entry ]
%p.09 = phi i8* [ %incdec.ptr, %for.body ], [ %str, %entry ]
%h.08 = phi i32 [ %add, %for.body ], [ 0, %entry ]
%conv = zext i8 %1 to i32
%mul = mul i32 %h.08, 65599
%add = add i32 %conv, %mul
%incdec.ptr = getelementptr inbounds i8, i8* %p.09, i64 1
%2 = load i8, i8* %incdec.ptr, align 1, !tbaa !​2
%cmp = icmp eq i8 %2, 0
br i1 %cmp, label %for.end, label %for.body

for.end: ; preds = %for.body, %entry
%h.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
%rem = urem i32 %h.0.lcssa, %hash_tab_size
ret i32 %rem
}