* [RFC] CFG hooks for rtl/tree specificities @ 2003-04-01 16:11 Pop Sébastian 2003-04-01 16:23 ` Jan Hubicka 0 siblings, 1 reply; 10+ messages in thread From: Pop Sébastian @ 2003-04-01 16:11 UTC (permalink / raw) To: gcc 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; { } ---- ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-04-01 16:11 [RFC] CFG hooks for rtl/tree specificities Pop Sébastian @ 2003-04-01 16:23 ` Jan Hubicka 2003-04-01 17:05 ` Pop Sébastian 0 siblings, 1 reply; 10+ messages in thread From: Jan Hubicka @ 2003-04-01 16:23 UTC (permalink / raw) To: Pop Sébastian; +Cc: gcc > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-04-01 16:23 ` Jan Hubicka @ 2003-04-01 17:05 ` Pop Sébastian 2003-04-01 17:08 ` Jan Hubicka 2003-04-01 18:12 ` Diego Novillo 0 siblings, 2 replies; 10+ messages in thread From: Pop Sébastian @ 2003-04-01 17:05 UTC (permalink / raw) To: Jan Hubicka; +Cc: gcc 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-04-01 17:05 ` Pop Sébastian @ 2003-04-01 17:08 ` Jan Hubicka 2003-04-01 18:12 ` Diego Novillo 1 sibling, 0 replies; 10+ messages in thread From: Jan Hubicka @ 2003-04-01 17:08 UTC (permalink / raw) To: Pop Sébastian; +Cc: Jan Hubicka, gcc > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-04-01 17:05 ` Pop Sébastian 2003-04-01 17:08 ` Jan Hubicka @ 2003-04-01 18:12 ` Diego Novillo 2003-04-02 14:19 ` Pop Sébastian 1 sibling, 1 reply; 10+ messages in thread From: Diego Novillo @ 2003-04-01 18:12 UTC (permalink / raw) To: Pop Sébastian; +Cc: Jan Hubicka, gcc 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-04-01 18:12 ` Diego Novillo @ 2003-04-02 14:19 ` Pop Sébastian 2003-06-14 13:13 ` Jan Hubicka 0 siblings, 1 reply; 10+ messages in thread From: Pop Sébastian @ 2003-04-02 14:19 UTC (permalink / raw) To: Diego Novillo; +Cc: Jan Hubicka, gcc 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-04-02 14:19 ` Pop Sébastian @ 2003-06-14 13:13 ` Jan Hubicka 2003-06-14 19:42 ` Pop Sébastian 0 siblings, 1 reply; 10+ messages in thread From: Jan Hubicka @ 2003-06-14 13:13 UTC (permalink / raw) To: Pop Sébastian; +Cc: Diego Novillo, Jan Hubicka, gcc > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-06-14 13:13 ` Jan Hubicka @ 2003-06-14 19:42 ` Pop Sébastian 2003-06-14 21:01 ` Jan Hubicka 0 siblings, 1 reply; 10+ messages in thread From: Pop Sébastian @ 2003-06-14 19:42 UTC (permalink / raw) To: Jan Hubicka; +Cc: Diego Novillo, gcc 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-06-14 19:42 ` Pop Sébastian @ 2003-06-14 21:01 ` Jan Hubicka 2003-06-15 16:38 ` Jan Hubicka 0 siblings, 1 reply; 10+ messages in thread From: Jan Hubicka @ 2003-06-14 21:01 UTC (permalink / raw) To: Pop Sébastian; +Cc: Jan Hubicka, Diego Novillo, gcc > > > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFC] CFG hooks for rtl/tree specificities 2003-06-14 21:01 ` Jan Hubicka @ 2003-06-15 16:38 ` Jan Hubicka 0 siblings, 0 replies; 10+ messages in thread From: Jan Hubicka @ 2003-06-15 16:38 UTC (permalink / raw) To: Jan Hubicka; +Cc: Pop Sébastian, Diego Novillo, gcc > > > > > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2003-06-15 15:53 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2003-04-01 16:11 [RFC] CFG hooks for rtl/tree specificities Pop Sébastian 2003-04-01 16:23 ` Jan Hubicka 2003-04-01 17:05 ` Pop Sébastian 2003-04-01 17:08 ` Jan Hubicka 2003-04-01 18:12 ` Diego Novillo 2003-04-02 14:19 ` Pop Sébastian 2003-06-14 13:13 ` Jan Hubicka 2003-06-14 19:42 ` Pop Sébastian 2003-06-14 21:01 ` Jan Hubicka 2003-06-15 16:38 ` Jan Hubicka
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).