[Analysis] Qualify auto variables in for loops (NFC)

Revert "[IPT] Restructure cache to allow lazy update following invalidation [NFC]"

This reverts commit baea663a6e9bc52f80995d02bb8149934c825612.

Causes crashes, e.g. https://lab.llvm.org/buildbot/#

Revert "[IPT] Restructure cache to allow lazy update following invalidation [NFC]"

This reverts commit baea663a6e9bc52f80995d02bb8149934c825612.

Causes crashes, e.g. https://lab.llvm.org/buildbot/#/builders/77/builds/10715.

show more ...

[IPT] Restructure cache to allow lazy update following invalidation [NFC]

This change restructures the cache used in IPT to point not to the first special instruction, but to the first instruction w

[IPT] Restructure cache to allow lazy update following invalidation [NFC]

This change restructures the cache used in IPT to point not to the first special instruction, but to the first instruction which *could* be special. That is, the cached reference is always equal to the first special, or comes before it in the block.

This avoids expensive block scans when we are removing special instructions from the beginning of the block. At the moment, this case is not heavily used, though it does trigger in GVN when doing CSE of calls. The main motivation was a change I'm no longer planning to move forward with, but the cache optimization seemed worthwhile as a minor perf win at low cost.

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

show more ...

[IPT] Add a statistic to track instructions scanned to answer queries

I'm planning some changes to the invalidation mechanism here, and having a concrete mechanism to track progress is key.

[IPT] Narrow scope of removeInstruction invalidation [NFC]

We only need to invalidate if the instruction being removed is the cached "first special instruction". If the instruction is before that o

[IPT] Narrow scope of removeInstruction invalidation [NFC]

We only need to invalidate if the instruction being removed is the cached "first special instruction". If the instruction is before that one, it can't (by assumption) be special. If it is after that one, it wasn't the first.

show more ...

[GVN] Properly invalidate ICF cache when we simplify a value

This fixes a "Cached first special instruction is wrong!" assert.

The assert fires because replacing a value with another can cause an
i

[GVN] Properly invalidate ICF cache when we simplify a value

This fixes a "Cached first special instruction is wrong!" assert.

The assert fires because replacing a value with another can cause an
instruction to no longer be "special" to ICF. In this case,
devirtualization happened, turning an indirect call to a
call to a willreturn function which is no longer special.

Reviewed By: nikic, rnk

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

show more ...

[IPT] Don't use OrderedInstructions (NFC)

Use Instruction::comesBefore() instead of OrderedInstructions
inside InstructionPrecedenceTracking. This also removes the
dominator tree dependency.

Differ

[IPT] Don't use OrderedInstructions (NFC)

Use Instruction::comesBefore() instead of OrderedInstructions
inside InstructionPrecedenceTracking. This also removes the
dominator tree dependency.

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

show more ...

[NFC] Remove obsolete checks followed by fix of isGuaranteedToTransferExecutionToSuccessor

In past, isGuaranteedToTransferExecutionToSuccessor contained some weird logic
for volatile loads/stores th

[NFC] Remove obsolete checks followed by fix of isGuaranteedToTransferExecutionToSuccessor

In past, isGuaranteedToTransferExecutionToSuccessor contained some weird logic
for volatile loads/stores that was ultimately removed by patch D65375. It's time to
remove a piece of dependent logic that used to be a workaround for the code which
is now deleted.

Reviewed By: uenoku
Differential Revision: https://reviews.llvm.org/D76918

show more ...

[IR] Lazily number instructions for local dominance queries

Essentially, fold OrderedBasicBlock into BasicBlock, and make it
auto-invalidate the instruction ordering when new instructions are
added.

[IR] Lazily number instructions for local dominance queries

Essentially, fold OrderedBasicBlock into BasicBlock, and make it
auto-invalidate the instruction ordering when new instructions are
added. Notably, we don't need to invalidate it when removing
instructions, which is helpful when a pass mostly delete dead
instructions rather than transforming them.

The downside is that Instruction grows from 56 bytes to 64 bytes. The
resulting LLVM code is substantially simpler and automatically handles
invalidation, which makes me think that this is the right speed and size
tradeoff.

The important change is in SymbolTableTraitsImpl.h, where the numbering
is invalidated. Everything else should be straightforward.

We probably want to implement a fancier re-numbering scheme so that
local updates don't invalidate the ordering, but I plan for that to be
future work, maybe for someone else.

Reviewed By: lattner, vsk, fhahn, dexonsmith

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

show more ...

Add missing includes needed to prune LLVMContext.h include, NFC

These are a pre-requisite to removing #include "llvm/Support/Options.h"
from LLVMContext.h: https://reviews.llvm.org/D70280

Make widenable condition transparent for MemoryWriteTracking

Side effects of widenable condition intrinsic are modelled via
InaccessibleMemOnly, and there is no way to say that it isn't
really writi

Make widenable condition transparent for MemoryWriteTracking

Side effects of widenable condition intrinsic are modelled via
InaccessibleMemOnly, and there is no way to say that it isn't
really writing any memory. This patch teaches MemoryWriteTracking
ignore this intrinsic.

llvm-svn: 354021

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[IPT] Drop cache less eagerly in GVN and LoopSafetyInfo

Current strategy of dropping `InstructionPrecedenceTracking` cache is to
invalidate the entire basic block whenever we change its contents. In

[IPT] Drop cache less eagerly in GVN and LoopSafetyInfo

Current strategy of dropping `InstructionPrecedenceTracking` cache is to
invalidate the entire basic block whenever we change its contents. In fact,
`InstructionPrecedenceTracking` has 2 internal strictures: `OrderedInstructions`
that is needed to be invalidated whenever the contents changes, and the map
with first special instructions in block. This second map does not need an
update if we add/remove a non-special instuction because it cannot
affect the contents of this map.

This patch changes API of `InstructionPrecedenceTracking` so that it now
accounts for reasons under which we invalidate blocks. This should lead
to much less recalculations of the map and should save us some compile time
because in practice we don't typically add/remove special instructions.

Differential Revision: https://reviews.llvm.org/D54462
Reviewed By: efriedma

llvm-svn: 350694

show more ...

[LICM] Hoist guards from non-header blocks

This patch relaxes overconservative checks on whether or not we could write
memory before we execute an instruction. This allows us to hoist guards out of

[LICM] Hoist guards from non-header blocks

This patch relaxes overconservative checks on whether or not we could write
memory before we execute an instruction. This allows us to hoist guards out of
loops even if they are not in the header block.

Differential Revision: https://reviews.llvm.org/D50891
Reviewed By: fedor.sergeev

llvm-svn: 346643

show more ...

[NFC] Rename variable

llvm-svn: 341901

[NFC] Simplify inner structure of InstructionPrecedenceTracking

Currently it has a set KnownBlocks that marks blocks as having cached
answers and a map FirstSpecialInsts that maps these blocks to fi

[NFC] Simplify inner structure of InstructionPrecedenceTracking

Currently it has a set KnownBlocks that marks blocks as having cached
answers and a map FirstSpecialInsts that maps these blocks to first
special instructions in them. The value in the map is always non-null,
and for blocks that are known to have no special instructions the map
does not have an instance.

This patch removes KnownBlocks as obsolete. Instead, for blocks that
are known to have no special instructions, we just put a nullptr value.
This makes the code much easier to read.

llvm-svn: 341531

show more ...

Return "[NFC] Add severe validation of InstructionPrecedenceTracking"

This validation patch has been reverted as rL341147 because of conserns raised by
@reames. This revision returns it as is to rai

Return "[NFC] Add severe validation of InstructionPrecedenceTracking"

This validation patch has been reverted as rL341147 because of conserns raised by
@reames. This revision returns it as is to raise a discussion and address the concerns.

Differential Revision: https://reviews.llvm.org/D51523
Reviewed By: reames

llvm-svn: 341526

show more ...

Revert "[NFC] Add severe validation of InstructionPrecedenceTracking" for discussion

llvm-svn: 341147

[NFC] Add severe validation of InstructionPrecedenceTracking

llvm-svn: 341051

[NFC] Rename map to make the naming consistent

llvm-svn: 341043

[NFC] Move OrderedInstructions and InstructionPrecedenceTracking to Analysis

These classes don't make any changes to IR and have no reason to be in
Transform/Utils. This patch moves them to Analysis

[NFC] Move OrderedInstructions and InstructionPrecedenceTracking to Analysis

These classes don't make any changes to IR and have no reason to be in
Transform/Utils. This patch moves them to Analysis folder. This will allow
us reusing these classes in some analyzes, like MustExecute.

llvm-svn: 341015

show more ...