reg-stack rewrite to use new flow graph representation

[Jan Hubicka]

On Wed, Apr 07, 1999 at 01:15:09AM -0700, Richard Henderson wrote:
> On Tue, Apr 06, 1999 at 12:31:42AM +0200, Jan Hubicka wrote:
> > The bad news are, that this patch changes reg-stack to call life analysis
> > once again. (the reg stack was doing it itself, so it is not worse than
> > before). But flow.c' life analysis are more heavyweight and makes
> > reg-stack slower (about twice on FPU intensive code, making overall
> > compilation time about 5% longer w/o optimization (with optimization
> > the relative time increase will not be so noticeable)).
> 
> This is fine for now.  As you say, there's ways to correct this.
> 
> > Also I had to hack flow.c to avoid removing of insns in this call.
> 
> We'll have to find a different sort of hack for this.  Perhaps an
> argument to life_analysis.
OK. This sounds well.
> 
> > I hope this problem will be solved by changing reg-stack to produce
> > correct RTL. Then we can move reg-stack before jump (and this save
> > third jump pass as well) and modify sched to keep life and basic block
> > information produced by flow2. This can improve compilation time.
> 
> Yep.
> 
> > There are some hacks in this patch. Mainly the patch to flow.c to
> > avoid removing of dead code and hack that removes (use (reg stack_reg))
> > insns in non-optimizing compilation before flow. With this notes
> > most of registers was live before start of function causing reg-stack
> > to generate very ugly code.
> 
> I don't think I understand what you're seeing here wrt the use insns.
> Could you give me an example of the losage?
In non optimizing pass, the use insns are often emited before first set.
This causes reg-stack to think, that there is uninitialized variable.
So it adds necesare "load zero" commands (i387 fails on uninitialized versiables)
Then it needs to take care for such "dead zeros" so resulting code is much worse.

I was getting incorrect code with use in one stage of development. I don't
remember why, so I I will re-check it.
> 
> >   /* Element N says all about the stack at entry block N */
> >   static stack block_stack_in;
> 
> I think it'd be nice to see all these per-block arrays collapsed into
> a structure and hung off bb->aux.  That's what it's there for.  Then
> quit using block indicies quite so much in favour of the bb struct.
OK.
> 
> >   /* Element N says all about the stack life at the end of block N */
> >   static HARD_REG_SET *block_out_reg_set;
> 
> This should be gone in favour of bb->global_live_at_end, no?
I don't think so. I have some plans about critical abnormal edges. If we need to
handle dhem and they are unsplitable, we might use folowing approcach:
1) first component of consistent subgraph created only using abnormal critical edge.
2) create "common live registers set" by oring all output live registrs of block
where src edge is in component and all input live registers of block where dest edge
is in component.
3) we will define "common interface" for all these blocks (all blocks will input all
"common live registers" lets say in increasing order and output them in the same order.

this will make the abnormal edge happy w/o need to split them. (at the cost of worse
code, but it is IMO still better than current reg-stack approach "silently generate wrong code")
> 
> >        Note that we are inserting virtual register references here:
> > !      these insns must be processed by convert_regs later.  */
> >   
> >     for (reg = LAST_STACK_REG; reg >= FIRST_STACK_REG; reg--)
> >       if (TEST_HARD_REG_BIT (block_stack_in[0].reg_set, reg)
> > ! 	 && ! TEST_HARD_REG_BIT (*stackentry, reg))
> >         {
> >   	rtx init_rtx;
> > + 	rtx insn;
> > + 	rtx pos;
> > + 
> > + 	pos = BASIC_BLOCK (0)->head;
> > + 	if (GET_CODE (pos) == CODE_LABEL)
> > + 	  pos = NEXT_INSN (pos);
> 
> Even if the first insn of the first block is a label, wouldn't we
> still be wanting to put these before that?

I tought that every basic block have form: "optional label" "BASIC_BLOCK_NOTE" "code"....
so I was trying to keep this invariant consistent.
But you are right, that we will probably need to take care for case, where block
have multiple input edges, where only one is entry. IMO the correct approach
is to generate code to the edge, reg-stackiize it here and set the entry reg-stack order.

Luckily enought this happends only in non-optimizing compilation so we don't need to care
much about code quality.
> 
> > *************** emit_swap_insn (insn, regstack, reg)
> > *** 1565,1571 ****
> >   
> >     swap_rtx = gen_swapdf (FP_MODE_REG (hard_regno, DFmode),
> >   			 FP_MODE_REG (FIRST_STACK_REG, DFmode));
> > !   swap_insn = emit_insn_after (swap_rtx, i1);
> >   }
> >   
> >   /* Handle a move to or from a stack register in PAT, which is in INSN.
> > --- 1027,1036 ----
> >   
> >     swap_rtx = gen_swapdf (FP_MODE_REG (hard_regno, DFmode),
> >   			 FP_MODE_REG (FIRST_STACK_REG, DFmode));
> > !   if(i1)
> > !     swap_insn = emit_insn_after_bb (swap_rtx, i1);
> > !   else
> > !     swap_insn = emit_insn_before (swap_rtx, insn);
> 
> Since we never cross a block boundary, and we search backwards,
> then we know that bb->end does not need updating here. 
> 
> You might as well keep the old code.
OK I will check it. The if(i1) (oops, the spacing problem :)
is present here because we can emit to the edge (sequence) and we can search
up to the start of seqence so we can need to emit before first insn.

And I believe reg-stack is asking swap_insn to mit code at the end of block as well
(in case last insn is fp insn). I will check this.
> 
> > !   /* To keep basic block boundaries consistent, we need to emit before
> > !      end of basic block.  So create temporary insn.  */
> > !   if (when == emit_insn_after_bb)
> > !     {
> > !        insn = emit_insn_after_bb (gen_rtx_CONST_INT (SImode, 0),insn);
> > !     }
> > !     /*insn = NEXT_INSN (insn);*/
> 
> Ug.  Can we find another way to do this?  Perhaps by keeping
> track of that NEXT_INSN and backing up one to the new bb->end?
> 
> I would also perfer to see `when' be a boolean or enum instead
> of a function pointer -- it's only usefuly one of two things.

OK, when was function in the old code.
I don't understand exactly what are you suggesting, but I will try to make some
cleaner version.
> 
> > ! 		    /* ??? old reg-stack code was not handling abnormal edges.
> > ! 		       So I expect this is acceptable.  
> > ! 		       We know we are generating incorrect code here now, so
> > ! 		       we might complain.  */
> > ! 		    if ((e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL)) 
> > ! 			== (EDGE_ABNORMAL | EDGE_CRITICAL))
> > ! 		      {
> > ! 			/* Be on the safe side and abort for now.  */
> > ! 			abort ();
> > ! 			e = e->succ_next;
> > ! 			continue;
> > ! 		      }
> 
> This is handled in global_conflicts by explicitly killing all
> stacked registers across abnormal edges.
Aha... :)
So then I can remove that global variable.
> 
> > +       if (changed == -1)
> > + 	changed = 0;
> > +       else if (!changed)
> > + 	changed = -1;
> 
> A bit more commentary on this state machine before the while loop
> would be appreciated.
I think it is there (I am describing the -1 meaning)
> 
> Also, go back through and fix up gnu style conformance issues wrt
> parenthesis and whitespace.
Yes I've seen this. I apologize for that. I was checking the patch for GNU style
conformance, but it was pretty long I see I've missed something. sorry.
> 
> So the main thing is the USE issue, which I need to understand
> what's going on.  Otherwise it looks good.
Great.

So I will create the structure, fix the end pointer hack and document the -1 loop.
And check the spacing :)

Honza
> 
> 
> r~

-- 
------------------------------------------------------------------------------
                   Have you browsed my www pages? Look at:
                       http://www.paru.cas.cz/~hubicka
      Koules-the game for Svgalib,X11 and OS/2,  Xonix-the game for X11
      czech documentation for linux index, original 2D computer art and
              funny 100 years old photos and articles are there!