SCCP can use PredicateInfo to constrain ranges based on assume and
branch conditions. Currently, this is only enabled during IPSCCP.
This enables it for SCCP as well, which runs after functions have
already been simplified, while IPSCCP runs pre-inline. To a large
degree, CVP already handles range-based optimizations, but SCCP is more
reliable for the cases it can handle. In particular, SCCP works reliably
inside loops, which is something that CVP struggles with due to LVI
cycles.
I have made various optimizations to make PredicateInfo more efficient,
but unfortunately this still has significant compile-time cost (around
0.1-0.2%).
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>
In replaceSignedInst, if a signed instruction can be repalced with
unsigned instruction, we created a new instruction and removed the old
instruction's value state. If the following instructions has this new
instruction as a use operand, transformations like replaceSignedInst and
refineInstruction would be blocked. The reason is there is no value
state for the new instrution.
This patch set the new instruction's value state with the removed
instruction's value state. I believe it is correct bacause when we
repalce a signed instruction with unsigned instruction, the value state
is not changed.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D152337
This reverts commit a9a1950115d7db95c7439128b14af2cefe8f796d.
The legacy PM uses in Polly have been removed, so recommit the patch.
Original message:
This is part of the optimization pipeline, of which the legacy pass manager version is deprecated.
Reviewed By: aeubanks
Differential Revision: https://reviews.llvm.org/D144201
This reverts commit 5356fefc19df3fbf32d180b1b10e6226e8743541.
It looks like Polly still relies on the legacy SCCP pass. Bring it back
until the best way forward is determined.
This is part of the optimization pipeline, of which the legacy pass manager version is deprecated.
Reviewed By: aeubanks
Differential Revision: https://reviews.llvm.org/D144201
This patch moves a couple of helper functions from the global llvm::
namespace into the SCCPSolver class. This reduces the need for separate
SCCPSolver arguments and also limits the scope of those functions that
have quite generic names.
(The remaining isConstant and isOverdefined should ideally be removed)
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D142370
Reland 42c2dc401742266da3e0251b6c1ca491f4779963 which was reverted
in cb03b1bd99313a728d47060b909a73e7f5991231. The fix for the link
errors was to reintroduce one of the two occurences of 'Scalar'
under the LINK_COMPONENTS.
Differential Revision: https://reviews.llvm.org/D138654
This reverts commit 42c2dc401742266da3e0251b6c1ca491f4779963.
This broke some buildbots:
undefined reference to `llvm::createBitTrackingDCEPass()'
undefined reference to `llvm::createAlignmentFromAssumptionsPass()'
undefined reference to `llvm::createLoopUnrollPass(int, bool, bool, int, int, int, int, int, int)'
undefined reference to `llvm::createLICMPass(unsigned int, unsigned int, bool)'
undefined reference to `llvm::createWarnMissedTransformationsPass()'
undefined reference to `llvm::createAlignmentFromAssumptionsPass()'
undefined reference to `llvm::createCallSiteSplittingPass()'
undefined reference to `llvm::createCFGSimplificationPass(llvm::SimplifyCFGOptions, std::function<bool (llvm::Function const&)>)'
undefined reference to `llvm::createFloat2IntPass()'
undefined reference to `llvm::createLowerConstantIntrinsicsPass()'
undefined reference to `llvm::createLoopRotatePass(int, bool)'
undefined reference to `llvm::createLoopDistributePass()'
undefined reference to `llvm::createLoopSinkPass()'
undefined reference to `llvm::createInstSimplifyLegacyPass()'
undefined reference to `llvm::createDivRemPairsPass()'
undefined reference to `llvm::createCFGSimplificationPass(llvm::SimplifyCFGOptions, std::function<bool (llvm::Function const&)>)'
undefined reference to `llvm::SetLicmMssaOptCap'
undefined reference to `llvm::SetLicmMssaNoAccForPromotionCap'
undefined reference to `llvm::ForgetSCEVInLoopUnroll'
The LLVMipo library no longer depends on the Scalar component.
The shared functions between IPSCCP and SCCP have been moved
under Utils, in the SCCPSolver.
This is preliminary work for D126455, in order to break a cyclic
dependency between LLVM libraries.
Differential Revision: https://reviews.llvm.org/D138654
This switches everything to use the memory attribute proposed in
https://discourse.llvm.org/t/rfc-unify-memory-effect-attributes/65579.
The old argmemonly, inaccessiblememonly and inaccessiblemem_or_argmemonly
attributes are dropped. The readnone, readonly and writeonly attributes
are restricted to parameters only.
The old attributes are auto-upgraded both in bitcode and IR.
The bitcode upgrade is a policy requirement that has to be retained
indefinitely. The IR upgrade is mainly there so it's not necessary
to update all tests using memory attributes in this patch, which
is already large enough. We could drop that part after migrating
tests, or retain it longer term, to make it easier to import IR
from older LLVM versions.
High-level Function/CallBase APIs like doesNotAccessMemory() or
setDoesNotAccessMemory() are mapped transparently to the memory
attribute. Code that directly manipulates attributes (e.g. via
AttributeList) on the other hand needs to switch to working with
the memory attribute instead.
Differential Revision: https://reviews.llvm.org/D135780
I'm not sure how to test this because we seem to constant-fold
all examples already. We changed this code to use the common
isNonNegative() helper, so it should not be necessary to avoid
a constant. This makes the code uniform for all transforms.
This is similar to the existing signed instruction folds.
We get the obvious minimal patterns in other passes, but
this avoids potential missed folds when the multi-block
tests are converted to selects.
The original commit ( fe1f3cfc2669 ) was reverted because it could
crash / assert when trying to fold a value that was replaced
by a constant. In that case, there might not be an entry for the
constant in the solver yet.
This version adds a check for that possibility along with tests to
exercise that pattern (they used to crash).
Original commit message:
This extends the transform added with D81756 to handle div/rem opcodes.
For example:
https://alive2.llvm.org/ce/z/cX6za6
This replicates part of what CVP already does, but the motivating example
from issue #57472 demonstrates a phase ordering problem - we convert
branches to select before CVP runs and miss the transform.
Differential Revision: https://reviews.llvm.org/D133198
This reverts commit fe1f3cfc2669aca387a45c8ce615b45c1db50fc6.
It looks like this commit breaks building llvm-test-suite.
To reproduce, run `opt -passes=ipsccp` on the IR below.
@g = internal global i32 256, align 4
define void @test() {
entry:
%0 = load i32, ptr @g, align 4
%div = sdiv i32 %0, undef
ret void
}
This extends the transform added with D81756 to handle div/rem opcodes.
For example:
https://alive2.llvm.org/ce/z/cX6za6
This replicates part of what CVP already does, but the motivating example
from issue #57472 demonstrates a phase ordering problem - we convert
branches to select before CVP runs and miss the transform.
Differential Revision: https://reviews.llvm.org/D133198
Currently, we only remove dead blocks and non-feasible edges in
IPSCCP, but not in SCCP. I'm not aware of any strong reason for
that difference, so this patch updates SCCP to perform the CFG
cleanup as well.
Compile-time impact seems to be pretty minimal, in the 0.05%
geomean range on CTMark.
For the test case from https://reviews.llvm.org/D126962#3611579
the result after -sccp now looks like this:
define void @test(i1 %c) {
entry:
br i1 %c, label %unreachable, label %next
next:
unreachable
unreachable:
call void @bar()
unreachable
}
-jump-threading does nothing on this, but -simplifycfg will produce
the optimal result.
Differential Revision: https://reviews.llvm.org/D128796
As branch on undef is immediate undefined behavior, there is no need
to mark one of the edges as feasible. We can leave all the edges
non-feasible. In IPSCCP, we can replace the branch with an unreachable
terminator.
Differential Revision: https://reviews.llvm.org/D126962
In D115737 I found that I needed to teach Instruction::isSafeToRemove()
about strictfp/constrained intrinsics. It was pointed out that this is
probably the wrong function to use isInstructionTriviallyDead(). It doesn't
make sense to have a "second, worse implementation".
I also believe that the Instruction class is the wrong place for this
functionality. The information about whether or not an instruction can be
removed is in the transform passes and should stay there.
Differential Revision: https://reviews.llvm.org/D118387
This makes the output IR more readable since we're doing a one to
one replacement.
Reviewed By: fhahn
Differential Revision: https://reviews.llvm.org/D125280
At the moment, unfeasible default destinations are not handled properly
in removeNonFeasibleEdges. So far, only unfeasible cases are removed,
but later code expects unreachable blocks to have no predecessors.
This is causing the crash reported in PR49573.
If the default destination is unfeasible it won't be executed. Create
a new unreachable block on demand and use that as default
destination.
Note that at the moment this only is relevant for cases where
resolvedUndefsIn marks the first case as executable. Regular switch
handling has a FIXME/TODO to support determining whether the default
case is feasible or not.
Fixes#48917.
Differential Revision: https://reviews.llvm.org/D113497
[SCCP] do not clean up dead blocks that have their address taken
Fixes a crash observed in IPSCCP.
Because the SCCPSolver has already internalized BlockAddresses as
Constants or ConstantExprs, we don't want to try to update their Values
in the ValueLatticeElement. Instead, continue to propagate these
BlockAddress Constants, continue converting BasicBlocks to unreachable,
but don't delete the "dead" BasicBlocks which happen to have their
address taken. Leave replacing the BlockAddresses to another pass.
Fixes: https://github.com/llvm/llvm-project/issues/54238
Fixes: https://github.com/llvm/llvm-project/issues/54251
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D121744
This class is solely used as a lightweight and clean way to build a set of
attributes to be removed from an AttrBuilder. Previously AttrBuilder was used
both for building and removing, which introduced odd situation like creation of
Attribute with dummy value because the only relevant part was the attribute
kind.
Differential Revision: https://reviews.llvm.org/D116110
This adds a function specialization pass to LLVM. Constant parameters
like function pointers and constant globals are propagated to the callee by
specializing the function.
This is a first version with a number of limitations:
- The pass is off by default, so needs to be enabled on the command line,
- It does not handle specialization of recursive functions,
- It does not yet handle constants and constant ranges,
- Only 1 argument per function is specialised,
- The cost-model could be further looked into, and perhaps related,
- We are not yet caching analysis results.
This is based on earlier work by Matthew Simpson (D36432) and Vinay Madhusudan.
More recently this was also discussed on the list, see:
https://lists.llvm.org/pipermail/llvm-dev/2021-March/149380.html.
The motivation for this work is that function specialisation often comes up as
a reason for performance differences of generated code between LLVM and GCC,
which has this enabled by default from optimisation level -O3 and up. And while
this certainly helps a few cpu benchmark cases, this also triggers in real
world codes and is thus a generally useful transformation to have in LLVM.
Function specialisation has great potential to increase compile-times and
code-size. The summary from some investigations with this patch is:
- Compile-time increases for short compile jobs is high relatively, but the
increase in absolute numbers still low.
- For longer compile-jobs, the extra compile time is around 1%, and very much
in line with GCC.
- It is difficult to blame one thing for compile-time increases: it looks like
everywhere a little bit more time is spent processing more functions and
instructions.
- But the function specialisation pass itself is not very expensive; it doesn't
show up very high in the profile of the optimisation passes.
The goal of this work is to reach parity with GCC which means that eventually
we would like to get this enabled by default. But first we would like to address
some of the limitations before that.
Differential Revision: https://reviews.llvm.org/D93838
Currently all AA analyses marked as preserved are stateless, not taking
into account their dependent analyses. So there's no need to mark them
as preserved, they won't be invalidated unless their analyses are.
SCEVAAResults was the one exception to this, it was treated like a
typical analysis result. Make it like the others and don't invalidate
unless SCEV is invalidated.
Reviewed By: asbirlea
Differential Revision: https://reviews.llvm.org/D102032
This refactors SCCP and creates a SCCPSolver interface and class so that it can
be used by other passes and transformations. We will use this in D93838, which
adds a function specialisation pass.
This is based on an early version by Vinay Madhusudan.
Differential Revision: https://reviews.llvm.org/D93762
When run under valgrind, or with a malloc that poisons freed memory,
this can lead to segfaults or other problems.
To avoid modifying the AdditionalUsers DenseMap while still iterating,
save the instructions to be notified in a separate SmallPtrSet, and use
this to later call OperandChangedState on each instruction.
Fixes PR49582.
Reviewed By: fhahn
Differential Revision: https://reviews.llvm.org/D98602
