Reload pass ignores constraints. Why?

Reload pass ignores constraints. Why?

[Georg-Johann Lay]

Hi.

Working out recommendations for a new instruction set architecture (no 
silicon yet), I run into the following problem with a port based on 
gcc_4_3_3_release: postreload complains

error: insn does not satisfy its constraints:
(insn 1636 1635 410 35 k_rem_pio2.c:816 (set (reg:SI 28 a12)
         (lshiftrt:SI (reg:SI 28 a12)
             (const_int 8 [0x8]))) 22 {lshrsi3} (nil))
k_rem_pio2.c:910: internal compiler error: in 
reload_cse_simplify_operands, at postreload.c:395

The reason is obvious: Pass greg chooses reg a12 which is not in class 
"d" as required by this insn:

(define_insn "lshrsi3"
   [(set (match_operand:SI 0 "register_operand"                 "=d ,d 
  ,d")
         (lshiftrt:SI (match_operand:SI 1 "register_operand"     "d ,0 
  ,d")
                      (match_operand:SI 2 "reg_or_u5_operand"    "d ,Ku4 
,Ku5")))]
   ""
   "...")

"Ku4" is an unsigned 4-bit constant, "Ku5" likewise.
The register set consists of two disjoint register classes "a" and "d":
a-regs are used to access memory, address arithmetic, etc.
d-regs are used to perform arithmetic
Both classes allow SImode=Pmode, a12 is an element of "a".

In pass lreg everything is all right:

*lreg*
(insn:HI 408 202 409 17 k_rem_pio2.c:816 (set (reg:SI 569)
         (const_int -1 [0xffffffff])) 2 {*movsi_insn} 
(expr_list:REG_EQUIV (const_int -1 [0xffffffff])
         (nil)))

(insn:HI 409 408 400 17 k_rem_pio2.c:816 (set (reg:SI 570)
         (lshiftrt:SI (reg:SI 569)
             (const_int 8 [0x8]))) 22 {lshrsi3} (expr_list:REG_EQUIV 
(const_int 16777215 [0xffffff])
         (expr_list:REG_DEAD (reg:SI 569)
             (nil))))

This is the cheapest way to load the desired constant 0xffffff into a 
register: load -1 and shift it right by 8. The sequence was expanded in 
pass expand. But despite the constraints "d" in the insns, greg 
allocates a12:

*greg*
(insn 1635 407 1636 35 k_rem_pio2.c:816 (set (reg:SI 28 a12)
         (const_int -1 [0xffffffff])) 2 {*movsi_insn} (nil))

(insn 1636 1635 410 35 k_rem_pio2.c:816 (set (reg:SI 28 a12)
         (lshiftrt:SI (reg:SI 28 a12)
             (const_int 8 [0x8]))) 22 {lshrsi3} (nil))

movsi knows how to move all kinds of memory, registers and constants. 
There is no secondary reload needed to copy from "a" to "d" or from "d" 
to "a". -1 is allright for both "a" and "d". The classes are big enough 
so that CLASS_LIKELY_SPILLED_P is false for them. 
PREFERRED_(OUTPUT_)RELOAD_CLASS does nothing.

According to GCC internals this should work without any problems:

 > Any operand expression can be reloaded by copying it into a register.
 > So if an operand's constraints allow some kind of register, it is
 > certain to be safe.  It need not permit all classes of registers; the
 > compiler knows how to copy a register into another register of the
 > proper class in order to make an instruction valid.

What am I missing? Would be great if some expert could give me a hint.

I browsed SVN for bug fixes in reload/ira, but no fix seems to address 
this problem. Is therer a problem with REG_EQUIV notes that make reload 
blindly take some register?

To give it a try I also defined a "d_register_operand" predicate which 
leads to "unrecognizable insn", just as I expected...

Thanks very mutch

Re: Reload pass ignores constraints. Why?

[Ian Lance Taylor]

Georg-Johann Lay <avr@gjlay.de> writes:

> Working out recommendations for a new instruction set architecture (no
> silicon yet), I run into the following problem with a port based on
> gcc_4_3_3_release: postreload complains

From your description, I would have expected reload to handle this
correctly.  I don't know why it didn't.  The first place to look would
be to verify that the REG_CLASS_CONTENTS bitmasks are correct.  Next,
look at the .greg dump to see if the insn in question required any
reloads.  If not, the next step may be to debug find_reloads to find out
why no reloads were required.  This can somewhat tedious; you can set a
breakpoint to match the insn UID so that you are looking at the right
insn in find_reloads, but following the loops can still take a while.
Good luck.  I've spent many days on this sort of problem.

Ian

Re: Reload pass ignores constraints. Why?

[Georg-Johann Lay]

Ian Lance Taylor schrieb:
> Georg-Johann Lay <avr@gjlay.de> writes:
> 
>> Working out recommendations for a new instruction set architecture (no
>> silicon yet), I run into the following problem with a port based on
>> gcc_4_3_3_release: postreload complains
> 
>From your description, I would have expected reload to handle this
> correctly.  I don't know why it didn't.  The first place to look would
> be to verify that the REG_CLASS_CONTENTS bitmasks are correct.  Next,
> look at the .greg dump to see if the insn in question required any
> reloads.  If not, the next step may be to debug find_reloads to find out
> why no reloads were required.  This can somewhat tedious; you can set a
> breakpoint to match the insn UID so that you are looking at the right
> insn in find_reloads, but following the loops can still take a while.
> Good luck.  I've spent many days on this sort of problem.
> 
> Ian
> 

Hi Ian,

greg does not generate reloads for the insn in question (the {lshrsi3}), 
and find_reloads is never called for it.

I guess the caller should be reload1.c::calculate_needs_all_insns?

When calculate_needs_all_insns runs on the insn the insn looks like this 
(other insn numbers than above as I proceed my very work regardless of 
the possible bug)

calculate_needs_all_insns[__kernel_rem_pio2:greg(180)]: (insn:HI 409 438 
400 17 k_rem_pio2.c:816 (set (reg:SI 566)
         (lshiftrt:SI (reg:SI 0 d0 [565])
             (const_int 8 [0x8]))) 22 {lshrsi3} (expr_list:REG_EQUIV 
(const_int 16777215 [0xffffff])
         (expr_list:REG_DEAD (reg:SI 0 d0 [565])

Someone already replaced #1 with d0, a reg of the right class "d". Maybe 
a function parameter or return value is propagated.

However, calculate_needs_all_insns decides that there are no reloads 
needed. reload1.c:1554 reads:

	  /* Skip insns that only set an equivalence.  */
	  if (set && REG_P (SET_DEST (set))
	      && reg_renumber[REGNO (SET_DEST (set))] < 0
	      && (reg_equiv_constant[REGNO (SET_DEST (set))]
		  || (reg_equiv_invariant[REGNO (SET_DEST (set))]))
		      && reg_equiv_init[REGNO (SET_DEST (set))])
               continue;

Before lreg, the insn is tagged REG_EQUAL but lreg then retags it as 
REG_EQUIV.

So is the problem in lreg because it says REG_EQUIV?
Or is it wrong to omit REG_EQUIV insns from reload?

Georg-Johann

Re: Reload pass ignores constraints. Why?

[Ian Lance Taylor]

Georg-Johann Lay <avr@gjlay.de> writes:

> When calculate_needs_all_insns runs on the insn the insn looks like
> this (other insn numbers than above as I proceed my very work
> regardless of the possible bug)
>
> calculate_needs_all_insns[__kernel_rem_pio2:greg(180)]: (insn:HI 409
> 438 400 17 k_rem_pio2.c:816 (set (reg:SI 566)
>         (lshiftrt:SI (reg:SI 0 d0 [565])
>             (const_int 8 [0x8]))) 22 {lshrsi3} (expr_list:REG_EQUIV
> (const_int 16777215 [0xffffff])
>         (expr_list:REG_DEAD (reg:SI 0 d0 [565])
>
> Someone already replaced #1 with d0, a reg of the right class
> "d". Maybe a function parameter or return value is propagated.
>
> However, calculate_needs_all_insns decides that there are no reloads
> needed. reload1.c:1554 reads:
>
> 	  /* Skip insns that only set an equivalence.  */
> 	  if (set && REG_P (SET_DEST (set))
> 	      && reg_renumber[REGNO (SET_DEST (set))] < 0
> 	      && (reg_equiv_constant[REGNO (SET_DEST (set))]
> 		  || (reg_equiv_invariant[REGNO (SET_DEST (set))]))
> 		      && reg_equiv_init[REGNO (SET_DEST (set))])
>               continue;
>
> Before lreg, the insn is tagged REG_EQUAL but lreg then retags it as
> REG_EQUIV.
>
> So is the problem in lreg because it says REG_EQUIV?
> Or is it wrong to omit REG_EQUIV insns from reload?

Neither is the problem.

This case happens when a pseudo-register which is equivalent to a
constant or a memory location is not given a hard register.  Reload is
supposed to replace every use of the register with the constant.  The
insn would then normally be deleted.  I don't know why it wasn't deleted
in your case.

One way to address this would probably be to define
LEGITIMATE_CONSTANT_P such that it rejects 0xffffff.  If you don't do
that--if LEGITIMATE_CONSTANT_P accepts 0xffffff--then you need to ensure
that your movsi insn will handle 0xffffff directly, without using any
pseudo-registers when can_create_pseudo_p returns false.

Ian

Re: Reload pass ignores constraints. Why?

[Georg-Johann Lay]

Ian Lance Taylor schrieb:
> Georg-Johann Lay <avr@gjlay.de> writes:
> 
>> When calculate_needs_all_insns runs on the insn the insn looks like
>> this (other insn numbers than above as I proceed my very work
>> regardless of the possible bug)
>>
>> calculate_needs_all_insns[__kernel_rem_pio2:greg(180)]: (insn:HI 409
>> 438 400 17 k_rem_pio2.c:816 (set (reg:SI 566)
>>         (lshiftrt:SI (reg:SI 0 d0 [565])
>>             (const_int 8 [0x8]))) 22 {lshrsi3} (expr_list:REG_EQUIV
>> (const_int 16777215 [0xffffff])
>>         (expr_list:REG_DEAD (reg:SI 0 d0 [565])
>>
>> Someone already replaced #1 with d0, a reg of the right class
>> "d". Maybe a function parameter or return value is propagated.
>>
>> However, calculate_needs_all_insns decides that there are no reloads
>> needed. reload1.c:1554 reads:
>>
>> 	  /* Skip insns that only set an equivalence.  */
>> 	  if (set && REG_P (SET_DEST (set))
>> 	      && reg_renumber[REGNO (SET_DEST (set))] < 0
>> 	      && (reg_equiv_constant[REGNO (SET_DEST (set))]
>> 		  || (reg_equiv_invariant[REGNO (SET_DEST (set))]))
>> 		      && reg_equiv_init[REGNO (SET_DEST (set))])
>>               continue;
>>
>> Before lreg, the insn is tagged REG_EQUAL but lreg then retags it as
>> REG_EQUIV.
>>
>> So is the problem in lreg because it says REG_EQUIV?
>> Or is it wrong to omit REG_EQUIV insns from reload?
> 
> Neither is the problem.
> 
> This case happens when a pseudo-register which is equivalent to a
> constant or a memory location is not given a hard register.  Reload is
> supposed to replace every use of the register with the constant.  The
> insn would then normally be deleted.  I don't know why it wasn't deleted
> in your case.
> 
> One way to address this would probably be to define
> LEGITIMATE_CONSTANT_P such that it rejects 0xffffff.  If you don't do

This will force the 0xffffff into constant pool, which adds penalty of 
+100% in code size and even more in execution time.

> that--if LEGITIMATE_CONSTANT_P accepts 0xffffff--then you need to ensure
> that your movsi insn will handle 0xffffff directly, without using any
> pseudo-registers when can_create_pseudo_p returns false.

That works, of course. But I must admit that I prefer to express what is 
going on in terms of algebra, i.e. in terms of RTL instead of acting as 
if the core could handle the constant and just printng out some asm 
sequencs. movsi expands constants that cannot be loaded in one machine 
instruction to a movesi_insn and an arithmetic insn, and movsi_insn 
therefore allows only constants that are easy to load.

Many RISC machines employ MOV/ADD sequences to load large const_int and 
emit appropriate RTL. Just printing out several instructions in one asm 
string would bypasses all optimizations like CSE, Schedule, etc.

What I do not understand is that a MOV/ADD sequence (which covers large 
constants) works on RTL level, whereas MOV/SHIFTRT (which is more 
efficient in some cases) shreds global alloc. Other strategies could be 
MOV/[AND|IOR|XOR|BSWAP...] which won't work either, though.

greg treats the shift insn as if it was a movsi_insn. I still think it's 
not correct what is going on -- at least as far as I ungerstand the 
internals. They do not say a single word about that large const_int must 
not be expanded into insn sequences. They say an insn alternative was 
*always* safe if it allowed some kind of general register.

Many thanks for your explanations! It's much clearer now. It's much more 
important to me to understand gcc better and learn more about it than to 
quench out some bits of efficiency in the generated code ;-)

Georg-Johann

Re: Reload pass ignores constraints. Why?

[Ian Lance Taylor]

Georg-Johann Lay <avr@gjlay.de> writes:

>> that--if LEGITIMATE_CONSTANT_P accepts 0xffffff--then you need to ensure
>> that your movsi insn will handle 0xffffff directly, without using any
>> pseudo-registers when can_create_pseudo_p returns false.
>
> That works, of course. But I must admit that I prefer to express what
> is going on in terms of algebra, i.e. in terms of RTL instead of
> acting as if the core could handle the constant and just printng out
> some asm sequencs. movsi expands constants that cannot be loaded in
> one machine instruction to a movesi_insn and an arithmetic insn, and
> movsi_insn therefore allows only constants that are easy to load.

You shouldn't print out some asm sequence, you should make movsi a
define_expand which emits a sequence of insns which do not require new
pseudo-registers.  See, e.g., mips_move_integer which is called
(indirectly) by the mov<mode> define_expand in mips.md.

> What I do not understand is that a MOV/ADD sequence (which covers
> large constants) works on RTL level, whereas MOV/SHIFTRT (which is
> more efficient in some cases) shreds global alloc. Other strategies
> could be MOV/[AND|IOR|XOR|BSWAP...] which won't work either, though.

I don't know exactly what is going on.  But it is most likely just a
coincidence that it is failing when using SHIFTRT.  There is probably
some way to make it fail in other ways as well.

> greg treats the shift insn as if it was a movsi_insn. I still think
> it's not correct what is going on -- at least as far as I ungerstand
> the internals. They do not say a single word about that large
> const_int must not be expanded into insn sequences. They say an insn
> alternative was *always* safe if it allowed some kind of general
> register.

Sure, it's always safe if it allows some kind of general register, but
it is also true that the movMM insns must be able to materialize any
constant which is LEGITIMATE_CONSTANT_P, and when can_create_pseudo_p
returns false they must be able to do so without using any new
pseudo-registers.

Ian

Re: Reload pass ignores constraints. Why?

[Georg-Johann Lay]

Ian Lance Taylor schrieb:
> Georg-Johann Lay <avr@gjlay.de> writes:
> 
>>> that--if LEGITIMATE_CONSTANT_P accepts 0xffffff--then you need to ensure
>>> that your movsi insn will handle 0xffffff directly, without using any
>>> pseudo-registers when can_create_pseudo_p returns false.
>> That works, of course. But I must admit that I prefer to express what
>> is going on in terms of algebra, i.e. in terms of RTL instead of
>> acting as if the core could handle the constant and just printng out
>> some asm sequencs. movsi expands constants that cannot be loaded in
>> one machine instruction to a movesi_insn and an arithmetic insn, and
>> movsi_insn therefore allows only constants that are easy to load.
> 
> You shouldn't print out some asm sequence, you should make movsi a
> define_expand which emits a sequence of insns which do not require new
> pseudo-registers.  See, e.g., mips_move_integer which is called
> (indirectly) by the mov<mode> define_expand in mips.md.

Up to now, I see the following stategies:

i)   Expand to a single insn that matched by *movsi_insn:
      Bad, because not optimal and the insn output will print several
      asm statements en bloc (the movsi expander does not print
      anything, of course)

ii)  Expand into MOV+LSHIFTRT and deny the resulting const in
      *movsi_insn predicate and condition:
      Bad, because it crashes reload (as we saw above)

iii) Expand into MOV+LSHIFTRT and allow the resulting const in
      *movsi_insn:
      CSE et. al. will reconstruct the original constant and
      replace MOV+LSHIFTRT with a single SET:
      Bad: expanding was in vain and we Goto i)

iv)  Expand into MOV+LSHIFTRT and remove the const from
      LEGITIMATE_CONSTANT_P:
      Bad, because constant will end up in constant pool.

v)   Expand into MOV+ADD sequence. Works(?), but
      Bad: Code bloat of 100% compared to optimum.
      Ok, I could catch it in a peep2...
      The difference is that in contrast to lshiftrt the add
      can handle the required addition without need of reloads.

vi)  Expand into MOV+LSHIFTRT and allow the constand only if
      reload_in_progress||reload_completed:
      Bad: runs into ICE
      I didn't follow this path any further. Looks too hacky.

The movMM expa
> 
>> What I do not understand is that a MOV/ADD sequence (which covers
>> large constants) works on RTL level, whereas MOV/SHIFTRT (which is
>> more efficient in some cases) shreds global alloc. Other strategies
>> could be MOV/[AND|IOR|XOR|BSWAP...] which won't work either, though.
> 
> I don't know exactly what is going on.  But it is most likely just a
> coincidence that it is failing when using SHIFTRT.  There is probably
> some way to make it fail in other ways as well.

Would state it like this: If the movMM expander expands the move into
several insns, each insn must be able to handle an alternative (which
reload might select) without needing a reload.

Georg-Johann

Re: Reload pass ignores constraints. Why?

[Ian Lance Taylor]

Georg-Johann Lay <avr@gjlay.de> writes:

> iii) Expand into MOV+LSHIFTRT and allow the resulting const in
>      *movsi_insn:
>      CSE et. al. will reconstruct the original constant and
>      replace MOV+LSHIFTRT with a single SET:
>      Bad: expanding was in vain and we Goto i)

I think this is the option you should use.  You should use
TARGET_RTX_COSTS to make the constants which may not be immediate
operands expensive.  Then CSE will not reconstruct them.


>> I don't know exactly what is going on.  But it is most likely just a
>> coincidence that it is failing when using SHIFTRT.  There is probably
>> some way to make it fail in other ways as well.
>
> Would state it like this: If the movMM expander expands the move into
> several insns, each insn must be able to handle an alternative (which
> reload might select) without needing a reload.

Yes, but also when can_create_pseudo_p returns false the move expander
must not call force_reg or gen_reg_reg or anything else which creates a
new pseudo register.  When can_create_pseudo_p returns true, it is often
preferable to generate a new pseudo-reg rather than reuse an existing
one.

Ian

Re: Reload pass ignores constraints. Why?

[Georg-Johann Lay]

Ian Lance Taylor schrieb:
> Georg-Johann Lay <avr@gjlay.de> writes:
> 
>> iii) Expand into MOV+LSHIFTRT and allow the resulting const in
>>      *movsi_insn:
>>      CSE et. al. will reconstruct the original constant and
>>      replace MOV+LSHIFTRT with a single SET:
>>      Bad: expanding was in vain and we Goto i)
> 
> I think this is the option you should use.  You should use
> TARGET_RTX_COSTS to make the constants which may not be immediate
> operands expensive.  Then CSE will not reconstruct them.

Jepp, that works.

Thanks a lot!

Georg-Johann