From mboxrd@z Thu Jan  1 00:00:00 1970
From: Jeffrey A Law <law@hurl.cygnus.com>
To: Michael Hayes <m.hayes@elec.canterbury.ac.nz>
Cc: egcs@cygnus.com
Subject: Unswitching [Was: Re: Ternary operator in loop condition]
Date: Sun, 31 Jan 1999 23:58:00 -0000
Message-id: <28168.916226264@hurl.cygnus.com>
References: <13980.29872.698277.543613@ongaonga.elec.canterbury.ac.nz>
X-SW-Source: 1999-01n/msg00471.html

  In message < 13980.29872.698277.543613@ongaonga.elec.canterbury.ac.nz >you writ
e:
  > Right, this would be the more general and my preferred solution.
  > However, it's also the much harder problem to solve ;-(
Maybe harder to solve.  But the benefits are probably greater than
having the unroller realize the loop iterates a multiple of 4 times and
optimizing the unrolled loop & precondition code accordingly.


Anyway, given a loop condition like:

bar ? (i < 4) : (i < 8)

One of the easy ways to pull the "bar" test out of the loop is to create
two loops:

if (bar)
  loop using i < 4
else
  loop using i < 8

The code expansion is greater then reworking the condition into
i < (bar ? 4 : 8), then hoisting the (bar ? 4 : 8) out of the loop.

But the net result is two loops with very simple conditions which can
easily be unrolled.  If they get completely unrolled it's likely cross
jumping would be able to eliminate the code expansion later by having the
i < 4 code jump into the middle of the i < 8 code.

Plus the work would be re-useable for implementing unswitching.  

Toon -- stop jumping up and down.  Calm down. I know you want this
optimization  ;-)



      do i = 1, n
         if (lcond) then
            <body1>
         else
            <body2>
         endif
      enddo

If lcond is a loop invariant it can be turned into:

      if (lcond) then
         do i = 1, n
            <body1>
         enddo
      else
         do i = 1, n
            <body2>
         enddo
      endif


It'd be awful cool.  And I don't think it's a horribly difficult problem
to solve.

  > Currently we do a pitiful job of hoisting invariants out of the loop
  > termination testing instructions and it's easy to overlook that the
  > termination testing code is executed every iteration.  If the
  > iteration count is invariant and can be hoisted out we've got a lot to
  > gain.
Yup.  No arguments.

jeff