[Bug tree-optimization/86136] Modular multiplication optimization

[navidrahimi at microsoft dot com via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86136

Navid Rahimi  changed:

   What|Removed |Added

 CC||navidrahimi at microsoft dot 
com

--- Comment #4 from Navid Rahimi  ---
We can close this bug. Transformation doesn't verify!


Codegen: 
https://compiler-explorer.com/z/Waoz4qaz6

Proof:
https://alive2.llvm.org/ce/z/5H9ahK

[Bug tree-optimization/86136] Modular multiplication optimization

[mcccs at gmx dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86136

--- Comment #3 from MCCCS  ---
What about

unsigned int k (unsigned int a) {
if (a > 5) {
__builtin_unreachable();
}
return (a * 83) % 5;
}

[Bug tree-optimization/86136] Modular multiplication optimization

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86136

Richard Biener  changed:

   What|Removed |Added

 Status|UNCONFIRMED |NEW
   Last reconfirmed||2018-06-14
 Ever confirmed|0   |1

--- Comment #2 from Richard Biener  ---
So

(simplify
 (trunc_mod (mult @0 INTEGER_CST@1) INTEGER_CST@2)
 (trunc_mod (mult @0 (trunc_mod @1 @2)) @2))

if (trunc_mod @1 @2) is smaller than @1.

I suspect this doesn't hold if the multiplication may overflow?

[Bug tree-optimization/86136] Modular multiplication optimization

[mcccs at gmx dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86136

--- Comment #1 from MCCCS  ---
Note: It can notice (a * n) % k = 0 if n is a multiple of k. The bug happens
only if n % k != 0.