[NFC][DebugInfo] Use iterator-flavour getFirstNonPHI at many call-sites (#123737)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNo

[NFC][DebugInfo] Use iterator-flavour getFirstNonPHI at many call-sites (#123737)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to getFirstNonPHI use the iterator-returning version.

This patch changes a bunch of call-sites calling getFirstNonPHI to use
getFirstNonPHIIt, which returns an iterator. All these call sites are
where it's obviously safe to fetch the iterator then dereference it. A
follow-up patch will contain less-obviously-safe changes.

We'll eventually deprecate and remove the instruction-pointer
getFirstNonPHI, but not before adding concise documentation of what
considerations are needed (very few).

---------

Co-authored-by: Stephen Tozer <Melamoto@gmail.com>

show more ...

[SSAUpdater] Avoid scanning basic blocks to find instruction order. (#123803)

This fixes a compile-time regression caused by #116645, where an entry
basic block with a very large number of allocas

[SSAUpdater] Avoid scanning basic blocks to find instruction order. (#123803)

This fixes a compile-time regression caused by #116645, where an entry
basic block with a very large number of allocas and other instructions
caused SROA to take ~100× its expected runtime, as every alloca (with ~2
uses) now calls this method to find the order of those few instructions,
rescanning the very large basic block every single time.

Since this code was originally written, Instructions now have ordering
numbers available to determine relative order without unnecessarily
scanning the basic block.

show more ...

[SROA] Optimize reloaded values in allocas that escape into readonly nocapture calls. (#116645)

Given an alloca that potentially has many uses in big complex code and
escapes into a call that is rea

[SROA] Optimize reloaded values in allocas that escape into readonly nocapture calls. (#116645)

Given an alloca that potentially has many uses in big complex code and
escapes into a call that is readonly+nocapture, we cannot easily split
up the alloca. There are several optimizations that will attempt to take
a value that is stored and a reload, and replace the load with the
original stored value. Instcombine has some simple heuristics, GVN can
sometimes do it, as can CSE in limited situations. They all suffer from
the same issue with complex code - they start from a load/store and need
to prove no-alias for all code between, which in complex cases might be
a lot to look through. Especially if the ptr is an alloca with many uses
that is over the normal escape capture limits.

The pass that does do well with allocas is SROA, as it has a complete
view of all of the uses. This patch adds a case to SROA where it can
detect allocas that are passed into calls that are no-capture readonly.
It can then optimize the reloaded values inside the alloca slice with
the stored value knowing that it is valid no matter the location of the
loads/stores from the no-escaping nature of the alloca.

show more ...

Revert "[SROA] Optimize reloaded values in allocas that escape into readonly nocapture calls. (#116645)"

Causing buffer overflow:

SUMMARY: AddressSanitizer: heap-buffer-overflow llvm/lib/Transforms

Revert "[SROA] Optimize reloaded values in allocas that escape into readonly nocapture calls. (#116645)"

Causing buffer overflow:

SUMMARY: AddressSanitizer: heap-buffer-overflow llvm/lib/Transforms/Scalar/SROA.cpp:5552:35

This reverts commit 5e247d726d7a54cf0acc997bc17b50e7494e6fa3.

show more ...

[SROA] Optimize reloaded values in allocas that escape into readonly nocapture calls. (#116645)

Given an alloca that potentially has many uses in big complex code and
escapes into a call that is re

[SROA] Optimize reloaded values in allocas that escape into readonly nocapture calls. (#116645)

Given an alloca that potentially has many uses in big complex code and
escapes into a call that is readonly+nocapture, we cannot easily split
up the alloca. There are several optimizations that will attempt to take
a value that is stored and a reload, and replace the load with the
original stored value. Instcombine has some simple heuristics, GVN can
sometimes do it, as can CSE in limited situations. They all suffer from
the same issue with complex code - they start from a load/store and need
to prove no-alias for all code between, which in complex cases might be
a lot to look through. Especially if the ptr is an alloca with many uses
that is over the normal escape capture limits.

The pass that does do well with allocas is SROA, as it has a complete
view of all of the uses. This patch adds a case to SROA where it can
detect allocas that are passed into calls that are no-capture readonly.
It can then optimize the reloaded values inside the alloca slice with
the stored value knowing that it is valid no matter the location of the
loads/stores from the no-escaping nature of the alloca.

show more ...

[Utils] Remove unused includes (NFC) (#114748)

Identified with misc-include-cleaner.

SSAUpdater: use poison instead of undef in phi entries for unreachable predecessors

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[RemoveDIs][NFC] Rename DPValue -> DbgVariableRecord (#85216)

This is the major rename patch that prior patches have built towards.
The DPValue class is being renamed to DbgVariableRecord, which re

[RemoveDIs][NFC] Rename DPValue -> DbgVariableRecord (#85216)

This is the major rename patch that prior patches have built towards.
The DPValue class is being renamed to DbgVariableRecord, which reflects
the updated terminology for the "final" implementation of the RemoveDI
feature. This is a pure string substitution + clang-format patch. The
only manual component of this patch was determining where to perform
these string substitutions: `DPValue` and `DPV` are almost exclusively
used for DbgRecords, *except* for:

- llvm/lib/target, where 'DP' is used to mean double-precision, and so
appears as part of .td files and in variable names. NB: There is a
single existing use of `DPValue` here that refers to debug info, which
I've manually updated.
- llvm/tools/gold, where 'LDPV' is used as a prefix for symbol
visibility enums.

Outside of these places, I've applied several basic string
substitutions, with the intent that they only affect DbgRecord-related
identifiers; I've checked them as I went through to verify this, with
reasonable confidence that there are no unintended changes that slipped
through the cracks. The substitutions applied are all case-sensitive,
and are applied in the order shown:

```
DPValue -> DbgVariableRecord
DPVal -> DbgVarRec
DPV -> DVR
```

Following the previous rename patches, it should be the case that there
are no instances of any of these strings that are meant to refer to the
general case of DbgRecords, or anything other than the DPValue class.
The idea behind this patch is therefore that pure string substitution is
correct in all cases as long as these assumptions hold.

show more ...

[DebugInfo][RemoveDIs] Instrument jump-threading to update DPValues (#73127)

This patch makes jump-threading handle non-instruction debug-info stored
in DPValues in the same way that it updates dbg

[DebugInfo][RemoveDIs] Instrument jump-threading to update DPValues (#73127)

This patch makes jump-threading handle non-instruction debug-info stored
in DPValues in the same way that it updates dbg.values nowadays. This
involves re-targetting their operands as with dbg.values getting moved
from one block to another, and manually cloning them when duplicating
blocks. The SSAUpdater class also grows some functions for SSA-updating
DPValues in the same way as dbg.values.

All of this is largely covered by existing debug-info tests, except for
the cloning of DPValues attached to elidable instructions and branches,
where I've added a test to thread-debug-info.ll. Where previously we
could rely on dbg.values being copied and cloned as normal instructions
are, as we need to explicitly perform that operation now I've added some
explicit testing for it.

show more ...

[NFC][RemoveDIs] Prefer iterator-insertion over instructions

Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruc

[NFC][RemoveDIs] Prefer iterator-insertion over instructions

Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruction pointers,
so that we can communicate information in the iterator class. This patch
adds an iterator-taking insertBefore method and converts various call sites
to take iterators. These are all sites where such debug-info needs to be
preserved so that a stage2 clang can be built identically; it's likely that
many more will need to be changed in the future.

At this stage, this is just changing the spelling of a few operations,
which will eventually become signifiant once the debug-info bearing
iterator is used.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

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

show more ...

[debug-info] Followup to e0374fb2f4, avoid changing codegen

As discussed on D140404, calling GetValueInMiddleOfBlock can force PHI
nodes to be created, but the patch was only supposed to fetch a Val

[debug-info] Followup to e0374fb2f4, avoid changing codegen

As discussed on D140404, calling GetValueInMiddleOfBlock can force PHI
nodes to be created, but the patch was only supposed to fetch a Value if it
wasn't going to generate any PHIs. Fix this by using GetValueAtEndOfBlock
instead of the Middle variant, which was the original intention given the
check of HasValueForBlock.

We don't need to consider the "middle of block" scenario as we're only
dealing with blocks where there are no value definitions.

show more ...

[DebugInfo] Make debug intrinsics to track cloned values in JumpThreading

This patch causes debug value intrinsics outside of cloned blocks in the
Jump Threading pass to correctly point towards any

[DebugInfo] Make debug intrinsics to track cloned values in JumpThreading

This patch causes debug value intrinsics outside of cloned blocks in the
Jump Threading pass to correctly point towards any derived values. If it cannot,
it kills them.

Reviewed By: probinson, StephenTozer

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

show more ...

[NFC] Switch a few uses of undef to poison as placeholders for unreachable code

Revert "[MachineSSAUpdater] compile time improvement in GetValueInMiddleOfBlock"

It looks like it causes buildbot failures.
As an example: https://lab.llvm.org/buildbot/#/builders/121/builds/20364

Revert "[MachineSSAUpdater] compile time improvement in GetValueInMiddleOfBlock"

It looks like it causes buildbot failures.
As an example: https://lab.llvm.org/buildbot/#/builders/121/builds/20364

Revert to investigate...

This reverts commit 6bf27918144cb843cf5ae9a93cb5f936730f3cce.

show more ...

[MachineSSAUpdater] compile time improvement in GetValueInMiddleOfBlock

GetValueInMiddleOfBlock uses result of GetValueAtEndOfBlockInternal if there is no value
defined for current basic block.

If

[MachineSSAUpdater] compile time improvement in GetValueInMiddleOfBlock

GetValueInMiddleOfBlock uses result of GetValueAtEndOfBlockInternal if there is no value
defined for current basic block.

If there is already a value it tries (in this order):

to find single register coming from all predecessors
find existing phi node which matches our incoming registers
build new phi.
The compile time improvement is to use current available value if
it is defined out of current BB or it is a PHI register.
This is due to it can be used in the middle basic block.

Reviewed By: sameerds
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D126523

show more ...

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with
the cleanup of InstructionSimplify in one commit.

This is the alternative to the less invasive clang-format only patch: D126783

Reviewed By: spatel, rengolin

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

show more ...

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120741

show more ...

Reland "[LICM] Hoist LOAD without sinking the STORE"

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can pro

Reland "[LICM] Hoist LOAD without sinking the STORE"

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can prove the load could
be dereferenced and moved outside the loop. This patch
implements the load promotion by moving it in the loop
preheader by inserting proper PHI in the loop. The store
is kept as is in the loop. By doing this, we avoid doing
the load from a memory location in each iteration.

Please consider this small example:

loop {
var = *ptr;
if (var) break;
*ptr= var + 1;
}
After this patch, it will be:

var0 = *ptr;
loop {
var1 = phi (var0, var2);
if (var1) break;
var2 = var1 + 1;
*ptr = var2;
}
This addresses some problems from [0].

[0] https://bugs.llvm.org/show_bug.cgi?id=51193

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

show more ...

Revert "[LICM] Hoist LOAD without sinking the STORE"

This reverts commit ecb9d8e4e3c4623c2edcd2c50727103927d31508.

I'll reland this as soon as the failing tests are fixed/updated.

[LICM] Hoist LOAD without sinking the STORE

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can prove the lo

[LICM] Hoist LOAD without sinking the STORE

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can prove the load could
be dereferenced and moved outside the loop. This patch
implements the load promotion by moving it in the loop
preheader by inserting proper PHI in the loop. The store
is kept as is in the loop. By doing this, we avoid doing
the load from a memory location in each iteration.

Please consider this small example:

loop {
var = *ptr;
if (var) break;
*ptr= var + 1;
}
After this patch, it will be:

var0 = *ptr;
loop {
var1 = phi (var0, var2);
if (var1) break;
var2 = var1 + 1;
*ptr = var2;
}
This addresses some problems from [0].

[0] https://bugs.llvm.org/show_bug.cgi?id=51193

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

show more ...

[Transforms/Utils] Use range-based for loops (NFC)

[Transforms] Use llvm::append_range (NFC)

[SSAUpdater] Remove unused code InstrIsPHI (NFC)

The last use of this function was removed on Jan 4, 2018 in commit
commit 90ecac01e9dcbcaf92781a6dcffa07a27191b661.

[CodeGen, Transforms] Use *Map::lookup (NFC)