[tree-ssa] CFG cleanup (was: Re: clean)

[Steven Bosscher <s dot bosscher at student dot tudelft dot nl>]

[ moved to list; concerns improved tree cfg cleanup with
  Rice University's DEAD/CLEAN algorithms ]

Op wo 06-08-2003, om 14:08 schreef Diego Novillo:
> On Tue, 2003-08-05 at 11:04, Steven Bosscher wrote:
> > The pointer I previously gave was kind of useless: only some slides.  I
> > found this document in our university library.  It's far more complete
> > so if you're really interested in this it's more useful.
> > Gr.
> > Steven
> >
> Thanks.  Looks interesting.  Are you going to work on it?  If not,
> perhaps you could discuss it on the list.  I know Jeff Law has been
> looking at things of these nature lately.  He might be interested.

I'm trying to implement some of the transformations we need to fully
implement their algorithm (I sent a patch to Jeff yesterday because I
know he's been looking at this kind of thing).  I had a patch that would
forward jumps and did not break bootstrap, but this morning I broke it
with something that I had expected to uncover more opportunities :(
Without this improvement we miss even some of the most obvous cases, see
later in this msg...

(Note of frustration: It still _does_ pass all testing of C/C++ with no
new regressions, but it doesn't bootstrap!?)


I have to say, it's quite difficult to do many of the things they
suggest in that lab report, because we have those syntactic entities in
our representation that Zdenek complained about.

For example, they represent something like this (branch to a jump):

if (...)
  goto block1;
else
  goto block1;

as

if (...)
     / \
    /   \
block1  block1

and in this case it's easy to see that the branch is useless and can be
removed.

But we have to represent the same code as:

if (...)
     / \
    /   \
   /    block3
  /	goto block1
block2
goto block1

so it's not obvious that the targets of this branch are really the
same.  I doubt it's worth the trouble to try and discover this the hard
way.  (Especially of course if we're going to get rid of this "duality
of the data structures" soonish anyway)

Next, we fail to merge empty blocks (ie. blocks with only non-executable
stmts, such as labels or empty stmts).  Until this is fixed, this
prevents us from forwarding jumps like this:

.... some big switch stmt...
                                                                                                                 
              # BLOCK 14 (t.c:65).  PRED: 5.  SUCC: 16.
              case 18:;
              r = 18;
              goto <UL3380>;;
                                                                                                                 
              # BLOCK 15 (t.c:69).  PRED: 5.  SUCC: 16.
              case 19:;
              r = 19;
              goto <UL3380>;
            };
                                                                                                                 
          # BLOCK 16.  PRED: 15 14 13 12 11 10 9 8 7 6 5.  SUCC: 17.
          <UL3380>:;
        };
                                                                                                                 
      # BLOCK 17 (t.c:74).  PRED: 16 4.  SUCC: 20.
      goto <UL2850>;;

Here, block 16 and 17 could safely be merged, exposing another series of
jump-to-jump stmts.  That's what I tried to do this morning, and I got a
nice abort for prize.

I'll send a patch to the list when I'm less dissatisfied with it,
probably after the weekend.  I don't have time to work on it any further
this week.

Gr.
Steven