diff mbox

New rematerialization sub-pass in LRA

Message ID 5437F4EC.2070809@redhat.com
State New
Headers show

Commit Message

Vladimir Makarov Oct. 10, 2014, 3:02 p.m. UTC 
Here is a new rematerialization sub-pass of LRA.

   This summer, I tried to implement a separate register pressure
release pass based on rematerialization described in Simpson's PhD.
Although this approach is very attractive as implementation of a
separate pass is simpler, it did not work in GCC.  I saw no code
improvement but mostly big performance degradations.  We have pretty
decent register pressure evaluation infrastructure but apparently it
is not enough to make right rematerialization based only on this info
as IRA/LRA make many other optimizations which can be hard to take
into account before the RA.  So I guess Simpson's approach works only
for basic/simple RA for regular file architectures (as register
pressure decrease pass described in Morgan's book which I also tried).

   So I had to implement rematerialization in LRA itself where all
necessary info is available.  The implementation is more complicated
than Simpson's one but it is worth it as there is no performance
degradation in vast majority cases.

   The new LRA rematerialization sub-pass works right before spilling
subpass and tries to rematerialize values of spilled pseudos.  To
implement the new sub-pass, some important changes in LRA were done.
First, lra-lives.c updates live info about all registers (not only
allocatable ones) and, second, lra-constraints.c was modified to
permit to check that insn satisfies all constraints in strict sense
even if it still contains pseudos.

   I've tested and benchmarked the sub-pass on x86-64 and ARM.  The
sub-pass permits to generate a smaller code in average on both
architecture (although improvement no-significant), adds < 0.4%
additional compilation time in -O2 mode of release GCC (according user
time of compilation of 500K lines fortran program and valgrind lakey #
insns in combine.i compilation) and about 0.7% in -O0 mode.  As the
performance result, the best I found is 1% SPECFP2000 improvement on
ARM Ecynos 5410 (973 vs 963) but for Intel Haswell the performance
results are practically the same (Haswell has a very good
sophisticated memory sub-system).

  There is a room for the pass improvements.  I wrote some ideas at the
top level comment of file lra-remat.c

  Rematerialization sub-pass will work at -O2 and higher and new option
-flra-remat is introduced.

  The patch was successfully tested on x86-64 and ARM.  I am going to
submit it on next week.  Any comments are appreciated.

2014-10-10  Vladimir Makarov  <vmakarov@redhat.com>

         * common.opt (flra-remat): New.
         * opts.c (default_options_table): Add entry for flra_remat.
         * timevar_def (TV_LRA_REMAT): New.
         * doc/invoke.texi (-flra-remat): Add description of the new
         option.
         * doc/passes.texi (-flra-remat): Remove lra-equivs.c and
         lra-saves.c.  Add lra-remat.c.
         * Makefile.in (OBJS): Add lra-remat.o.
         * lra-remat.c: New file.
         * lra.c: Add info about the rematerialization pass in the top
         comment.
         (collect_non_operand_hard_regs, add_regs_to_insn_regno_info):
         Process unallocatable regs too.
         (lra_constraint_new_insn_uid_start): Remove.
         (lra): Add code for calling rematerialization sub-pass.
         * lra-int.h (lra_constraint_new_insn_uid_start): Remove.
         (lra_constrain_insn, lra_remat): New prototypes.
         (lra_eliminate_regs_1): Add parameter.
         * lra-lives.c (make_hard_regno_born, make_hard_regno_dead):
         Process unallocatable hard regs too.
         (process_bb_lives): Ditto.
         * lra-spills.c (remove_pseudos): Add argument to
         lra_eliminate_regs_1 call.
         * lra-eliminations.c (lra_eliminate_regs_1): Add parameter.
         Use it for sp offset calculation.
         (lra_eliminate_regs): Add argument for lra_eliminate_regs_1
         call.
         (eliminate_regs_in_insn): Add parameter.  Use it for sp offset
         calculation.
         (process_insn_for_elimination): Add argument for
         eliminate_regs_in_insn call.
         * lra-constraints.c (get_equiv_with_elimination):  Add argument
         for lra_eliminate_regs_1 call.
         (process_addr_reg): Add parameter.  Use it.
         (process_address_1): Ditto.  Add argument for process_addr_reg
         call.
         (process_address): Ditto.
         (curr_insn_transform): Add parameter.  Use it.  Add argument for
         process_address calls.
         (lra_constrain_insn): New function.
         (lra_constraints): Add argument for curr_insn_transform call.

Comments

Jeff Law Oct. 10, 2014, 4:50 p.m. UTC | #1 
On 10/10/14 09:02, Vladimir Makarov wrote:
>    The new LRA rematerialization sub-pass works right before spilling
> subpass and tries to rematerialize values of spilled pseudos.  To
> implement the new sub-pass, some important changes in LRA were done.
> First, lra-lives.c updates live info about all registers (not only
> allocatable ones) and, second, lra-constraints.c was modified to
> permit to check that insn satisfies all constraints in strict sense
> even if it still contains pseudos.
>
>    I've tested and benchmarked the sub-pass on x86-64 and ARM.  The
> sub-pass permits to generate a smaller code in average on both
> architecture (although improvement no-significant), adds < 0.4%
> additional compilation time in -O2 mode of release GCC (according user
> time of compilation of 500K lines fortran program and valgrind lakey #
> insns in combine.i compilation) and about 0.7% in -O0 mode.  As the
> performance result, the best I found is 1% SPECFP2000 improvement on
> ARM Ecynos 5410 (973 vs 963) but for Intel Haswell the performance
> results are practically the same (Haswell has a very good
> sophisticated memory sub-system).
>
>   There is a room for the pass improvements.  I wrote some ideas at the
> top level comment of file lra-remat.c
>
>   Rematerialization sub-pass will work at -O2 and higher and new option
> -flra-remat is introduced.
>
>   The patch was successfully tested on x86-64 and ARM.  I am going to
> submit it on next week.  Any comments are appreciated.
I wonder if this could help with some of the rematerialization issues 
Intel is running into with their allocatable PIC register changes for i686.

I'll let them pass along test cases you can play with :-)

jeff
Sebastian Pop Oct. 10, 2014, 10:31 p.m. UTC | #2 
Vladimir Makarov wrote:
>   I've tested and benchmarked the sub-pass on x86-64 and ARM.  The
> sub-pass permits to generate a smaller code in average on both
> architecture (although improvement no-significant), adds < 0.4%
> additional compilation time in -O2 mode of release GCC (according user
> time of compilation of 500K lines fortran program and valgrind lakey #
> insns in combine.i compilation) and about 0.7% in -O0 mode.  As the
> performance result, the best I found is 1% SPECFP2000 improvement on
> ARM Ecynos 5410 (973 vs 963) but for Intel Haswell the performance
> results are practically the same (Haswell has a very good
> sophisticated memory sub-system).

On aarch64 I have seen some minor perf improvements to libpng compress and
decompress.  The patch does not change the perf for all other benchmarks that I
have tested.

Thanks,
Sebastian
Evgeny Stupachenko Oct. 13, 2014, 3:54 p.m. UTC | #3 
I don't see significant performance changes from the patch (with and
without patch enabling ebx) on x86 in 32bits mode.

Thanks,
Evgeny

On Sat, Oct 11, 2014 at 2:31 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> Vladimir Makarov wrote:
>>   I've tested and benchmarked the sub-pass on x86-64 and ARM.  The
>> sub-pass permits to generate a smaller code in average on both
>> architecture (although improvement no-significant), adds < 0.4%
>> additional compilation time in -O2 mode of release GCC (according user
>> time of compilation of 500K lines fortran program and valgrind lakey #
>> insns in combine.i compilation) and about 0.7% in -O0 mode.  As the
>> performance result, the best I found is 1% SPECFP2000 improvement on
>> ARM Ecynos 5410 (973 vs 963) but for Intel Haswell the performance
>> results are practically the same (Haswell has a very good
>> sophisticated memory sub-system).
>
> On aarch64 I have seen some minor perf improvements to libpng compress and
> decompress.  The patch does not change the perf for all other benchmarks that I
> have tested.
>
> Thanks,
> Sebastian
Wilco Oct. 13, 2014, 4:24 p.m. UTC | #4 
>   Here is a new rematerialization sub-pass of LRA.
> 
>   I've tested and benchmarked the sub-pass on x86-64 and ARM.  The
> sub-pass permits to generate a smaller code in average on both
> architecture (although improvement no-significant), adds < 0.4%
> additional compilation time in -O2 mode of release GCC (according user
> time of compilation of 500K lines fortran program and valgrind lakey #
> insns in combine.i compilation) and about 0.7% in -O0 mode.  As the
> performance result, the best I found is 1% SPECFP2000 improvement on
> ARM Ecynos 5410 (973 vs 963) but for Intel Haswell the performance
> results are practically the same (Haswell has a very good
> sophisticated memory sub-system).

I ran SPEC2k on AArch64, and EON fails to run correctly with -fno-caller-saves
-mcpu=cortex-a57 -fomit-frame-pointer -Ofast. I'm not sure whether this is
AArch64 specific, but previously non-optimal register allocation choices triggered
A latent bug in ree (it's unclear why GCC still allocates FP registers in 
high-pressure integer code, as I set the costs for int<->FP moves high).

On SPECINT2k performance is ~0.5% worse (5.5% regression on perlbmk), and 
SPECFP is ~0.2% faster.

Generally I think it is good to have a specific pass for rematerialization.
However should this not also affect the costs of instructions that can be 
cheaply rematerialized? Similarly for the choice whether to caller save or spill 
(today the caller-save code doesn't care at all about rematerialization, so it 
aggressively caller-saves values which could be rematerialized - see eg. 
https://gcc.gnu.org/ml/gcc/2014-09/msg00071.html).

Also I am confused by the claim "memory reads are not profitable to rematerialize". 
Surely rematerializing a memory read from const-data or literal pool is cheaper
than spilling as you avoid a store to the stack?

Wilco
Vladimir Makarov Oct. 14, 2014, 2:17 p.m. UTC | #5 
On 10/13/2014 12:24 PM, Wilco Dijkstra wrote:
>>   Here is a new rematerialization sub-pass of LRA.
>>
>>   I've tested and benchmarked the sub-pass on x86-64 and ARM.  The
>> sub-pass permits to generate a smaller code in average on both
>> architecture (although improvement no-significant), adds < 0.4%
>> additional compilation time in -O2 mode of release GCC (according user
>> time of compilation of 500K lines fortran program and valgrind lakey #
>> insns in combine.i compilation) and about 0.7% in -O0 mode.  As the
>> performance result, the best I found is 1% SPECFP2000 improvement on
>> ARM Ecynos 5410 (973 vs 963) but for Intel Haswell the performance
>> results are practically the same (Haswell has a very good
>> sophisticated memory sub-system).
> I ran SPEC2k on AArch64, and EON fails to run correctly with -fno-caller-saves
> -mcpu=cortex-a57 -fomit-frame-pointer -Ofast. I'm not sure whether this is
> AArch64 specific, but previously non-optimal register allocation choices triggered
> A latent bug in ree (it's unclear why GCC still allocates FP registers in 
> high-pressure integer code, as I set the costs for int<->FP moves high).
>
> On SPECINT2k performance is ~0.5% worse (5.5% regression on perlbmk), and 
> SPECFP is ~0.2% faster.
Thanks for reporting this.  It is important for me as I have no aarch64
machine for benchmarking.

Perlbmk performance degradation is too big and I'll definitely look at
this problem.

> Generally I think it is good to have a specific pass for rematerialization.
> However should this not also affect the costs of instructions that can be 
> cheaply rematerialized? Similarly for the choice whether to caller save or spill 
> (today the caller-save code doesn't care at all about rematerialization, so it 
> aggressively caller-saves values which could be rematerialized - see eg. 
> https://gcc.gnu.org/ml/gcc/2014-09/msg00071.html).
I wanted to address the cost issues later but I guess perlbmk
performance problem might be solved by this.  So I'll be starting
working on this.

The rematerialization pass can fix caller-saves code if we add
processing move insns too.  So it could be another project to improve
the rematerialization.  Thanks for pointing this out.
 
>
> Also I am confused by the claim "memory reads are not profitable to rematerialize". 
> Surely rematerializing a memory read from const-data or literal pool is cheaper
> than spilling as you avoid a store to the stack?
>
Most such cases are covered by cfg-insensitive rematerialization but I
guess there are cfg-sensitve cases.  I should try this too.

Wilco, thanks for very informative email with three ideas to improve the
rematerialization.  As I wrote the patch is an initial implementation of
the rematerialization and the infrastructure with modifications will be
able to handle these and other improvements.  Most important we have the
infrastructure in the right place now,
Wilco Oct. 14, 2014, 4:01 p.m. UTC | #6 
> Vladimir Makarov wrote:
> > On SPECINT2k performance is ~0.5% worse (5.5% regression on perlbmk), and
> > SPECFP is ~0.2% faster.
> Thanks for reporting this.  It is important for me as I have no aarch64
> machine for benchmarking.
> 
> Perlbmk performance degradation is too big and I'll definitely look at
> this problem.

Looking at the diffs in regexec.c which has the hot function regmatch(), 
nothing obvious stands out that could cause a serious regression.
I did notice this around line 2300:

.L802:
        ldr     x1, [x23, 48]
        adrp    x5, PL_savestack_ix
        ldr     w0, [x23]
        str     x5, [sp, 104]
        str     x1, [x24, #:lo12:PL_regcc]
        ldr     w27, [x1, 4]
        bl      regcppush
-       ldr     x5, [sp, 104]        
        str     w0, [sp, 112]
        ldr     x0, [x23, 32]
+       adrp    x5, PL_savestack_ix
        ldr     w28, [x5, #:lo12:PL_savestack_ix]
+       str     x5, [sp, 104]
        bl      regmatch
        ldr     x5, [sp, 104]
        mov     w19, w0
        ldr     w1, [sp, 112]
        ldr     w0, [x5, #:lo12:PL_savestack_ix]

So it rematerializes once instance, but fails to rematerialize the second use. 
An extra store is inserted, and the first adrp and store are not removed as dead.

Wilco
Wilco Oct. 14, 2014, 4:37 p.m. UTC | #7 
> Wilco Dijkstra wrote:
> > Vladimir Makarov wrote:
> > > On SPECINT2k performance is ~0.5% worse (5.5% regression on perlbmk), and
> > > SPECFP is ~0.2% faster.
> > Thanks for reporting this.  It is important for me as I have no aarch64
> > machine for benchmarking.
> >
> > Perlbmk performance degradation is too big and I'll definitely look at
> > this problem.
> 
> Looking at the diffs in regexec.c which has the hot function regmatch(),
> nothing obvious stands out that could cause a serious regression.
> I did notice this around line 2300:
> 
> .L802:
>         ldr     x1, [x23, 48]
>         adrp    x5, PL_savestack_ix
>         ldr     w0, [x23]
>         str     x5, [sp, 104]
>         str     x1, [x24, #:lo12:PL_regcc]
>         ldr     w27, [x1, 4]
>         bl      regcppush
> -       ldr     x5, [sp, 104]
>         str     w0, [sp, 112]
>         ldr     x0, [x23, 32]
> +       adrp    x5, PL_savestack_ix
>         ldr     w28, [x5, #:lo12:PL_savestack_ix]
> +       str     x5, [sp, 104]
>         bl      regmatch
>         ldr     x5, [sp, 104]
>         mov     w19, w0
>         ldr     w1, [sp, 112]
>         ldr     w0, [x5, #:lo12:PL_savestack_ix]
> 
> So it rematerializes once instance, but fails to rematerialize the second use.
> An extra store is inserted, and the first adrp and store are not removed as dead.

A simple example that reproduces the issue (-mcpu=cortex-a57 -O2 -fomit-frame-pointer 
-ffixed-x19 -ffixed-x20 -ffixed-x21 -ffixed-x22 -ffixed-x23 -ffixed-x24 -ffixed-x25 
-ffixed-x26 -ffixed-x27 -ffixed-x28 -ffixed-x29 -ffixed-x30). It looks like an odd
interaction between -fcaller-saves and rematerialization.

void g(void);
int x;
int f3b(int y)
{
   y += x;
   g();
   y += x;
   g();
   y += x;
   return y;
}

f3b:
        adrp    x2, x   --> DEAD
        sub     sp, sp, #16
        ldr     w1, [x2, #:lo12:x]
        str     x2, [sp]  --> DEAD
        add     w0, w0, w1
        str     w0, [sp]  --> reuse of stackslot!!!
        bl      g
        adrp    x2, x
        ldr     w0, [sp]
        ldr     w1, [x2, #:lo12:x]
        str     x2, [sp, 8]
        add     w0, w0, w1
        str     w0, [sp]  --> REMOVE
        bl      g
        ldr     x2, [sp, 8] --> rematerialize adrp
        ldr     w0, [sp]
        add     sp, sp, 16
        ldr     w1, [x2, #:lo12:x]
        add     w0, w0, w1
        ret

Wilco
Vladimir Makarov Oct. 15, 2014, 4:30 p.m. UTC | #8 
On 2014-10-14 12:01 PM, Wilco Dijkstra wrote:
>> Vladimir Makarov wrote:
>>> On SPECINT2k performance is ~0.5% worse (5.5% regression on perlbmk), and
>>> SPECFP is ~0.2% faster.
>> Thanks for reporting this.  It is important for me as I have no aarch64
>> machine for benchmarking.
>>
>> Perlbmk performance degradation is too big and I'll definitely look at
>> this problem.
>
> Looking at the diffs in regexec.c which has the hot function regmatch(),
> nothing obvious stands out that could cause a serious regression.
> I did notice this around line 2300:
>
> .L802:
>          ldr     x1, [x23, 48]
>          adrp    x5, PL_savestack_ix
>          ldr     w0, [x23]
>          str     x5, [sp, 104]
>          str     x1, [x24, #:lo12:PL_regcc]
>          ldr     w27, [x1, 4]
>          bl      regcppush
> -       ldr     x5, [sp, 104]
>          str     w0, [sp, 112]
>          ldr     x0, [x23, 32]
> +       adrp    x5, PL_savestack_ix
>          ldr     w28, [x5, #:lo12:PL_savestack_ix]
> +       str     x5, [sp, 104]
>          bl      regmatch
>          ldr     x5, [sp, 104]
>          mov     w19, w0
>          ldr     w1, [sp, 112]
>          ldr     w0, [x5, #:lo12:PL_savestack_ix]
>
> So it rematerializes once instance, but fails to rematerialize the second use.
> An extra store is inserted, and the first adrp and store are not removed as dead.
>

Thanks for the analysis.  Dead store elimination would help 
rematerialization.  LRA can not update global life info as it does not 
use DF-infrastracture for compile speed reasons.  However LRA does local 
life info analysis (or in EBBs).  So in some simple cases we can 
implement removing dead stores (at this stage it is still pseudo instead 
of memory).  I'll think what can I do here.
diff mbox

Patch

Index: Makefile.in
===================================================================
--- Makefile.in	(revision 216039)
+++ Makefile.in	(working copy)
@@ -1296,6 +1296,7 @@  OBJS = \
 	lra-constraints.o \
 	lra-eliminations.o \
 	lra-lives.o \
+	lra-remat.o \
 	lra-spills.o \
 	lto-cgraph.o \
 	lto-streamer.o \
Index: common.opt
===================================================================
--- common.opt	(revision 216039)
+++ common.opt	(working copy)
@@ -1530,6 +1530,10 @@  floop-optimize
 Common Ignore
 Does nothing.  Preserved for backward compatibility.
 
+flra-remat
+Common Report Var(flag_lra_remat) Optimization
+Do CFG-sensitive rematerialization in LRA
+
 flto
 Common
 Enable link-time optimization.
Index: doc/invoke.texi
===================================================================
--- doc/invoke.texi	(revision 216039)
+++ doc/invoke.texi	(working copy)
@@ -390,7 +390,7 @@  Objective-C and Objective-C++ Dialects}.
 -fisolate-erroneous-paths-dereference -fisolate-erroneous-paths-attribute @gol
 -fivopts -fkeep-inline-functions -fkeep-static-consts -flive-range-shrinkage @gol
 -floop-block -floop-interchange -floop-strip-mine -floop-nest-optimize @gol
--floop-parallelize-all -flto -flto-compression-level @gol
+-floop-parallelize-all -flra-remat -flto -flto-compression-level @gol
 -flto-partition=@var{alg} -flto-report -flto-report-wpa -fmerge-all-constants @gol
 -fmerge-constants -fmodulo-sched -fmodulo-sched-allow-regmoves @gol
 -fmove-loop-invariants -fno-branch-count-reg @gol
@@ -7136,6 +7136,7 @@  also turns on the following optimization
 -findirect-inlining @gol
 -fipa-cp @gol
 -fipa-sra @gol
+-flra-remat @gol
 -fisolate-erroneous-paths-dereference @gol
 -foptimize-sibling-calls @gol
 -foptimize-strlen @gol
@@ -7765,6 +7766,14 @@  Control the verbosity of the dump file f
 The default value is 5.  If the value @var{n} is greater or equal to 10,
 the dump output is sent to stderr using the same format as @var{n} minus 10.
 
+@item -flra-remat
+@opindex fcaller-saves
+Enable CFG-sensitive rematerialization in LRA.  Instead of loading
+values of spilled pseudos, LRA tries to rematerialize (recalculate)
+values if it is profitable.
+
+Enabled at levels @option{-O2}, @option{-O3}, @option{-Os}.
+
 @item -fdelayed-branch
 @opindex fdelayed-branch
 If supported for the target machine, attempt to reorder instructions
Index: doc/passes.texi
===================================================================
--- doc/passes.texi	(revision 216039)
+++ doc/passes.texi	(working copy)
@@ -911,10 +911,10 @@  Source files are @file{reload.c} and @fi
 This pass is a modern replacement of the reload pass.  Source files
 are @file{lra.c}, @file{lra-assign.c}, @file{lra-coalesce.c},
 @file{lra-constraints.c}, @file{lra-eliminations.c},
-@file{lra-equivs.c}, @file{lra-lives.c}, @file{lra-saves.c},
-@file{lra-spills.c}, the header @file{lra-int.h} used for
-communication between them, and the header @file{lra.h} used for
-communication between LRA and the rest of compiler.
+@file{lra-lives.c}, @file{lra-remat.c}, @file{lra-spills.c}, the
+header @file{lra-int.h} used for communication between them, and the
+header @file{lra.h} used for communication between LRA and the rest of
+compiler.
 
 Unlike the reload pass, intermediate LRA decisions are reflected in
 RTL as much as possible.  This reduces the number of target-dependent
Index: lra-constraints.c
===================================================================
--- lra-constraints.c	(revision 216039)
+++ lra-constraints.c	(working copy)
@@ -497,7 +497,8 @@  get_equiv_with_elimination (rtx x, rtx_i
 
   if (x == res || CONSTANT_P (res))
     return res;
-  return lra_eliminate_regs_1 (insn, res, GET_MODE (res), false, false, true);
+  return lra_eliminate_regs_1 (insn, res, GET_MODE (res),
+			       0, false, false, true);
 }
 
 /* Set up curr_operand_mode.  */
@@ -1234,12 +1235,16 @@  static bool no_input_reloads_p, no_outpu
    insn.  */
 static int curr_swapped;
 
-/* Arrange for address element *LOC to be a register of class CL.
-   Add any input reloads to list BEFORE.  AFTER is nonnull if *LOC is an
-   automodified value; handle that case by adding the required output
-   reloads to list AFTER.  Return true if the RTL was changed.  */
+/* if CHECK_ONLY_P is false, arrange for address element *LOC to be a
+   register of class CL.  Add any input reloads to list BEFORE.  AFTER
+   is nonnull if *LOC is an automodified value; handle that case by
+   adding the required output reloads to list AFTER.  Return true if
+   the RTL was changed.
+
+   if CHECK_ONLY_P is true, check that the *LOC is a correct address
+   register.  Return false if the address register is correct.  */
 static bool
-process_addr_reg (rtx *loc, rtx_insn **before, rtx_insn **after,
+process_addr_reg (rtx *loc, bool check_only_p, rtx_insn **before, rtx_insn **after,
 		  enum reg_class cl)
 {
   int regno;
@@ -1256,6 +1261,8 @@  process_addr_reg (rtx *loc, rtx_insn **b
   mode = GET_MODE (reg);
   if (! REG_P (reg))
     {
+      if (check_only_p)
+	return true;
       /* Always reload memory in an address even if the target supports
 	 such addresses.  */
       new_reg = lra_create_new_reg_with_unique_value (mode, reg, cl, "address");
@@ -1265,7 +1272,8 @@  process_addr_reg (rtx *loc, rtx_insn **b
     {
       regno = REGNO (reg);
       rclass = get_reg_class (regno);
-      if ((*loc = get_equiv_with_elimination (reg, curr_insn)) != reg)
+      if (! check_only_p
+	  && (*loc = get_equiv_with_elimination (reg, curr_insn)) != reg)
 	{
 	  if (lra_dump_file != NULL)
 	    {
@@ -1279,6 +1287,8 @@  process_addr_reg (rtx *loc, rtx_insn **b
 	}
       if (*loc != reg || ! in_class_p (reg, cl, &new_class))
 	{
+	  if (check_only_p)
+	    return true;
 	  reg = *loc;
 	  if (get_reload_reg (after == NULL ? OP_IN : OP_INOUT,
 			      mode, reg, cl, subreg_p, "address", &new_reg))
@@ -1286,6 +1296,8 @@  process_addr_reg (rtx *loc, rtx_insn **b
 	}
       else if (new_class != NO_REGS && rclass != new_class)
 	{
+	  if (check_only_p)
+	    return true;
 	  lra_change_class (regno, new_class, "	   Change to", true);
 	  return false;
 	}
@@ -2731,8 +2743,9 @@  equiv_address_substitution (struct addre
   return change_p;
 }
 
-/* Major function to make reloads for an address in operand NOP.
-   The supported cases are:
+/* Major function to make reloads for an address in operand NOP or
+   check its correctness (If CHECK_ONLY_P is true). The supported
+   cases are:
 
    1) an address that existed before LRA started, at which point it
    must have been valid.  These addresses are subject to elimination
@@ -2752,18 +2765,19 @@  equiv_address_substitution (struct addre
    address.  Return true for any RTL change.
 
    The function is a helper function which does not produce all
-   transformations which can be necessary.  It does just basic steps.
-   To do all necessary transformations use function
-   process_address.  */
+   transformations (when CHECK_ONLY_P is false) which can be
+   necessary.  It does just basic steps.  To do all necessary
+   transformations use function process_address.  */
 static bool
-process_address_1 (int nop, rtx_insn **before, rtx_insn **after)
+process_address_1 (int nop, bool check_only_p,
+		   rtx_insn **before, rtx_insn **after)
 {
   struct address_info ad;
   rtx new_reg;
   rtx op = *curr_id->operand_loc[nop];
   const char *constraint = curr_static_id->operand[nop].constraint;
   enum constraint_num cn = lookup_constraint (constraint);
-  bool change_p;
+  bool change_p = false;
 
   if (insn_extra_address_constraint (cn))
     decompose_lea_address (&ad, curr_id->operand_loc[nop]);
@@ -2774,10 +2788,11 @@  process_address_1 (int nop, rtx_insn **b
     decompose_mem_address (&ad, SUBREG_REG (op));
   else
     return false;
-  change_p = equiv_address_substitution (&ad);
+  if (! check_only_p)
+    change_p = equiv_address_substitution (&ad);
   if (ad.base_term != NULL
       && (process_addr_reg
-	  (ad.base_term, before,
+	  (ad.base_term, check_only_p, before,
 	   (ad.autoinc_p
 	    && !(REG_P (*ad.base_term)
 		 && find_regno_note (curr_insn, REG_DEAD,
@@ -2791,7 +2806,8 @@  process_address_1 (int nop, rtx_insn **b
 	*ad.base_term2 = *ad.base_term;
     }
   if (ad.index_term != NULL
-      && process_addr_reg (ad.index_term, before, NULL, INDEX_REG_CLASS))
+      && process_addr_reg (ad.index_term, check_only_p,
+			   before, NULL, INDEX_REG_CLASS))
     change_p = true;
 
   /* Target hooks sometimes don't treat extra-constraint addresses as
@@ -2800,6 +2816,9 @@  process_address_1 (int nop, rtx_insn **b
       && satisfies_address_constraint_p (&ad, cn))
     return change_p;
 
+  if (check_only_p)
+    return change_p;
+
   /* There are three cases where the shape of *AD.INNER may now be invalid:
 
      1) the original address was valid, but either elimination or
@@ -2968,15 +2987,24 @@  process_address_1 (int nop, rtx_insn **b
   return true;
 }
 
-/* Do address reloads until it is necessary.  Use process_address_1 as
-   a helper function.  Return true for any RTL changes.  */
+/* If CHECK_ONLY_P is false, do address reloads until it is necessary.
+   Use process_address_1 as a helper function.  Return true for any
+   RTL changes.
+
+   If CHECK_ONLY_P is true, just check address correctness.  Return
+   false if the address correct.  */
 static bool
-process_address (int nop, rtx_insn **before, rtx_insn **after)
+process_address (int nop, bool check_only_p,
+		 rtx_insn **before, rtx_insn **after)
 {
   bool res = false;
 
-  while (process_address_1 (nop, before, after))
-    res = true;
+  while (process_address_1 (nop, check_only_p, before, after))
+    {
+      if (check_only_p)
+	return true;
+      res = true;
+    }
   return res;
 }
 
@@ -3148,9 +3176,15 @@  swap_operands (int nop)
    model can be changed in future.  Make commutative operand exchange
    if it is chosen.
 
-   Return true if some RTL changes happened during function call.  */
+   if CHECK_ONLY_P is false, do RTL changes to satisfy the
+   constraints.  Return true if any change happened during function
+   call.
+
+   If CHECK_ONLY_P is true then don't do any transformation.  Just
+   check that the insn satisfies all constraints.  If the insn does
+   not satisfy any constraint, return true.  */
 static bool
-curr_insn_transform (void)
+curr_insn_transform (bool check_only_p)
 {
   int i, j, k;
   int n_operands;
@@ -3217,50 +3251,53 @@  curr_insn_transform (void)
   curr_swapped = false;
   goal_alt_swapped = false;
 
-  /* Make equivalence substitution and memory subreg elimination
-     before address processing because an address legitimacy can
-     depend on memory mode.  */
-  for (i = 0; i < n_operands; i++)
-    {
-      rtx op = *curr_id->operand_loc[i];
-      rtx subst, old = op;
-      bool op_change_p = false;
-
-      if (GET_CODE (old) == SUBREG)
-	old = SUBREG_REG (old);
-      subst = get_equiv_with_elimination (old, curr_insn);
-      if (subst != old)
-	{
-	  subst = copy_rtx (subst);
-	  lra_assert (REG_P (old));
-	  if (GET_CODE (op) == SUBREG)
-	    SUBREG_REG (op) = subst;
-	  else
-	    *curr_id->operand_loc[i] = subst;
-	  if (lra_dump_file != NULL)
-	    {
-	      fprintf (lra_dump_file,
-		       "Changing pseudo %d in operand %i of insn %u on equiv ",
-		       REGNO (old), i, INSN_UID (curr_insn));
-	      dump_value_slim (lra_dump_file, subst, 1);
+  if (! check_only_p)
+    /* Make equivalence substitution and memory subreg elimination
+       before address processing because an address legitimacy can
+       depend on memory mode.  */
+    for (i = 0; i < n_operands; i++)
+      {
+	rtx op = *curr_id->operand_loc[i];
+	rtx subst, old = op;
+	bool op_change_p = false;
+	
+	if (GET_CODE (old) == SUBREG)
+	  old = SUBREG_REG (old);
+	subst = get_equiv_with_elimination (old, curr_insn);
+	if (subst != old)
+	  {
+	    subst = copy_rtx (subst);
+	    lra_assert (REG_P (old));
+	    if (GET_CODE (op) == SUBREG)
+	      SUBREG_REG (op) = subst;
+	    else
+	      *curr_id->operand_loc[i] = subst;
+	    if (lra_dump_file != NULL)
+	      {
+		fprintf (lra_dump_file,
+			 "Changing pseudo %d in operand %i of insn %u on equiv ",
+			 REGNO (old), i, INSN_UID (curr_insn));
+		dump_value_slim (lra_dump_file, subst, 1);
 	      fprintf (lra_dump_file, "\n");
-	    }
-	  op_change_p = change_p = true;
-	}
-      if (simplify_operand_subreg (i, GET_MODE (old)) || op_change_p)
-	{
-	  change_p = true;
-	  lra_update_dup (curr_id, i);
-	}
-    }
+	      }
+	    op_change_p = change_p = true;
+	  }
+	if (simplify_operand_subreg (i, GET_MODE (old)) || op_change_p)
+	  {
+	    change_p = true;
+	    lra_update_dup (curr_id, i);
+	  }
+      }
 
   /* Reload address registers and displacements.  We do it before
      finding an alternative because of memory constraints.  */
   before = after = NULL;
   for (i = 0; i < n_operands; i++)
     if (! curr_static_id->operand[i].is_operator
-	&& process_address (i, &before, &after))
+	&& process_address (i, check_only_p, &before, &after))
       {
+	if (check_only_p)
+	  return true;
 	change_p = true;
 	lra_update_dup (curr_id, i);
       }
@@ -3270,13 +3307,13 @@  curr_insn_transform (void)
        we chose previously may no longer be valid.  */
     lra_set_used_insn_alternative (curr_insn, -1);
 
-  if (curr_insn_set != NULL_RTX
+  if (! check_only_p && curr_insn_set != NULL_RTX
       && check_and_process_move (&change_p, &sec_mem_p))
     return change_p;
 
  try_swapped:
 
-  reused_alternative_num = curr_id->used_insn_alternative;
+  reused_alternative_num = check_only_p ? -1 : curr_id->used_insn_alternative;
   if (lra_dump_file != NULL && reused_alternative_num >= 0)
     fprintf (lra_dump_file, "Reusing alternative %d for insn #%u\n",
 	     reused_alternative_num, INSN_UID (curr_insn));
@@ -3284,6 +3321,9 @@  curr_insn_transform (void)
   if (process_alt_operands (reused_alternative_num))
     alt_p = true;
 
+  if (check_only_p)
+    return ! alt_p || best_losers != 0;
+
   /* If insn is commutative (it's safe to exchange a certain pair of
      operands) then we need to try each alternative twice, the second
      time matching those two operands as if we had exchanged them.  To
@@ -3513,7 +3553,7 @@  curr_insn_transform (void)
 
 	    *curr_id->operand_loc[i] = tem;
 	    lra_update_dup (curr_id, i);
-	    process_address (i, &before, &after);
+	    process_address (i, false, &before, &after);
 
 	    /* If the alternative accepts constant pool refs directly
 	       there will be no reload needed at all.  */
@@ -3737,6 +3777,26 @@  curr_insn_transform (void)
   return change_p;
 }
 
+/* Return true if INSN satisfies all constraints.  In other words, no
+   reload insns are needed.  */
+bool
+lra_constrain_insn (rtx_insn *insn)
+{
+  int saved_new_regno_start = new_regno_start;
+  int saved_new_insn_uid_start = new_insn_uid_start;
+  bool change_p;
+
+  curr_insn = insn;
+  curr_id = lra_get_insn_recog_data (curr_insn);
+  curr_static_id = curr_id->insn_static_data;
+  new_insn_uid_start = get_max_uid ();
+  new_regno_start = max_reg_num ();
+  change_p = curr_insn_transform (true);
+  new_regno_start = saved_new_regno_start;
+  new_insn_uid_start = saved_new_insn_uid_start;
+  return ! change_p;
+}
+
 /* Return true if X is in LIST.	 */
 static bool
 in_list_p (rtx x, rtx list)
@@ -4200,7 +4260,7 @@  lra_constraints (bool first_p)
 	  curr_static_id = curr_id->insn_static_data;
 	  init_curr_insn_input_reloads ();
 	  init_curr_operand_mode ();
-	  if (curr_insn_transform ())
+	  if (curr_insn_transform (false))
 	    changed_p = true;
 	  /* Check non-transformed insns too for equiv change as USE
 	     or CLOBBER don't need reloads but can contain pseudos
Index: lra-eliminations.c
===================================================================
--- lra-eliminations.c	(revision 216039)
+++ lra-eliminations.c	(working copy)
@@ -290,7 +290,8 @@  get_elimination (rtx reg)
    a change in the offset between the eliminable register and its
    substitution if UPDATE_P, or the full offset if FULL_P, or
    otherwise zero.  If FULL_P, we also use the SP offsets for
-   elimination to SP.
+   elimination to SP.  If UPDATE_P, use UPDATE_SP_OFFSET for updating
+   offsets of register elimnable to SP.
 
    MEM_MODE is the mode of an enclosing MEM.  We need this to know how
    much to adjust a register for, e.g., PRE_DEC.  Also, if we are
@@ -303,7 +304,8 @@  get_elimination (rtx reg)
    sp offset.  */
 rtx
 lra_eliminate_regs_1 (rtx_insn *insn, rtx x, enum machine_mode mem_mode,
-		      bool subst_p, bool update_p, bool full_p)
+		      bool subst_p, bool update_p,
+		      HOST_WIDE_INT update_sp_offset, bool full_p)
 {
   enum rtx_code code = GET_CODE (x);
   struct lra_elim_table *ep;
@@ -338,7 +340,10 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 	  rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
 
 	  if (update_p)
-	    return plus_constant (Pmode, to, ep->offset - ep->previous_offset);
+	    return plus_constant (Pmode, to,
+				  ep->offset - ep->previous_offset
+				  + (ep->to_rtx == stack_pointer_rtx
+				     ? update_sp_offset : 0));
 	  else if (full_p)
 	    return plus_constant (Pmode, to,
 				  ep->offset
@@ -365,7 +370,10 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 		return gen_rtx_PLUS (Pmode, to, XEXP (x, 1));
 
 	      offset = (update_p
-			? ep->offset - ep->previous_offset : ep->offset);
+			? ep->offset - ep->previous_offset
+			+ (ep->to_rtx == stack_pointer_rtx
+			   ? update_sp_offset : 0)
+			: ep->offset);
 	      if (full_p && insn != NULL_RTX && ep->to_rtx == stack_pointer_rtx)
 		offset -= lra_get_insn_recog_data (insn)->sp_offset;
 	      if (CONST_INT_P (XEXP (x, 1))
@@ -394,9 +402,11 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 
       {
 	rtx new0 = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
-					 subst_p, update_p, full_p);
+					 subst_p, update_p,
+					 update_sp_offset, full_p);
 	rtx new1 = lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
-					 subst_p, update_p, full_p);
+					 subst_p, update_p,
+					 update_sp_offset, full_p);
 
 	if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
 	  return form_sum (new0, new1);
@@ -415,11 +425,12 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 	  rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
 
 	  if (update_p)
-	    return
-	      plus_constant (Pmode,
-			     gen_rtx_MULT (Pmode, to, XEXP (x, 1)),
-			     (ep->offset - ep->previous_offset)
-			     * INTVAL (XEXP (x, 1)));
+	    return plus_constant (Pmode,
+				  gen_rtx_MULT (Pmode, to, XEXP (x, 1)),
+				  (ep->offset - ep->previous_offset
+				   + (ep->to_rtx == stack_pointer_rtx
+				      ? update_sp_offset : 0))
+				  * INTVAL (XEXP (x, 1)));
 	  else if (full_p)
 	    {
 	      HOST_WIDE_INT offset = ep->offset;
@@ -451,10 +462,12 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
     case LE:	   case LT:	  case LEU:    case LTU:
       {
 	rtx new0 = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
-					 subst_p, update_p, full_p);
+					 subst_p, update_p, 
+					 update_sp_offset, full_p);
 	rtx new1 = XEXP (x, 1)
 		   ? lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
-					   subst_p, update_p, full_p) : 0;
+					   subst_p, update_p,
+					   update_sp_offset, full_p) : 0;
 
 	if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
 	  return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1);
@@ -467,7 +480,8 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
       if (XEXP (x, 0))
 	{
 	  new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
-					  subst_p, update_p, full_p);
+					  subst_p, update_p,
+					  update_sp_offset, full_p);
 	  if (new_rtx != XEXP (x, 0))
 	    {
 	      /* If this is a REG_DEAD note, it is not valid anymore.
@@ -476,7 +490,8 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 	      if (REG_NOTE_KIND (x) == REG_DEAD)
 		return (XEXP (x, 1)
 			? lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
-						subst_p, update_p, full_p)
+						subst_p, update_p,
+						update_sp_offset, full_p)
 			: NULL_RTX);
 
 	      x = alloc_reg_note (REG_NOTE_KIND (x), new_rtx, XEXP (x, 1));
@@ -493,7 +508,8 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
       if (XEXP (x, 1))
 	{
 	  new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
-					  subst_p, update_p, full_p);
+					  subst_p, update_p,
+					  update_sp_offset, full_p);
 	  if (new_rtx != XEXP (x, 1))
 	    return
 	      gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x),
@@ -520,8 +536,8 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 	  && XEXP (XEXP (x, 1), 0) == XEXP (x, 0))
 	{
 	  rtx new_rtx = lra_eliminate_regs_1 (insn, XEXP (XEXP (x, 1), 1),
-					      mem_mode,
-					      subst_p, update_p, full_p);
+					      mem_mode, subst_p, update_p,
+					      update_sp_offset, full_p);
 
 	  if (new_rtx != XEXP (XEXP (x, 1), 1))
 	    return gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (x, 0),
@@ -545,14 +561,16 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
     case PARITY:
     case BSWAP:
       new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
-				      subst_p, update_p, full_p);
+				      subst_p, update_p,
+				      update_sp_offset, full_p);
       if (new_rtx != XEXP (x, 0))
 	return gen_rtx_fmt_e (code, GET_MODE (x), new_rtx);
       return x;
 
     case SUBREG:
       new_rtx = lra_eliminate_regs_1 (insn, SUBREG_REG (x), mem_mode,
-				      subst_p, update_p, full_p);
+				      subst_p, update_p,
+				      update_sp_offset, full_p);
 
       if (new_rtx != SUBREG_REG (x))
 	{
@@ -590,12 +608,12 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 	replace_equiv_address_nv
 	(x,
 	 lra_eliminate_regs_1 (insn, XEXP (x, 0), GET_MODE (x),
-			       subst_p, update_p, full_p));
+			       subst_p, update_p, update_sp_offset, full_p));
 
     case USE:
       /* Handle insn_list USE that a call to a pure function may generate.  */
       new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 0), VOIDmode,
-				      subst_p, update_p, full_p);
+				      subst_p, update_p, update_sp_offset, full_p);
       if (new_rtx != XEXP (x, 0))
 	return gen_rtx_USE (GET_MODE (x), new_rtx);
       return x;
@@ -616,7 +634,8 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
       if (*fmt == 'e')
 	{
 	  new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, i), mem_mode,
-					  subst_p, update_p, full_p);
+					  subst_p, update_p,
+					  update_sp_offset, full_p);
 	  if (new_rtx != XEXP (x, i) && ! copied)
 	    {
 	      x = shallow_copy_rtx (x);
@@ -630,7 +649,8 @@  lra_eliminate_regs_1 (rtx_insn *insn, rt
 	  for (j = 0; j < XVECLEN (x, i); j++)
 	    {
 	      new_rtx = lra_eliminate_regs_1 (insn, XVECEXP (x, i, j), mem_mode,
-					      subst_p, update_p, full_p);
+					      subst_p, update_p,
+					      update_sp_offset, full_p);
 	      if (new_rtx != XVECEXP (x, i, j) && ! copied_vec)
 		{
 		  rtvec new_v = gen_rtvec_v (XVECLEN (x, i),
@@ -657,7 +677,7 @@  rtx
 lra_eliminate_regs (rtx x, enum machine_mode mem_mode,
 		    rtx insn ATTRIBUTE_UNUSED)
 {
-  return lra_eliminate_regs_1 (NULL, x, mem_mode, true, false, true);
+  return lra_eliminate_regs_1 (NULL, x, mem_mode, true, false, 0, true);
 }
 
 /* Stack pointer offset before the current insn relative to one at the
@@ -842,13 +862,15 @@  remove_reg_equal_offset_note (rtx insn,
 
    If REPLACE_P is false, just update the offsets while keeping the
    base register the same.  If FIRST_P, use the sp offset for
-   elimination to sp.  Attach the note about used elimination for
-   insns setting frame pointer to update elimination easy (without
-   parsing already generated elimination insns to find offset
-   previously used) in future.  */
+   elimination to sp.  Otherwise, use UPDATE_SP_OFFSET for this.
+   Attach the note about used elimination for insns setting frame
+   pointer to update elimination easy (without parsing already
+   generated elimination insns to find offset previously used) in
+   future.  */
 
-static void
-eliminate_regs_in_insn (rtx_insn *insn, bool replace_p, bool first_p)
+void
+eliminate_regs_in_insn (rtx_insn *insn, bool replace_p, bool first_p,
+			HOST_WIDE_INT update_sp_offset)
 {
   int icode = recog_memoized (insn);
   rtx old_set = single_set (insn);
@@ -978,8 +1000,13 @@  eliminate_regs_in_insn (rtx_insn *insn,
 	  if (! replace_p)
 	    {
 	      offset += (ep->offset - ep->previous_offset);
-	      if (first_p && ep->to_rtx == stack_pointer_rtx)
-		offset -= lra_get_insn_recog_data (insn)->sp_offset;
+	      if (ep->to_rtx == stack_pointer_rtx)
+		{
+		  if (first_p)
+		    offset -= lra_get_insn_recog_data (insn)->sp_offset;
+		  else
+		    offset += update_sp_offset;
+		}
 	      offset = trunc_int_for_mode (offset, GET_MODE (plus_cst_src));
 	    }
 
@@ -1053,7 +1080,7 @@  eliminate_regs_in_insn (rtx_insn *insn,
 	  substed_operand[i]
 	    = lra_eliminate_regs_1 (insn, *id->operand_loc[i], VOIDmode,
 				    replace_p, ! replace_p && ! first_p,
-				    first_p);
+				    update_sp_offset, first_p);
 	  if (substed_operand[i] != orig_operand[i])
 	    validate_p = true;
 	}
@@ -1341,7 +1368,7 @@  lra_eliminate_reg_if_possible (rtx *loc)
 static void
 process_insn_for_elimination (rtx_insn *insn, bool final_p, bool first_p)
 {
-  eliminate_regs_in_insn (insn, final_p, first_p);
+  eliminate_regs_in_insn (insn, final_p, first_p, 0);
   if (! final_p)
     {
       /* Check that insn changed its code.  This is a case when a move
Index: lra-int.h
===================================================================
--- lra-int.h	(revision 216039)
+++ lra-int.h	(working copy)
@@ -323,7 +323,6 @@  extern bitmap_head lra_inheritance_pseud
 extern bitmap_head lra_split_regs;
 extern bitmap_head lra_subreg_reload_pseudos;
 extern bitmap_head lra_optional_reload_pseudos;
-extern int lra_constraint_new_insn_uid_start;
 
 /* lra-constraints.c: */
 
@@ -335,6 +334,7 @@  extern int lra_constraint_iter_after_spi
 extern bool lra_risky_transformations_p;
 extern int lra_inheritance_iter;
 extern int lra_undo_inheritance_iter;
+extern bool lra_constrain_insn (rtx_insn *);
 extern bool lra_constraints (bool);
 extern void lra_constraints_init (void);
 extern void lra_constraints_finish (void);
@@ -383,13 +383,17 @@  extern bool lra_need_for_spills_p (void)
 extern void lra_spill (void);
 extern void lra_final_code_change (void);
 
+/* lra-remat.c:  */
+
+extern bool lra_remat (void);
 
 /* lra-elimination.c: */
 
 extern void lra_debug_elim_table (void);
 extern int lra_get_elimination_hard_regno (int);
-extern rtx lra_eliminate_regs_1 (rtx_insn *, rtx, enum machine_mode, bool,
-				 bool, bool);
+extern rtx lra_eliminate_regs_1 (rtx_insn *, rtx, enum machine_mode,
+				 bool, bool, HOST_WIDE_INT, bool);
+extern void eliminate_regs_in_insn (rtx_insn *insn, bool, bool, HOST_WIDE_INT);
 extern void lra_eliminate (bool, bool);
 
 extern void lra_eliminate_reg_if_possible (rtx *);
Index: lra-lives.c
===================================================================
--- lra-lives.c	(revision 216039)
+++ lra-lives.c	(working copy)
@@ -243,8 +243,7 @@  make_hard_regno_born (int regno)
   unsigned int i;
 
   lra_assert (regno < FIRST_PSEUDO_REGISTER);
-  if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
-      || TEST_HARD_REG_BIT (hard_regs_live, regno))
+  if (TEST_HARD_REG_BIT (hard_regs_live, regno))
     return;
   SET_HARD_REG_BIT (hard_regs_live, regno);
   sparseset_set_bit (start_living, regno);
@@ -258,8 +257,7 @@  static void
 make_hard_regno_dead (int regno)
 {
   lra_assert (regno < FIRST_PSEUDO_REGISTER);
-  if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
-      || ! TEST_HARD_REG_BIT (hard_regs_live, regno))
+  if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
     return;
   sparseset_set_bit (start_dying, regno);
   CLEAR_HARD_REG_BIT (hard_regs_live, regno);
@@ -501,7 +499,6 @@  process_bb_lives (basic_block bb, int &c
   sparseset_clear (pseudos_live_through_setjumps);
   REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
   AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
-  AND_COMPL_HARD_REG_SET (hard_regs_live, lra_no_alloc_regs);
   EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
     mark_pseudo_live (j, curr_point);
 
Index: lra-remat.c
===================================================================
--- lra-remat.c	(revision 0)
+++ lra-remat.c	(working copy)
@@ -0,0 +1,1225 @@ 
+/* Rematerialize pseudos values.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+   Contributed by Vladimir Makarov <vmakarov@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.	If not see
+<http://www.gnu.org/licenses/>.	 */
+
+/* This code objective is to rematerialize spilled pseudo values.  To
+   do this we calculate available insn candidates.  The candidate is
+   available at some point if there is dominated set of insns with the
+   same pattern, the insn inputs are not dying or modified on any path
+   from the set, the outputs are not modified.
+
+   The insns containing memory or spilled pseudos (except for the
+   rematerialized pseudo) are not considered as such insns are not
+   profitable in comparison with regular loads of spilled pseudo
+   values.  That simplifies the implementation as we don't need to
+   deal with memory aliasing.
+
+   To speed up available candidate calculation, we calculate partially
+   available candidates first and use them for initialization of the
+   availability.  That is because (partial) availability sets are
+   sparse.
+
+   The rematerialization sub-pass could be improved further in the
+   following ways:
+
+   o We could make longer live ranges of inputs in the
+     rematerialization candidates if their hard registers are not used
+     for other purposes.  This could be complicated if we need to
+     update BB live info information as LRA does not use
+     DF-infrastructure for compile-time reasons.  This problem could
+     be overcome if constrain making live ranges longer only in BB/EBB
+     scope.
+   o We could use cost-based decision to choose rematerialization insn
+     (currently all insns without memory is can be used).
+   o We could use other free hard regs for unused output pseudos in
+     rematerialization candidates although such cases probably will
+     be very rare.  */
+
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "output.h"
+#include "regs.h"
+#include "hard-reg-set.h"
+#include "flags.h"
+#include "function.h"
+#include "expr.h"
+#include "basic-block.h"
+#include "except.h"
+#include "timevar.h"
+#include "target.h"
+#include "lra-int.h"
+#include "ira.h"
+#include "df.h"
+
+/* Number of candidates for rematerialization.  */
+static unsigned int cands_num;
+
+/* The following is used for representation of call_used_reg_set in
+   form array whose elements are hard register numbers with nonzero bit
+   in CALL_USED_REG_SET. */
+static int call_used_regs_arr_len;
+static int call_used_regs_arr[FIRST_PSEUDO_REGISTER];
+
+/* Bitmap used for different calculations.  */
+static bitmap_head temp_bitmap;
+
+typedef struct cand *cand_t;
+typedef const struct cand *const_cand_t;
+
+/* Insn candidates for rematerialization.  The candidate insn should
+   have the following properies:
+   o no any memory (as access to memory is non-profitable)
+   o no INOUT regs (it means no non-paradoxical subreg of output reg)
+   o one output spilled pseudo (or reload pseudo of a spilled pseudo)
+   o all other pseudos are with assigned hard regs.  */
+struct cand
+{
+  /* Index of the candidates in all_cands. */
+  int index;
+  /* The candidate insn.  */
+  rtx_insn *insn;
+  /* Insn pseudo regno for rematerialization.  */
+  int regno;
+  /* Non-negative if a reload pseudo is in the insn instead of the
+     pseudo for rematerialization.  */
+  int reload_regno;
+  /* Number of the operand containing the regno or its reload
+     regno.  */
+  int nop;
+  /* Next candidate for the same regno.  */
+  cand_t next_regno_cand;
+};
+
+/* Vector containing all candidates.  */
+static vec<cand_t> all_cands;
+/* Map: insn -> candidate representing it.  It is null if the insn can
+   not be used for rematerialization.  */
+static cand_t *insn_to_cand;
+
+/* Map regno -> candidates can be used for the regno
+   rematerialization.  */
+static cand_t *regno_cands;
+
+/* Data about basic blocks used for the rematerialization
+   sub-pass.  */
+struct bb_data
+{
+  /* Basic block about which the below data are.  */
+  basic_block bb;
+  /* Registers changed in the basic block: */
+  bitmap_head changed_regs;
+  /* Registers becoming dead in the BB.  */
+  bitmap_head dead_regs;
+  /* Cands present in the BB whose in/out regs are not changed after
+     the cands occurence and are not dead (except the reload
+     regno).  */
+  bitmap_head gen_cands;
+  bitmap_head livein_cands; /* cands whose inputs live at the BB start.  */
+  bitmap_head pavin_cands; /* cands partially available at BB entry.  */
+  bitmap_head pavout_cands; /* cands partially available at BB exit.  */
+  bitmap_head avin_cands; /* cands available at the entry of the BB.  */
+  bitmap_head avout_cands; /* cands available at the exit of the BB.  */
+};
+
+/* Array for all BB data.  Indexed by the corresponding BB index.  */
+typedef struct bb_data *bb_data_t;
+
+/* Basic blocks for data flow problems -- all bocks except the special
+   ones.  */
+static bitmap_head all_blocks;
+
+/* All basic block data are referred through the following array.  */
+static bb_data_t bb_data;
+
+/* Two small functions for access to the bb data.  */
+static inline bb_data_t
+get_bb_data (basic_block bb)
+{
+  return &bb_data[(bb)->index];
+}
+
+static inline bb_data_t
+get_bb_data_by_index (int index)
+{
+  return &bb_data[index];
+}
+
+
+
+/* Dump bitmap SET with TITLE and BB INDEX.  */
+static void
+dump_bitmap_with_title (const char *title, bitmap set, int index)
+{
+  unsigned int i;
+  int count;
+  bitmap_iterator bi;
+  static const int max_nums_on_line = 10;
+
+  if (bitmap_empty_p (set))
+    return;
+  fprintf (lra_dump_file, "  %s %d:", title, index);
+  fprintf (lra_dump_file, "\n");
+  count = max_nums_on_line + 1;
+  EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+    {
+      if (count > max_nums_on_line)
+	{
+	  fprintf (lra_dump_file, "\n    ");
+	  count = 0;
+	}
+      fprintf (lra_dump_file, " %4u", i);
+      count++;
+    }
+  fprintf (lra_dump_file, "\n");
+}
+
+
+
+/* Recursive hash function for RTL X.  */
+static hashval_t
+rtx_hash (rtx x)
+{
+  int i, j;
+  enum rtx_code code;
+  const char *fmt;
+  hashval_t val = 0;
+
+  if (x == 0)
+    return val;
+
+  code = GET_CODE (x);
+  val += (int) code + 4095;
+
+  /* Some RTL can be compared nonrecursively.  */
+  switch (code)
+    {
+    case REG:
+      return val + REGNO (x);
+
+    case LABEL_REF:
+      return iterative_hash_object (XEXP (x, 0), val);
+
+    case SYMBOL_REF:
+      return iterative_hash_object (XSTR (x, 0), val);
+
+    case SCRATCH:
+    case CONST_DOUBLE:
+    case CONST_INT:
+    case CONST_VECTOR:
+      return val;
+
+    default:
+      break;
+    }
+
+  /* Hash the elements.  */
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      switch (fmt[i])
+	{
+	case 'w':
+	  val += XWINT (x, i);
+	  break;
+
+	case 'n':
+	case 'i':
+	  val += XINT (x, i);
+	  break;
+
+	case 'V':
+	case 'E':
+	  val += XVECLEN (x, i);
+
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    val += rtx_hash (XVECEXP (x, i, j));
+	  break;
+
+	case 'e':
+	  val += rtx_hash (XEXP (x, i));
+	  break;
+
+	case 'S':
+	case 's':
+	  val += htab_hash_string (XSTR (x, i));
+	  break;
+
+	case 'u':
+	case '0':
+	case 't':
+	  break;
+
+	  /* It is believed that rtx's at this level will never
+	     contain anything but integers and other rtx's, except for
+	     within LABEL_REFs and SYMBOL_REFs.  */
+	default:
+	  abort ();
+	}
+    }
+  return val;
+}
+
+
+
+/* Hash table for the candidates.  Different insns (e.g. structurally
+   the same insns or even insns with different unused output regs) can
+   be represented by the same candidate in the table.  */
+static htab_t cand_table;
+
+/* Hash function for candidate CAND.  */
+static hashval_t
+cand_hash (const void *cand)
+{
+  const_cand_t c = (const_cand_t) cand;
+  lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
+  struct lra_static_insn_data *static_id = id->insn_static_data;
+  int nops = static_id->n_operands;
+  hashval_t hash = 0;
+
+  for (int i = 0; i < nops; i++)
+    if (i == c->nop)
+      hash = iterative_hash_object (c->regno, hash);
+    else if (static_id->operand[i].type == OP_IN)
+      hash = iterative_hash_object (*id->operand_loc[i], hash);
+  return hash;
+}
+
+/* Equal function for candidates CAND1 and CAND2.  They are equal if
+   the corresponding candidate insns have the same code, the same
+   regno for rematerialization, the same input operands.  */
+static int
+cand_eq_p (const void *cand1, const void *cand2)
+{
+  const_cand_t c1 = (const_cand_t) cand1;
+  const_cand_t c2 = (const_cand_t) cand2;
+  lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
+  lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
+  struct lra_static_insn_data *static_id1 = id1->insn_static_data;
+  int nops = static_id1->n_operands;
+
+  if (c1->regno != c2->regno
+      || INSN_CODE (c1->insn) < 0
+      || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
+    return false;
+  gcc_assert (c1->nop == c2->nop);
+  for (int i = 0; i < nops; i++)
+    if (i != c1->nop && static_id1->operand[i].type == OP_IN
+	&& *id1->operand_loc[i] != *id2->operand_loc[i])
+      return false;
+  return true;
+}
+
+/* Insert candidate CAND into the table if it is not there yet.
+   Return candidate which is in the table.  */
+static cand_t
+insert_cand (cand_t cand)
+{
+  void **entry_ptr;
+
+  entry_ptr = htab_find_slot (cand_table, cand, INSERT);
+  if (*entry_ptr == NULL)
+    *entry_ptr = (void *) cand;
+  return (cand_t) *entry_ptr;
+}
+
+/* Free candidate CAND memory.  */
+static void
+free_cand (void *cand)
+{
+  free (cand);
+}
+
+/* Initiate the candidate table.  */
+static void
+initiate_cand_table (void)
+{
+  cand_table = htab_create (8000, cand_hash, cand_eq_p,
+			    (htab_del) free_cand);
+}
+
+/* Finish the candidate table.  */
+static void
+finish_cand_table (void)
+{
+  htab_delete (cand_table);
+}
+
+
+
+/* Return true if X contains memory or UNSPEC.  We can not just check
+   insn operands as memory or unspec might be not an operand itself
+   but contain an operand.  Insn with memory access is not profitable
+   for rematerialization.  Rematerialization of UNSPEC might result in
+   wrong code generation as the UNPEC effect is unknown
+   (e.g. generating a label).  */
+static bool
+bad_for_rematerialization_p (rtx x)
+{
+  int i, j;
+  const char *fmt;
+  enum rtx_code code;
+
+  if (MEM_P (x) || GET_CODE (x) == UNSPEC)
+    return true;
+  code = GET_CODE (x);
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  if (bad_for_rematerialization_p (XEXP (x, i)))
+	    return true;
+	}
+      else if (fmt[i] == 'E')
+	{
+	  for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+	    if (bad_for_rematerialization_p (XVECEXP (x, i, j)))
+	      return true;
+	}
+    }
+  return false;
+}
+
+/* If INSN can not be used for rematerialization, return negative
+   value.  If INSN can be considered as a candidate for
+   rematerialization, return value which is the operand number of the
+   pseudo for which the insn can be used for rematerialization.  Here
+   we consider the insns without any memory, spilled pseudo (except
+   for the rematerialization pseudo), or dying or unused regs.  */
+static int
+operand_to_remat (rtx_insn *insn)
+{
+  lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+  struct lra_static_insn_data *static_id = id->insn_static_data;
+  struct lra_insn_reg *reg, *found_reg = NULL;
+
+  /* First find a pseudo which can be rematerialized.  */
+  for (reg = id->regs; reg != NULL; reg = reg->next)
+    if (reg->type == OP_OUT && ! reg->subreg_p
+	&& find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
+      {
+	/* We permits only one spilled reg.  */
+	if (found_reg != NULL)
+	  return -1;
+	found_reg = reg;
+      }
+  if (found_reg == NULL)
+    return -1;
+  if (found_reg->regno < FIRST_PSEUDO_REGISTER)
+    return -1;
+  if (bad_for_rematerialization_p (PATTERN (insn)))
+    return -1;
+  /* Check the other regs are not spilled. */
+  for (reg = id->regs; reg != NULL; reg = reg->next)
+    if (found_reg == reg)
+      continue;
+    else if (reg->type == OP_INOUT)
+      return -1;
+    else if (reg->regno >= FIRST_PSEUDO_REGISTER
+	     && reg_renumber[reg->regno] < 0)
+      /* Another spilled reg.  */
+      return -1;
+    else if (reg->type == OP_IN)
+      {
+	if (find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
+	  /* We don't want to make live ranges longer.  */
+	  return -1;
+	/* Check that there is no output reg as the input one.  */
+	for (struct lra_insn_reg *reg2 = id->regs;
+	     reg2 != NULL;
+	     reg2 = reg2->next)
+	  if (reg2->type == OP_OUT && reg->regno == reg2->regno)
+	    return -1;
+      }
+  /* Find the rematerialization operand.  */
+  int nop = static_id->n_operands;
+  for (int i = 0; i < nop; i++)
+    if (REG_P (*id->operand_loc[i])
+	&& (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
+      return i;
+  return -1;
+}
+
+/* Create candidate for INSN with rematerialization operand NOP and
+   REGNO.  Insert the candidate into the table and set up the
+   corresponding INSN_TO_CAND element.  */
+static void
+create_cand (rtx_insn *insn, int nop, int regno)
+{
+  lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+  rtx reg = *id->operand_loc[nop];
+  gcc_assert (REG_P (reg));
+  int op_regno = REGNO (reg);
+  gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
+  cand_t cand = XNEW (struct cand);
+  cand->insn = insn;
+  cand->nop = nop;
+  cand->regno = regno;
+  cand->reload_regno = op_regno == regno ? -1 : op_regno;
+  gcc_assert (cand->regno >= 0);
+  cand_t cand_in_table = insert_cand (cand);
+  insn_to_cand[INSN_UID (insn)] = cand_in_table;
+  if (cand != cand_in_table)
+    free (cand);
+  else
+    {
+      /* A new cand.  */
+      cand->index = all_cands.length ();
+      all_cands.safe_push (cand);
+      cand->next_regno_cand = regno_cands[cand->regno];
+      regno_cands[cand->regno] = cand;
+    }
+}
+
+/* Create rematerialization candidates (inserting them into the
+   table).  */
+static void
+create_cands (void)
+{
+  rtx_insn *insn;
+  struct potential_cand
+  {
+    rtx_insn *insn;
+    int nop;
+  };
+  struct potential_cand *regno_potential_cand;
+
+  /* Create candidates.  */
+  regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
+  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+    if (INSN_P (insn))
+      {
+	rtx set;
+	int src_regno, dst_regno;
+	rtx_insn *insn2;
+	lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+	int nop = operand_to_remat (insn);
+	int regno = -1;
+
+	if ((set = single_set (insn)) != NULL
+	    && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))
+	    && (src_regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
+	    && (dst_regno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
+	    && reg_renumber[dst_regno] < 0
+	    && (insn2 = regno_potential_cand[src_regno].insn) != NULL
+	    && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
+	  create_cand (insn2, regno_potential_cand[src_regno].nop, dst_regno);
+	if (nop < 0)
+	  goto fail;
+	gcc_assert (REG_P (*id->operand_loc[nop]));
+ 	regno = REGNO (*id->operand_loc[nop]);
+	gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
+	if (reg_renumber[regno] < 0)
+	  create_cand (insn, nop, regno);
+	else
+	  {
+	    regno_potential_cand[regno].insn = insn;
+	    regno_potential_cand[regno].nop = nop;
+	    goto fail;
+	  }
+	regno = -1;
+      fail:
+	for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
+	  if (reg->type != OP_IN && reg->regno != regno
+	      && reg->regno >= FIRST_PSEUDO_REGISTER)
+	    regno_potential_cand[reg->regno].insn = NULL;
+      }
+  cands_num = all_cands.length ();
+  free (regno_potential_cand);
+}
+
+
+
+/* Create and initialize BB data.  */
+static void
+create_bb_data (void)
+{
+  basic_block bb;
+  bb_data_t bb_info;
+
+  bb_data = XNEWVEC (struct bb_data, last_basic_block_for_fn (cfun));
+  FOR_ALL_BB_FN (bb, cfun)
+    {
+#ifdef ENABLE_CHECKING
+      if (bb->index < 0 || bb->index >= last_basic_block_for_fn (cfun))
+	abort ();
+#endif
+      bb_info = get_bb_data (bb);
+      bb_info->bb = bb;
+      bitmap_initialize (&bb_info->changed_regs, &reg_obstack);
+      bitmap_initialize (&bb_info->dead_regs, &reg_obstack);
+      bitmap_initialize (&bb_info->gen_cands, &reg_obstack);
+      bitmap_initialize (&bb_info->livein_cands, &reg_obstack);
+      bitmap_initialize (&bb_info->pavin_cands, &reg_obstack);
+      bitmap_initialize (&bb_info->pavout_cands, &reg_obstack);
+      bitmap_initialize (&bb_info->avin_cands, &reg_obstack);
+      bitmap_initialize (&bb_info->avout_cands, &reg_obstack);
+    }
+}
+
+/* Dump all candidates to DUMP_FILE.  */
+static void
+dump_cands (FILE *dump_file)
+{
+  int i;
+  cand_t cand;
+
+  fprintf (dump_file, "\nCands:\n");
+  for (i = 0; i < (int) cands_num; i++)
+    {
+      cand = all_cands[i];
+      fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
+	       i, cand->nop, cand->regno, cand->reload_regno);
+      print_inline_rtx (dump_file, cand->insn, 6);
+      fprintf (dump_file, "\n");
+    }
+}
+
+/* Dump all candidates and BB data.  */
+static void
+dump_candidates_and_bb_data (void)
+{
+  basic_block bb;
+
+  if (lra_dump_file == NULL)
+    return;
+  dump_cands (lra_dump_file);
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
+      /* Livein */
+      fprintf (lra_dump_file, "  register live in:");
+      dump_regset (df_get_live_in (bb), lra_dump_file);
+      putc ('\n', lra_dump_file);
+      /* Liveout */
+      fprintf (lra_dump_file, "  register live out:");
+      dump_regset (df_get_live_out (bb), lra_dump_file);
+      putc ('\n', lra_dump_file);
+      /* Changed/dead regs: */
+      fprintf (lra_dump_file, "  changed regs:");
+      dump_regset (&get_bb_data (bb)->changed_regs, lra_dump_file);
+      putc ('\n', lra_dump_file);
+      fprintf (lra_dump_file, "  dead regs:");
+      dump_regset (&get_bb_data (bb)->dead_regs, lra_dump_file);
+      putc ('\n', lra_dump_file);
+      dump_bitmap_with_title ("cands generated in BB",
+			       &get_bb_data (bb)->gen_cands, bb->index);
+      dump_bitmap_with_title ("livein cands in BB",
+			       &get_bb_data (bb)->livein_cands, bb->index);
+      dump_bitmap_with_title ("pavin cands in BB",
+			       &get_bb_data (bb)->pavin_cands, bb->index);
+      dump_bitmap_with_title ("pavout cands in BB",
+			       &get_bb_data (bb)->pavout_cands, bb->index);
+      dump_bitmap_with_title ("avin cands in BB",
+			       &get_bb_data (bb)->avin_cands, bb->index);
+      dump_bitmap_with_title ("avout cands in BB",
+			       &get_bb_data (bb)->avout_cands, bb->index);
+    }
+}
+
+/* Free all BB data.  */
+static void
+finish_bb_data (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      bitmap_clear (&get_bb_data (bb)->avout_cands);
+      bitmap_clear (&get_bb_data (bb)->avin_cands);
+      bitmap_clear (&get_bb_data (bb)->pavout_cands);
+      bitmap_clear (&get_bb_data (bb)->pavin_cands);
+      bitmap_clear (&get_bb_data (bb)->livein_cands);
+      bitmap_clear (&get_bb_data (bb)->gen_cands);
+      bitmap_clear (&get_bb_data (bb)->dead_regs);
+      bitmap_clear (&get_bb_data (bb)->changed_regs);
+    }
+  free (bb_data);
+}
+
+
+
+/* Update changed_regs and dead_regs of BB from INSN.  */
+static void
+set_bb_regs (basic_block bb, rtx_insn *insn)
+{
+  lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+  struct lra_insn_reg *reg;
+
+  for (reg = id->regs; reg != NULL; reg = reg->next)
+    if (reg->type != OP_IN)
+      bitmap_set_bit (&get_bb_data (bb)->changed_regs, reg->regno);
+    else
+      {
+	if (find_regno_note (insn, REG_DEAD, (unsigned) reg->regno) != NULL)
+	  bitmap_set_bit (&get_bb_data (bb)->dead_regs, reg->regno);
+      }
+  if (CALL_P (insn))
+    for (int i = 0; i < call_used_regs_arr_len; i++)
+      bitmap_set_bit (&get_bb_data (bb)->dead_regs, call_used_regs_arr[i]);
+}
+
+/* Calculate changed_regs and dead_regs for each BB.  */
+static void
+calculate_local_reg_bb_data (void)
+{
+  basic_block bb;
+  rtx_insn *insn;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    FOR_BB_INSNS (bb, insn)
+      if (INSN_P (insn))
+	set_bb_regs (bb, insn);
+}
+
+
+
+/* Return true if REGNO is an input operand of INSN.  */
+static bool
+input_regno_present_p (rtx_insn *insn, int regno)
+{
+  lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+  struct lra_insn_reg *reg;
+
+  for (reg = id->regs; reg != NULL; reg = reg->next)
+    if (reg->type == OP_IN && reg->regno == regno)
+      return true;
+  return false;
+}
+
+/* Return true if a call used register is an input operand of INSN.  */
+static bool
+call_used_input_regno_present_p (rtx_insn *insn)
+{
+  lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+  struct lra_insn_reg *reg;
+
+  for (reg = id->regs; reg != NULL; reg = reg->next)
+    if (reg->type == OP_IN && reg->regno <= FIRST_PSEUDO_REGISTER
+	&& TEST_HARD_REG_BIT (call_used_reg_set, reg->regno))
+      return true;
+  return false;
+}
+
+/* Calculate livein_cands for each BB.  */
+static void
+calculate_livein_cands (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      bitmap livein_regs = df_get_live_in (bb);
+      bitmap livein_cands = &get_bb_data (bb)->livein_cands;
+      for (unsigned int i = 0; i < cands_num; i++)
+	{
+	  cand_t cand = all_cands[i];
+	  lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
+	  struct lra_insn_reg *reg;
+
+	  for (reg = id->regs; reg != NULL; reg = reg->next)
+	    if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
+	      break;
+	  if (reg == NULL)
+	    bitmap_set_bit (livein_cands, i);
+	}
+    }
+}
+
+/* Calculate gen_cands for each BB.  */
+static void
+calculate_gen_cands (void)
+{
+  basic_block bb;
+  bitmap gen_cands;
+  bitmap_head gen_insns;
+  rtx_insn *insn;
+
+  bitmap_initialize (&gen_insns, &reg_obstack);
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      gen_cands = &get_bb_data (bb)->gen_cands;
+      bitmap_clear (&gen_insns);
+      FOR_BB_INSNS (bb, insn)
+	if (INSN_P (insn))
+	  {
+	    lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+	    struct lra_insn_reg *reg;
+	    unsigned int uid;
+	    bitmap_iterator bi;
+	    cand_t cand;
+	    rtx set;
+	    int src_regno = -1, dst_regno = -1;
+
+	    if ((set = single_set (insn)) != NULL
+		&& REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
+	      {
+		src_regno = REGNO (SET_SRC (set));
+		dst_regno = REGNO (SET_DEST (set));
+	      }
+
+	    /* Update gen_cands:  */
+	    bitmap_clear (&temp_bitmap);
+	    for (reg = id->regs; reg != NULL; reg = reg->next)
+	      if (reg->type != OP_IN
+		  || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
+		EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
+		  {
+		    rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
+
+		    cand = insn_to_cand[INSN_UID (insn2)];
+		    gcc_assert (cand != NULL);
+		    /* Ignore the reload insn.  */
+		    if (src_regno == cand->reload_regno
+			&& dst_regno == cand->regno)
+		      continue;
+		    if (cand->regno == reg->regno
+			|| input_regno_present_p (insn2, reg->regno))
+		      {
+			bitmap_clear_bit (gen_cands, cand->index);
+			bitmap_set_bit (&temp_bitmap, uid);
+		      }
+		  }
+	    
+	    if (CALL_P (insn))
+	      EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
+		{
+		  rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
+		  
+		  cand = insn_to_cand[INSN_UID (insn2)];
+		  gcc_assert (cand != NULL);
+		  if (call_used_input_regno_present_p (insn2))
+		    {
+		      bitmap_clear_bit (gen_cands, cand->index);
+		      bitmap_set_bit (&temp_bitmap, uid);
+		    }
+		}
+	    bitmap_and_compl_into (&gen_insns, &temp_bitmap);
+
+	    cand = insn_to_cand[INSN_UID (insn)];
+	    if (cand != NULL)
+	      {
+		bitmap_set_bit (gen_cands, cand->index);
+		bitmap_set_bit (&gen_insns, INSN_UID (insn));
+	      }
+	  }
+    }  
+  bitmap_clear (&gen_insns);
+}
+
+
+
+/* The common transfer function used by the DF equation solver to
+   propagate (partial) availability info BB_IN to BB_OUT through block
+   with BB_INDEX according to the following equation:
+
+      bb.out =  ((bb.in & bb.livein) - bb.killed) OR  bb.gen
+*/
+static bool
+cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
+{
+  bb_data_t bb_info;
+  bitmap bb_livein, bb_changed_regs, bb_dead_regs;
+  unsigned int cid;
+  bitmap_iterator bi;
+
+  bb_info = get_bb_data_by_index (bb_index);
+  bb_livein = &bb_info->livein_cands;
+  bb_changed_regs = &bb_info->changed_regs;
+  bb_dead_regs = &bb_info->dead_regs;
+  /* Calculate killed avin cands -- cands whose regs are changed or
+     becoming dead in the BB.  We calculate it here as we hope that
+     repeated calculations are compensated by smaller size of BB_IN in
+     comparison with all candidates number.  */
+  bitmap_clear (&temp_bitmap);
+  EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
+    {
+      cand_t cand = all_cands[cid];
+      lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
+      struct lra_insn_reg *reg;
+
+      if (! bitmap_bit_p (bb_livein, cid))
+	{
+	  bitmap_set_bit (&temp_bitmap, cid);
+	  continue;
+	}
+      for (reg = id->regs; reg != NULL; reg = reg->next)
+	/* Ignore all outputs which are not the regno for
+	   rematerialization.  */
+	if (reg->type == OP_OUT && reg->regno != cand->regno)
+	  continue;
+	else if (bitmap_bit_p (bb_changed_regs, reg->regno)
+		 || bitmap_bit_p (bb_dead_regs, reg->regno))
+	  {
+	    bitmap_set_bit (&temp_bitmap, cid);
+	    break;
+	  }
+    }
+  return bitmap_ior_and_compl (bb_out,
+			       &bb_info->gen_cands, bb_in, &temp_bitmap);
+}
+
+
+
+/* The transfer function used by the DF equation solver to propagate
+   partial candidate availability info through block with BB_INDEX
+   according to the following equation:
+
+     bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
+*/
+static bool
+cand_pav_trans_fun (int bb_index)
+{
+  bb_data_t bb_info;
+
+  bb_info = get_bb_data_by_index (bb_index);
+  return cand_trans_fun (bb_index, &bb_info->pavin_cands, &bb_info->pavout_cands);
+}
+
+/* The confluence function used by the DF equation solver to set up
+   cand_pav info for a block BB without predecessor.  */
+static void
+cand_pav_con_fun_0 (basic_block bb)
+{
+  bitmap_clear (&get_bb_data (bb)->pavin_cands);
+}
+
+/* The confluence function used by the DF equation solver to propagate
+   partial candidate availability info from predecessor to successor
+   on edge E (pred->bb) according to the following equation:
+
+      bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
+ */
+static bool
+cand_pav_con_fun_n (edge e)
+{
+  basic_block pred = e->src;
+  basic_block bb = e->dest;
+  bb_data_t bb_info;
+  bitmap bb_pavin, pred_pavout;
+  
+  bb_info = get_bb_data (bb);
+  bb_pavin = &bb_info->pavin_cands;
+  pred_pavout = &get_bb_data (pred)->pavout_cands;
+  return bitmap_ior_into (bb_pavin, pred_pavout);
+}
+
+
+
+/* The transfer function used by the DF equation solver to propagate
+   candidate availability info through block with BB_INDEX according
+   to the following equation:
+
+      bb.avout =  ((bb.avin & bb.livein) - bb.killed) OR  bb.gen
+*/
+static bool
+cand_av_trans_fun (int bb_index)
+{
+  bb_data_t bb_info;
+
+  bb_info = get_bb_data_by_index (bb_index);
+  return cand_trans_fun (bb_index, &bb_info->avin_cands, &bb_info->avout_cands);
+}
+
+/* The confluence function used by the DF equation solver to set up
+   cand_av info for a block BB without predecessor.  */
+static void
+cand_av_con_fun_0 (basic_block bb)
+{
+  bitmap_clear (&get_bb_data (bb)->avin_cands);
+}
+
+/* The confluence function used by the DF equation solver to propagate
+   cand_av info from predecessor to successor on edge E (pred->bb)
+   according to the following equation:
+
+      bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
+ */
+static bool
+cand_av_con_fun_n (edge e)
+{
+  basic_block pred = e->src;
+  basic_block bb = e->dest;
+  bb_data_t bb_info;
+  bitmap bb_avin, pred_avout;
+  
+  bb_info = get_bb_data (bb);
+  bb_avin = &bb_info->avin_cands;
+  pred_avout = &get_bb_data (pred)->avout_cands;
+  return bitmap_and_into (bb_avin, pred_avout);
+}
+
+/* Calculate available candidates for each BB.  */
+static void
+calculate_global_bb_data (void)
+{
+  basic_block bb;
+
+  df_simple_dataflow
+    (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
+     cand_pav_trans_fun, &all_blocks,
+     df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
+  /* Initialize avin by pavin.  */
+  FOR_EACH_BB_FN (bb, cfun)
+    bitmap_copy (&get_bb_data (bb)->avin_cands, &get_bb_data (bb)->pavin_cands);
+  df_simple_dataflow
+    (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
+     cand_av_trans_fun, &all_blocks,
+     df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
+}
+
+
+
+/* Setup sp offset attribute to SP_OFFSET for all INSNS.  */
+static void
+change_sp_offset (rtx_insn *insns, HOST_WIDE_INT sp_offset)
+{
+  for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
+    eliminate_regs_in_insn (insn, false, false, sp_offset);
+}
+
+/* Return start hard register of REG (can be a hard or a pseudo reg)
+   or -1 (if it is a spilled pseudo).  Return number of hard registers
+   occupied by REG through parameter NREGS if the start hard reg is
+   not negative.  */
+static int
+get_hard_regs (struct lra_insn_reg *reg, int &nregs)
+{
+  int regno = reg->regno;
+  int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
+
+  if (hard_regno >= 0)
+    nregs = hard_regno_nregs[hard_regno][reg->biggest_mode];
+  return hard_regno;
+}
+
+/* Insert rematerialization insns using the data-flow data calculated
+   earlier.  */
+static bool
+do_remat (void)
+{
+  rtx_insn *insn;
+  basic_block bb;
+  bitmap_head avail_cands;
+  bool changed_p = false;
+  /* Living hard regs and hard registers of living pseudos.  */
+  HARD_REG_SET live_hard_regs;
+
+  bitmap_initialize (&avail_cands, &reg_obstack);
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_out (bb));
+      bitmap_and (&avail_cands,
+		  &get_bb_data (bb)->avin_cands, &get_bb_data (bb)->livein_cands);
+      FOR_BB_INSNS (bb, insn)
+	{
+	  if (!NONDEBUG_INSN_P (insn))
+	    continue;
+
+	  lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
+	  struct lra_insn_reg *reg;
+	  cand_t cand;
+	  unsigned int cid;
+	  bitmap_iterator bi;
+	  rtx set;
+	  int src_regno = -1, dst_regno = -1;
+
+	  if ((set = single_set (insn)) != NULL
+	      && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
+	    {
+	      src_regno = REGNO (SET_SRC (set));
+	      dst_regno = REGNO (SET_DEST (set));
+	    }
+
+	  cand = NULL;
+	  /* Check possibility of rematerialization (hard reg or
+	     unpsilled pseudo <- spilled pseudo): */
+	  if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
+	      && reg_renumber[src_regno] < 0
+	      && (dst_regno < FIRST_PSEUDO_REGISTER
+		  || reg_renumber[dst_regno] >= 0))
+	    {
+	      for (cand = regno_cands[src_regno];
+		   cand != NULL;
+		   cand = cand->next_regno_cand)
+		if (bitmap_bit_p (&avail_cands, cand->index))
+		  break;
+	    }
+	  int i, hard_regno, nregs;
+	  rtx_insn *remat_insn = NULL;
+	  HOST_WIDE_INT cand_sp_offset = 0;
+	  if (cand != NULL)
+	    {
+	      lra_insn_recog_data_t cand_id = lra_get_insn_recog_data (cand->insn);
+	      rtx saved_op = *cand_id->operand_loc[cand->nop];
+
+	      /* Check clobbers do not kill something living.  */
+	      gcc_assert (REG_P (saved_op));
+	      int ignore_regno = REGNO (saved_op); 
+
+	      for (reg = cand_id->regs; reg != NULL; reg = reg->next)
+		if (reg->type != OP_IN && reg->regno != ignore_regno)
+		  {
+		    hard_regno = get_hard_regs (reg, nregs);
+		    gcc_assert (hard_regno >= 0);
+		    for (i = 0; i < nregs; i++)
+		      if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
+			break;
+		    if (i < nregs)
+		      break;
+		  }
+
+	      if (reg == NULL)
+		{
+		  *cand_id->operand_loc[cand->nop] = SET_DEST (set);
+		  lra_update_insn_regno_info (cand->insn);
+		  bool ok_p = lra_constrain_insn (cand->insn);
+		  if (ok_p)
+		    {
+		      rtx remat_pat = copy_insn (PATTERN (cand->insn));
+		      
+		      start_sequence ();
+		      emit_insn (remat_pat);
+		      remat_insn = get_insns ();
+		      end_sequence ();
+		      if (recog_memoized (remat_insn) < 0)
+			remat_insn = NULL;
+		      cand_sp_offset = cand_id->sp_offset;
+		    }
+		  *cand_id->operand_loc[cand->nop] = saved_op;
+		  lra_update_insn_regno_info (cand->insn);
+		}
+	    }
+
+	  /* Update avail_cands (see analogous code for
+	     calculate_gen_cands).  */
+	  for (reg = id->regs; reg != NULL; reg = reg->next)
+	    if (reg->type != OP_IN
+		|| find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
+	      EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
+		{
+		  cand = all_cands[cid];
+
+		  /* Ignore the reload insn.  */
+		  if (src_regno == cand->reload_regno
+		      && dst_regno == cand->regno)
+		    continue;
+		  if (cand->regno == reg->regno
+		      || input_regno_present_p (cand->insn, reg->regno))
+		    bitmap_clear_bit (&avail_cands, cand->index);
+		}
+
+	  if (CALL_P (insn))
+	    EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
+	      {
+		cand = all_cands[cid];
+		
+		if (call_used_input_regno_present_p (cand->insn))
+		  bitmap_clear_bit (&avail_cands, cand->index);
+	      }
+
+	  if ((cand = insn_to_cand[INSN_UID (insn)]) != NULL)
+	    bitmap_set_bit (&avail_cands, cand->index);
+	    
+	  if (remat_insn != NULL)
+	    {
+	      HOST_WIDE_INT sp_offset_change = cand_sp_offset - id->sp_offset;
+	      if (sp_offset_change != 0)
+		change_sp_offset (remat_insn, sp_offset_change);
+	      lra_process_new_insns (insn, remat_insn, NULL,
+				     "Inserting rematerialization insn");
+	      lra_set_insn_deleted (insn);
+	      changed_p = true;
+	      continue;
+	    }
+
+	  /* Update live hard regs: */
+	  for (reg = id->regs; reg != NULL; reg = reg->next)
+	    if (reg->type == OP_IN && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
+	      {
+		if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
+		  continue;
+		for (i = 0; i < nregs; i++)
+		  CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
+	      }
+	    else if (reg->type != OP_IN
+		     && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
+	      {
+		if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
+		  continue;
+		for (i = 0; i < nregs; i++)
+		  SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
+	      }
+	}
+    }
+  bitmap_clear (&avail_cands);
+  return changed_p;
+}
+
+
+
+/* Entry point of the rematerialization sub-pass.  Return true if we
+   did any rematerialization.  */
+bool
+lra_remat (void)
+{
+  basic_block bb;
+  bool result;
+  int max_regno = max_reg_num ();
+
+  if (! flag_lra_remat)
+    return false;
+  timevar_push (TV_LRA_REMAT);
+  insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
+  regno_cands = XCNEWVEC (cand_t, max_regno);
+  all_cands.create (8000);
+  call_used_regs_arr_len = 0;
+  for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if (call_used_regs[i])
+      call_used_regs_arr[call_used_regs_arr_len++] = i;
+  initiate_cand_table ();
+  create_cands ();
+  create_bb_data ();
+  bitmap_initialize (&temp_bitmap, &reg_obstack);
+  calculate_local_reg_bb_data ();
+  calculate_livein_cands ();
+  calculate_gen_cands ();
+  bitmap_initialize (&all_blocks, &reg_obstack);
+  FOR_ALL_BB_FN (bb, cfun)
+    bitmap_set_bit (&all_blocks, bb->index);
+  calculate_global_bb_data ();
+  dump_candidates_and_bb_data ();
+  result = do_remat ();
+  all_cands.release ();
+  bitmap_clear (&temp_bitmap);
+  finish_bb_data ();
+  finish_cand_table ();
+  bitmap_clear (&all_blocks);
+  free (regno_cands);
+  free (insn_to_cand);
+  timevar_pop (TV_LRA_REMAT);
+  return result;
+}
Index: lra-spills.c
===================================================================
--- lra-spills.c	(revision 216039)
+++ lra-spills.c	(working copy)
@@ -436,7 +436,7 @@  remove_pseudos (rtx *loc, rtx_insn *insn
 	{
 	  rtx x = lra_eliminate_regs_1 (insn, pseudo_slots[i].mem,
 					GET_MODE (pseudo_slots[i].mem),
-					false, false, true);
+					0, false, false, true);
 	  *loc = x != pseudo_slots[i].mem ? x : copy_rtx (x);
 	}
       return;
Index: lra.c
===================================================================
--- lra.c	(revision 216039)
+++ lra.c	(working copy)
@@ -37,6 +37,7 @@  along with GCC; see the file COPYING3.	I
        generated;
      o Some pseudos might be spilled to assign hard registers to
        new reload pseudos;
+     o Recalculating spilled pseudo values (rematerialization);
      o Changing spilled pseudos to stack memory or their equivalences;
      o Allocation stack memory changes the address displacement and
        new iteration is needed.
@@ -57,19 +58,26 @@  along with GCC; see the file COPYING3.	I
  -----------      |              ----------------                   |
                   |                      |                          |
                   |                      V         New              |
-         ----------------    No    ------------  pseudos   -------------------
-        | Spilled pseudo | change |Constraints:| or insns | Inheritance/split |
-        |    to memory   |<-------|    RTL     |--------->|  transformations  |
-        |  substitution  |        | transfor-  |          |    in EBB scope   |
-         ----------------         |  mations   |           -------------------
-                |                   ------------
-                V
-    -------------------------
-   | Hard regs substitution, |
-   |  devirtalization, and   |------> Finish
-   | restoring scratches got |
-   |         memory          |
-    -------------------------
+                  |                 ------------  pseudos   -------------------
+                  |                |Constraints:| or insns | Inheritance/split |
+                  |                |    RTL     |--------->|  transformations  |
+                  |                | transfor-  |          |    in EBB scope   |
+                  | substi-        |  mations   |           -------------------
+                  | tutions         ------------
+                  |                     | No change
+          ----------------              V
+         | Spilled pseudo |      -------------------
+         |    to memory   |<----| Rematerialization |
+         |  substitution  |      -------------------
+          ----------------        
+                  | No susbtitions
+                  V                
+      -------------------------
+     | Hard regs substitution, |
+     |  devirtalization, and   |------> Finish
+     | restoring scratches got |
+     |         memory          |
+      -------------------------
 
    To speed up the process:
      o We process only insns affected by changes on previous
@@ -811,38 +819,38 @@  collect_non_operand_hard_regs (rtx *x, l
     {
       if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
 	return list;
+      /* Process all regs even unallocatable ones as we need info
+	 about all regs for rematerialization pass.  */
       for (last = regno + hard_regno_nregs[regno][mode];
 	   regno < last;
 	   regno++)
-	if (! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
-	    || TEST_HARD_REG_BIT (eliminable_regset, regno))
-	  {
-	    for (curr = list; curr != NULL; curr = curr->next)
-	      if (curr->regno == regno && curr->subreg_p == subreg_p
-		  && curr->biggest_mode == mode)
-		{
-		  if (curr->type != type)
-		    curr->type = OP_INOUT;
-		  if (curr->early_clobber != early_clobber)
-		    curr->early_clobber = true;
-		  break;
-		}
-	    if (curr == NULL)
+	{
+	  for (curr = list; curr != NULL; curr = curr->next)
+	    if (curr->regno == regno && curr->subreg_p == subreg_p
+		&& curr->biggest_mode == mode)
 	      {
-		/* This is a new hard regno or the info can not be
-		   integrated into the found structure.	 */
+		if (curr->type != type)
+		  curr->type = OP_INOUT;
+		if (curr->early_clobber != early_clobber)
+		  curr->early_clobber = true;
+		break;
+	      }
+	  if (curr == NULL)
+	    {
+	      /* This is a new hard regno or the info can not be
+		 integrated into the found structure.	 */
 #ifdef STACK_REGS
-		early_clobber
-		  = (early_clobber
-		     /* This clobber is to inform popping floating
-			point stack only.  */
-		     && ! (FIRST_STACK_REG <= regno
-			   && regno <= LAST_STACK_REG));
+	      early_clobber
+		= (early_clobber
+		   /* This clobber is to inform popping floating
+		      point stack only.  */
+		   && ! (FIRST_STACK_REG <= regno
+			 && regno <= LAST_STACK_REG));
 #endif
-		list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
-				     early_clobber, list);
-	      }
-	  }
+	      list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
+				   early_clobber, list);
+	    }
+	}
       return list;
     }
   switch (code)
@@ -1438,10 +1446,8 @@  add_regs_to_insn_regno_info (lra_insn_re
   if (REG_P (x))
     {
       regno = REGNO (x);
-      if (regno < FIRST_PSEUDO_REGISTER
-	  && TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
-	  && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
-	return;
+      /* Process all regs even unallocatable ones as we need info about
+	 all regs for rematerialization pass.  */
       expand_reg_info ();
       if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
 	{
@@ -2071,9 +2077,6 @@  bitmap_head lra_optional_reload_pseudos;
    pass.  */
 bitmap_head lra_subreg_reload_pseudos;
 
-/* First UID of insns generated before a new spill pass.  */
-int lra_constraint_new_insn_uid_start;
-
 /* File used for output of LRA debug information.  */
 FILE *lra_dump_file;
 
@@ -2176,7 +2179,6 @@  lra (FILE *f)
   lra_curr_reload_num = 0;
   push_insns (get_last_insn (), NULL);
   /* It is needed for the 1st coalescing.  */
-  lra_constraint_new_insn_uid_start = get_max_uid ();
   bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
   bitmap_initialize (&lra_split_regs, &reg_obstack);
   bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
@@ -2269,12 +2271,19 @@  lra (FILE *f)
 	  lra_create_live_ranges (lra_reg_spill_p);
 	  live_p = true;
 	}
+      /* Now we know what pseudos should be spilled.  Try to
+	 rematerialize them first.  */
+      if (lra_remat ())
+	{
+	  /* We need full live info -- see the comment above.  */
+	  lra_create_live_ranges (lra_reg_spill_p);
+	  live_p = true;
+	}
       lra_spill ();
       /* Assignment of stack slots changes elimination offsets for
 	 some eliminations.  So update the offsets here.  */
       lra_eliminate (false, false);
       lra_constraint_new_regno_start = max_reg_num ();
-      lra_constraint_new_insn_uid_start = get_max_uid ();
       lra_constraint_iter_after_spill = 0;
     }
   restore_scratches ();
Index: opts.c
===================================================================
--- opts.c	(revision 216039)
+++ opts.c	(working copy)
@@ -499,6 +499,7 @@  static const struct default_options defa
     { OPT_LEVELS_2_PLUS, OPT_fhoist_adjacent_loads, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_fisolate_erroneous_paths_dereference, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_fuse_caller_save, NULL, 1 },
+    { OPT_LEVELS_2_PLUS, OPT_flra_remat, NULL, 1 },
 
     /* -O3 optimizations.  */
     { OPT_LEVELS_3_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
Index: timevar.def
===================================================================
--- timevar.def	(revision 216039)
+++ timevar.def	(working copy)
@@ -235,6 +235,7 @@  DEFTIMEVAR (TV_LRA_INHERITANCE	     , "L
 DEFTIMEVAR (TV_LRA_CREATE_LIVE_RANGES, "LRA create live ranges")
 DEFTIMEVAR (TV_LRA_ASSIGN	     , "LRA hard reg assignment")
 DEFTIMEVAR (TV_LRA_COALESCE	     , "LRA coalesce pseudo regs")
+DEFTIMEVAR (TV_LRA_REMAT	     , "LRA rematerialization")
 DEFTIMEVAR (TV_RELOAD		     , "reload")
 DEFTIMEVAR (TV_RELOAD_CSE_REGS       , "reload CSE regs")
 DEFTIMEVAR (TV_GCSE_AFTER_RELOAD     , "load CSE after reload")