This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Insert on edge comment
- From: Chris Lattner <sabre at nondot dot org>
- To: law at redhat dot com
- Cc: vmakarov at redhat dot com, <matz at suse dot de>, <amacleod at redhat dot com>,<gcc at gcc dot gnu dot org>
- Date: Sat, 31 May 2003 11:41:24 -0500 (CDT)
- Subject: Re: [tree-ssa] Insert on edge comment
Jeff Law writes:
> In message <3ED7E4C7.69416EBC@redhat.com>, "Vladimir N. Makarov" writes:
>> I am ignorant too (never looked at ssa-tree branch). As I understand the
>> problem is in phi nodes which are based on dominator frontier analysis.
>> Insertion of new BB is simple for general IR but for SSA it can significantly
>> change dominator frontiers for many blocks and as consequence phi-nodes in
>> the dominator frontiers. So updating phi-nodes is not a trivial task.
> That's certainly true as well. If you look at how we do this at the
> RTL level, you'll find that we don't split edges while in SSA form.
> Instead we queue things (such as edge insertions) and split the edge
> after we no longer need dominance info and PHI nodes.
Inserting on edges really isn't that hard if you realize that you only
need to change the CFG for insertion on _critical_ edges. At critical
edges, the dominance properties are much simpler, and allow updating a lot
of data structures incrementally with only local knowledge (including PHI
nodes). If you're interested in how we do it in LLVM, here is the source:
http://llvm.cs.uiuc.edu/doxygen/BreakCriticalEdges_8cpp-source.html
The "SplitCriticalEdge" function updates SSA (of course), dominator sets,
immediate dominators, dominator tree, and dominance frontier information.
It makes the changes appropriate to the particular structure to update
them so they don't need to be recomputed.
IMO, the real problem in tree-ssa is that it uses a nested control flow
structure instead of a linearized one...
-Chris
--
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/