Page MenuHomePhabricator

[LoopInterchange] Fix interchanging contents of preheader BBs

Authored by alexey.zhikhar on Mar 10 2020, 10:12 AM.



Previously LCSSA was getting broken by placing instructions into the
(newly) inner *header* instead of the *pre*header.

Fixes PR43474

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptMar 10 2020, 10:12 AM

CFG before the patch, LCSSA broken:

CFG after the patch, LCSSA preserved:

fhahn added a comment.Mar 11 2020, 5:06 AM

Thanks for the patch! It mostly looks good, just a few small comments inline.


The assertions here might be a bit over-conservative. I think isLCSSAForm can potentially be expensive, so I would be slightly in favor of dropping them.


I think this could just be something like
SmallVector<Instruction *, 4> TempInstrs(BB1->begin(), std::prev(BB1->end()); // Save all non-terminator instructions.


nit: drop unneeded {


nit: drop unneeded {


With adjustLoopPreheaders being so short now, please inline it directly into adjustLoopLinks.


Please update the test to check the IR to ensure the pre-headers are swapped correctly. It would probably be good to check the whole structure. I think you should be able to also reduce the inner loop body a bit (one load/store should be enough).


Please drop the target triple. Otherwise the test will fail when LLVM is built without the X86 backend. And it should not be required for the test.


not needed.


please drop the un-needed things like dso_local, local_unnamed_addr and #0.

Addressed part of Florian's comments.

alexey.zhikhar marked 8 inline comments as done.Mar 11 2020, 10:31 AM
alexey.zhikhar added inline comments.

I saw them in LICM so I thought that there's no harm in adding them to loop interchange. When I first saw the error that this patch aims to fix, it was an assertion in LICM that runs after loop interchange, which was misleading.


That would be nice but it doesn't seem to work, I'm getting error: cannot convert ‘llvm::Instruction’ to ‘llvm::Instruction*’ in initialization.
Instead, I replaced the for-each loop with explicit iterators and stop before when the terminator is encountered.


This is a small thing but it's something that I thought about before and I would appreciate your input. I personally prefer adding braces even when there's only one statement in a loop/if condition since this way it is both easier and less error-prone to add new statements. I also don't see the LLVM guidelines mentioning anything in this regard but, of course, I'll fix this nit if you insist.

fhahn accepted this revision.Mar 12 2020, 5:41 AM

LGTM, with the remaining comments, thanks!


Yes, the assertions after we do the transformations (lines 586 and 588) are very beneficial and should guard against similar error in the future. The ones here mean an earlier pass violated LCSSA and I think it would be slightly preferable to remove them; other passes are responsible for that (and -verify-lcssa can be used to catch those).


Ah right, this is unfortunate.for the iterator version, you could use something like for (auto &I : make_range(BB->begin(), std::prev(BB-end)))

If you use make_early_inc_range, it should be safe to merge the loops adding to TempInstrs and removing I.

Or you could use map_range to get an iterator range that returns Instruction * instead Instruction& like below.

+  auto Iter = map_range(*BB1, [](Instruction &I) { return &I });
+  SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
+  for (Instruction &I : TempInstrs)
+    I.removeFromParent();

Any of the options is fine by me.


I don't think this is explicitly spelled out in the coding standard, but not using unnecessary braces is *very very* common (at least in llvm/ from my experience). IMO this falls under use the style that is already being used so that the source is uniform and easy to follow which is mentioned in the beginning of

As far as I'm aware, the existing code in LoopInterchange.cpp does not use trivial braces (and if it does it's probably by accident) and IMO it would be good for the sake of consistency to keep it like that.

This revision is now accepted and ready to land.Mar 12 2020, 5:41 AM
fhahn added a comment.Mar 12 2020, 7:06 AM

I think it would be good to update the title to highlight the details of the patch, something like: [LoopInterchange] Fix interchanging contents of preheader BBs.

alexey.zhikhar retitled this revision from [LoopInterchange] Do not break LCSSA to [LoopInterchange] Fix interchanging contents of preheader BBs.Mar 12 2020, 9:21 AM

Addressed the rest of Florian's comments.

alexey.zhikhar marked 9 inline comments as done.Mar 12 2020, 9:31 AM
alexey.zhikhar added inline comments.

Oh, I see now. Fixed.


Thanks, I didn't know about these utils. I ended up with using map_range().

fhahn added a comment.Mar 13 2020, 5:09 AM

Looks good, thanks! Please let me know if you need me to commit this on your behalf.

This revision was automatically updated to reflect the committed changes.