On Jan 15, 2008, at 1:36 PM, Wojciech Matyjewicz wrote: > The attached patch should fix the aforementioned bug. It passes > DejaGnu > testsuite. Nick also checked that it passes llvm-test and llvm-gcc > bootstrap (thanks!).
Oooh cool! > > The patch: > 1) changes SCEVSDivExpr into SCEVUDivExpr, > 2) replaces PartialFact() function with BinomialCoefficient(); the > computations in BinomialCoefficient() are performed with the > apprioprate > bitwidth necessary to avoid overflow. > > The short explanation why the patch should be correct is contained in > the comments. The longer can be found in the bugzilla discussion: > http://llvm.org/bugs/show_bug.cgi?id=1798. > > However, there is one problem. The fix needs support for integers of > arbitrary bitwitdth to work in every possible case. Here is a short > explanation why: > To evaluate a chrec of length K at a given iteration we need, in > general, to generate LLVM code performing accurate multiplication of K > numbers. Suppose, W is their bitwidth. Then, multiplication need to > use > K*W bits, what can potentially be an arbitrary number. > > I can see two ways what we can do now: > 1) wait for the backend support, > 2) make the patch unoptimal by using the more bits than needed to > perform the multiplication (the minimum power of 2 greater or equal > to K*W) I think we should wait to address this after LLVM 2.2 branches. That said, the short-term fix is to round up to the next power of two (e.g. 32 or 64 bits) and disable this transformation when that size is not a "normal" llvm size (8, 16, 32, 64). Hopefully llvm 2.3 will have real APInt support in the code generator, at which time we can remove these hacks. :) Does this sound reasonable? -Chris _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
