Re: Big find_cross_jump performance regression.

[Brad Lucier <lucier at math dot purdue dot edu>]

I think I've localized the problem that the current CVS source has with

http://www.math.purdue.edu/~lucier/new_t-c-2.i.gz

compiled with -O1 on alphaev6-unknown-gnu-linux.

I instrumented the main loop of jump_optimize_1 in jump.c to record the
value of changed each time it enters the loop, and to set a different
bit of changed for each reason it might want to set changed to a nonzero
value.

For the largest routine in new_t-c-2.i, the main loop of jump_optimize_1
was executed 261 times.  After entering the loop the first time, it ran
the loop 259 more times because changed was set nonzero at both of the
following places in the code (this is the output of tcov):

			  /* See if this jump goes to another jump and redirect if so.  */
     1051345    	  nlabel = follow_jumps (JUMP_LABEL (insn));
call 0 returns = 100%
     1051345    	  if (nlabel != JUMP_LABEL (insn))
branch 0 taken = 96%
			    {
       38820    	      brad_temp = redirect_jump (insn, nlabel, 1);
call 0 returns = 100%
       38820    	      if (brad_temp)
branch 0 taken = 1%
       38559    		changed |= 1 << 4;
     1051345    	    }

and

			      /* Cross jumping of unconditional jumps:
				 a few differences.  */
		
     1050850    	      if (cross_jump && simplejump_p (insn))
branch 0 taken = 2%
call 1 returns = 100%
branch 2 taken = 28%
				{
      746866    		  rtx newjpos, newlpos;
				  rtx target;
		
      746866    		  newjpos = 0;
		
				  /* TARGET is nonzero if it is ok to cross jump
				     to code before TARGET.  If so, see if matches.  */
      746866    		  find_cross_jump (insn, JUMP_LABEL (insn),
branch 0 taken = 100%
branch 1 never executed
call 2 returns = 100%
						   optimize_size ? 1 : BRANCH_COST,
						   &newjpos, &newlpos);
		
				  /* If cannot cross jump to code before the label,
				     see if we can cross jump to another jump to
				     the same label.  */
				  /* Try each other jump to this label.  */
      746866    		  if (INSN_UID (JUMP_LABEL (insn)) < max_uid)
branch 0 taken = 9%
      677112    		    for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))];
   313613067    			 target != 0 && newjpos == 0;
branch 0 taken = 0%
branch 1 taken = 0%
branch 2 taken = 4%
branch 3 taken = 100%
   312935955    			 target = jump_chain[INSN_UID (target)])
branch 0 taken = 4%
   312935955    		      if (target != insn
branch 0 taken = 0%
branch 1 taken = 0%
branch 2 taken = 0%
					  && JUMP_LABEL (target) == JUMP_LABEL (insn)
					  /* Ignore TARGET if it's deleted.  */
					  && ! INSN_DELETED_P (target))
   312258938    			find_cross_jump (insn, target,
branch 0 taken = 4%
branch 1 never executed
call 2 returns = 100%
							 (optimize_size ? 1 : BRANCH_COST) + 1,
							 &newjpos, &newlpos);
		
      746866    		  if (newjpos != 0)
branch 0 taken = 100%
				    {
         406    		      do_cross_jump (insn, newjpos, newlpos);
call 0 returns = 100%
         406    		      changed |= 1 << 15;
         406    		      next = insn;
         406    		    }
     1050850    		}

Finally, the loop was run one more time because the first block of
code set changed |= 1 << 4 again.  This part of the computation takes
about 1100 seconds on my 500 MHz 21264 when cc1 is compiled with -O0
-ftest-coverage -fprofile-arcs.

Now, I can't say that I understand this code, because I don't.  But can
I ask---can one take a worklist approach to all this, to either (a)
cut down on the total number of iterations through the main loop or (b)
not examine so many instructions each iteration?  Or can there be some
other way to reorganize this computation so it doesn't take so long?

If anyone's interested, the gcov output of jump.c run on new_t-c-2.i is
at

http://www.math.purdue.edu/~lucier/jump.c.gcov.gz

Brad