[UnrollRuntime] Fix domTree failures in multiexit unrolling

Summary:
This fixes the IDom for exit blocks and all blocks reachable from the exit blocks, when runtime unrolling under multiexit/exiting

[UnrollRuntime] Fix domTree failures in multiexit unrolling

Summary:
This fixes the IDom for exit blocks and all blocks reachable from the exit blocks, when runtime unrolling under multiexit/exiting case.
We initially had a restrictive check that the IDom is only updated when
it is the header of the loop.
However, we also need to update the IDom to the correct one when the
IDom is any block within the original loop. See added test cases (which
fail dom tree verification without the patch).

Reviewers: reames, mzolotukhin, mkazantsev, hfinkel

Reviewed by: brzycki, kuhar

Subscribers: zzheng, dmgreen, llvm-commits

Differential Revision: https://reviews.llvm.org/D56284

llvm-svn: 350640

show more ...

[UnrollRuntime] Move the DomTree verification under expensive checks

Suggested by Hal as done in r349871.

llvm-svn: 350349

[UnrollRuntime] Add DomTree verification under debug mode

NFC: This adds the dom tree verification under debug mode at a point
just before we start unrolling the loop. This allows us to verify dom
t

[UnrollRuntime] Add DomTree verification under debug mode

NFC: This adds the dom tree verification under debug mode at a point
just before we start unrolling the loop. This allows us to verify dom
tree at a state where it is much smaller and before the unrolling
actually happens.
This also implies we do not need to run -verify-dom-info everytime to
see if the DT is in a valid state when we transform the loop for runtime
unrolling.

llvm-svn: 350334

show more ...

[UnrollRuntime] NFC: Add comment and verify LCSSA

Added -verify-loop-lcssa to test cases.
Updated comments in ConnectProlog.

llvm-svn: 350131

[RuntimeUnrolling] NFC: Add TODO and comments in connectProlog

Currently, runtime unrolling does not support loops where multiple
exiting blocks exit to the latchExit. Added TODO and other code
clar

[RuntimeUnrolling] NFC: Add TODO and comments in connectProlog

Currently, runtime unrolling does not support loops where multiple
exiting blocks exit to the latchExit. Added TODO and other code
clarifications for ConnectProlog code.

llvm-svn: 349944

show more ...

[Unroll/UnrollAndJam/Vectorizer/Distribute] Add followup loop attributes.

When multiple loop transformation are defined in a loop's metadata, their order of execution is defined by the order of thei

[Unroll/UnrollAndJam/Vectorizer/Distribute] Add followup loop attributes.

When multiple loop transformation are defined in a loop's metadata, their order of execution is defined by the order of their respective passes in the pass pipeline. For instance, e.g.

#pragma clang loop unroll_and_jam(enable)
#pragma clang loop distribute(enable)

is the same as

#pragma clang loop distribute(enable)
#pragma clang loop unroll_and_jam(enable)

and will try to loop-distribute before Unroll-And-Jam because the LoopDistribute pass is scheduled after UnrollAndJam pass. UnrollAndJamPass only supports one inner loop, i.e. it will necessarily fail after loop distribution. It is not possible to specify another execution order. Also,t the order of passes in the pipeline is subject to change between versions of LLVM, optimization options and which pass manager is used.

This patch adds 'followup' attributes to various loop transformation passes. These attributes define which attributes the resulting loop of a transformation should have. For instance,

!0 = !{!0, !1, !2}
!1 = !{!"llvm.loop.unroll_and_jam.enable"}
!2 = !{!"llvm.loop.unroll_and_jam.followup_inner", !3}
!3 = !{!"llvm.loop.distribute.enable"}

defines a loop ID (!0) to be unrolled-and-jammed (!1) and then the attribute !3 to be added to the jammed inner loop, which contains the instruction to distribute the inner loop.

Currently, in both pass managers, pass execution is in a fixed order and UnrollAndJamPass will not execute again after LoopDistribute. We hope to fix this in the future by allowing pass managers to run passes until a fixpoint is reached, use Polly to perform these transformations, or add a loop transformation pass which takes the order issue into account.

For mandatory/forced transformations (e.g. by having been declared by #pragma omp simd), the user must be notified when a transformation could not be performed. It is not possible that the responsible pass emits such a warning because the transformation might be 'hidden' in a followup attribute when it is executed, or it is not present in the pipeline at all. For this reason, this patche introduces a WarnMissedTransformations pass, to warn about orphaned transformations.

Since this changes the user-visible diagnostic message when a transformation is applied, two test cases in the clang repository need to be updated.

To ensure that no other transformation is executed before the intended one, the attribute `llvm.loop.disable_nonforced` can be added which should disable transformation heuristics before the intended transformation is applied. E.g. it would be surprising if a loop is distributed before a #pragma unroll_and_jam is applied.

With more supported code transformations (loop fusion, interchange, stripmining, offloading, etc.), transformations can be used as building blocks for more complex transformations (e.g. stripmining+stripmining+interchange -> tiling).

Reviewed By: hfinkel, dmgreen

Differential Revision: https://reviews.llvm.org/D49281
Differential Revision: https://reviews.llvm.org/D55288

llvm-svn: 348944

show more ...

[LoopUnroll] Add check to Latch's terminator in UnrollRuntimeLoopRemainder

In this patch, I'm adding an extra check to the Latch's terminator in llvm::UnrollRuntimeLoopRemainder,
similar to how it i

[LoopUnroll] Add check to Latch's terminator in UnrollRuntimeLoopRemainder

In this patch, I'm adding an extra check to the Latch's terminator in llvm::UnrollRuntimeLoopRemainder,
similar to how it is already done in the llvm::UnrollLoop.

The compiler would crash if this function is called with a malformed loop.

Patch by Rodrigo Caetano Rocha!

Differential Revision: https://reviews.llvm.org/D51486

llvm-svn: 342958

show more ...

Update MemorySSA in BasicBlockUtils.

Summary:
Extend BasicBlocksUtils to update MemorySSA.

Subscribers: sanjoy, arsenm, nhaehnle, jlebar, Prazek, llvm-commits

Differential Revision: https://review

Update MemorySSA in BasicBlockUtils.

Summary:
Extend BasicBlocksUtils to update MemorySSA.

Subscribers: sanjoy, arsenm, nhaehnle, jlebar, Prazek, llvm-commits

Differential Revision: https://reviews.llvm.org/D45300

llvm-svn: 340365

show more ...

Use SmallPtrSet explicitly for SmallSets with pointer types (NFC).

Currently SmallSet<PointerTy> inherits from SmallPtrSet<PointerTy>. This
patch replaces such types with SmallPtrSet, because IMO it

Use SmallPtrSet explicitly for SmallSets with pointer types (NFC).

Currently SmallSet<PointerTy> inherits from SmallPtrSet<PointerTy>. This
patch replaces such types with SmallPtrSet, because IMO it is slightly
clearer and allows us to get rid of unnecessarily including SmallSet.h

Reviewers: dblaikie, craig.topper

Reviewed By: dblaikie

Differential Revision: https://reviews.llvm.org/D47836

llvm-svn: 334492

show more ...

Rename DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/

Rename DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g'
- git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM
- Manual change to APInt
- Manually chage DOCS as regex doesn't match it.

In the transition period the DEBUG() macro is still present and aliased
to the LLVM_DEBUG() one.

Differential Revision: https://reviews.llvm.org/D43624

llvm-svn: 332240

show more ...

[LoopUnroll] Fix potentially incorrect SCEV invalidation in UnrollRuntime

Current runtime unrolling invalidates parent loop saying that it might have changed
after the inner loop has changed, but it

[LoopUnroll] Fix potentially incorrect SCEV invalidation in UnrollRuntime

Current runtime unrolling invalidates parent loop saying that it might have changed
after the inner loop has changed, but it doesn't bother to do the same to its parents.
With patch rL329047, SCEV becomes much smarter about calculation of exit counts for
outer loops. We might need to invalidate not only the immediate parent, but also
any of its parents as well.

There is no clear evidence that there is some miscompile happening because of this
(at least I don't have such test), but the common sense says that the current code
is wrong.

Differential Revision: https://reviews.llvm.org/D45940
Reviewed By: chandlerc

llvm-svn: 330577

show more ...

Transforms: Introduce Transforms/Utils.h rather than spreading the declarations amongst Scalar.h and IPO.h

Fixes layering - Transforms/Utils shouldn't depend on including a Scalar
or IPO header, bec

Transforms: Introduce Transforms/Utils.h rather than spreading the declarations amongst Scalar.h and IPO.h

Fixes layering - Transforms/Utils shouldn't depend on including a Scalar
or IPO header, because Scalar and IPO depend on Utils.

llvm-svn: 328717

show more ...

Use phi ranges to simplify code. No functionality change intended.

llvm-svn: 321585

[Unroll][DebugInfo] Propagate loop body's debug location to epilog preheader

NewExit and epilog PreHeader should has the same debug loc as the original loop
body, instead of original loop exit.

llv

[Unroll][DebugInfo] Propagate loop body's debug location to epilog preheader

NewExit and epilog PreHeader should has the same debug loc as the original loop
body, instead of original loop exit.

llvm-svn: 321465

show more ...

Remove redundant includes from lib/Transforms.

llvm-svn: 320628

[LoopUnroll] Clean up remarks for unroll remainder

The optimisation remarks for loop unrolling with an unrolled remainder looks something like:

test.c:7:18: remark: completely unrolled loop with 3

[LoopUnroll] Clean up remarks for unroll remainder

The optimisation remarks for loop unrolling with an unrolled remainder looks something like:

test.c:7:18: remark: completely unrolled loop with 3 iterations [-Rpass=loop-unroll]
C[i] += A[i*N+j];
^
test.c:6:9: remark: unrolled loop by a factor of 4 with run-time trip count [-Rpass=loop-unroll]
for(int j = 0; j < N; j++)
^
This removes the first of the two messages.

Differential revision: https://reviews.llvm.org/D38725

llvm-svn: 316986

show more ...

[LoopInfo][Refactor] Make SetLoopAlreadyUnrolled a member function of the Loop Pass, NFC.

This avoid code duplication and allow us to add the disable unroll metadata elsewhere.

Differential Revisio

[LoopInfo][Refactor] Make SetLoopAlreadyUnrolled a member function of the Loop Pass, NFC.

This avoid code duplication and allow us to add the disable unroll metadata elsewhere.

Differential Revision: https://reviews.llvm.org/D38928

llvm-svn: 315850

show more ...

[RuntimeUnroll] Add heuristic for unrolling multi-exit loop

Add a profitability heuristic to enable runtime unrolling of multi-exit
loop: There can be atmost two unique exit blocks for the loop and

[RuntimeUnroll] Add heuristic for unrolling multi-exit loop

Add a profitability heuristic to enable runtime unrolling of multi-exit
loop: There can be atmost two unique exit blocks for the loop and the
second exit block should be a deoptimizing block. Also, there can be one
other exiting block other than the latch exiting block. The reason for
the latter is so that we limit the number of branches in the unrolled
code to being at most the unroll factor. Deoptimizing blocks are rarely
taken so these additional number of branches created due to the
unrolling are predictable, since one of their target is the deopt block.

Reviewers: apilipenko, reames, evstupac, mkuper

Subscribers: llvm-commits

Reviewed by: reames

Differential Revision: https://reviews.llvm.org/D35380

llvm-svn: 313363

show more ...

[RuntimeUnrolling] Populate the VMap entry correctly when default generated through lookup

During runtime unrolling on loops with multiple exits, we update the
exit blocks with the correct phi value

[RuntimeUnrolling] Populate the VMap entry correctly when default generated through lookup

During runtime unrolling on loops with multiple exits, we update the
exit blocks with the correct phi values from both original and remainder
loop.
In this process, we lookup the VMap for the mapped incoming phi values,
but did not update the VMap if a default entry was generated in the VMap
during the lookup. This default value is generated when constants or
values outside the current loop are looked up.
This patch fixes the assertion failure when null entries are present in
the VMap because of this lookup. Added a testcase that showcases the
problem.

llvm-svn: 313358

show more ...

[LoopUnroll][DebugInfo] Don't add metadata to unrolled remainder loop

Debug information can be, and was, corrupted when the runtime
remainder loop was fully unrolled. This is because a !null node ca

[LoopUnroll][DebugInfo] Don't add metadata to unrolled remainder loop

Debug information can be, and was, corrupted when the runtime
remainder loop was fully unrolled. This is because a !null node can
be created instead of a unique one describing the loop. In this case,
the original node gets incorrectly updated with the NewLoopID
metadata.

In the case when the remainder loop is going to be quickly fully
unrolled, there isn't the need to add loop metadata for it anyway.

Differential Revision: https://reviews.llvm.org/D37338

llvm-svn: 312471

show more ...

[LoopUnroll] Enable option to peel remainder loop

On some targets, the penalty of executing runtime unrolling checks
and then not the unrolled loop can be significantly detrimental to
performance. T

[LoopUnroll] Enable option to peel remainder loop

On some targets, the penalty of executing runtime unrolling checks
and then not the unrolled loop can be significantly detrimental to
performance. This results in the need to be more conservative with
the unroll count, keeping a trip count of 2 reduces the overhead as
well as increasing the chance of the unrolled body being executed. But
being conservative leaves performance gains on the table.

This patch enables the unrolling of the remainder loop introduced by
runtime unrolling. This can help reduce the overhead of misunrolled
loops because the cost of non-taken branches is much less than the
cost of the backedge that would normally be executed in the remainder
loop. This allows larger unroll factors to be used without suffering
performance loses with smaller iteration counts.

Differential Revision: https://reviews.llvm.org/D36309

llvm-svn: 310824

show more ...

[RuntimeUnroll] NFC: Add a profitability function for mutliexit loop

Separated out the profitability from the safety analysis for multiexit
loop unrolling. Currently, this is an NFC because profitab

[RuntimeUnroll] NFC: Add a profitability function for mutliexit loop

Separated out the profitability from the safety analysis for multiexit
loop unrolling. Currently, this is an NFC because profitability is true
only if the unroll-runtime-multi-exit is set to true (off-by-default).

This is to ease adding the profitability heuristic up for review at
D35380.

llvm-svn: 308753

show more ...

Fix unused variable warning on EXPENSIVE_CHECKS release builds. NFCI.

llvm-svn: 307929

[RuntimeUnrolling] Update DomTree correctly when exit blocks have successors

Summary:
When we runtime unroll with multiple exit blocks, we also need to update the
immediate dominators of the immedia

[RuntimeUnrolling] Update DomTree correctly when exit blocks have successors

Summary:
When we runtime unroll with multiple exit blocks, we also need to update the
immediate dominators of the immediate successors of the exit blocks.

Reviewers: reames, mkuper, mzolotukhin, apilipenko

Reviewed by: mzolotukhin

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D35304

llvm-svn: 307909

show more ...

[LoopUnrollRuntime] NFC: Refactored safety checks of unrolling multi-exit loop

Refactored the code and separated out a function
`canSafelyUnrollMultiExitLoop` to reduce redundant checks and make it

[LoopUnrollRuntime] NFC: Refactored safety checks of unrolling multi-exit loop

Refactored the code and separated out a function
`canSafelyUnrollMultiExitLoop` to reduce redundant checks and make it
easier to add profitability heuristics later.
Added tests to runtime unrolling to make sure that unrolling for
multi-exit loops is not done unless the option
-unroll-runtime-multi-exit is true.

llvm-svn: 307843

show more ...