[ARM] Find VPT implicitly predicated by VCTP

On failing to find a VCTP in the list of instructions that explicitly
predicate the entry of a VPT block, inspect whether the block is
controlled via VPT

[ARM] Find VPT implicitly predicated by VCTP

On failing to find a VCTP in the list of instructions that explicitly
predicate the entry of a VPT block, inspect whether the block is
controlled via VPT which is implicitly predicated due to it's
predicated operand(s).

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

show more ...

[RDA] Fix getUniqueReachingDef for self loops

We've fixed the case where this could return an instruction after the
given instruction, but also means that we can falsely return a
'unique' def when t

[RDA] Fix getUniqueReachingDef for self loops

We've fixed the case where this could return an instruction after the
given instruction, but also means that we can falsely return a
'unique' def when they could be one coming from the backedge of a
loop.

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

show more ...

[ARM][LowOverheadLoops] Liveouts and reductions

Remove the code that tried to look for reduction patterns, since the
vectorizer and isel can now produce predicated arithmetic instructios
within the

[ARM][LowOverheadLoops] Liveouts and reductions

Remove the code that tried to look for reduction patterns, since the
vectorizer and isel can now produce predicated arithmetic instructios
within the loop body. This has required some reorganisation and fixes
around live-out and predication checks, as well as looking for cases
where an input/output is initialised to zero.

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

show more ...

[RDA] Don't visit the BB of the instruction in getReachingUniqueMIDef

If the basic block of the instruction passed to getUniqueReachingMIDef
is a transitive predecessor of itself and has a definitio

[RDA] Don't visit the BB of the instruction in getReachingUniqueMIDef

If the basic block of the instruction passed to getUniqueReachingMIDef
is a transitive predecessor of itself and has a definition of the
register, the function will return that definition even if it is after
the instruction given to the function. This patch stops the function
from scanning the instruction's basic block to prevent this.

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

show more ...

[NFC][RDA] Add explicit def check

Explicitly check that there is a local def prior to the given
instruction in getReachingLocalMIDef instead of just relying on
a nullptr return from getInstFromId.

[RDA] Fix DBG_VALUE issues

We skip debug instructions in RDA so we cannot attempt to look them
up in our instruction map without causing a crash. But some of the
methods select the last instruction

[RDA] Fix DBG_VALUE issues

We skip debug instructions in RDA so we cannot attempt to look them
up in our instruction map without causing a crash. But some of the
methods select the last instruction in the block and this
instruction may be a debug instruction... So, use getLastNonDebugInstr
instead of calling back on a MachineBasicBlock.

MachineBasicBlock iterators have also been updated to use
instructionsWithoutDebug so we can avoid the manual checks for debug
instructions.

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

show more ...

[ARM][LowOverheadLoops] Handle reductions

While validating live-out values, record instructions that look like
a reduction. This will comprise of a vector op (for now only vadd),
a vorr (vmov) which

[ARM][LowOverheadLoops] Handle reductions

While validating live-out values, record instructions that look like
a reduction. This will comprise of a vector op (for now only vadd),
a vorr (vmov) which store the previous value of vadd and then a vpsel
in the exit block which is predicated upon a vctp. This vctp will
combine the last two iterations using the vmov and vadd into a vector
which can then be consumed by a vaddv.

Once we have determined that it's safe to perform tail-predication,
we need to change this sequence of instructions so that the
predication doesn't produce incorrect code. This involves changing
the register allocation of the vadd so it updates itself and the
predication on the final iteration will not update the falsely
predicated lanes. This mimics what the vmov, vctp and vpsel do and
so we then don't need any of those instructions.

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

show more ...

[NFC] Correct spelling of "ambiguous"

[RDA] Avoid full reprocessing of blocks in loops (NFCI)

RDA sometimes needs to visit blocks twice, to take into account
reaching defs coming in along loop back edges. Currently it handles
repeated v

[RDA] Avoid full reprocessing of blocks in loops (NFCI)

RDA sometimes needs to visit blocks twice, to take into account
reaching defs coming in along loop back edges. Currently it handles
repeated visitation the same way as usual, which means that it will
scan through all instructions and their reg unit defs again. Not
only is this very inefficient, it also means that all reaching defs
in loops are going to be inserted twice.

We can do much better than this. The only thing we need to handle
is a new reaching def from a predecessor, which either needs to be
prepended to the reaching definitions (if there was no reaching def
from a predecessor), or needs to replace an existing predecessor
reaching def, if it is more recent. Since D77508 we only store the
most recent predecessor reaching def, so that's the only one that
may need updating.

This also has the nice side-effect that reaching definitions are
now automatically sorted and unique, so drop the llvm::sort() call
in favor of an assertion.

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

show more ...

[RDA] Don't pass down TraversedMBB (NFC)

Only pass the MachineBasicBlock itself down to helper methods,
they don't need to know about traversal. Move the debug print
into the main method.

[RDA] Avoid inserting duplicate reaching defs (NFCI)

An instruction may define the same reg unit multiple times,
avoid inserting the same reaching def multiple times in that case.

Also print the re

[RDA] Avoid inserting duplicate reaching defs (NFCI)

An instruction may define the same reg unit multiple times,
avoid inserting the same reaching def multiple times in that case.

Also print the reg unit, rather than the super-register, in the
debug code.

show more ...

[RDA] Only store most recent reaching def from predecessors (NFCI)

When entering a basic block, RDA inserts reaching definitions coming
from predecessor blocks (which will be negative numbers) in a

[RDA] Only store most recent reaching def from predecessors (NFCI)

When entering a basic block, RDA inserts reaching definitions coming
from predecessor blocks (which will be negative numbers) in a rather
peculiar way. If you have incoming reaching definitions -4, -3, -2, -1,
it will insert those. If you have incoming reaching definitions
-1, -2, -3, -4, it will insert -1, -1, -1, -1, as the max is taken
at each step. That's probably not what was intended...

However, RDA only actually cares about the most recent reaching
definition from a predecessor (to calculate clearance), so this
ends up working fine as far as behavior is concerned. It does
waste memory on unnecessary reaching definitions though.

This patch changes the implementation to first compute the most
recent reaching definition in one loop, and then insert only that
one in a separate loop.

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

show more ...

[RDA] Don't adjust ReachingDefDefaultVal (NFCI)

At the end of a basic block, RDA adjusts all the reaching defs it
found to be relative to the end of the basic block, rather than the
start of it. How

[RDA] Don't adjust ReachingDefDefaultVal (NFCI)

At the end of a basic block, RDA adjusts all the reaching defs it
found to be relative to the end of the basic block, rather than the
start of it. However, it also does this to registers which don't
have a reaching def, indicated by ReachingDefDefaultVal. This means
that code checking against ReachingDefDefaultVal will not skip them,
and may insert them into the reaching definition list. This is
ultimately harmless, but causes unnecessary work and is logically
not right.

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

show more ...

Give helpers internal linkage. NFC.

[RDA][ARM] collectKilledOperands across multiple blocks

Use MIOperand in collectLocalKilledOperands to make the search
global, as we already have to search for global uses too. This
allows us to del

[RDA][ARM] collectKilledOperands across multiple blocks

Use MIOperand in collectLocalKilledOperands to make the search
global, as we already have to search for global uses too. This
allows us to delete more dead code when tail predicating.

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

show more ...

[ARM][RDA] Allow multiple killed users

In RDA, check against the already decided dead instructions when
looking at users. This allows an instruction to be removed if it
has multiple users, but they'

[ARM][RDA] Allow multiple killed users

In RDA, check against the already decided dead instructions when
looking at users. This allows an instruction to be removed if it
has multiple users, but they're all dead.

This means that IT instructions can be considered killed once all
the itstate using instructions are dead.

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

show more ...

[RDA] Track implicit-defs

Ensure that we're recording implicit defs, as well as visiting implicit
uses and implicit defs when we're walking through operands.

Differential Revision: https://reviews.

[RDA] Track implicit-defs

Ensure that we're recording implicit defs, as well as visiting implicit
uses and implicit defs when we're walking through operands.

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

show more ...

[ARM][RDA] add getUniqueReachingMIDef

Add getUniqueReachingMIDef to RDA which performs a global search for
a machine instruction that produces a unique definition of a given
register at a given poin

[ARM][RDA] add getUniqueReachingMIDef

Add getUniqueReachingMIDef to RDA which performs a global search for
a machine instruction that produces a unique definition of a given
register at a given point. Also add two helper functions
(getMIOperand) that wrap around this functionality to get the
incoming definition uses of a given instruction. These now replace
the uses of getReachingMIDef in ARMLowOverheadLoops. getReachingMIDef
has been renamed to getReachingLocalMIDef and has been made private
along with getInstFromId.

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

show more ...

[RDA][ARM][LowOverheadLoops] Iteration count IT blocks

Change the way that we remove the redundant iteration count code in
the presence of IT blocks. collectLocalKilledOperands has been
introduced t

[RDA][ARM][LowOverheadLoops] Iteration count IT blocks

Change the way that we remove the redundant iteration count code in
the presence of IT blocks. collectLocalKilledOperands has been
introduced to scan an instructions operands, collecting the killed
instructions and then visiting them too. This is used to delete the
code in the preheader which calculates the iteration count. We also
track any IT blocks within the preheader and, if we remove all the
instructions from the IT block, we also remove the IT instruction.
isSafeToRemove is used to remove any redundant uses of the iteration
count within the loop body.

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

show more ...

[NFC][RDA] Break-up initialization code

Separate out the initialization code from the loop traversal so
that the analysis can be reset and re-run by a user.

[RDA] getInstFromId: find instructions. NFC.

To find the instruction in the block for a given ID, first a count and then a
lookup was performed in the map, which is almost the same thing, thus doing

[RDA] getInstFromId: find instructions. NFC.

To find the instruction in the block for a given ID, first a count and then a
lookup was performed in the map, which is almost the same thing, thus doing
double the work.

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

show more ...

[ReachingDefs] Make isSafeToMove more strict.

Test that we're not moving the instruction through instructions with
side-effects.

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

[RDA][ARM] Move functionality into RDA

Add several new helpers to RDA:
- hasLocalDefBefore
- isRegDefinedAfter
- isSafeToDefRegAt

And move two bits of logic from ARMLowOverheadLoops into RDA:
- isS

[RDA][ARM] Move functionality into RDA

Add several new helpers to RDA:
- hasLocalDefBefore
- isRegDefinedAfter
- isSafeToDefRegAt

And move two bits of logic from ARMLowOverheadLoops into RDA:
- isSafeToMove
- isSafeToRemove

Both of these have some wrappers too to make them more convienent to
use.

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

show more ...

[NFC][RDA] typedef SmallPtrSetImpl<MachineInstr*>

[RDA] Skip debug values

Skip debug instructions when iterating through a block to find uses.

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