lib/Transforms/Utils/Local.cpp

   1 //===-- Local.cpp - Functions to perform local transformations ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This family of functions perform various local transformations to the
  11 // program.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/Local.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Intrinsics.h"
  20 #include "llvm/IntrinsicInst.h"
  21 #include "llvm/Analysis/ConstantFolding.h"
  22 #include "llvm/Target/TargetData.h"
  23 #include "llvm/Support/GetElementPtrTypeIterator.h"
  24 #include "llvm/Support/MathExtras.h"
  25 using namespace llvm;
  26
  27 //===----------------------------------------------------------------------===//
  28 //  Local constant propagation.
  29 //
  30
  31 // ConstantFoldTerminator - If a terminator instruction is predicated on a
  32 // constant value, convert it into an unconditional branch to the constant
  33 // destination.
  34 //
  35 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
  36   TerminatorInst *T = BB->getTerminator();
  37
  38   // Branch - See if we are conditional jumping on constant
  39   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
  40     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
  41     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
  42     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
  43
  44     if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
  45       // Are we branching on constant?
  46       // YES.  Change to unconditional branch...
  47       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
  48       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
  49
  50       //cerr << "Function: " << T->getParent()->getParent()
  51       //     << "\nRemoving branch from " << T->getParent()
  52       //     << "\n\nTo: " << OldDest << endl;
  53
  54       // Let the basic block know that we are letting go of it.  Based on this,
  55       // it will adjust it's PHI nodes.
  56       assert(BI->getParent() && "Terminator not inserted in block!");
  57       OldDest->removePredecessor(BI->getParent());
  58
  59       // Set the unconditional destination, and change the insn to be an
  60       // unconditional branch.
  61       BI->setUnconditionalDest(Destination);
  62       return true;
  63     } else if (Dest2 == Dest1) {       // Conditional branch to same location?
  64       // This branch matches something like this:
  65       //     br bool %cond, label %Dest, label %Dest
  66       // and changes it into:  br label %Dest
  67
  68       // Let the basic block know that we are letting go of one copy of it.
  69       assert(BI->getParent() && "Terminator not inserted in block!");
  70       Dest1->removePredecessor(BI->getParent());
  71
  72       // Change a conditional branch to unconditional.
  73       BI->setUnconditionalDest(Dest1);
  74       return true;
  75     }
  76   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
  77     // If we are switching on a constant, we can convert the switch into a
  78     // single branch instruction!
  79     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
  80     BasicBlock *TheOnlyDest = SI->getSuccessor(0);  // The default dest
  81     BasicBlock *DefaultDest = TheOnlyDest;
  82     assert(TheOnlyDest == SI->getDefaultDest() &&
  83            "Default destination is not successor #0?");
  84
  85     // Figure out which case it goes to...
  86     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
  87       // Found case matching a constant operand?
  88       if (SI->getSuccessorValue(i) == CI) {
  89         TheOnlyDest = SI->getSuccessor(i);
  90         break;
  91       }
  92
  93       // Check to see if this branch is going to the same place as the default
  94       // dest.  If so, eliminate it as an explicit compare.
  95       if (SI->getSuccessor(i) == DefaultDest) {
  96         // Remove this entry...
  97         DefaultDest->removePredecessor(SI->getParent());
  98         SI->removeCase(i);
  99         --i; --e;  // Don't skip an entry...
 100         continue;
 101       }
 102
 103       // Otherwise, check to see if the switch only branches to one destination.
 104       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
 105       // destinations.
 106       if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
 107     }
 108
 109     if (CI && !TheOnlyDest) {
 110       // Branching on a constant, but not any of the cases, go to the default
 111       // successor.
 112       TheOnlyDest = SI->getDefaultDest();
 113     }
 114
 115     // If we found a single destination that we can fold the switch into, do so
 116     // now.
 117     if (TheOnlyDest) {
 118       // Insert the new branch..
 119       BranchInst::Create(TheOnlyDest, SI);
 120       BasicBlock *BB = SI->getParent();
 121
 122       // Remove entries from PHI nodes which we no longer branch to...
 123       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
 124         // Found case matching a constant operand?
 125         BasicBlock *Succ = SI->getSuccessor(i);
 126         if (Succ == TheOnlyDest)
 127           TheOnlyDest = 0;  // Don't modify the first branch to TheOnlyDest
 128         else
 129           Succ->removePredecessor(BB);
 130       }
 131
 132       // Delete the old switch...
 133       BB->getInstList().erase(SI);
 134       return true;
 135     } else if (SI->getNumSuccessors() == 2) {
 136       // Otherwise, we can fold this switch into a conditional branch
 137       // instruction if it has only one non-default destination.
 138       Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(),
 139                                  SI->getSuccessorValue(1), "cond", SI);
 140       // Insert the new branch...
 141       BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
 142
 143       // Delete the old switch...
 144       SI->eraseFromParent();
 145       return true;
 146     }
 147   }
 148   return false;
 149 }
 150
 151
 152 //===----------------------------------------------------------------------===//
 153 //  Local dead code elimination...
 154 //
 155
 156 /// isInstructionTriviallyDead - Return true if the result produced by the
 157 /// instruction is not used, and the instruction has no side effects.
 158 ///
 159 bool llvm::isInstructionTriviallyDead(Instruction *I) {
 160   if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
 161
 162   if (!I->mayWriteToMemory())
 163     return true;
 164
 165   // Special case intrinsics that "may write to memory" but can be deleted when
 166   // dead.
 167   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
 168     // Safe to delete llvm.stacksave if dead.
 169     if (II->getIntrinsicID() == Intrinsic::stacksave)
 170       return true;
 171
 172   return false;
 173 }
 174
 175 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 176 /// trivially dead instruction, delete it.  If that makes any of its operands
 177 /// trivially dead, delete them too, recursively.
 178 ///
 179 /// If DeadInst is specified, the vector is filled with the instructions that
 180 /// are actually deleted.
 181 void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
 182                                       SmallVectorImpl<Instruction*> *DeadInst) {
 183   Instruction *I = dyn_cast<Instruction>(V);
 184   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I))
 185     return;
 186
 187   SmallVector<Instruction*, 16> DeadInsts;
 188   DeadInsts.push_back(I);
 189
 190   while (!DeadInsts.empty()) {
 191     I = DeadInsts.back();
 192     DeadInsts.pop_back();
 193
 194     // If the client wanted to know, tell it about deleted instructions.
 195     if (DeadInst)
 196       DeadInst->push_back(I);
 197
 198     // Null out all of the instruction's operands to see if any operand becomes
 199     // dead as we go.
 200     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 201       Value *OpV = I->getOperand(i);
 202       I->setOperand(i, 0);
 203
 204       if (!OpV->use_empty()) continue;
 205
 206       // If the operand is an instruction that became dead as we nulled out the
 207       // operand, and if it is 'trivially' dead, delete it in a future loop
 208       // iteration.
 209       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
 210         if (isInstructionTriviallyDead(OpI))
 211           DeadInsts.push_back(OpI);
 212     }
 213
 214     I->eraseFromParent();
 215   }
 216 }
 217
 218
 219 //===----------------------------------------------------------------------===//
 220 //  Control Flow Graph Restructuring...
 221 //
 222
 223 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 224 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 225 /// between them, moving the instructions in the predecessor into DestBB and
 226 /// deleting the predecessor block.
 227 ///
 228 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB) {
 229   // If BB has single-entry PHI nodes, fold them.
 230   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
 231     Value *NewVal = PN->getIncomingValue(0);
 232     // Replace self referencing PHI with undef, it must be dead.
 233     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
 234     PN->replaceAllUsesWith(NewVal);
 235     PN->eraseFromParent();
 236   }
 237
 238   BasicBlock *PredBB = DestBB->getSinglePredecessor();
 239   assert(PredBB && "Block doesn't have a single predecessor!");
 240
 241   // Splice all the instructions from PredBB to DestBB.
 242   PredBB->getTerminator()->eraseFromParent();
 243   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
 244
 245   // Anything that branched to PredBB now branches to DestBB.
 246   PredBB->replaceAllUsesWith(DestBB);
 247
 248   // Nuke BB.
 249   PredBB->eraseFromParent();
 250 }