This is an archive of the discontinued LLVM Phabricator instance.

Remove SCEVCache and FindConstantPointers from complete loop unrolling heuristic.
ClosedPublic

Authored by mzolotukhin on Jun 2 2015, 6:19 PM.

Details

Summary

Using some SCEV functionality helped to entirely remove SCEVCache class and FindConstantPointers SCEV visitor.
Also, this makes the code more universal - I'll take advandate of it in next patches where I start handling additional types of instructions.

Diff Detail

Event Timeline

mzolotukhin updated this revision to Diff 27020.Jun 2 2015, 6:19 PM
mzolotukhin retitled this revision from to Remove SCEVCache and FindConstantPointers from complete loop unrolling heuristic..
mzolotukhin updated this object.
mzolotukhin edited the test plan for this revision. (Show Details)
mzolotukhin added a reviewer: chandlerc.
mzolotukhin added a subscriber: Unknown Object (MLST).
atrick accepted this revision.Jun 2 2015, 11:34 PM
atrick added a reviewer: atrick.
atrick added a subscriber: atrick.

Great use of SCEV.

lib/Transforms/Scalar/LoopUnrollPass.cpp
307

"I am"

329

"AddRec"

This revision is now accepted and ready to land.Jun 2 2015, 11:34 PM

Thanks, Andy!

I also want to wait for a response from Chandler since he put a lot of efforts into this code.

Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp
307

There is no typo here, but probably I should've added \param:

/// \brief Try to simplify instruction \param I using its SCEV expression.
329

Thanks for the catch!

mzolotukhin edited edge metadata.
  • Fix typos.
mzolotukhin updated this revision to Diff 27089.Jun 3 2015, 9:52 PM
  • Not only GetElementPtrInst could have a base pointer - allow for that in GEPPointerBases type.
chandlerc requested changes to this revision.Jun 4 2015, 5:13 PM
chandlerc edited edge metadata.

As Andy said, really nice use of SCEV. This is exactly the direction I was hoping for here.

Detailed comments below. Mostly this is about sorting out minor details, naming, and how to cache these things.

lib/Transforms/Scalar/LoopUnrollPass.cpp
281–288

Based on this (very nice) comment, the name should just be "PointerBases"... Or even better, BasePointers. But see below...

315

I think a better name for this would be 'simplifyInstWithSCEV'

326

I'd compute this as part of the constructor (and thus once).

338–339

For pointer types, is this the byte difference or are the units in something other than bytes?

340–341

I don't think this quite works.

The offset value, while constant, is not the simplification of this instruction. For example, if the offset is 2, and we see 'icmp eq' of I and the constant '2', it shouldn't be able to constant fold.

I think you want to store a mapping from instruction to a pair of Value* and Constant*, "BasePointersAndOffsets" or some such. Not sure of a good name here.

361–362

Is this better than constant folding? It's not clear to me that it is, it seems like it might be much more expensive.

I think I would change the *end* of this function to 'if (SimpleV) return true;' and then add a final return that was essentially 'return Base::visitBinaryOperator(I);' so its clear you're just delegating.

387–389

This shouldn't be needed now, right?

407–411

The comment above doesn't make much sense any more. =]

I'd also consider bailing or asserting if the offset requires lots of bits here rather than limiting it.

This revision now requires changes to proceed.Jun 4 2015, 5:13 PM
mzolotukhin updated this revision to Diff 27259.Jun 5 2015, 9:06 PM
mzolotukhin edited edge metadata.
  • Rebase on master.
  • Rename SCEVSimplify to simplifyInstWithSCEV.
  • Use assert + getSExtValue instead of getLimitedValue and remove no
  • Introduce SimplifiedOffsets.
  • Remove unneeded code.
  • Move initialize of IterationNumber to constructor.
  • Doxygenify comment for SimplifiedValues.
  • Fallback to Base visitor if failed to constant fold (and only then call simplifyInstWithSCEV).

This is looking really good. A bunch of minor stuff below. I'm happy for you to just address most of this before it gets committed, but I don't see the definition of 'simplifyUsingOffsets'. That's the only thing I really want to see before LGTM-ing.

lib/Transforms/Scalar/LoopUnrollPass.cpp
270

I think this should just be a ConstantInt, it'll save you casting below.

280–286

I'd call this 'SimplifiedAddresses'. That also corresponds nicely to them being pointers.

325

I would invert this to use early exit.

auto *AR = dyn_cast<SCEVAddRecExpr>(S);
if (!AR)
  return false;

...
333–334

Should we check that I is a pointer? Shouldn't this be dyn_cast_or_null?

341–342

If you're going to assert, you can just write 'cast<ConstantInt>' and it will assert for you.

I think that means you can just write:

SimplifiedOffsets[I] = {Base->getValue(), cast<ConstantInt>(Offset->getValue())};
372

Where is this defined?

390–395

I think I've mentioned this before, but please don't use 'count' and then 'lookup'. It queries the hashtable twice. You should just use 'find' and the iterator.

Hi Chandler,

Thanks for the review! I'll address the concerns and commit the patch soon. Please also find some comments inline:

lib/Transforms/Scalar/LoopUnrollPass.cpp
333–334

No, this is correct.
getPointerBase(S) returns a SCEV expression - if it fails to find the base, it'll return the incoming SCEV expression S. Then, when we try to cast it to SCEVUnknown we get nullptr, which is tested in the following check.
So, the fail condition here is getting not SCEVUnknown.

372

Oops, it crept to the subsequent patch (D10206). I'll move it to this one before committing, but do you mind taking a glance there too?

chandlerc accepted this revision.Jun 5 2015, 11:10 PM
chandlerc edited edge metadata.

See below before committing please.

lib/Transforms/Scalar/LoopUnrollPass.cpp
372

Please commit *without* this change.

I don't think simplifyUsingOffsets is the right approach (as handled in D10206), and I'd rather not hold the rest of this up on that review.

This revision is now accepted and ready to land.Jun 5 2015, 11:10 PM
This revision was automatically updated to reflect the committed changes.

Thanks for review, updated patch landed in r239282.