[RFC] CFG hooks for rtl/tree specificities

[RFC] CFG hooks for rtl/tree specificities

[Pop Sébastian]

Hi,

I would like to have your opinion on the following reorganization of the CFG functions.

I propose to keep all the functions that deal with IR specificities into a hook structure
a little bit the same way we handle the specificities of a language front-end in langhooks.  
These functions are initialized during the CFG construction.  This would allow the CFG 
analyzers and optimizers to work at both the RTL and the tree levels.  


cfghooks.h will contain something like:
----

/* Initializations specific to either the tree or the rtl level.  */
extern void tree_register_cfg_hooks    PARAMS ((void));
extern void rtl_register_cfg_hooks     PARAMS ((void));

struct cfg_hooks
{
  basic_block (*cfgh_split_edge)       PARAMS ((edge));
  void (*cfgh_cfg_layout_initialize)   PARAMS ((struct loops *));
  void (*cfgh_cfg_layout_finalize)     PARAMS ((void));
  void (*cfgh_verify_flow_info)        PARAMS ((void));
}; 

/* The following macros act either at the tree level or at the rtl level.  */
#define split_edge(e)                  cfg_hooks.cfgh_split_edge (e) 
#define cfg_layout_initialize(l)       cfg_hooks.cfgh_cfg_layout_initialize (l) 
#define cfg_layout_finalize()          cfg_hooks.cfgh_cfg_layout_finalize () 
#define verify_flow_info()             cfg_hooks.cfgh_verify_flow_info () 

extern struct cfg_hooks cfg_hooks;

----


cfghooks.c looks like:
----

struct cfg_hooks cfg_hooks;

/* Static declarations.  */
static void cfgh_do_nothing            PARAMS ((void));
static void cfgh_do_nothing_loops      PARAMS ((struct loops *));


/* Initialization of functions specific to the tree IR.  */

void
tree_register_cfg_hooks ()
{
  cfg_hooks.cfgh_split_edge = &tree_split_edge;
  cfg_hooks.cfgh_cfg_layout_initialize = &cfgh_do_nothing_loops;
  cfg_hooks.cfgh_cfg_layout_finalize = &cfgh_do_nothing;
  cfg_hooks.cfgh_verify_flow_info = &cfgh_do_nothing;
} 

/* Initialization of functions specific to the rtl IR.  */

void
rtl_register_cfg_hooks ()
{
  cfg_hooks.cfgh_split_edge = &rtl_split_edge;
  cfg_hooks.cfgh_cfg_layout_initialize = &rtl_cfg_layout_initialize;
  cfg_hooks.cfgh_cfg_layout_finalize = &rtl_cfg_layout_finalize;
  cfg_hooks.cfgh_verify_flow_info = &rtl_verify_flow_info;
} 

/* Do-nothing functions.  */
static void
cfgh_do_nothing ()
{
} 

static void
cfgh_do_nothing_loops (l)
     struct loops *l ATTRIBUTE_UNUSED;
{
} 

----

Re: [RFC] CFG hooks for rtl/tree specificities

[Jan Hubicka]

> Hi,
> 
> I would like to have your opinion on the following reorganization of the CFG functions.
> 
> I propose to keep all the functions that deal with IR specificities into a hook structure
> a little bit the same way we handle the specificities of a language front-end in langhooks.  

I like it :)

> These functions are initialized during the CFG construction.  This would allow the CFG 
> analyzers and optimizers to work at both the RTL and the tree levels.  

I think all we need is to have two cfg_hooks pointer and switch betwen
cfg_rtl_hooks, cfg_rtl_layout_hooks and cfg_tree_hooks so we don't need
to fill up the structure each time.
> 
> 
> cfghooks.h will contain something like:
> ----
> 
> /* Initializations specific to either the tree or the rtl level.  */
> extern void tree_register_cfg_hooks    PARAMS ((void));
> extern void rtl_register_cfg_hooks     PARAMS ((void));
> 
> struct cfg_hooks
> {
>   basic_block (*cfgh_split_edge)       PARAMS ((edge));
>   void (*cfgh_cfg_layout_initialize)   PARAMS ((struct loops *));
>   void (*cfgh_cfg_layout_finalize)     PARAMS ((void));
>   void (*cfgh_verify_flow_info)        PARAMS ((void));
> }; 
> 
> /* The following macros act either at the tree level or at the rtl level.  */
> #define split_edge(e)                  cfg_hooks.cfgh_split_edge (e) 
> #define cfg_layout_initialize(l)       cfg_hooks.cfgh_cfg_layout_initialize (l) 
> #define cfg_layout_finalize()          cfg_hooks.cfgh_cfg_layout_finalize () 
> #define verify_flow_info()             cfg_hooks.cfgh_verify_flow_info () 
> 
> extern struct cfg_hooks cfg_hooks;

This looks nice.
It would be interesting to think about what operations do we really need
- for instance split_edge should be probably implementable already via
the primitive operations (basic block creation, edge redirection).  Our
current API is not 100% ready for that so we will probably need cleanup
on the way.

I would be happy about switching to the hooks first and leaving it to me
to cleanup the APIs if you preffer.

Honza

Re: [RFC] CFG hooks for rtl/tree specificities

[Pop Sébastian]

On Tue, Apr 01, 2003 at 05:46:07PM +0200, Jan Hubicka wrote:
> 
> This looks nice.
> It would be interesting to think about what operations do we really need
> - for instance split_edge should be probably implementable already via
> the primitive operations (basic block creation, edge redirection).  Our

Yes, the split_edge function is trivially implemented at the tree level:

basic_block
tree_split_edge (edge_in)
     edge edge_in;
{
  basic_block new_bb, dest;
  
  /* Abnormal edges cannot be split.  */
  if (edge_in->flags & EDGE_ABNORMAL)
    abort ();
  
  dest = edge_in->dest;
  new_bb = create_bb ();
  redirect_edge_succ  (edge_in, new_bb);
  make_edge (new_bb, dest, EDGE_FALLTHRU);
  return new_bb;
}

except "create_bb" all the other functions are CFG generic, making the split_edge
a good candidate for the CFG API.  At RTL level the split_edge function deals
with insns at this moment.

> current API is not 100% ready for that so we will probably need cleanup
> on the way.
> 
> I would be happy about switching to the hooks first and leaving it to me
> to cleanup the APIs if you preffer.
> 
Yes, thanks.

Sebastian

Re: [RFC] CFG hooks for rtl/tree specificities

[Jan Hubicka]

> On Tue, Apr 01, 2003 at 05:46:07PM +0200, Jan Hubicka wrote:
> > 
> > This looks nice.
> > It would be interesting to think about what operations do we really need
> > - for instance split_edge should be probably implementable already via
> > the primitive operations (basic block creation, edge redirection).  Our
> 
> Yes, the split_edge function is trivially implemented at the tree level:
> 
> basic_block
> tree_split_edge (edge_in)
>      edge edge_in;
> {
>   basic_block new_bb, dest;
>   
>   /* Abnormal edges cannot be split.  */
>   if (edge_in->flags & EDGE_ABNORMAL)
>     abort ();
>   
>   dest = edge_in->dest;
>   new_bb = create_bb ();
>   redirect_edge_succ  (edge_in, new_bb);
>   make_edge (new_bb, dest, EDGE_FALLTHRU);
>   return new_bb;
> }
> 
> except "create_bb" all the other functions are CFG generic, making the split_edge
> a good candidate for the CFG API.  At RTL level the split_edge function deals
> with insns at this moment.

Yes, the generic implementation would have to deal with idea of
linearized RTL chain (so know what to do about fallthru edges and so
on).  Lets leave it hooked for now.

Honza
> 
> > current API is not 100% ready for that so we will probably need cleanup
> > on the way.
> > 
> > I would be happy about switching to the hooks first and leaving it to me
> > to cleanup the APIs if you preffer.
> > 
> Yes, thanks.
> 
> Sebastian

Re: [RFC] CFG hooks for rtl/tree specificities

[Diego Novillo]

On Tue, 2003-04-01 at 11:11, Pop Sébastian wrote:
> On Tue, Apr 01, 2003 at 05:46:07PM +0200, Jan Hubicka wrote:
> > 
> > This looks nice.
> > It would be interesting to think about what operations do we really need
> > - for instance split_edge should be probably implementable already via
> > the primitive operations (basic block creation, edge redirection).  Our
> 
> Yes, the split_edge function is trivially implemented at the tree level:
> 
Note that the edge insertion functions in tree-cfg.c already split
edges.  If you are going to implement a split_edge routine, could you
update bsi_commit_first_edge_insert?


Thanks.  Diego.

Re: [RFC] CFG hooks for rtl/tree specificities

[Pop Sébastian]

On Tue, Apr 01, 2003 at 11:23:12AM -0500, Diego Novillo wrote:
> Note that the edge insertion functions in tree-cfg.c already split
> edges.  If you are going to implement a split_edge routine, could you
> update bsi_commit_first_edge_insert?
> 
Yes.  
That's exactly from where I have took the code for the tree level split_edge.


A question: 
what do you think about extending the basic block iterator (bsi) to handle 
a union {tree, rtl}, then use iterators instead of rtx-es in functions like 
split_block (basic_block, rtx) ?
The implementation (ie. tree_split_block and rtl_split_block) will decide 
wheter the iterator contains a tree or an rtx (C poor man's polymorphism).

Sebastian

Re: [RFC] CFG hooks for rtl/tree specificities

[Jan Hubicka]

> On Tue, Apr 01, 2003 at 11:23:12AM -0500, Diego Novillo wrote:
> > Note that the edge insertion functions in tree-cfg.c already split
> > edges.  If you are going to implement a split_edge routine, could you
> > update bsi_commit_first_edge_insert?
> > 
> Yes.  
> That's exactly from where I have took the code for the tree level split_edge.

Hi,
I've already hookized most of the basic RTL CFG API in the mainline.
(basic block creation/duplication/merging is missing, I will proceed on
that).  In general I would like to see the parts of current cfg cleanup
that does not deal with presence of fallthru edges (which hopefully will
never exists elsewhere) to be generic possibly replacing the current
tree implementation of the same thing.  I would like now to break out
the crossjumping and probably slowly kill the jump threading if Josef's
VRP patch comes in so we will stay with BB merging, edge forwarding and
such.

Now I am thinking how to map this API into tree level and I obviously do
have problems :)  The high level control flow structure is not too
compatible with the low level one RTL CFG is built on.  The ideology of
RTL CFG API is to provide set of primitives that update both - CFG and
RTL at the same time, so CFG always match closely what RTL chain
represents as if it were built from the scratch at given point.
Originally we were updating RTL and CFG by hand and it lead to endless
headaches so I slowly avoided that scheme even when the set of
"primitives" is pretty large and never 100% complette (parts of
cfgcleanup still needs to be done using direct API, but these parts deal
with fallthru edges so perhaps they can be avoided entirely on higher
level).

Still the profile needs to be udpated by hand as even those primitives
are too low level to allow easy updating of the profile info itself.
THis if fragile, but there seems to be no better way.  It is very time
consuming to revisit existing code for profile updating.  Can you,
please write the code to update profile when new code is added to
tree-ssa even when we don't do profiling on tree-ssa level at the very
moment?

This seems to be different from tree-ssa one where for instance basic
block removeal does not appear to take care to kill the surrouding
control flow constructs, just kill the contained statements.  

I am not sure how much of the API we can map - I was looking at the edge
splitting code and don't quite understand how it preserves the CFG
consistent with the tree representation. I.E when the new basic block is
created there is no modification into underlying IL made and I have no
idea how you do decide wehre to place code that eventually will be
inserted into the BB.  Can you please try to take a quick look on what I
do have on mainline now and let me know you ideas?

Concerning the high level constructs, I am not very convienced that we
actually need it and I would like to proceed on gradual lowering of
these constructs on gimple level (so at RTL expansion time we do have
conditional jumps, jumptables and computed jumps constructs same as RTL
has with exception of conditional jumps being two way jumps with no
fallthru).  I am not sure how the exception handling should be
represented. Current RTL EH seems to be bit inflexible too - we should
be able to redirect edges easilly but currently I am not quite sure how
the region structures should be updated.  But the RTL idea of
instructions having attached EH region information looks fine to me.

I think it makes sense to employ WHIRL-like approach where
the constructs are killed gradually during the expansion even when I am
not very conveienced that the high level construct actually help some
optimizer (because the constructs can not be fully normalized so one
still has to check CFG and direct operations on CFG are dificult at the
same time) but perhaps my mind is simply limited.  This should also
allow us to preserve CFG during RTL expansion and thus preserve profile
information.

First show-stopper in this plan appears to be representation of scoping
regions and exception handling.  Do you think it would be dificult to
convert it into RTL-style information?

I also dug out my old CFG structural analysis code and trying to finish
it, so we will be able to pretty print the CFG even without having the
explicit nodes and we can try to use this alternative instead of the
high level constructs for our optimizations.  The structure is in some
whays prettier than what we do have now in the loop tree (and in other
ways it is not, so it probably makes sense to have both)

Honza

Re: [RFC] CFG hooks for rtl/tree specificities

[Pop Sébastian]

On Sat, Jun 14, 2003 at 02:09:13PM +0200, Jan Hubicka wrote:
> 
> Hi,
> I've already hookized most of the basic RTL CFG API in the mainline.
Cool, thanks for working on that. 

> THis if fragile, but there seems to be no better way.  It is very time
> consuming to revisit existing code for profile updating.  Can you,
> please write the code to update profile when new code is added to
> tree-ssa even when we don't do profiling on tree-ssa level at the very
> moment?
> 
Sure, I'll try to write this code.  
I have some exams this month, but after that, I will give it a look.

> This seems to be different from tree-ssa one where for instance basic
> block removeal does not appear to take care to kill the surrouding
> control flow constructs, just kill the contained statements.  
> 
> I am not sure how much of the API we can map - I was looking at the edge
> splitting code and don't quite understand how it preserves the CFG
> consistent with the tree representation. 
The BB that splits the edge is artificial, and thus it does not have to 
modify the underlying representation.  

> I.E when the new basic block is
> created there is no modification into underlying IL made and I have no
> idea how you do decide wehre to place code that eventually will be
> inserted into the BB.  

I would say that this is the job of the bsi_insert*-ers.  
It would be interesting to have this interface also at RTL level: 
ie. insertions performed with the help of iterators using 
bsi_insert_after, bsi_insert_before, and bsi_insert_on_edge.

I don't think that the tree level insertion of code is confused by the 
presence of a new empty/artificial basic block in the flow. 

> Can you please try to take a quick look on what I
> do have on mainline now and let me know you ideas?
> 
If I recall correctly, the edge splitting at RTL level inserts code 
in the newly created basic block.  In some intermediate version, I have 
also inserted NOP_EXPRs in the newly created BB, but I ended up by not 
inserting anything in the new BB since the role of the artificial BB
is only to modify the properties of the CFG, without modifying the 
underlying representation.  In the loop detector we need a single 
back edge (aka. latch) per loop, and thus we have to slightly modify the 
properties of the CFG, but the underlying representation does not have to 
change.  

> Concerning the high level constructs, I am not very convienced that we
> actually need it and I would like to proceed on gradual lowering of
> these constructs on gimple level (so at RTL expansion time we do have
> conditional jumps, jumptables and computed jumps constructs same as RTL
> has with exception of conditional jumps being two way jumps with no
> fallthru).  
I agree that having a high level DO_EXPR for normalized loops would not 
help, since all the information is already well stored in the loops/loop
structures.  

[...]
> First show-stopper in this plan appears to be representation of scoping
> regions and exception handling.  Do you think it would be dificult to
> convert it into RTL-style information?
> 
I have no idea.

Re: [RFC] CFG hooks for rtl/tree specificities

[Jan Hubicka]

> 
> > This seems to be different from tree-ssa one where for instance basic
> > block removeal does not appear to take care to kill the surrouding
> > control flow constructs, just kill the contained statements.  
> > 
> > I am not sure how much of the API we can map - I was looking at the edge
> > splitting code and don't quite understand how it preserves the CFG
> > consistent with the tree representation. 
> The BB that splits the edge is artificial, and thus it does not have to 
> modify the underlying representation.  

What exactly do you mean by artifical BB?
> 
> > I.E when the new basic block is
> > created there is no modification into underlying IL made and I have no
> > idea how you do decide wehre to place code that eventually will be
> > inserted into the BB.  
> 
> I would say that this is the job of the bsi_insert*-ers.  
> It would be interesting to have this interface also at RTL level: 
> ie. insertions performed with the help of iterators using 
> bsi_insert_after, bsi_insert_before, and bsi_insert_on_edge.

Hmm, I see, bsi_insert_on_edge called on edge between two abstract
blocks will call bsi_insert_after on iterator containing the empty block
that will in turn look for the followup block that is again empty block
and abort ().

It also appears to fail in the case the edge is in between abstract
block and normal block that starts at a label and this edge comes from
goto statement, while the label can be also reached via fallthru.
In that case bsi_insert_after appears to insert code at the beggining of
parent stmt of the destination block that may be well before the
label and thus it is reached by the other ede than it is supposed to.

I am not quite sure how good idea is to have basic blocks that do not
exists in the underlying code and vice versa.  I believe there are too
many side cases one can run into.
> 
> I don't think that the tree level insertion of code is confused by the 
> presence of a new empty/artificial basic block in the flow. 
> 
> > Can you please try to take a quick look on what I
> > do have on mainline now and let me know you ideas?
> > 
> If I recall correctly, the edge splitting at RTL level inserts code 
> in the newly created basic block.  In some intermediate version, I have 

It does not insert really anything, just sets up the basic block in RTL
representation (you are required to have BASIC_BLOCK note in it that is
there mostly to avoid need for the iterators - so we have something to
point to even inside empty basic blocks).

> also inserted NOP_EXPRs in the newly created BB, but I ended up by not 
> inserting anything in the new BB since the role of the artificial BB
> is only to modify the properties of the CFG, without modifying the 
> underlying representation.  In the loop detector we need a single 
> back edge (aka. latch) per loop, and thus we have to slightly modify the 
> properties of the CFG, but the underlying representation does not have to 
> change.  

The loop analysis is probably not best example here as it really
modifies the CFG for no obvious reason. But OK, I see that you can add
machinery to create basic blocks on the edges lazilly once they are
used.
> 
> > Concerning the high level constructs, I am not very convienced that we
> > actually need it and I would like to proceed on gradual lowering of
> > these constructs on gimple level (so at RTL expansion time we do have
> > conditional jumps, jumptables and computed jumps constructs same as RTL
> > has with exception of conditional jumps being two way jumps with no
> > fallthru).  
> I agree that having a high level DO_EXPR for normalized loops would not 
> help, since all the information is already well stored in the loops/loop
> structures.  
> 
> [...]
> > First show-stopper in this plan appears to be representation of scoping
> > regions and exception handling.  Do you think it would be dificult to
> > convert it into RTL-style information?
> > 
> I have no idea.
Me neither.  I have to understand the treessa closer I guess :)

Good luck with your exam!
Honza

Re: [RFC] CFG hooks for rtl/tree specificities

[Jan Hubicka]

> > 
> > > This seems to be different from tree-ssa one where for instance basic
> > > block removeal does not appear to take care to kill the surrouding
> > > control flow constructs, just kill the contained statements.  
> > > 
> > > I am not sure how much of the API we can map - I was looking at the edge
> > > splitting code and don't quite understand how it preserves the CFG
> > > consistent with the tree representation. 
> > The BB that splits the edge is artificial, and thus it does not have to 
> > modify the underlying representation.  
> 
> What exactly do you mean by artifical BB?
> > 
> > > I.E when the new basic block is
> > > created there is no modification into underlying IL made and I have no
> > > idea how you do decide wehre to place code that eventually will be
> > > inserted into the BB.  
> > 
> > I would say that this is the job of the bsi_insert*-ers.  
> > It would be interesting to have this interface also at RTL level: 
> > ie. insertions performed with the help of iterators using 
> > bsi_insert_after, bsi_insert_before, and bsi_insert_on_edge.
> 
> Hmm, I see, bsi_insert_on_edge called on edge between two abstract
> blocks will call bsi_insert_after on iterator containing the empty block
> that will in turn look for the followup block that is again empty block
> and abort ().
> 
> It also appears to fail in the case the edge is in between abstract
> block and normal block that starts at a label and this edge comes from
> goto statement, while the label can be also reached via fallthru.
> In that case bsi_insert_after appears to insert code at the beggining of
> parent stmt of the destination block that may be well before the
> label and thus it is reached by the other ede than it is supposed to.

Hi,
I was looking bit more on the bsi code and it is very interesting :) I
wonder what operations can be implemented this way without running into
inexpected dead ends.  Is there some other compiler using similar
approach in practice I can look on too?

Honza