[LoopUnrollRuntime] NFC: Add some debugging trace messages for why loop wasn't unrolled.

llvm-svn: 307705

[LoopUnrollRuntime] Avoid multi-exit nested loop with epilog generation

The loop structure for the outer loop does not contain the epilog
preheader when we try to unroll inner loop with multiple exi

[LoopUnrollRuntime] Avoid multi-exit nested loop with epilog generation

The loop structure for the outer loop does not contain the epilog
preheader when we try to unroll inner loop with multiple exits and
epilog code is generated. For now, we just bail out in such cases.
Added a test case that shows the problem. Without this bailout, we would
trip on assert saying LCSSA form is incorrect for outer loop.

llvm-svn: 307676

show more ...

[LoopUnrollRuntime] Remove strict assert about VMap requirement

When unrolling under multiple exits which is under off-by-default option,
the assert that checks for VMap entry in loop exit values is

[LoopUnrollRuntime] Remove strict assert about VMap requirement

When unrolling under multiple exits which is under off-by-default option,
the assert that checks for VMap entry in loop exit values is too strong.
(assert if VMap entry did not exist, the value should be a
constant). However, values derived from
constants or from values outside loop, does not have a VMap entry too.

Removed the assert and added a testcase showcasing the property for
non-constant values.

llvm-svn: 307542

show more ...

[LoopUnrollRuntime] Support multiple exit blocks unrolling when prolog remainder generated

With the NFC refactoring in rL307417 (git SHA 987dd01), all the logic
is in place to support multiple exit/

[LoopUnrollRuntime] Support multiple exit blocks unrolling when prolog remainder generated

With the NFC refactoring in rL307417 (git SHA 987dd01), all the logic
is in place to support multiple exit/exiting blocks when prolog
remainder is generated.
This patch removed the assert that multiple exit blocks unrolling is only
supported when epilog remainder is generated.

Also, added test runs and checks with PROLOG prefix in
runtime-loop-multiple-exits.ll test cases.

llvm-svn: 307435

show more ...

[LoopUnrollRuntime] NFC: use the precomputed loop exit in ConnectProlog

Minor refactoring to use the preexisting loop exit that's already
calculated. We do not need to recompute the loop exit in Con

[LoopUnrollRuntime] NFC: use the precomputed loop exit in ConnectProlog

Minor refactoring to use the preexisting loop exit that's already
calculated. We do not need to recompute the loop exit in ConnectProlog.
Apart from avoiding redundant computation, this is required for
supporting multiple loop exits when Prolog remainder loops are generated.

llvm-svn: 307417

show more ...

[LoopUnrollRuntime] Bailout when multiple exiting blocks to the unique latch exit block

Currently, we do not support multiple exiting blocks to the
latch exit block. However, this bailout wasn't tri

[LoopUnrollRuntime] Bailout when multiple exiting blocks to the unique latch exit block

Currently, we do not support multiple exiting blocks to the
latch exit block. However, this bailout wasn't triggered when we had a
unique exit block (which is the latch exit), with multiple exiting
blocks to that unique exit.

Moved the bailout so that it's triggered in both cases and added
testcase.

llvm-svn: 307291

show more ...

[RuntimeUnrolling] Add logic for loops with multiple exit blocks

Summary:
Runtime unrolling is done for loops with a single exit block and a
single exiting block (and this exiting block should be th

[RuntimeUnrolling] Add logic for loops with multiple exit blocks

Summary:
Runtime unrolling is done for loops with a single exit block and a
single exiting block (and this exiting block should be the latch block).
This patch adds logic to support unrolling in the presence of multiple exit
blocks (which also means multiple exiting blocks).
Currently this is under an off-by-default option and is supported when
epilog code is generated. Support in presence of prolog code will be in
a future patch (we just need to add more tests, and update comments).

This patch is essentially an implementation patch. I have not added any
heuristic (in terms of branches added or code size) to decide when
this should be enabled.

Reviewers: mkuper, sanjoy, reames, evstupac

Reviewed by: reames

Subscribers: llvm-commits

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

llvm-svn: 306846

show more ...

[LoopUnrollRuntime] Use SCEV exit count for calculating trip count. NFCI

Instead of getBackEdgeTakenCount, use getExitCount on the latch exiting block
(which is proven to be the only exiting block i

[LoopUnrollRuntime] Use SCEV exit count for calculating trip count. NFCI

Instead of getBackEdgeTakenCount, use getExitCount on the latch exiting block
(which is proven to be the only exiting block in the loop to be unrolled).

llvm-svn: 306410

show more ...

[RuntimeLoopUnrolling] Rename exit block and move assert earlier. NFC

The single exit block allowed in runtime unrolling is guaranteed to be
the Latch's successor, so rename it as LatchExitBlock.

l

[RuntimeLoopUnrolling] Rename exit block and move assert earlier. NFC

The single exit block allowed in runtime unrolling is guaranteed to be
the Latch's successor, so rename it as LatchExitBlock.

llvm-svn: 306105

show more ...

Sort the remaining #include lines in include/... and lib/....

I did this a long time ago with a janky python script, but now
clang-format has built-in support for this. I fed clang-format every
line

Sort the remaining #include lines in include/... and lib/....

I did this a long time ago with a janky python script, but now
clang-format has built-in support for this. I fed clang-format every
line with a #include and let it re-sort things according to the precise
LLVM rules for include ordering baked into clang-format these days.

I've reverted a number of files where the results of sorting includes
isn't healthy. Either places where we have legacy code relying on
particular include ordering (where possible, I'll fix these separately)
or where we have particular formatting around #include lines that
I didn't want to disturb in this patch.

This patch is *entirely* mechanical. If you get merge conflicts or
anything, just ignore the changes in this patch and run clang-format
over your #include lines in the files.

Sorry for any noise here, but it is important to keep these things
stable. I was seeing an increasing number of patches with irrelevant
re-ordering of #include lines because clang-format was used. This patch
at least isolates that churn, makes it easy to skip when resolving
conflicts, and gets us to a clean baseline (again).

llvm-svn: 304787

show more ...

Avoid warning of unused variable in release builds. NFC

llvm-svn: 302068

Fix PPC64 warning for missing parantheses. NFC.

llvm-svn: 302061

[RuntimeLoopUnroller] Add assert that we dont unroll non-rotated loops

Summary:
Cloning basic blocks in the loop for runtime loop unroller depends on loop being
in rotated form (i.e. loop latch targ

[RuntimeLoopUnroller] Add assert that we dont unroll non-rotated loops

Summary:
Cloning basic blocks in the loop for runtime loop unroller depends on loop being
in rotated form (i.e. loop latch target is the exit block).
Assert that this is true, so that callers of runtime loop unroller pass in
canonical loops.
The single caller of this function has that check recently added:
https://reviews.llvm.org/rL301239

Reviewers: davide

Subscribers: llvm-commits

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

llvm-svn: 302058

show more ...

[LoopUnroll] Use addClonedBlockToLoopInfo to clone the top level loop (NFC)

Summary:
rL293124 added the necessary infrastructure to properly add the cloned
top level loop to LoopInfo, which means we

[LoopUnroll] Use addClonedBlockToLoopInfo to clone the top level loop (NFC)

Summary:
rL293124 added the necessary infrastructure to properly add the cloned
top level loop to LoopInfo, which means we do not have to do it manually
in CloneLoopBlocks.

@mkuper sorry for not pointing this out during my review of D29156, I just
realized that today.


Reviewers: mzolotukhin, chandlerc, mkuper

Reviewed By: mkuper

Subscribers: llvm-commits, mkuper

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

llvm-svn: 293615

show more ...

[LoopUnroll] Properly update loopinfo for runtime unrolling by 2

Even when we don't create a remainder loop (that is, when we unroll by 2), we
may duplicate nested loops into the remainder. This is

[LoopUnroll] Properly update loopinfo for runtime unrolling by 2

Even when we don't create a remainder loop (that is, when we unroll by 2), we
may duplicate nested loops into the remainder. This is complicated by the fact
the remainder may itself be either inserted into an outer loop, or at the top
level. In the latter case, we may need to create new top-level loops.

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

llvm-svn: 293124

show more ...

Preserve domtree and loop-simplify for runtime unrolling.

Mostly straightforward changes; we just didn't do the computation before.
One sort of interesting change in LoopUnroll.cpp: we weren't handl

Preserve domtree and loop-simplify for runtime unrolling.

Mostly straightforward changes; we just didn't do the computation before.
One sort of interesting change in LoopUnroll.cpp: we weren't handling
dominance for children of the loop latch correctly, but
foldBlockIntoPredecessor hid the problem for complete unrolling.

Currently punting on loop peeling; made some minor changes to isolate
that problem to LoopUnrollPeel.cpp.

Adds a flag -unroll-verify-domtree; it verifies the domtree immediately
after we finish updating it. This is on by default for +Asserts builds.

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

llvm-svn: 292447

show more ...

[loop-unroll] Properly populate LoopInfo for loops cloned in LoopUnrollRuntime.

Summary:
This fixes Transforms/LoopUnroll/runtime-loop3.ll which failed with
EXTENSIVE_DEBUG, because the cloned basic

[loop-unroll] Properly populate LoopInfo for loops cloned in LoopUnrollRuntime.

Summary:
This fixes Transforms/LoopUnroll/runtime-loop3.ll which failed with
EXTENSIVE_DEBUG, because the cloned basic blocks were not added to the
correct sub-loops in LoopUnrollRuntime.cpp.


Reviewers: dexonsmith, mzolotukhin

Subscribers: llvm-commits

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

llvm-svn: 291619

show more ...

Revert "[LoopUnroll] Properly update loop-info when cloning prologues and epilogues."

This reverts commit r280901.

This caused a bunch of failures, reverting it until I investigate them.

llvm-svn:

Revert "[LoopUnroll] Properly update loop-info when cloning prologues and epilogues."

This reverts commit r280901.

This caused a bunch of failures, reverting it until I investigate them.

llvm-svn: 280905

show more ...

[LoopUnroll] Properly update loop-info when cloning prologues and epilogues.

Summary:
When cloning blocks for prologue/epilogue we need to replicate the loop
structure from the original loop. It was

[LoopUnroll] Properly update loop-info when cloning prologues and epilogues.

Summary:
When cloning blocks for prologue/epilogue we need to replicate the loop
structure from the original loop. It wasn't a problem for the innermost
loops, but it led to an incorrect loop info when we unrolled a loop with
a child loop - in this case created prologue-loop had a child loop, but
loop info didn't reflect that.

This fixes PR28888.

Reviewers: chandlerc, sanjoy, hfinkel

Subscribers: llvm-commits, silvas

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

llvm-svn: 280901

show more ...

[UNROLL] Postpone ScalarEvolution::forgetLoop after TripCountSC is expanded
when unroll runtime iteration loop.

In llvm::UnrollRuntimeLoopRemainder, if the loop to be unrolled is the inner
loop insi

[UNROLL] Postpone ScalarEvolution::forgetLoop after TripCountSC is expanded
when unroll runtime iteration loop.

In llvm::UnrollRuntimeLoopRemainder, if the loop to be unrolled is the inner
loop inside a loop nest, the scalar evolution needs to be dropped for its
parent loop which is done by ScalarEvolution::forgetLoop. However, we can
postpone forgetLoop to the end of UnrollRuntimeLoopRemainder so TripCountSC
expansion can still reuse existing value.

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

llvm-svn: 279748

show more ...

[LoopUnroll] Ensure we create prolog loops in simplified form.

llvm-svn: 277502

The patch fixes PR27392.
Summary:
It is incorrect to compare TripCount (which is BECount + 1)
with extraiters (or Count) to check if we should enter unrolled
loop or not, because TripCount can p

The patch fixes PR27392.
Summary:
It is incorrect to compare TripCount (which is BECount + 1)
with extraiters (or Count) to check if we should enter unrolled
loop or not, because TripCount can potentially overflow
(when BECount is max unsigned integer).
While comparing BECount with (Count - 1) is overflow safe and
therefore correct.

Reviewer: hfinkel

Differential Revision: http://reviews.llvm.org/D19256

From: Evgeny Stupachenko <evstupac@gmail.com>
llvm-svn: 267662

show more ...

Transforms: Fix bootstrap after r266565

Apparently there isn't test coverage for all of these. I'd appreciate
if someone with could reproduce and send me something to reduce, but for
now I've just

Transforms: Fix bootstrap after r266565

Apparently there isn't test coverage for all of these. I'd appreciate
if someone with could reproduce and send me something to reduce, but for
now I've just looked for users of RemapInstruction and MapValue and
ensured they don't accidentally insert nullptr. Here is one of the
bootstraps that caught:

http://lab.llvm.org:8011/builders/clang-x64-ninja-win7/builds/11494

llvm-svn: 266567

show more ...

test commit

llvm-svn: 265840

IR: RF_IgnoreMissingValues => RF_IgnoreMissingLocals, NFC

Clarify what this RemapFlag actually means.

- Change the flag name to match its intended behaviour.
- Clearly document that it's not su

IR: RF_IgnoreMissingValues => RF_IgnoreMissingLocals, NFC

Clarify what this RemapFlag actually means.

- Change the flag name to match its intended behaviour.
- Clearly document that it's not supposed to affect globals.
- Add a host of FIXMEs to indicate how to fix the behaviour to match
the intent of the flag.

RF_IgnoreMissingLocals should only affect the behaviour of
RemapInstruction for function-local operands; namely, for operands of
type Argument, Instruction, and BasicBlock. Currently, it is *only*
passed into RemapInstruction calls (and the transitive MapValue calls
that it makes).

When I split Metadata from Value I didn't understand the flag, and I
used it in a bunch of places for "global" metadata.

This commit doesn't have any functionality change, but prepares to
cleanup MapMetadata and MapValue.

llvm-svn: 265628

show more ...