Fixed one more case with PRE, updated tests accordingly.

Nits.

Factored the filling of implicit control flow map out of main iteration loop.

Added some tests, changed commit message.

Reused isGuaranteedToTransferExecutionToSuccessor, added some clarifying comments. In this version of patch, we explicitly allow hoisting across volatile loads/stores. Given the discussion here, we might want to modify isGuaranteedToTransferExecutionToSuccessor so that it returns true for volatile loads/stores. Once the ongoing discussion on volatiles comes to some conclusion, this part can be reworked.

Cleaning between iterations now.

Need to clean guard set between iterations, not one time in the end.

The expected size of set of blocks with guards is actually small, so cleaning should be cheap. Could you please approve the patch for merge?

Actually we don't even need OrderedInstructions to do that. It's enough to maintain a set of blocks where we have ever seen the guards. We iterate through blocks in reverse postorder which guarantees us that if a block has one predecessor it will be visited before the block. We also traverse block instructions in direct order. Using this, we just mark a block as having a guard when we meet one and know for sure that:

Fixed buggy tests & code, added a new test.

This one was reverted due to found bug, I'm working on fix.

Thanks for the detailed clarification! I will do that.

1. Removed assumes-related stuff.
2. Added a motivating test and comment.
3. Daniel, I didn't get what you mean under using ordered instructions to do this stuff. OrderedInstructions can only answer if a particular guard dominates our load. It will still take linear time to gather the guards, and for them we know for sure that they dominate the load and don't basically need to ask anything from OrderdeInstructions. I used any_of to speed the things up, but don't see any way to reduce complexity.

I need to read what C++ specification says about this particular issue, but basically LLVM is not only used to compile C++. This situation can be illegal in other languages (again, need to dig more through specifications). My proposal is to add an option that prohibits this transform and set it to false by default, with abitily to turn it off for languages where it is prohibited.

Hi Daniel,

Fixed formatting.

LGTM with nits: use isa for boolean type checks, not dyn_cast.

Code part looks ok for me (with comments addressed). I propose you to add a C++ unit test.

Rebased, moved tests to existing test file, fixed the wrap check,

Oh. My bad. Re-uploaded version with context.

Added some clarifying comments & tests.

Renamed test's blocks.

Fixed the problem with incorrect end value in changeIterationSpaceEnd, updated tests wrt this change.

One more (rare) failure was found on internal testing. Need to investigate it. Also need to extend the test base.

Split into two parts (NFC rename and new logic) to make it easier to review.

Ping

Fixed the bug that was found on internal testing, extended tests.

Addressed nits, reworked tests so that now they check the structure of transformed loop, not only the fact that the transformation has happened.

Our internal testing has detected some bugs with this patch, so I will fix them and re-submit the fixed version.

Seems that I've missed the comment here.

Rebased after underlying patch update, added comments.

Reworked tests, made some refactoring, addressed TODOs.

Now we don't throw away the exit limit for sake of a more optimistic future estimation every time we calculate getBackedgeTakenInfo. It doesn't look like estimation of Exit Limit for a particular exit block may be improved from what we have there.

Needs update to pass its own test within reasonable time.

I just realized that the attached IR test takes unreasonably long time with this fix, what makes the entire patch pointless.