-/// OptimizeNoopCopyExpression - We have determined that the specified cast
-/// instruction is a noop copy (e.g. it's casting from one pointer type to
-/// another, int->uint, or int->sbyte on PPC.
-///
-/// Return true if any changes are made.
-static bool OptimizeNoopCopyExpression(CastInst *CI) {
- BasicBlock *DefBB = CI->getParent();
-
- /// InsertedCasts - Only insert a cast in each block once.
- std::map<BasicBlock*, CastInst*> InsertedCasts;
-
- bool MadeChange = false;
- for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
- UI != E; ) {
- Use &TheUse = UI.getUse();
- Instruction *User = cast<Instruction>(*UI);
-
- // Figure out which BB this cast is used in. For PHI's this is the
- // appropriate predecessor block.
- BasicBlock *UserBB = User->getParent();
- if (PHINode *PN = dyn_cast<PHINode>(User)) {
- unsigned OpVal = UI.getOperandNo()/2;
- UserBB = PN->getIncomingBlock(OpVal);
- }
-
- // Preincrement use iterator so we don't invalidate it.
- ++UI;
-
- // If this user is in the same block as the cast, don't change the cast.
- if (UserBB == DefBB) continue;
-
- // If we have already inserted a cast into this block, use it.
- CastInst *&InsertedCast = InsertedCasts[UserBB];
-
- if (!InsertedCast) {
- BasicBlock::iterator InsertPt = UserBB->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
-
- InsertedCast =
- CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
- InsertPt);
- MadeChange = true;
- }
-
- // Replace a use of the cast with a use of the new casat.
- TheUse = InsertedCast;
- }
-
- // If we removed all uses, nuke the cast.
- if (CI->use_empty())
- CI->eraseFromParent();
-
- return MadeChange;
-}
-
-/// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset,
-/// casting to the type of GEPI.
-static Instruction *InsertGEPComputeCode(Instruction *&V, BasicBlock *BB,
- Instruction *GEPI, Value *Ptr,
- Value *PtrOffset) {
- if (V) return V; // Already computed.
-
- // Figure out the insertion point
- BasicBlock::iterator InsertPt;
- if (BB == GEPI->getParent()) {
- // If GEP is already inserted into BB, insert right after the GEP.
- InsertPt = GEPI;
- ++InsertPt;
- } else {
- // Otherwise, insert at the top of BB, after any PHI nodes
- InsertPt = BB->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
- }
-
- // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into
- // BB so that there is only one value live across basic blocks (the cast
- // operand).
- if (CastInst *CI = dyn_cast<CastInst>(Ptr))
- if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType()))
- Ptr = CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(),
- "", InsertPt);
-
- // Add the offset, cast it to the right type.
- Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt);
- // Ptr is an integer type, GEPI is pointer type ==> IntToPtr
- return V = CastInst::create(Instruction::IntToPtr, Ptr, GEPI->getType(),
- "", InsertPt);
-}
-
-/// ReplaceUsesOfGEPInst - Replace all uses of RepPtr with inserted code to
-/// compute its value. The RepPtr value can be computed with Ptr+PtrOffset. One
-/// trivial way of doing this would be to evaluate Ptr+PtrOffset in RepPtr's
-/// block, then ReplaceAllUsesWith'ing everything. However, we would prefer to
-/// sink PtrOffset into user blocks where doing so will likely allow us to fold
-/// the constant add into a load or store instruction. Additionally, if a user
-/// is a pointer-pointer cast, we look through it to find its users.
-static void ReplaceUsesOfGEPInst(Instruction *RepPtr, Value *Ptr,
- Constant *PtrOffset, BasicBlock *DefBB,
- GetElementPtrInst *GEPI,
- std::map<BasicBlock*,Instruction*> &InsertedExprs) {
- while (!RepPtr->use_empty()) {
- Instruction *User = cast<Instruction>(RepPtr->use_back());
-
- // If the user is a Pointer-Pointer cast, recurse. Only BitCast can be
- // used for a Pointer-Pointer cast.
- if (isa<BitCastInst>(User)) {
- ReplaceUsesOfGEPInst(User, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs);
-
- // Drop the use of RepPtr. The cast is dead. Don't delete it now, else we
- // could invalidate an iterator.
- User->setOperand(0, UndefValue::get(RepPtr->getType()));
- continue;
- }
-
- // If this is a load of the pointer, or a store through the pointer, emit
- // the increment into the load/store block.
- Instruction *NewVal;
- if (isa<LoadInst>(User) ||
- (isa<StoreInst>(User) && User->getOperand(0) != RepPtr)) {
- NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()],
- User->getParent(), GEPI,
- Ptr, PtrOffset);
- } else {
- // If this use is not foldable into the addressing mode, use a version
- // emitted in the GEP block.
- NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI,
- Ptr, PtrOffset);
- }
-
- if (GEPI->getType() != RepPtr->getType()) {
- BasicBlock::iterator IP = NewVal;
- ++IP;
- // NewVal must be a GEP which must be pointer type, so BitCast
- NewVal = new BitCastInst(NewVal, RepPtr->getType(), "", IP);
- }
- User->replaceUsesOfWith(RepPtr, NewVal);
- }
-}
-
-
-/// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction
-/// selection, we want to be a bit careful about some things. In particular, if
-/// we have a GEP instruction that is used in a different block than it is
-/// defined, the addressing expression of the GEP cannot be folded into loads or
-/// stores that use it. In this case, decompose the GEP and move constant
-/// indices into blocks that use it.
-static bool OptimizeGEPExpression(GetElementPtrInst *GEPI,
- const TargetData *TD) {
- // If this GEP is only used inside the block it is defined in, there is no
- // need to rewrite it.
- bool isUsedOutsideDefBB = false;
- BasicBlock *DefBB = GEPI->getParent();
- for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end();
- UI != E; ++UI) {
- if (cast<Instruction>(*UI)->getParent() != DefBB) {
- isUsedOutsideDefBB = true;
- break;
- }
- }
- if (!isUsedOutsideDefBB) return false;
-
- // If this GEP has no non-zero constant indices, there is nothing we can do,
- // ignore it.
- bool hasConstantIndex = false;
- bool hasVariableIndex = false;
- for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
- E = GEPI->op_end(); OI != E; ++OI) {
- if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) {
- if (CI->getZExtValue()) {
- hasConstantIndex = true;
- break;
- }
- } else {
- hasVariableIndex = true;
- }
- }
-
- // If this is a "GEP X, 0, 0, 0", turn this into a cast.
- if (!hasConstantIndex && !hasVariableIndex) {
- /// The GEP operand must be a pointer, so must its result -> BitCast
- Value *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
- GEPI->getName(), GEPI);
- GEPI->replaceAllUsesWith(NC);
- GEPI->eraseFromParent();
- return true;
- }
-
- // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses.
- if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0)))
- return false;
-
- // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the
- // constant offset (which we now know is non-zero) and deal with it later.
- uint64_t ConstantOffset = 0;
- const Type *UIntPtrTy = TD->getIntPtrType();
- Value *Ptr = new PtrToIntInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI);
- const Type *Ty = GEPI->getOperand(0)->getType();
-
- for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
- E = GEPI->op_end(); OI != E; ++OI) {
- Value *Idx = *OI;
- if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
- unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
- if (Field)
- ConstantOffset += TD->getStructLayout(StTy)->getElementOffset(Field);
- Ty = StTy->getElementType(Field);
- } else {
- Ty = cast<SequentialType>(Ty)->getElementType();
-
- // Handle constant subscripts.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
- if (CI->getZExtValue() == 0) continue;
- ConstantOffset += (int64_t)TD->getTypeSize(Ty)*CI->getSExtValue();
- continue;
- }
-
- // Ptr = Ptr + Idx * ElementSize;
-
- // Cast Idx to UIntPtrTy if needed.
- Idx = CastInst::createIntegerCast(Idx, UIntPtrTy, true/*SExt*/, "", GEPI);
-
- uint64_t ElementSize = TD->getTypeSize(Ty);
- // Mask off bits that should not be set.
- ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
- Constant *SizeCst = ConstantInt::get(UIntPtrTy, ElementSize);
-
- // Multiply by the element size and add to the base.
- Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI);
- Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI);
- }
- }
-
- // Make sure that the offset fits in uintptr_t.
- ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
- Constant *PtrOffset = ConstantInt::get(UIntPtrTy, ConstantOffset);
-
- // Okay, we have now emitted all of the variable index parts to the BB that
- // the GEP is defined in. Loop over all of the using instructions, inserting
- // an "add Ptr, ConstantOffset" into each block that uses it and update the
- // instruction to use the newly computed value, making GEPI dead. When the
- // user is a load or store instruction address, we emit the add into the user
- // block, otherwise we use a canonical version right next to the gep (these
- // won't be foldable as addresses, so we might as well share the computation).
-
- std::map<BasicBlock*,Instruction*> InsertedExprs;
- ReplaceUsesOfGEPInst(GEPI, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs);
-
- // Finally, the GEP is dead, remove it.
- GEPI->eraseFromParent();
-
- return true;
-}
-
-
-/// SplitEdgeNicely - Split the critical edge from TI to it's specified
-/// successor if it will improve codegen. We only do this if the successor has
-/// phi nodes (otherwise critical edges are ok). If there is already another
-/// predecessor of the succ that is empty (and thus has no phi nodes), use it
-/// instead of introducing a new block.
-static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) {
- BasicBlock *TIBB = TI->getParent();
- BasicBlock *Dest = TI->getSuccessor(SuccNum);
- assert(isa<PHINode>(Dest->begin()) &&
- "This should only be called if Dest has a PHI!");
-
- /// TIPHIValues - This array is lazily computed to determine the values of
- /// PHIs in Dest that TI would provide.
- std::vector<Value*> TIPHIValues;
-
- // Check to see if Dest has any blocks that can be used as a split edge for
- // this terminator.
- for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) {
- BasicBlock *Pred = *PI;
- // To be usable, the pred has to end with an uncond branch to the dest.
- BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator());
- if (!PredBr || !PredBr->isUnconditional() ||
- // Must be empty other than the branch.
- &Pred->front() != PredBr)
- continue;
-
- // Finally, since we know that Dest has phi nodes in it, we have to make
- // sure that jumping to Pred will have the same affect as going to Dest in
- // terms of PHI values.
- PHINode *PN;
- unsigned PHINo = 0;
- bool FoundMatch = true;
- for (BasicBlock::iterator I = Dest->begin();
- (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) {
- if (PHINo == TIPHIValues.size())
- TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB));
-
- // If the PHI entry doesn't work, we can't use this pred.
- if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) {
- FoundMatch = false;
- break;
- }
- }
-
- // If we found a workable predecessor, change TI to branch to Succ.
- if (FoundMatch) {
- Dest->removePredecessor(TIBB);
- TI->setSuccessor(SuccNum, Pred);
- return;
- }
- }
-
- SplitCriticalEdge(TI, SuccNum, P, true);
-}
-