vm/compiler/codegen/mips/GlobalOptimizations.cpp - platform/dalvik2 - Git at Google

 /*
  * Copyright (C) 2009 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "Dalvik.h"
 #include "vm/compiler/CompilerInternals.h"
 #include "MipsLIR.h"

 /*
  * Identify unconditional branches that jump to the immediate successor of the
  * branch itself.
  */
 static void applyRedundantBranchElimination(CompilationUnit *cUnit)
 {
     MipsLIR *thisLIR;

     for (thisLIR = (MipsLIR *) cUnit->firstLIRInsn;
          thisLIR != (MipsLIR *) cUnit->lastLIRInsn;
          thisLIR = NEXT_LIR(thisLIR)) {

         /* Branch to the next instruction */
         if (!thisLIR->flags.isNop && thisLIR->opcode == kMipsB) {
             MipsLIR *nextLIR = thisLIR;

             while (true) {
                 nextLIR = NEXT_LIR(nextLIR);

                 /*
                  * Is the branch target the next instruction?
                  */
                 if (nextLIR == (MipsLIR *) thisLIR->generic.target) {
                     thisLIR->flags.isNop = true;
                     break;
                 }

                 /*
                  * Found real useful stuff between the branch and the target.
                  * Need to explicitly check the lastLIRInsn here since with
                  * method-based JIT the branch might be the last real
                  * instruction.
                  */
                 if (!isPseudoOpCode(nextLIR->opcode) ||
                     (nextLIR = (MipsLIR *) cUnit->lastLIRInsn))
                     break;
             }
         }
     }
 }

 /*
  * Do simple a form of copy propagation and elimination.
  */
 static void applyCopyPropagation(CompilationUnit *cUnit)
 {
     MipsLIR *thisLIR;

     /* look for copies to possibly eliminate */
     for (thisLIR = (MipsLIR *) cUnit->firstLIRInsn;
          thisLIR != (MipsLIR *) cUnit->lastLIRInsn;
          thisLIR = NEXT_LIR(thisLIR)) {

         if (thisLIR->flags.isNop || thisLIR->opcode != kMipsMove)
             continue;

         const int max_insns = 10;
         MipsLIR *savedLIR[max_insns];
         int srcRedefined = 0;
         int insnCount = 0;
         MipsLIR *nextLIR;

         /* look for and record all uses of reg defined by the copy */
         for (nextLIR = (MipsLIR *) NEXT_LIR(thisLIR);
              nextLIR != (MipsLIR *) cUnit->lastLIRInsn;
              nextLIR = NEXT_LIR(nextLIR)) {

             if (nextLIR->flags.isNop || nextLIR->opcode == kMips32BitData)
                 continue;

             if (isPseudoOpCode(nextLIR->opcode)) {
                 if (nextLIR->opcode == kMipsPseudoDalvikByteCodeBoundary ||
                     nextLIR->opcode == kMipsPseudoBarrier ||
                     nextLIR->opcode == kMipsPseudoExtended ||
                     nextLIR->opcode == kMipsPseudoSSARep)
                     continue; /* these pseudos don't pose problems */
                 else if (nextLIR->opcode == kMipsPseudoTargetLabel ||
                          nextLIR->opcode == kMipsPseudoEntryBlock ||
                          nextLIR->opcode == kMipsPseudoExitBlock)
                     insnCount = 0;  /* give up for these pseudos */
                 break; /* reached end for copy propagation */
             }

             /* Since instructions with IS_BRANCH flag set will have its */
             /* useMask and defMask set to ENCODE_ALL, any checking of   */
             /* these flags must come after the branching checks.        */

             /* don't propagate across branch/jump and link case
                or jump via register */
             if (EncodingMap[nextLIR->opcode].flags & REG_DEF_LR ||
                 nextLIR->opcode == kMipsJalr ||
                 nextLIR->opcode == kMipsJr) {
                 insnCount = 0;
                 break;
             }

             /* branches with certain targets ok while others aren't */
             if (EncodingMap[nextLIR->opcode].flags & IS_BRANCH) {
                 MipsLIR *targetLIR =  (MipsLIR *) nextLIR->generic.target;
                 if (targetLIR->opcode != kMipsPseudoEHBlockLabel &&
                     targetLIR->opcode != kMipsPseudoChainingCellHot &&
                     targetLIR->opcode != kMipsPseudoChainingCellNormal &&
                     targetLIR->opcode != kMipsPseudoChainingCellInvokePredicted &&
                     targetLIR->opcode != kMipsPseudoChainingCellInvokeSingleton &&
                     targetLIR->opcode != kMipsPseudoPCReconstructionBlockLabel &&
                     targetLIR->opcode != kMipsPseudoPCReconstructionCell) {
                     insnCount = 0;
                     break;
                 }
                 /* FIXME - for now don't propagate across any branch/jump. */
                 insnCount = 0;
                 break;
             }

             /* copy def reg used here, so record insn for copy propagation */
             if (thisLIR->defMask & nextLIR->useMask) {
                 if (insnCount == max_insns || srcRedefined) {
                     insnCount = 0;
                     break; /* just give up if too many or not possible */
                 }
                 savedLIR[insnCount++] = nextLIR;
             }

             if (thisLIR->defMask & nextLIR->defMask) {
 		if (nextLIR->opcode == kMipsMovz)
 		    insnCount = 0; /* movz relies on thisLIR setting dst reg so abandon propagation*/
                 break;
             }

             /* copy src reg redefined here, so can't propagate further */
             if (thisLIR->useMask & nextLIR->defMask) {
                 if (insnCount == 0)
                     break; /* nothing to propagate */
                 srcRedefined = 1;
             }
        }

         /* conditions allow propagation and copy elimination */
         if (insnCount) {
             int i;
             for (i = 0; i < insnCount; i++) {
                 int flags = EncodingMap[savedLIR[i]->opcode].flags;
                 savedLIR[i]->useMask &= ~(1 << thisLIR->operands[0]);
                 savedLIR[i]->useMask |= 1 << thisLIR->operands[1];
                 if ((flags & REG_USE0) &&
                     savedLIR[i]->operands[0] == thisLIR->operands[0])
                     savedLIR[i]->operands[0] = thisLIR->operands[1];
                 if ((flags & REG_USE1) &&
                     savedLIR[i]->operands[1] == thisLIR->operands[0])
                     savedLIR[i]->operands[1] = thisLIR->operands[1];
                 if ((flags & REG_USE2) &&
                     savedLIR[i]->operands[2] == thisLIR->operands[0])
                     savedLIR[i]->operands[2] = thisLIR->operands[1];
                 if ((flags & REG_USE3) &&
                     savedLIR[i]->operands[3] == thisLIR->operands[0])
                     savedLIR[i]->operands[3] = thisLIR->operands[1];
             }
             thisLIR->flags.isNop = true;
         }
     }
 }

 #ifdef __mips_hard_float
 /*
  * Look for pairs of mov.s instructions that can be combined into mov.d
  */
 static void mergeMovs(CompilationUnit *cUnit)
 {
   MipsLIR *movsLIR = NULL;
   MipsLIR *thisLIR;

   for (thisLIR = (MipsLIR *) cUnit->firstLIRInsn;
        thisLIR != (MipsLIR *) cUnit->lastLIRInsn;
        thisLIR = NEXT_LIR(thisLIR)) {
     if (thisLIR->flags.isNop)
       continue;

     if (isPseudoOpCode(thisLIR->opcode)) {
       if (thisLIR->opcode == kMipsPseudoDalvikByteCodeBoundary ||
                 thisLIR->opcode == kMipsPseudoExtended ||
 	  thisLIR->opcode == kMipsPseudoSSARep)
 	continue;  /* ok to move across these pseudos */
       movsLIR = NULL; /* don't merge across other pseudos */
       continue;
     }

     /* merge pairs of mov.s instructions */
     if (thisLIR->opcode == kMipsFmovs) {
       if (movsLIR == NULL)
 	movsLIR = thisLIR;
       else if (((movsLIR->operands[0] & 1) == 0) &&
 	       ((movsLIR->operands[1] & 1) == 0) &&
 	       ((movsLIR->operands[0] + 1) == thisLIR->operands[0]) &&
 	       ((movsLIR->operands[1] + 1) == thisLIR->operands[1])) {
 	/* movsLIR is handling even register - upgrade to mov.d */
 	movsLIR->opcode = kMipsFmovd;
 	movsLIR->operands[0] = S2D(movsLIR->operands[0], movsLIR->operands[0]+1);
 	movsLIR->operands[1] = S2D(movsLIR->operands[1], movsLIR->operands[1]+1);
 	thisLIR->flags.isNop = true;
 	movsLIR = NULL;
       }
       else if (((movsLIR->operands[0] & 1) == 1) &&
 	       ((movsLIR->operands[1] & 1) == 1) &&
 	       ((movsLIR->operands[0] - 1) == thisLIR->operands[0]) &&
 	       ((movsLIR->operands[1] - 1) == thisLIR->operands[1])) {
 	/* thissLIR is handling even register - upgrade to mov.d */
 	thisLIR->opcode = kMipsFmovd;
 	thisLIR->operands[0] = S2D(thisLIR->operands[0], thisLIR->operands[0]+1);
 	thisLIR->operands[1] = S2D(thisLIR->operands[1], thisLIR->operands[1]+1);
 	movsLIR->flags.isNop = true;
 	movsLIR = NULL;
       }
       else
 	/* carry on searching from here */
 	movsLIR = thisLIR;
       continue;
     }

     /* intervening instruction - start search from scratch */
     movsLIR = NULL;
   }
 }
 #endif


 /*
  * Look back first and then ahead to try to find an instruction to move into
  * the branch delay slot.  If the analysis can be done cheaply enough, it may be
  * be possible to tune this routine to be more beneficial (e.g., being more
  * particular about what instruction is speculated).
  */
 static MipsLIR *delaySlotLIR(MipsLIR *firstLIR, MipsLIR *branchLIR)
 {
     int isLoad;
     int loadVisited = 0;
     int isStore;
     int storeVisited = 0;
     u8 useMask = branchLIR->useMask;
     u8 defMask = branchLIR->defMask;
     MipsLIR *thisLIR;
     MipsLIR *newLIR = (MipsLIR *) dvmCompilerNew(sizeof(MipsLIR), true);

     for (thisLIR = PREV_LIR(branchLIR);
          thisLIR != firstLIR;
          thisLIR = PREV_LIR(thisLIR)) {
         if (thisLIR->flags.isNop)
             continue;

         if (isPseudoOpCode(thisLIR->opcode)) {
             if (thisLIR->opcode == kMipsPseudoDalvikByteCodeBoundary ||
                 thisLIR->opcode == kMipsPseudoExtended ||
                 thisLIR->opcode == kMipsPseudoSSARep)
                 continue;  /* ok to move across these pseudos */
             break; /* don't move across all other pseudos */
         }

         /* give up on moving previous instruction down into slot */
         if (thisLIR->opcode == kMipsNop ||
             thisLIR->opcode == kMips32BitData ||
             EncodingMap[thisLIR->opcode].flags & IS_BRANCH)
             break;

         /* don't reorder loads/stores (the alias info could
            possibly be used to allow as a future enhancement) */
         isLoad = EncodingMap[thisLIR->opcode].flags & IS_LOAD;
         isStore = EncodingMap[thisLIR->opcode].flags & IS_STORE;

         if (!(thisLIR->useMask & defMask) &&
             !(thisLIR->defMask & useMask) &&
             !(thisLIR->defMask & defMask) &&
             !(isLoad && storeVisited) &&
             !(isStore && loadVisited) &&
             !(isStore && storeVisited)) {
             *newLIR = *thisLIR;
             thisLIR->flags.isNop = true;
             return newLIR; /* move into delay slot succeeded */
         }

         loadVisited |= isLoad;
         storeVisited |= isStore;

         /* accumulate def/use constraints */
         useMask |= thisLIR->useMask;
         defMask |= thisLIR->defMask;
     }

     /* for unconditional branches try to copy the instruction at the
        branch target up into the delay slot and adjust the branch */
     if (branchLIR->opcode == kMipsB) {
         MipsLIR *targetLIR;
         for (targetLIR = (MipsLIR *) branchLIR->generic.target;
              targetLIR;
              targetLIR = NEXT_LIR(targetLIR)) {
             if (!targetLIR->flags.isNop &&
                 (!isPseudoOpCode(targetLIR->opcode) || /* can't pull predicted up */
                  targetLIR->opcode == kMipsPseudoChainingCellInvokePredicted))
                 break; /* try to get to next real op at branch target */
         }
         if (targetLIR && !isPseudoOpCode(targetLIR->opcode) &&
             !(EncodingMap[targetLIR->opcode].flags & IS_BRANCH)) {
             *newLIR = *targetLIR;
             branchLIR->generic.target = (LIR *) NEXT_LIR(targetLIR);
             return newLIR;
         }
     } else if (branchLIR->opcode >= kMipsBeq && branchLIR->opcode <= kMipsBne) {
         /* for conditional branches try to fill branch delay slot
            via speculative execution when safe */
         MipsLIR *targetLIR;
         for (targetLIR = (MipsLIR *) branchLIR->generic.target;
              targetLIR;
              targetLIR = NEXT_LIR(targetLIR)) {
             if (!targetLIR->flags.isNop && !isPseudoOpCode(targetLIR->opcode))
                 break; /* try to get to next real op at branch target */
         }

         MipsLIR *nextLIR;
         for (nextLIR = NEXT_LIR(branchLIR);
              nextLIR;
              nextLIR = NEXT_LIR(nextLIR)) {
             if (!nextLIR->flags.isNop && !isPseudoOpCode(nextLIR->opcode))
                 break; /* try to get to next real op for fall thru */
         }

         if (nextLIR && targetLIR) {
             int flags = EncodingMap[nextLIR->opcode].flags;
             int isLoad = flags & IS_LOAD;

             /* common branch and fall thru to normal chaining cells case */
             if (isLoad && nextLIR->opcode == targetLIR->opcode &&
                 nextLIR->operands[0] == targetLIR->operands[0] &&
                 nextLIR->operands[1] == targetLIR->operands[1] &&
                 nextLIR->operands[2] == targetLIR->operands[2]) {
                 *newLIR = *targetLIR;
                 branchLIR->generic.target = (LIR *) NEXT_LIR(targetLIR);
                 return newLIR;
             }

             /* try prefetching (maybe try speculating instructions along the
                trace like dalvik frame load which is common and may be safe) */
             int isStore = flags & IS_STORE;
             if (isLoad || isStore) {
                 newLIR->opcode = kMipsPref;
                 newLIR->operands[0] = isLoad ? 0 : 1;
                 newLIR->operands[1] = nextLIR->operands[1];
                 newLIR->operands[2] = nextLIR->operands[2];
                 newLIR->defMask = nextLIR->defMask;
                 newLIR->useMask = nextLIR->useMask;
                 return newLIR;
             }
         }
     }

     /* couldn't find a useful instruction to move into the delay slot */
     newLIR->opcode = kMipsNop;
     return newLIR;
 }

 /*
  * The branch delay slot has been ignored thus far.  This is the point where
  * a useful instruction is moved into it or a nop is inserted.  Leave existing
  * NOPs alone -- these came from sparse and packed switch ops and are needed
  * to maintain the proper offset to the jump table.
  */
 static void introduceBranchDelaySlot(CompilationUnit *cUnit)
 {
     MipsLIR *thisLIR;
     MipsLIR *firstLIR =(MipsLIR *) cUnit->firstLIRInsn;
     MipsLIR *lastLIR =(MipsLIR *) cUnit->lastLIRInsn;

     for (thisLIR = lastLIR; thisLIR != firstLIR; thisLIR = PREV_LIR(thisLIR)) {
         if (thisLIR->flags.isNop ||
             isPseudoOpCode(thisLIR->opcode) ||
             !(EncodingMap[thisLIR->opcode].flags & IS_BRANCH)) {
             continue;
         } else if (thisLIR == lastLIR) {
             dvmCompilerAppendLIR(cUnit,
                 (LIR *) delaySlotLIR(firstLIR, thisLIR));
         } else if (NEXT_LIR(thisLIR)->opcode != kMipsNop) {
             dvmCompilerInsertLIRAfter((LIR *) thisLIR,
                 (LIR *) delaySlotLIR(firstLIR, thisLIR));
         }
     }

     if (!thisLIR->flags.isNop &&
         !isPseudoOpCode(thisLIR->opcode) &&
         EncodingMap[thisLIR->opcode].flags & IS_BRANCH) {
         /* nothing available to move, so insert nop */
         MipsLIR *nopLIR = (MipsLIR *) dvmCompilerNew(sizeof(MipsLIR), true);
         nopLIR->opcode = kMipsNop;
         dvmCompilerInsertLIRAfter((LIR *) thisLIR, (LIR *) nopLIR);
     }
 }

 void dvmCompilerApplyGlobalOptimizations(CompilationUnit *cUnit)
 {
     applyRedundantBranchElimination(cUnit);
     applyCopyPropagation(cUnit);
 #ifdef __mips_hard_float
     mergeMovs(cUnit);
 #endif
     introduceBranchDelaySlot(cUnit);
 }
	/*
	* Copyright (C) 2009 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "Dalvik.h"
	#include "vm/compiler/CompilerInternals.h"
	#include "MipsLIR.h"

	/*
	* Identify unconditional branches that jump to the immediate successor of the
	* branch itself.
	*/
	static void applyRedundantBranchElimination(CompilationUnit *cUnit)
	{
	MipsLIR *thisLIR;

	for (thisLIR = (MipsLIR *) cUnit->firstLIRInsn;
	thisLIR != (MipsLIR *) cUnit->lastLIRInsn;
	thisLIR = NEXT_LIR(thisLIR)) {

	/* Branch to the next instruction */
	if (!thisLIR->flags.isNop && thisLIR->opcode == kMipsB) {
	MipsLIR *nextLIR = thisLIR;

	while (true) {
	nextLIR = NEXT_LIR(nextLIR);

	/*
	* Is the branch target the next instruction?
	*/
	if (nextLIR == (MipsLIR *) thisLIR->generic.target) {
	thisLIR->flags.isNop = true;
	break;
	}

	/*
	* Found real useful stuff between the branch and the target.
	* Need to explicitly check the lastLIRInsn here since with
	* method-based JIT the branch might be the last real
	* instruction.
	*/
	if (!isPseudoOpCode(nextLIR->opcode) \|\|
	(nextLIR = (MipsLIR *) cUnit->lastLIRInsn))
	break;
	}
	}
	}
	}

	/*
	* Do simple a form of copy propagation and elimination.
	*/
	static void applyCopyPropagation(CompilationUnit *cUnit)
	{
	MipsLIR *thisLIR;

	/* look for copies to possibly eliminate */
	for (thisLIR = (MipsLIR *) cUnit->firstLIRInsn;
	thisLIR != (MipsLIR *) cUnit->lastLIRInsn;
	thisLIR = NEXT_LIR(thisLIR)) {

	if (thisLIR->flags.isNop \|\| thisLIR->opcode != kMipsMove)
	continue;

	const int max_insns = 10;
	MipsLIR *savedLIR[max_insns];
	int srcRedefined = 0;
	int insnCount = 0;
	MipsLIR *nextLIR;

	/* look for and record all uses of reg defined by the copy */
	for (nextLIR = (MipsLIR *) NEXT_LIR(thisLIR);
	nextLIR != (MipsLIR *) cUnit->lastLIRInsn;
	nextLIR = NEXT_LIR(nextLIR)) {

	if (nextLIR->flags.isNop \|\| nextLIR->opcode == kMips32BitData)
	continue;

	if (isPseudoOpCode(nextLIR->opcode)) {
	if (nextLIR->opcode == kMipsPseudoDalvikByteCodeBoundary \|\|
	nextLIR->opcode == kMipsPseudoBarrier \|\|
	nextLIR->opcode == kMipsPseudoExtended \|\|
	nextLIR->opcode == kMipsPseudoSSARep)
	continue; /* these pseudos don't pose problems */
	else if (nextLIR->opcode == kMipsPseudoTargetLabel \|\|
	nextLIR->opcode == kMipsPseudoEntryBlock \|\|
	nextLIR->opcode == kMipsPseudoExitBlock)
	insnCount = 0; /* give up for these pseudos */
	break; /* reached end for copy propagation */
	}

	/* Since instructions with IS_BRANCH flag set will have its */
	/* useMask and defMask set to ENCODE_ALL, any checking of */
	/* these flags must come after the branching checks. */

	/* don't propagate across branch/jump and link case
	or jump via register */
	if (EncodingMap[nextLIR->opcode].flags & REG_DEF_LR \|\|
	nextLIR->opcode == kMipsJalr \|\|
	nextLIR->opcode == kMipsJr) {
	insnCount = 0;
	break;
	}

	/* branches with certain targets ok while others aren't */
	if (EncodingMap[nextLIR->opcode].flags & IS_BRANCH) {
	MipsLIR targetLIR = (MipsLIR ) nextLIR->generic.target;
	if (targetLIR->opcode != kMipsPseudoEHBlockLabel &&
	targetLIR->opcode != kMipsPseudoChainingCellHot &&
	targetLIR->opcode != kMipsPseudoChainingCellNormal &&
	targetLIR->opcode != kMipsPseudoChainingCellInvokePredicted &&
	targetLIR->opcode != kMipsPseudoChainingCellInvokeSingleton &&
	targetLIR->opcode != kMipsPseudoPCReconstructionBlockLabel &&
	targetLIR->opcode != kMipsPseudoPCReconstructionCell) {
	insnCount = 0;
	break;
	}
	/* FIXME - for now don't propagate across any branch/jump. */
	insnCount = 0;
	break;
	}

	/* copy def reg used here, so record insn for copy propagation */
	if (thisLIR->defMask & nextLIR->useMask) {
	if (insnCount == max_insns \|\| srcRedefined) {
	insnCount = 0;
	break; /* just give up if too many or not possible */
	}
	savedLIR[insnCount++] = nextLIR;
	}

	if (thisLIR->defMask & nextLIR->defMask) {
	if (nextLIR->opcode == kMipsMovz)
	insnCount = 0; /* movz relies on thisLIR setting dst reg so abandon propagation*/
	break;
	}

	/* copy src reg redefined here, so can't propagate further */
	if (thisLIR->useMask & nextLIR->defMask) {
	if (insnCount == 0)
	break; /* nothing to propagate */
	srcRedefined = 1;
	}
	}

	/* conditions allow propagation and copy elimination */
	if (insnCount) {
	int i;
	for (i = 0; i < insnCount; i++) {
	int flags = EncodingMap[savedLIR[i]->opcode].flags;
	savedLIR[i]->useMask &= ~(1 << thisLIR->operands[0]);
	savedLIR[i]->useMask \|= 1 << thisLIR->operands[1];
	if ((flags & REG_USE0) &&
	savedLIR[i]->operands[0] == thisLIR->operands[0])
	savedLIR[i]->operands[0] = thisLIR->operands[1];
	if ((flags & REG_USE1) &&
	savedLIR[i]->operands[1] == thisLIR->operands[0])
	savedLIR[i]->operands[1] = thisLIR->operands[1];
	if ((flags & REG_USE2) &&
	savedLIR[i]->operands[2] == thisLIR->operands[0])
	savedLIR[i]->operands[2] = thisLIR->operands[1];
	if ((flags & REG_USE3) &&
	savedLIR[i]->operands[3] == thisLIR->operands[0])
	savedLIR[i]->operands[3] = thisLIR->operands[1];
	}
	thisLIR->flags.isNop = true;
	}
	}
	}

	#ifdef __mips_hard_float
	/*
	* Look for pairs of mov.s instructions that can be combined into mov.d
	*/
	static void mergeMovs(CompilationUnit *cUnit)
	{
	MipsLIR *movsLIR = NULL;
	MipsLIR *thisLIR;

	for (thisLIR = (MipsLIR *) cUnit->firstLIRInsn;
	thisLIR != (MipsLIR *) cUnit->lastLIRInsn;
	thisLIR = NEXT_LIR(thisLIR)) {
	if (thisLIR->flags.isNop)
	continue;

	if (isPseudoOpCode(thisLIR->opcode)) {
	if (thisLIR->opcode == kMipsPseudoDalvikByteCodeBoundary \|\|
	thisLIR->opcode == kMipsPseudoExtended \|\|
	thisLIR->opcode == kMipsPseudoSSARep)
	continue; /* ok to move across these pseudos */
	movsLIR = NULL; /* don't merge across other pseudos */
	continue;
	}

	/* merge pairs of mov.s instructions */
	if (thisLIR->opcode == kMipsFmovs) {
	if (movsLIR == NULL)
	movsLIR = thisLIR;
	else if (((movsLIR->operands[0] & 1) == 0) &&
	((movsLIR->operands[1] & 1) == 0) &&
	((movsLIR->operands[0] + 1) == thisLIR->operands[0]) &&
	((movsLIR->operands[1] + 1) == thisLIR->operands[1])) {
	/* movsLIR is handling even register - upgrade to mov.d */
	movsLIR->opcode = kMipsFmovd;
	movsLIR->operands[0] = S2D(movsLIR->operands[0], movsLIR->operands[0]+1);
	movsLIR->operands[1] = S2D(movsLIR->operands[1], movsLIR->operands[1]+1);
	thisLIR->flags.isNop = true;
	movsLIR = NULL;
	}
	else if (((movsLIR->operands[0] & 1) == 1) &&
	((movsLIR->operands[1] & 1) == 1) &&
	((movsLIR->operands[0] - 1) == thisLIR->operands[0]) &&
	((movsLIR->operands[1] - 1) == thisLIR->operands[1])) {
	/* thissLIR is handling even register - upgrade to mov.d */
	thisLIR->opcode = kMipsFmovd;
	thisLIR->operands[0] = S2D(thisLIR->operands[0], thisLIR->operands[0]+1);
	thisLIR->operands[1] = S2D(thisLIR->operands[1], thisLIR->operands[1]+1);
	movsLIR->flags.isNop = true;
	movsLIR = NULL;
	}
	else
	/* carry on searching from here */
	movsLIR = thisLIR;
	continue;
	}

	/* intervening instruction - start search from scratch */
	movsLIR = NULL;
	}
	}
	#endif


	/*
	* Look back first and then ahead to try to find an instruction to move into
	* the branch delay slot. If the analysis can be done cheaply enough, it may be
	* be possible to tune this routine to be more beneficial (e.g., being more
	* particular about what instruction is speculated).
	*/
	static MipsLIR delaySlotLIR(MipsLIR firstLIR, MipsLIR *branchLIR)
	{
	int isLoad;
	int loadVisited = 0;
	int isStore;
	int storeVisited = 0;
	u8 useMask = branchLIR->useMask;
	u8 defMask = branchLIR->defMask;
	MipsLIR *thisLIR;
	MipsLIR newLIR = (MipsLIR ) dvmCompilerNew(sizeof(MipsLIR), true);

	for (thisLIR = PREV_LIR(branchLIR);
	thisLIR != firstLIR;
	thisLIR = PREV_LIR(thisLIR)) {
	if (thisLIR->flags.isNop)
	continue;

	if (isPseudoOpCode(thisLIR->opcode)) {
	if (thisLIR->opcode == kMipsPseudoDalvikByteCodeBoundary \|\|
	thisLIR->opcode == kMipsPseudoExtended \|\|
	thisLIR->opcode == kMipsPseudoSSARep)
	continue; /* ok to move across these pseudos */
	break; /* don't move across all other pseudos */
	}

	/* give up on moving previous instruction down into slot */
	if (thisLIR->opcode == kMipsNop \|\|
	thisLIR->opcode == kMips32BitData \|\|
	EncodingMap[thisLIR->opcode].flags & IS_BRANCH)
	break;

	/* don't reorder loads/stores (the alias info could
	possibly be used to allow as a future enhancement) */
	isLoad = EncodingMap[thisLIR->opcode].flags & IS_LOAD;
	isStore = EncodingMap[thisLIR->opcode].flags & IS_STORE;

	if (!(thisLIR->useMask & defMask) &&
	!(thisLIR->defMask & useMask) &&
	!(thisLIR->defMask & defMask) &&
	!(isLoad && storeVisited) &&
	!(isStore && loadVisited) &&
	!(isStore && storeVisited)) {
	newLIR = thisLIR;
	thisLIR->flags.isNop = true;
	return newLIR; /* move into delay slot succeeded */
	}

	loadVisited \|= isLoad;
	storeVisited \|= isStore;

	/* accumulate def/use constraints */
	useMask \|= thisLIR->useMask;
	defMask \|= thisLIR->defMask;
	}

	/* for unconditional branches try to copy the instruction at the
	branch target up into the delay slot and adjust the branch */
	if (branchLIR->opcode == kMipsB) {
	MipsLIR *targetLIR;
	for (targetLIR = (MipsLIR *) branchLIR->generic.target;
	targetLIR;
	targetLIR = NEXT_LIR(targetLIR)) {
	if (!targetLIR->flags.isNop &&
	(!isPseudoOpCode(targetLIR->opcode) \|\| /* can't pull predicted up */
	targetLIR->opcode == kMipsPseudoChainingCellInvokePredicted))
	break; /* try to get to next real op at branch target */
	}
	if (targetLIR && !isPseudoOpCode(targetLIR->opcode) &&
	!(EncodingMap[targetLIR->opcode].flags & IS_BRANCH)) {
	newLIR = targetLIR;
	branchLIR->generic.target = (LIR *) NEXT_LIR(targetLIR);
	return newLIR;
	}
	} else if (branchLIR->opcode >= kMipsBeq && branchLIR->opcode <= kMipsBne) {
	/* for conditional branches try to fill branch delay slot
	via speculative execution when safe */
	MipsLIR *targetLIR;
	for (targetLIR = (MipsLIR *) branchLIR->generic.target;
	targetLIR;
	targetLIR = NEXT_LIR(targetLIR)) {
	if (!targetLIR->flags.isNop && !isPseudoOpCode(targetLIR->opcode))
	break; /* try to get to next real op at branch target */
	}

	MipsLIR *nextLIR;
	for (nextLIR = NEXT_LIR(branchLIR);
	nextLIR;
	nextLIR = NEXT_LIR(nextLIR)) {
	if (!nextLIR->flags.isNop && !isPseudoOpCode(nextLIR->opcode))
	break; /* try to get to next real op for fall thru */
	}

	if (nextLIR && targetLIR) {
	int flags = EncodingMap[nextLIR->opcode].flags;
	int isLoad = flags & IS_LOAD;

	/* common branch and fall thru to normal chaining cells case */
	if (isLoad && nextLIR->opcode == targetLIR->opcode &&
	nextLIR->operands[0] == targetLIR->operands[0] &&
	nextLIR->operands[1] == targetLIR->operands[1] &&
	nextLIR->operands[2] == targetLIR->operands[2]) {
	newLIR = targetLIR;
	branchLIR->generic.target = (LIR *) NEXT_LIR(targetLIR);
	return newLIR;
	}

	/* try prefetching (maybe try speculating instructions along the
	trace like dalvik frame load which is common and may be safe) */
	int isStore = flags & IS_STORE;
	if (isLoad \|\| isStore) {
	newLIR->opcode = kMipsPref;
	newLIR->operands[0] = isLoad ? 0 : 1;
	newLIR->operands[1] = nextLIR->operands[1];
	newLIR->operands[2] = nextLIR->operands[2];
	newLIR->defMask = nextLIR->defMask;
	newLIR->useMask = nextLIR->useMask;
	return newLIR;
	}
	}
	}

	/* couldn't find a useful instruction to move into the delay slot */
	newLIR->opcode = kMipsNop;
	return newLIR;
	}

	/*
	* The branch delay slot has been ignored thus far. This is the point where
	* a useful instruction is moved into it or a nop is inserted. Leave existing
	* NOPs alone -- these came from sparse and packed switch ops and are needed
	* to maintain the proper offset to the jump table.
	*/
	static void introduceBranchDelaySlot(CompilationUnit *cUnit)
	{
	MipsLIR *thisLIR;
	MipsLIR firstLIR =(MipsLIR ) cUnit->firstLIRInsn;
	MipsLIR lastLIR =(MipsLIR ) cUnit->lastLIRInsn;

	for (thisLIR = lastLIR; thisLIR != firstLIR; thisLIR = PREV_LIR(thisLIR)) {
	if (thisLIR->flags.isNop \|\|
	isPseudoOpCode(thisLIR->opcode) \|\|
	!(EncodingMap[thisLIR->opcode].flags & IS_BRANCH)) {
	continue;
	} else if (thisLIR == lastLIR) {
	dvmCompilerAppendLIR(cUnit,
	(LIR *) delaySlotLIR(firstLIR, thisLIR));
	} else if (NEXT_LIR(thisLIR)->opcode != kMipsNop) {
	dvmCompilerInsertLIRAfter((LIR *) thisLIR,
	(LIR *) delaySlotLIR(firstLIR, thisLIR));
	}
	}

	if (!thisLIR->flags.isNop &&
	!isPseudoOpCode(thisLIR->opcode) &&
	EncodingMap[thisLIR->opcode].flags & IS_BRANCH) {
	/* nothing available to move, so insert nop */
	MipsLIR nopLIR = (MipsLIR ) dvmCompilerNew(sizeof(MipsLIR), true);
	nopLIR->opcode = kMipsNop;
	dvmCompilerInsertLIRAfter((LIR ) thisLIR, (LIR ) nopLIR);
	}
	}

	void dvmCompilerApplyGlobalOptimizations(CompilationUnit *cUnit)
	{
	applyRedundantBranchElimination(cUnit);
	applyCopyPropagation(cUnit);
	#ifdef __mips_hard_float
	mergeMovs(cUnit);
	#endif
	introduceBranchDelaySlot(cUnit);
	}