Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
Nick Lewycky wrote: After your question, I have realized that 32 bits for the divisor may be too much... Using only 16 bits would allow us to handle AddRecs up to length 8. If you agree 16 is a safe bitwidth, I'll change it. However, the maximum operation you ask about will still be necessary. Optimally, we'd use APInt and get the right length up front, but there's no need for that to hold up this patch. Ok. I've added a comment for that. I've also lifted the restriction that the dividend should be at least 32 bits wide. Currently, the dividend is computed with the minimum necessary bitwidth and extended, if needed, just before the division. The patch is here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080211/058097.html I think it's a good idea to keep the PR open. It will prevent us from forgetting to turn off the hack in future... Wojtek ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
On Feb 9, 2008, at 9:26 AM, Wojciech Matyjewicz wrote: Hi, I've attached an updated version of the patch. It is ready for using support for APInts in the code generator, but currently it doesn't rely on this feature. I've added a hack that rounds up the computation bitwidth to power of 2 (only these bitwidths are allowed: 1, 2, ..., 64). Hack is visible and very easy to remove in future. Is it safe to commit it now? The patch looks good to me. Nicholas, can you please review it also? If Nicholas likes it, please commit, -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
Chris Lattner wrote: On Feb 9, 2008, at 9:26 AM, Wojciech Matyjewicz wrote: Hi, I've attached an updated version of the patch. It is ready for using support for APInts in the code generator, but currently it doesn't rely on this feature. I've added a hack that rounds up the computation bitwidth to power of 2 (only these bitwidths are allowed: 1, 2, ..., 64). Hack is visible and very easy to remove in future. Is it safe to commit it now? The patch looks good to me. Nicholas, can you please review it also? If Nicholas likes it, please commit, Just one question, + const IntegerType *ExTy = IntegerType::get(std::max(DividendBits, 32U)); why the max of DividendBits and 32? If for whatever reason we think we need only 16 bits for the computation, why expand it to 32? Nick ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
Nick Lewycky wrote: Just one question, + const IntegerType *ExTy = IntegerType::get(std::max(DividendBits, 32U)); why the max of DividendBits and 32? If for whatever reason we think we need only 16 bits for the computation, why expand it to 32? We compute the divisor of the BC formula using 32-bit arithmetic. Hence, this is the lower bound for the bitwitdh of the division, and the dividend as well. After your question, I have realized that 32 bits for the divisor may be too much... Using only 16 bits would allow us to handle AddRecs up to length 8. If you agree 16 is a safe bitwidth, I'll change it. However, the maximum operation you ask about will still be necessary. The other way is to compute the dividend with the minimum bitwidth (say, 8), and then zero-extend it to 16 (32 withouth the above change) if necessary just before performing the division. But wouldn't it be an overkill? Wojtek ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
Wojciech Matyjewicz wrote: Nick Lewycky wrote: Just one question, + const IntegerType *ExTy = IntegerType::get(std::max(DividendBits, 32U)); why the max of DividendBits and 32? If for whatever reason we think we need only 16 bits for the computation, why expand it to 32? We compute the divisor of the BC formula using 32-bit arithmetic. Hence, this is the lower bound for the bitwitdh of the division, and the dividend as well. That makes sense. After your question, I have realized that 32 bits for the divisor may be too much... Using only 16 bits would allow us to handle AddRecs up to length 8. If you agree 16 is a safe bitwidth, I'll change it. However, the maximum operation you ask about will still be necessary. Optimally, we'd use APInt and get the right length up front, but there's no need for that to hold up this patch. Nick ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
Small correction: (only these bitwidths are allowed: 1, 2, ..., 64). Should be: 32, 64. -Wojtek ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] Fix for PR1798 (ScalarEvolution)
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!).
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)
What do you think?
-Wojtek
Index: test/Analysis/ScalarEvolution/2007-11-14-SignedAddRec.ll
===
--- test/Analysis/ScalarEvolution/2007-11-14-SignedAddRec.ll(revision 46007)
+++ test/Analysis/ScalarEvolution/2007-11-14-SignedAddRec.ll(working copy)
@@ -1,6 +1,5 @@
; RUN: llvm-as %s | opt -indvars | llvm-dis | grep printd | grep 1206807378
; PR1798
-; XFAIL: *
declare void @printd(i32)
Index: include/llvm/Analysis/ScalarEvolutionExpander.h
===
--- include/llvm/Analysis/ScalarEvolutionExpander.h (revision 46007)
+++ include/llvm/Analysis/ScalarEvolutionExpander.h (working copy)
@@ -126,10 +126,10 @@
Value *visitMulExpr(SCEVMulExpr *S);
-Value *visitSDivExpr(SCEVSDivExpr *S) {
+Value *visitUDivExpr(SCEVUDivExpr *S) {
Value *LHS = expand(S-getLHS());
Value *RHS = expand(S-getRHS());
- return InsertBinop(Instruction::SDiv, LHS, RHS, InsertPt);
+ return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
}
Value *visitAddRecExpr(SCEVAddRecExpr *S);
Index: include/llvm/Analysis/ScalarEvolution.h
===
--- include/llvm/Analysis/ScalarEvolution.h (revision 46007)
+++ include/llvm/Analysis/ScalarEvolution.h (working copy)
@@ -225,7 +225,7 @@
Ops.push_back(RHS);
return getMulExpr(Ops);
}
-SCEVHandle getSDivExpr(const SCEVHandle LHS, const SCEVHandle RHS);
+SCEVHandle getUDivExpr(const SCEVHandle LHS, const SCEVHandle RHS);
SCEVHandle getAddRecExpr(const SCEVHandle Start, const SCEVHandle Step,
const Loop *L);
SCEVHandle getAddRecExpr(std::vectorSCEVHandle Operands,
Index: include/llvm/Analysis/ScalarEvolutionExpressions.h
===
--- include/llvm/Analysis/ScalarEvolutionExpressions.h (revision 46007)
+++ include/llvm/Analysis/ScalarEvolutionExpressions.h (working copy)
@@ -25,7 +25,7 @@
// These should be ordered in terms of increasing complexity to make the
// folders simpler.
scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
-scSDivExpr, scAddRecExpr, scSMaxExpr, scUnknown, scCouldNotCompute
+scUDivExpr, scAddRecExpr, scSMaxExpr, scUnknown, scCouldNotCompute
};
//======//
@@ -322,16 +322,16 @@
//======//
- /// SCEVSDivExpr - This class represents a binary signed division operation.
+ /// SCEVUDivExpr - This class represents a binary unsigned division
operation.
///
- class SCEVSDivExpr : public SCEV {
+ class SCEVUDivExpr : public SCEV {
friend class ScalarEvolution;
SCEVHandle LHS, RHS;
-SCEVSDivExpr(const SCEVHandle lhs, const SCEVHandle rhs)
- : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {}
+SCEVUDivExpr(const SCEVHandle lhs, const SCEVHandle rhs)
+ : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
-virtual ~SCEVSDivExpr();
+virtual ~SCEVUDivExpr();
public:
const SCEVHandle getLHS() const { return LHS; }
const SCEVHandle getRHS() const { return RHS; }
@@ -353,7 +353,7 @@
if (L == LHS R == RHS)
return this;
else
-return SE.getSDivExpr(L, R);
+return SE.getUDivExpr(L, R);
}
@@ -363,9 +363,9 @@
void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
-static inline bool classof(const SCEVSDivExpr *S) { return true; }
+static inline bool classof(const
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
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
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
Chris Lattner wrote: 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? Yes, it does. I'll add the hacks and commit the patch after LLVM 2.2 release. -Wojtek ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Fix for PR1798 (ScalarEvolution)
On Jan 15, 2008, at 11:29 PM, Wojciech Matyjewicz wrote: Chris Lattner wrote: 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? Yes, it does. I'll add the hacks and commit the patch after LLVM 2.2 release. Thanks! -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
