Silviu Baranga
2015-Apr-29 17:06 UTC
[LLVMdev] [RFC][Float2Int] Converting (fcmp Pred, x * F, y) to (ICmp ...)
Hi, I'm trying expand the Float2Int pass in order to make it able to optimize expressions like f * x > y, where x and y are integers (we'll assume unsigned for simplicity) and f is a floating point constant. The optimization would convert the expression to something like: (a * x)/b > y where a and b are integers guessed by the compiler (currently using continued fractions, but some other method could also be used). The exact expression would depend on the comparison type and on the type of input integers. Note that dividing by an integer constant should be a cheap operation compared to FP multiplication and comparison as this would get lowered to a multiply+subtract+shift sequence (and should certainly be true on cores with no FP unit) The change will add some machinery to Float2Int in order to be able to match certain known patterns. All patterns will have exactly representable inputs and outputs. In this case, the FCMP will have two inputs, x and y and one output (the result of the comparison). This allows us to use the existing Float2Int infrastructure to track the integer length that would be required for the conversion. The main difficulty I can see with this is validating the transformation. Ideally the property that we want to prove for the guessed integers a and b would be that (a*x)/b == round_to_zero(f * to_float(x)), for every integer x in a given range. The problem with this is that we would need to come up with a reasonably quick method of proving this. My best guess (still need to work out the exact details) would be that we only need to check the first and last b numbers of the range. A hand-wavy argument for this would be that since errors increase on the extremities of the range, so if an error appears anywhere it must also appear at the edges of the range. I still need to prove this. If there are any floating-point experts that can help with this, I would greatly appreciate it. Any other comments about the overall merits of the idea and the approach are of course also welcome! Thanks, Silviu -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150429/dbf6769e/attachment.html>
Matt Arsenault
2015-Apr-29 18:33 UTC
[LLVMdev] [RFC][Float2Int] Converting (fcmp Pred, x * F, y) to (ICmp ...)
> On Apr 29, 2015, at 10:06 AM, Silviu Baranga <Silviu.Baranga at arm.com> wrote: > > Note that dividing by an integer constant should be a cheap operation > compared to FP multiplication and comparison as this would get lowered to a > multiply+subtract+shift sequence (and should certainly be true on cores with no > FP unit) >This is not true on the targets I care about. The integer division (which, even with the division by constant expansion to multiplies with magic constants) would be significantly more expensive. -Matt -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150429/b474877f/attachment.html>
Stephen Canon
2015-Apr-29 19:00 UTC
[LLVMdev] [RFC][Float2Int] Converting (fcmp Pred, x * F, y) to (ICmp ...)
> On Apr 29, 2015, at 2:33 PM, Matt Arsenault <arsenm2 at gmail.com> wrote: > >> On Apr 29, 2015, at 10:06 AM, Silviu Baranga <Silviu.Baranga at arm.com <mailto:Silviu.Baranga at arm.com>> wrote: >> >> Note that dividing by an integer constant should be a cheap operation >> compared to FP multiplication and comparison as this would get lowered to a >> multiply+subtract+shift sequence (and should certainly be true on cores with no >> FP unit) >> > > This is not true on the targets I care about. The integer division (which, even with the division by constant expansion to multiplies with magic constants) would be significantly more expensive.What targets *does* this benefit? Soft-float targets and Cortex-A8? Anyway, both integer and floating-point multiplication and division are monotonic, so it suffices to check the two values of x that bracket y/f. – Steve -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150429/bbf3325e/attachment.html>
Seemingly Similar Threads
- [LLVMdev] [RFC][Float2Int] Converting (fcmp Pred, x * F, y) to (ICmp ...)
- [cfe-dev] [libunwind] __ELF__ macro for arm-none-eabi
- [cfe-dev] [libunwind] __ELF__ macro for arm-none-eabi
- [cfe-dev] [libunwind] __ELF__ macro for arm-none-eabi
- [LLVMdev] About the partial update clearence / dependency breaking mechanism