[GlobalISel][Localizer] Allow localization of a small number of repeated phi uses. (#77566)

We previously had a heuristic that if a value V was used multiple times
in a single PHI, then to avoid po

[GlobalISel][Localizer] Allow localization of a small number of repeated phi uses. (#77566)

We previously had a heuristic that if a value V was used multiple times
in a single PHI, then to avoid potentially rematerializing into many predecessors
we bail out. The phi uses only counted as a single use in the shouldLocalize() hook
because it counted the PHI as a single instruction use, not factoring in it may
have many incoming edges.

It turns out this heuristic is slightly too pessimistic, and allowing a small number
of these uses to be localized can improve code size due to shortening live ranges,
especially if those ranges span a call.

This change results in some improvements in size on CTMark -Os:
```
Program size.__text
before after diff
kimwitu++/kc 451676.00 451860.00 0.0%
mafft/pairlocalalign 241460.00 241540.00 0.0%
tramp3d-v4/tramp3d-v4 389216.00 389208.00 -0.0%
7zip/7zip-benchmark 587528.00 587464.00 -0.0%
Bullet/bullet 457424.00 457348.00 -0.0%
consumer-typeset/consumer-typeset 405472.00 405376.00 -0.0%
SPASS/SPASS 410288.00 410120.00 -0.0%
lencod/lencod 426396.00 426108.00 -0.1%
ClamAV/clamscan 380108.00 379756.00 -0.1%
sqlite3/sqlite3 283664.00 283372.00 -0.1%
Geomean difference -0.0%
```
I experimented with different variations and thresholds. Using 3 instead
of 2 resulted in a further 0.1% improvement on ClamAV but also regressed
sqlite3 by the same %.

show more ...

[CodeGen] Define and use MachineOperand::getOperandNo

This is a helper function to very slightly simplify many calls to
MachineInstruction::getOperandNo.

Differential Revision: https://reviews.llvm

[CodeGen] Define and use MachineOperand::getOperandNo

This is a helper function to very slightly simplify many calls to
MachineInstruction::getOperandNo.

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

show more ...

[GlobalISel][DebugInfo] Propagate debug location for localized constants

After IRTranslator pass, constants are deduplicated and translated into instructions at entry block, having debug locations l

[GlobalISel][DebugInfo] Propagate debug location for localized constants

After IRTranslator pass, constants are deduplicated and translated into instructions at entry block, having debug locations lost.
Localization of constants may cause emission of extra zero lines in debug_line section, like here https://godbolt.org/z/ecvsxxfKn. In this example, constant gets placed as
a first instruction in entry block, and despite it has no debug location, AsmPrinter emits zero line for it.

If a localized constant has the only user, we can assume that it has the same debug location as its user, since they are placed consequently.

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

show more ...

Cleanup includes: DebugInfo & CodeGen

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

GlobalISel: Fix insert point in localizer

This was inserting the new G_CONSTANT after the use, and the later
block scan would run off the end. Fix calling SkipPHIsAndLabels for no
apparent reason.

GlobalISel: Use cloneVirtualRegister in localizer

[CodeGen] Use make_early_inc_range (NFC)

[CodeGen] Use range-based for loops (NFC)

[GlobalISel][Localizer] Don't localize phi operands which are used more than once in the phi.

The current algorithm just tries to localize defs as far as they can go, and in
the case of G_PHI operan

[GlobalISel][Localizer] Don't localize phi operands which are used more than once in the phi.

The current algorithm just tries to localize defs as far as they can go, and in
the case of G_PHI operands, it clones the def into the predecessor block for
each incoming edge. When multiple edges have the same register value, this can
cause unnecessary code bloat, and inhibit later optimizations.

This change checks if a given phi operand is unique in the phi, if not the
def of that register is not localized to the predecessor.

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

show more ...

Revert "Revert "[GlobalISel][Localizer] Enable intra-block localization of already-local uses.""

This reverts commit 5583c2f2fba5be1df60f00cbc34a5098b5a49909.

The lldb bot failure was a test that w

Revert "Revert "[GlobalISel][Localizer] Enable intra-block localization of already-local uses.""

This reverts commit 5583c2f2fba5be1df60f00cbc34a5098b5a49909.

The lldb bot failure was a test that was fragile and sensitive to irrelevant
changes in instruction ordering. Re-committing this as the test should have
been skipped for AArch64 now.

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

show more ...

Revert "[GlobalISel][Localizer] Enable intra-block localization of already-local uses."

This reverts commit e91e1df6ab74006e96b0cca94192e935542705a4.

[GlobalISel][Localizer] Enable intra-block localization of already-local uses.

This changes the localizer to attempt intra-block localizer of instructions
that have local uses. This is useful becaus

[GlobalISel][Localizer] Enable intra-block localization of already-local uses.

This changes the localizer to attempt intra-block localizer of instructions
that have local uses. This is useful because sometimes the entry block itself
has many uses of constant-like instructions, which would benefit from shortening
live ranges. Previously if an inst had no non-local uses, we wouldn't add it to
the list of instructions to attempt further intra-block localization.

This gives a 0.7% geomean code size improvement on CTMark.

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

show more ...

GlobalISel: Move Localizer::shouldLocalize(..) to TargetLowering

Add a new target hook for shouldLocalize so that
targets can customize the logic.

https://reviews.llvm.org/D75207

[GlobalISel] Localizer: Allow targets not to run the pass conditionally

Summary:
Previously, it was not possible to skip running the localizer pass
conditionally. This patch adds an input function t

[GlobalISel] Localizer: Allow targets not to run the pass conditionally

Summary:
Previously, it was not possible to skip running the localizer pass
conditionally. This patch adds an input function to the pass which
decides if the pass should run on the given MachineFunction or not.

No test case as there is no upstream target needs this functionality.

Reviewers: qcolombet

Reviewed By: qcolombet

Subscribers: rovka, hiraditya, Petar.Avramovic, llvm-commits

Tags: #llvm

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

show more ...

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of reco

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of recompilation.

I found this fact by looking at this table, which is sorted by the
number of times a file was changed over the last 100,000 git commits
multiplied by the number of object files that depend on it in the
current checkout:
recompiles touches affected_files header
342380 95 3604 llvm/include/llvm/ADT/STLExtras.h
314730 234 1345 llvm/include/llvm/InitializePasses.h
307036 118 2602 llvm/include/llvm/ADT/APInt.h
213049 59 3611 llvm/include/llvm/Support/MathExtras.h
170422 47 3626 llvm/include/llvm/Support/Compiler.h
162225 45 3605 llvm/include/llvm/ADT/Optional.h
158319 63 2513 llvm/include/llvm/ADT/Triple.h
140322 39 3598 llvm/include/llvm/ADT/StringRef.h
137647 59 2333 llvm/include/llvm/Support/Error.h
131619 73 1803 llvm/include/llvm/Support/FileSystem.h

Before this change, touching InitializePasses.h would cause 1345 files
to recompile. After this change, touching it only causes 550 compiles in
an incremental rebuild.

Reviewers: bkramer, asbirlea, bollu, jdoerfert

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

show more ...

Localizer - fix "variable used but never read" analyzer warning. NFCI.

Simplify the code by separating the modification of the Changed variable from returning it.

llvm-svn: 372583

Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVM

Summary:
This clang-tidy check is looking for unsigned integer variables whose initializer
starts with an implicit cast from llvm::Re

Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVM

Summary:
This clang-tidy check is looking for unsigned integer variables whose initializer
starts with an implicit cast from llvm::Register and changes the type of the
variable to llvm::Register (dropping the llvm:: where possible).

Partial reverts in:
X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister
X86FixupLEAs.cpp - Some functions return unsigned and arguably should be MCRegister
X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister
HexagonBitSimplify.cpp - Function takes BitTracker::RegisterRef which appears to be unsigned&
MachineVerifier.cpp - Ambiguous operator==() given MCRegister and const Register
PPCFastISel.cpp - No Register::operator-=()
PeepholeOptimizer.cpp - TargetInstrInfo::optimizeLoadInstr() takes an unsigned&
MachineTraceMetrics.cpp - MachineTraceMetrics lacks a suitable constructor

Manual fixups in:
ARMFastISel.cpp - ARMEmitLoad() now takes a Register& instead of unsigned&
HexagonSplitDouble.cpp - Ternary operator was ambiguous between unsigned/Register
HexagonConstExtenders.cpp - Has a local class named Register, used llvm::Register instead of Register.
PPCFastISel.cpp - PPCEmitLoad() now takes a Register& instead of unsigned&

Depends on D65919

Reviewers: arsenm, bogner, craig.topper, RKSimon

Reviewed By: arsenm

Subscribers: RKSimon, craig.topper, lenary, aemerson, wuzish, jholewinski, MatzeB, qcolombet, dschuff, jyknight, dylanmckay, sdardis, nemanjai, jvesely, wdng, nhaehnle, sbc100, jgravelle-google, kristof.beyls, hiraditya, aheejin, kbarton, fedor.sergeev, javed.absar, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, tpr, PkmX, jocewei, jsji, Petar.Avramovic, asbirlea, Jim, s.egerton, llvm-commits

Tags: #llvm

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

llvm-svn: 369041

show more ...

[GlobalISel][Localizer] Allow localization of G_INTTOPTR and chains of instructions.

G_INTTOPTR can prevent the localizer from moving G_CONSTANTs, but since it's
essentially a side effect free cast

[GlobalISel][Localizer] Allow localization of G_INTTOPTR and chains of instructions.

G_INTTOPTR can prevent the localizer from moving G_CONSTANTs, but since it's
essentially a side effect free cast instruction we can remat both instructions.
This patch changes the localizer to enable localization of the chains by
iterating over the entry block instructions in reverse order. That way, uses will
localized first, and then the defs are free to be localized as well.

This also changes the previous SmallPtrSet of localized instructions to use a
SetVector instead. We're dealing with pointers and need deterministic iteration
order.

Overall, this change improves ARM64 -O0 CTMark code size by around 0.7% geomean.

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

llvm-svn: 364001

show more ...

[GlobalISel][Localizer] Remove redundant set lookup.

After changing the algorithm to only process the entry block we never revisit
a processed instruction.

llvm-svn: 363745

GlobalISel: Remove redundant pass initialization

Summary:
All the GlobalISel passes are initialized when the target calls
initializeGlobalISel(), so we don't need to call the initializers
from the p

GlobalISel: Remove redundant pass initialization

Summary:
All the GlobalISel passes are initialized when the target calls
initializeGlobalISel(), so we don't need to call the initializers
from the pass constructors.

Reviewers: qcolombet, t.p.northover, paquette, dsanders, aemerson, aditya_nandakumar

Reviewed By: aemerson

Subscribers: rovka, kristof.beyls, hiraditya, volkan, Petar.Avramovic, llvm-commits

Tags: #llvm

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

llvm-svn: 363642

show more ...

[GlobalISel][Localizer] Rewrite localizer to run in 2 phases, inter & intra block.

Inter-block localization is the same as what currently happens, except now it
only runs on the entry block because

[GlobalISel][Localizer] Rewrite localizer to run in 2 phases, inter & intra block.

Inter-block localization is the same as what currently happens, except now it
only runs on the entry block because that's where the problematic constants with
long live ranges come from.

The second phase is a new intra-block localization phase which attempts to
re-sink the already localized instructions further right before one of the
multiple uses.

One additional change is to also localize G_GLOBAL_VALUE as they're constants
too. However, on some targets like arm64 it takes multiple instructions to
materialize the value, so some additional heuristics with a TTI hook have been
introduced attempt to prevent code size regressions when localizing these.

Overall, these changes improve CTMark code size on arm64 by 1.2%.

Full code size results:

Program baseline new diff
------------------------------------------------------------------------------
test-suite...-typeset/consumer-typeset.test 1249984 1217216 -2.6%
test-suite...:: CTMark/ClamAV/clamscan.test 1264928 1232152 -2.6%
test-suite :: CTMark/SPASS/SPASS.test 1394092 1361316 -2.4%
test-suite...Mark/mafft/pairlocalalign.test 731320 714928 -2.2%
test-suite :: CTMark/lencod/lencod.test 1340592 1324200 -1.2%
test-suite :: CTMark/kimwitu++/kc.test 3853512 3820420 -0.9%
test-suite :: CTMark/Bullet/bullet.test 3406036 3389652 -0.5%
test-suite...ark/tramp3d-v4/tramp3d-v4.test 8017000 8016992 -0.0%
test-suite...TMark/7zip/7zip-benchmark.test 2856588 2856588 0.0%
test-suite...:: CTMark/sqlite3/sqlite3.test 765704 765704 0.0%
Geomean difference -1.2%

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

llvm-svn: 363632

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 ...

CodeGen: Remove pipeline dependencies on StackProtector; NFC

This re-applies r336929 with a fix to accomodate for the Mips target
scheduling multiple SelectionDAG instances into the pass pipeline.

CodeGen: Remove pipeline dependencies on StackProtector; NFC

This re-applies r336929 with a fix to accomodate for the Mips target
scheduling multiple SelectionDAG instances into the pass pipeline.

PrologEpilogInserter and StackColoring depend on the StackProtector analysis
being alive from the point it is run until PEI, which requires that they are all
scheduled in the same FunctionPassManager. Inserting a (machine) ModulePass
between StackProtector and PEI results in these passes being in separate
FunctionPassManagers and the StackProtector is not available for PEI.

PEI and StackColoring don't use much information from the StackProtector pass,
so transfering the required information to MachineFrameInfo is cleaner than
keeping the StackProtector pass around. This commit moves the SSP layout
information to MFI instead of keeping it in the pass.

This patch set (D37580, D37581, D37582, D37583, D37584, D37585, D37586, D37587)
is a first draft of the pagerando implementation described in
http://lists.llvm.org/pipermail/llvm-dev/2017-June/113794.html.

Patch by Stephen Crane <sjc@immunant.com>

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

llvm-svn: 336964

show more ...

Revert "(HEAD -> master, origin/master, arcpatch-D37582) CodeGen: Remove pipeline dependencies on StackProtector; NFC"

This was triggering pass scheduling failures.

This reverts commit r336929.

ll

Revert "(HEAD -> master, origin/master, arcpatch-D37582) CodeGen: Remove pipeline dependencies on StackProtector; NFC"

This was triggering pass scheduling failures.

This reverts commit r336929.

llvm-svn: 336934

show more ...

CodeGen: Remove pipeline dependencies on StackProtector; NFC

PrologEpilogInserter and StackColoring depend on the StackProtector analysis
being alive from the point it is run until PEI, which requir

CodeGen: Remove pipeline dependencies on StackProtector; NFC

PrologEpilogInserter and StackColoring depend on the StackProtector analysis
being alive from the point it is run until PEI, which requires that they are all
scheduled in the same FunctionPassManager. Inserting a (machine) ModulePass
between StackProtector and PEI results in these passes being in separate
FunctionPassManagers and the StackProtector is not available for PEI.

PEI and StackColoring don't use much information from the StackProtector pass,
so transfering the required information to MachineFrameInfo is cleaner than
keeping the StackProtector pass around. This commit moves the SSP layout
information to MFI instead of keeping it in the pass.

This patch set (D37580, D37581, D37582, D37583, D37584, D37585, D37586, D37587)
is a first draft of the pagerando implementation described in
http://lists.llvm.org/pipermail/llvm-dev/2017-June/113794.html.

Patch by Stephen Crane <sjc@immunant.com>

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

llvm-svn: 336929

show more ...