gcc, support, for, nested, low-overhead, looping

gcc, support, for, nested, low-overhead, looping

[Saira]

I'm porting gcc for an architecture which supports
low-overhead looping for four levels of nested loops.

I've used the "doloop_begin" and "doloop_end" patterns
to emit the low overhead looping instruction.

However, the loop optimizer fails to use these
patterns for outer loops in some cases--for example
when the loop's index variable is declared global. e.g

  
    int a;
    int b;

    int main()
    {

       for(a=10;a>0;a--)
          for(b=10;b>0;b--);

    }
In the above code the loop optimizer will only insert
the doloop patterns for the inner loop and not the
outer loop.
And:


   int main()
   {

     int a;
     int b;

     for(a=10;a>0;a--)
       for(b=10;b>0;b--);

   }
Here aswell the loop optimizer will only insert the
doloop patterns for the inner loop and not the outer
loop.

However it works for both loops in the following code
:
   int main()
   {

     int a;
     int b=10;

     for(a=10;a>0;a--)
       for(;b>0;b--);

   }


Is there some way to overcome this problem? 

Here are the patterns i've used: 

(define_expand "doloop_begin"
  [(use (match_operand 0 "register_operand" ""))
   (use (match_operand 1 "general_operand" ""))
   (use (match_operand 2 "immediate_operand" ""))
   (use (match_operand 3 "immediate_operand" ""))]
  ""
  "
	if(INTVAL(operands[3])>4) FAIL;
	
  emit_insn (gen_rptb_init(operands[0],operands 
[1],operands[2]));
	
	DONE;
  ")


(define_insn "rptb_init"
  [(unspec [(match_operand 0 "register_operand" "d")
	(match_operand 1 "general_operand" "dn")
	(match_operand 2 "immediate_operand" "")
		] 1)
   ]
  ""
"*
if((INTVAL(operands[1])>0) &&
(INTVAL(operands[1])<64))
	{
		get_repeat_count(INTVAL(operands[1]));
		return pat;
	}	
	else return \"repeat %0 {\";
"
)


(define_insn "rptb_end"
  [(set (pc)
 (if_then_else 
    (ge (match_operand 0 "register_operand" "")
                          (const_int 0))
                   (label_ref (match_operand 1 "" ""))
                      (pc)))
   (set (match_dup 0)
        (plus (match_dup 0)
                 (const_int -1)))
   ]
  ""
  "}"
  )



(define_expand "doloop_end"
  [(use (match_operand 0 "register_operand" ""))
   (use (match_operand 1 "immediate_operand" ""))
   (use (match_operand 2 "immediate_operand" ""))
   (use (match_operand 3 "immediate_operand" ""))
   (use (label_ref (match_operand 4 "" "")))]
  ""
  "
   if(INTVAL(operands[3])>4) FAIL;
   emit_jump_insn
(gen_rptb_end(operands[0],operands[4]));
   DONE;
  ")




__________________________________________________
Do You Yahoo!?
Yahoo! Games - play chess, backgammon, pool and more
http://games.yahoo.com/

Re: gcc, support, for, nested, low-overhead, looping

[Michael Hayes]

Saira writes:

 > However, the loop optimizer fails to use these
 > patterns for outer loops in some cases--for example
 > when the loop's index variable is declared global. e.g

This I believe is fair punishment for using a global variable
as a loop counter :-)

<code snipped>

 > In the above code the loop optimizer will only insert
 > the doloop patterns for the inner loop and not the
 > outer loop.

What does the loop optimizer say when you compile with -dL?
It should indicate why it rejected optimising the outer loop.


Michael.

Re: gcc, support, for, nested, low-overhead, looping

[Michael Hayes]

Saira writes:

 > In some cases even loops with local loop counters are
 > not replaced. For instance in the following code:

Yes, I realised this.  Your problem is not specific to low overhead
looping; it is also a problem with loop unrolling as well.  With your
example, we should completely optimise away both loops.  However, this
does not happen due to hairy code in the old loop optimiser that tries
to determine if loops are well behaved or not.

 > If i comment out line 3505 of loop.c--
 >     //maybe_multiple = 1;
 > then it optimizes both loops exactly as they are in
 > the above code. But i don't know the consequences of
 > this for other optimizations-- it seems to affect loop
 > invariant code motion.

Yes, this is the root of the problem.  (BTW, what version of loop.c
are you looking at?)  We are correctly setting maybe_multiple when we
strike instructions of an inner loop but we never clear it again when
the inner loop finishes.  Thus the induction variables of the outer
loop are incorrectly marked as being possibly executed multiple times
and thus we cannot determine the iteration count.

I'm not sure of the best way to fix this problem off hand.  The best
solution is to properly use the CFG like the new loop optimiser is
doing.

Michael.