llvm-svn: 202735

The old implementation is no longer needed in C++11.

llvm-svn: 202644

Remove the old functions.

llvm-svn: 202636

llvm-svn: 202621

llvm-svn: 202618

directly, and remove the macro.

llvm-svn: 202612

llvm-svn: 202607

llvm-svn: 202596

No intended functionality change.

llvm-svn: 202588

Inside iterate, we scan backwards then scan forwards in a loop. When iteration
is not zero, the last node was just updated so we can skip it. But when
iteration is zero, we can't skip the last node.

For the testing case, fixing this will save a spill and move register copies
from hot path to cold path.

llvm-svn: 202557

Reverting until the C++11 switch is complete.

llvm-svn: 202554

The previous PBQP solver was very robust but consumed a lot of memory,
performed a lot of redundant computation, and contained some unnecessarily tight
coupling that prevented experimentation with novel solution techniques. This new
solver is an attempt to address these shortcomings.

Important/interesting changes:

1) The domain-independent PBQP solver class, HeuristicSolverImpl, is gone.
It is replaced by a register allocation specific solver, PBQP::RegAlloc::Solver
(see RegAllocSolver.h).

The optimal reduction rules and the backpropagation algorithm have been extracted
into stand-alone functions (see ReductionRules.h), which can be used to build
domain specific PBQP solvers. This provides many more opportunities for
domain-specific knowledge to inform the PBQP solvers' decisions. In theory this
should allow us to generate better solutions. In practice, we can at least test
out ideas now.

As a side benefit, I believe the new solver is more readable than the old one.

2) The solver type is now a template parameter of the PBQP graph.

This allows the graph to notify the solver of any modifications made (e.g. by
domain independent rules) without the overhead of a virtual call. It also allows
the solver to supply policy information to the graph (see below).

3) Significantly reduced memory overhead.

Memory management policy is now an explicit property of the PBQP graph (via
the CostAllocator typedef on the graph's solver template argument). Because PBQP
graphs for register allocation tend to contain many redundant instances of
single values (E.g. the value representing an interference constraint between
GPRs), the new RASolver class uses a uniquing scheme. This massively reduces
memory consumption for large register allocation problems. For example, looking
at the largest interference graph in each of the SPEC2006 benchmarks (the
largest graph will always set the memory consumption high-water mark for PBQP),
the average memory reduction for the PBQP costs was 400x. That's times, not
percent. The highest was 1400x. Yikes. So - this is fixed.

"PBQP: No longer feasting upon every last byte of your RAM".

Minor details:

- Fully C++11'd. Never copy-construct another vector/matrix!

- Cute tricks with cost metadata: Metadata that is derived solely from cost
matrices/vectors is attached directly to the cost instances themselves. That way
if you unique the costs you never have to recompute the metadata. 400x less
memory means 400x less cost metadata (re)computation.

Special thanks to Arnaud de Grandmaison, who has been the source of much
encouragement, and of many very useful test cases.

This new solver forms the basis for future work, of which there's plenty to do.
I will be adding TODO notes shortly.

- Lang.

llvm-svn: 202551

This extract-and-trunc vector optimization cannot work for i1 values as
currently implemented, and so I'm disabling this for now for i1 values. In the
future, this can be fixed properly.

Soon I'll commit support for i1 CR bit tracking in the PowerPC backend, and
this will be covered by one of the existing regression tests.

llvm-svn: 202449

This is a temporary workaround for native arm linux builds:
PR18996: Changing regalloc order breaks "lencod" on native arm linux builds.

llvm-svn: 202433

making the cache mutable.

llvm-svn: 202417

scan the register file for sub- and super-registers.
No functionality change intended.

(Tests are updated because the comments in the assembler output are
different.)

llvm-svn: 202416

any ranges - this includes CU ranges where we were previously emitting an
end list marker even if we didn't have a list.

Testcase includes a test for line table only code emission as the problem
was noticed while writing this test.

llvm-svn: 202357

any ranges to the list of ranges for the CU as we don't want to emit
them anyway. This ensures that we will still emit ranges if we have
a compile unit compiled with only line tables and one compiled with
full debug info requested (we'll emit for the one with full debug info).

Update testcase metadata accordingly to continue emitting ranges.

llvm-svn: 202333

llvm-svn: 202317

llvm-svn: 202316

more obvious.

llvm-svn: 202313

This handles pathological cases in which we see 2x increase in spill
code for large blocks (~50k instructions). I don't have a unit test
for this behavior.

Fixes rdar://16072279.

llvm-svn: 202304

The aggressive anti-dependency breaker scans instructions, bottom-up, within the
scheduling region in order to find opportunities where register renaming can
be used to break anti-dependencies.

Unfortunately, the aggressive anti-dep breaker was treating a register definition
as defining all of that register's aliases (including super registers). This behavior
is incorrect when the super register is live and there are other definitions of
subregisters of the super register.

For example, given the following sequence:

%CR2EQ<def> = CROR %CR3UN, %CR3UN<kill>
%CR2GT<def> = IMPLICIT_DEF
%X4<def> = MFOCRF8 %CR2

the analysis of the first subregister definition would work as expected:
Anti:   %CR2GT<def> = IMPLICIT_DEF
        Def Groups: CR2GT=g194->g0(via CR2)
        Antidep reg: CR2GT (zero group)
        Use Groups:

but the analysis of the second one would not:
Anti:   %CR2EQ<def> = CROR %CR3UN, %CR3UN<kill>
        Def Groups: CR2EQ=g195
        Antidep reg: CR2EQ
        Rename Candidates for Group g195: ...

because, when processing the %CR2GT<def>, we'd mark all super registers of
%CR2GT (%CR2 in this case) as defined. As a result, when processing
%CR2EQ<def>, %CR2 no longer appears to be live, and %CR2EQ<def>'s group is not
%unioned with the %CR2 group.

I don't have an in-tree test case for this yet (and even if I did, I don't have
a small one).

llvm-svn: 202294

llvm-svn: 202221

llvm-svn: 202220

llvm-svn: 202201

This is refactoring / simplifying code, updating comments and enabling the
testcase on non-x86 platforms.

No functionality change.

llvm-svn: 202199

Variadic functions have an unspecified parameter tag after the last
argument. In IR this is represented as an unspecified parameter in the
subroutine type.

Paired commit with CFE r202185.

rdar://problem/13690847

This re-applies r202184 + a bugfix in DwarfDebug's argument handling.

llvm-svn: 202188

This reverts commit r202184 because of buildbot breakage.

llvm-svn: 202187

llvm-svn: 202186

Variadic functions have an unspecified parameter tag after the last
argument. In IR this is represented as an unspecified parameter in the
subroutine type.

Paired commit with CFE.

rdar://problem/13690847

llvm-svn: 202184

The function with uwtable attribute might be visited by the
stack unwinder, thus the link register should be considered
as clobbered after the execution of the branch and link
instruction (i.e. the definition of the machine instruction
can't be ignored) even when the callee function are marked
with noreturn.

llvm-svn: 202165

llvm-svn: 202107

llvm-svn: 202096

llvm-svn: 202074

llvm-svn: 202073

After this I will set the default back to F_None. The advantage is that
before this patch forgetting to set F_Binary would corrupt a file on windows.
Forgetting to set F_Text produces one that cannot be read in notepad, which
is a better failure mode :-)

llvm-svn: 202052

This will make it easier to switch the default to being binary files.

llvm-svn: 202042

No functionality change.

llvm-svn: 201974

llvm-svn: 201944