ScalarEvolution Patch

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

ScalarEvolution Patch

John Criswell
Dear All,

Is the following patch to ScalarEvolution correct?  It seems that
without it, the enclosing for loop could skip over SCEVAddRecExpr's in
the Ops[] array.

-- John T.


Index: ScalarEvolution.cpp
===================================================================
--- ScalarEvolution.cpp (revision 47480)
+++ ScalarEvolution.cpp (working copy)
@@ -865,6 +865,7 @@
       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
         LIOps.push_back(Ops[i]);
         Ops.erase(Ops.begin()+i);
+        if (i <= Idx) --Idx;
         --i; --e;
       }
 

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: ScalarEvolution Patch

Dan Gohman-2
That patch looks right to me, though I think you can change
the <= to <, because an addrec won't be invariant in its own
loop. Also, there is similar code in getMulExpr to which this
also applies.

Do you happen to have a testcase affected by this?

Dan

On Feb 22, 2008, at 9:05 AM, John Criswell wrote:

> Dear All,
>
> Is the following patch to ScalarEvolution correct?  It seems that  
> without it, the enclosing for loop could skip over SCEVAddRecExpr's  
> in the Ops[] array.
>
> -- John T.
>
> Index: ScalarEvolution.cpp
> ===================================================================
> --- ScalarEvolution.cpp (revision 47480)
> +++ ScalarEvolution.cpp (working copy)
> @@ -865,6 +865,7 @@
>       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
>         LIOps.push_back(Ops[i]);
>         Ops.erase(Ops.begin()+i);
> +        if (i <= Idx) --Idx;
>         --i; --e;
>       }
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: ScalarEvolution Patch

Wojciech Matyjewicz
In reply to this post by John Criswell
Hi,

> Is the following patch to ScalarEvolution correct?  It seems that
> without it, the enclosing for loop could skip over SCEVAddRecExpr's in
> the Ops[] array.

The patch is correct, but doesn't seem to be necessary. Please note that
if a loop-invariant is found it is not only erased from the Ops[] array,
but also inserted into the LIOps[] one:

  for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
    std::vector<SCEVHandle> LIOps;
    SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
    for (unsigned i = 0, e = Ops.size(); i != e; ++i)
      if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
        LIOps.push_back(Ops[i]);
        Ops.erase(Ops.begin()+i);
        --i; --e;
      }

and just after this code there is an dead-end 'if':

    if (!LIOps.empty()) {
      [...]
      return getAddExpr(Ops);
    }
   [...]
  }

that will never allow the outer 'for' loop to continue, if some loop
invariant was found.

But I admit it's a little bit obscure.

Wojtek

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev