On Mon, Oct 12, 2009 at 8:22 PM, Eli Friedman <eli.friedman at gmail.com> wrote:> On Mon, Oct 12, 2009 at 6:15 PM, Villmow, Micah <Micah.Villmow at amd.com> wrote: >> I have a test case(attached as fc_long.ll) that when run through the >> optimizer produces 65bit integer math(fc_long-opt.ll). >> >> >> >> Now I understand that llvm can have any length integer, but I consider >> turning a 64bit mul into multiple 65 bit instructions to be a ‘bad’ >> optimization. This eventually expands to a 128bit multiply call(__multi3) >> which I have absolutely no interest in supporting. So I’m wondering what >> optimization might be the culprit here so I can disable it in this >> situation. > > I'm pretty sure this is the fault of one of the loop passes (I forget > which one off the top of my head). It's worth noting that the > optimizer manages to eliminate the loop; computing the exit value of > one of the loop variables uses the wide multiply.It's -indvars. I ran mem2reg, instcombine, and simplifycfg on your input and got the attached file. I thought I could add "nuw nsw" to the arithmetic inside the loop to say that i65 is unnecessary, but that doesn't cause indvars to leave the arithmetic at i64. Is that a bug in indvars, or in SCEV, or is this just a natural limitation of SCEV? -------------- next part -------------- A non-text attachment was scrubbed... Name: fc_long.ll Type: application/octet-stream Size: 1593 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091012/932523ab/attachment.obj>
On Mon, Oct 12, 2009 at 9:42 PM, Jeffrey Yasskin <jyasskin at google.com> wrote:> On Mon, Oct 12, 2009 at 8:22 PM, Eli Friedman <eli.friedman at gmail.com> wrote: >> On Mon, Oct 12, 2009 at 6:15 PM, Villmow, Micah <Micah.Villmow at amd.com> wrote: >>> I have a test case(attached as fc_long.ll) that when run through the >>> optimizer produces 65bit integer math(fc_long-opt.ll). >>> >>> >>> >>> Now I understand that llvm can have any length integer, but I consider >>> turning a 64bit mul into multiple 65 bit instructions to be a ‘bad’ >>> optimization. This eventually expands to a 128bit multiply call(__multi3) >>> which I have absolutely no interest in supporting. So I’m wondering what >>> optimization might be the culprit here so I can disable it in this >>> situation. >> >> I'm pretty sure this is the fault of one of the loop passes (I forget >> which one off the top of my head). It's worth noting that the >> optimizer manages to eliminate the loop; computing the exit value of >> one of the loop variables uses the wide multiply. > > It's -indvars. I ran mem2reg, instcombine, and simplifycfg on your > input and got the attached file. I thought I could add "nuw nsw" to > the arithmetic inside the loop to say that i65 is unnecessary, but > that doesn't cause indvars to leave the arithmetic at i64. Is that a > bug in indvars, or in SCEV, or is this just a natural limitation of > SCEV?It's a limitation of SCEV; the relevant function is SCEVAddRecExpr::evaluateAtIteration in ScalarEvolution.cpp. -Eli
On Oct 12, 2009, at 9:42 PM, Jeffrey Yasskin wrote:> On Mon, Oct 12, 2009 at 8:22 PM, Eli Friedman > <eli.friedman at gmail.com> wrote: >> On Mon, Oct 12, 2009 at 6:15 PM, Villmow, Micah <Micah.Villmow at amd.com >> > wrote: >>> I have a test case(attached as fc_long.ll) that when run through the >>> optimizer produces 65bit integer math(fc_long-opt.ll). >>> >>> >>> >>> Now I understand that llvm can have any length integer, but I >>> consider >>> turning a 64bit mul into multiple 65 bit instructions to be a ‘bad’ >>> optimization. This eventually expands to a 128bit multiply call >>> (__multi3) >>> which I have absolutely no interest in supporting. So I’m >>> wondering what >>> optimization might be the culprit here so I can disable it in this >>> situation. >> >> I'm pretty sure this is the fault of one of the loop passes (I forget >> which one off the top of my head). It's worth noting that the >> optimizer manages to eliminate the loop; computing the exit value of >> one of the loop variables uses the wide multiply. > > It's -indvars. I ran mem2reg, instcombine, and simplifycfg on your > input and got the attached file. I thought I could add "nuw nsw" to > the arithmetic inside the loop to say that i65 is unnecessary, but > that doesn't cause indvars to leave the arithmetic at i64. Is that a > bug in indvars, or in SCEV, or is this just a natural limitation of > SCEV?LLVM's ScalarEvolution's handling of non-linear recurrences has much room for improvement. The problem Micah describes sounds like the one in lib/Analysis/README.txt. Dan
What does nsw nuw do? Micah -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Dan Gohman Sent: Tuesday, October 13, 2009 10:06 AM To: Jeffrey Yasskin Cc: LLVM Developers Mailing List Subject: Re: [LLVMdev] 65bit integer math On Oct 12, 2009, at 9:42 PM, Jeffrey Yasskin wrote:> On Mon, Oct 12, 2009 at 8:22 PM, Eli Friedman > <eli.friedman at gmail.com> wrote: >> On Mon, Oct 12, 2009 at 6:15 PM, Villmow, Micah<Micah.Villmow at amd.com>> > wrote: >>> I have a test case(attached as fc_long.ll) that when run through the >>> optimizer produces 65bit integer math(fc_long-opt.ll). >>> >>> >>> >>> Now I understand that llvm can have any length integer, but I >>> consider >>> turning a 64bit mul into multiple 65 bit instructions to be a 'bad' >>> optimization. This eventually expands to a 128bit multiply call >>> (__multi3) >>> which I have absolutely no interest in supporting. So I'm >>> wondering what >>> optimization might be the culprit here so I can disable it in this >>> situation. >> >> I'm pretty sure this is the fault of one of the loop passes (I forget >> which one off the top of my head). It's worth noting that the >> optimizer manages to eliminate the loop; computing the exit value of >> one of the loop variables uses the wide multiply. > > It's -indvars. I ran mem2reg, instcombine, and simplifycfg on your > input and got the attached file. I thought I could add "nuw nsw" to > the arithmetic inside the loop to say that i65 is unnecessary, but > that doesn't cause indvars to leave the arithmetic at i64. Is that a > bug in indvars, or in SCEV, or is this just a natural limitation of > SCEV?LLVM's ScalarEvolution's handling of non-linear recurrences has much room for improvement. The problem Micah describes sounds like the one in lib/Analysis/README.txt. Dan _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev