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/GlobalVariable.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Intrinsics.h"
  21 #include "llvm/IntrinsicInst.h"
  22 #include "llvm/Analysis/ConstantFolding.h"
  23 #include "llvm/Analysis/DebugInfo.h"
  24 #include "llvm/Target/TargetData.h"
  25 #include "llvm/Support/GetElementPtrTypeIterator.h"
  26 #include "llvm/Support/MathExtras.h"
  27 using namespace llvm;
  28
  29 //===----------------------------------------------------------------------===//
  30 //  Local constant propagation.
  31 //
  32
  33 // ConstantFoldTerminator - If a terminator instruction is predicated on a
  34 // constant value, convert it into an unconditional branch to the constant
  35 // destination.
  36 //
  37 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
  38   TerminatorInst *T = BB->getTerminator();
  39
  40   // Branch - See if we are conditional jumping on constant
  41   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
  42     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
  43     BasicBlock *Dest1 = BI->getSuccessor(0);
  44     BasicBlock *Dest2 = BI->getSuccessor(1);
  45
  46     if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
  47       // Are we branching on constant?
  48       // YES.  Change to unconditional branch...
  49       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
  50       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
  51
  52       //cerr << "Function: " << T->getParent()->getParent()
  53       //     << "\nRemoving branch from " << T->getParent()
  54       //     << "\n\nTo: " << OldDest << endl;
  55
  56       // Let the basic block know that we are letting go of it.  Based on this,
  57       // it will adjust it's PHI nodes.
  58       assert(BI->getParent() && "Terminator not inserted in block!");
  59       OldDest->removePredecessor(BI->getParent());
  60
  61       // Set the unconditional destination, and change the insn to be an
  62       // unconditional branch.
  63       BI->setUnconditionalDest(Destination);
  64       return true;
  65     } else if (Dest2 == Dest1) {       // Conditional branch to same location?
  66       // This branch matches something like this:
  67       //     br bool %cond, label %Dest, label %Dest
  68       // and changes it into:  br label %Dest
  69
  70       // Let the basic block know that we are letting go of one copy of it.
  71       assert(BI->getParent() && "Terminator not inserted in block!");
  72       Dest1->removePredecessor(BI->getParent());
  73
  74       // Change a conditional branch to unconditional.
  75       BI->setUnconditionalDest(Dest1);
  76       return true;
  77     }
  78   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
  79     // If we are switching on a constant, we can convert the switch into a
  80     // single branch instruction!
  81     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
  82     BasicBlock *TheOnlyDest = SI->getSuccessor(0);  // The default dest
  83     BasicBlock *DefaultDest = TheOnlyDest;
  84     assert(TheOnlyDest == SI->getDefaultDest() &&
  85            "Default destination is not successor #0?");
  86
  87     // Figure out which case it goes to...
  88     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
  89       // Found case matching a constant operand?
  90       if (SI->getSuccessorValue(i) == CI) {
  91         TheOnlyDest = SI->getSuccessor(i);
  92         break;
  93       }
  94
  95       // Check to see if this branch is going to the same place as the default
  96       // dest.  If so, eliminate it as an explicit compare.
  97       if (SI->getSuccessor(i) == DefaultDest) {
  98         // Remove this entry...
  99         DefaultDest->removePredecessor(SI->getParent());
 100         SI->removeCase(i);
 101         --i; --e;  // Don't skip an entry...
 102         continue;
 103       }
 104
 105       // Otherwise, check to see if the switch only branches to one destination.
 106       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
 107       // destinations.
 108       if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
 109     }
 110
 111     if (CI && !TheOnlyDest) {
 112       // Branching on a constant, but not any of the cases, go to the default
 113       // successor.
 114       TheOnlyDest = SI->getDefaultDest();
 115     }
 116
 117     // If we found a single destination that we can fold the switch into, do so
 118     // now.
 119     if (TheOnlyDest) {
 120       // Insert the new branch..
 121       BranchInst::Create(TheOnlyDest, SI);
 122       BasicBlock *BB = SI->getParent();
 123
 124       // Remove entries from PHI nodes which we no longer branch to...
 125       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
 126         // Found case matching a constant operand?
 127         BasicBlock *Succ = SI->getSuccessor(i);
 128         if (Succ == TheOnlyDest)
 129           TheOnlyDest = 0;  // Don't modify the first branch to TheOnlyDest
 130         else
 131           Succ->removePredecessor(BB);
 132       }
 133
 134       // Delete the old switch...
 135       BB->getInstList().erase(SI);
 136       return true;
 137     } else if (SI->getNumSuccessors() == 2) {
 138       // Otherwise, we can fold this switch into a conditional branch
 139       // instruction if it has only one non-default destination.
 140       Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(),
 141                                  SI->getSuccessorValue(1), "cond", SI);
 142       // Insert the new branch...
 143       BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
 144
 145       // Delete the old switch...
 146       SI->eraseFromParent();
 147       return true;
 148     }
 149   }
 150   return false;
 151 }
 152
 153
 154 //===----------------------------------------------------------------------===//
 155 //  Local dead code elimination...
 156 //
 157
 158 /// isInstructionTriviallyDead - Return true if the result produced by the
 159 /// instruction is not used, and the instruction has no side effects.
 160 ///
 161 bool llvm::isInstructionTriviallyDead(Instruction *I) {
 162   if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
 163
 164   // We don't want debug info removed by anything this general.
 165   if (isa<DbgInfoIntrinsic>(I)) return false;
 166
 167   if (!I->mayWriteToMemory())
 168     return true;
 169
 170   // Special case intrinsics that "may write to memory" but can be deleted when
 171   // dead.
 172   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
 173     // Safe to delete llvm.stacksave if dead.
 174     if (II->getIntrinsicID() == Intrinsic::stacksave)
 175       return true;
 176
 177   return false;
 178 }
 179
 180 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 181 /// trivially dead instruction, delete it.  If that makes any of its operands
 182 /// trivially dead, delete them too, recursively.
 183 ///
 184 /// If DeadInst is specified, the vector is filled with the instructions that
 185 /// are actually deleted.
 186 void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
 187                                       SmallVectorImpl<Instruction*> *DeadInst) {
 188   Instruction *I = dyn_cast<Instruction>(V);
 189   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I))
 190     return;
 191
 192   SmallVector<Instruction*, 16> DeadInsts;
 193   DeadInsts.push_back(I);
 194
 195   while (!DeadInsts.empty()) {
 196     I = DeadInsts.back();
 197     DeadInsts.pop_back();
 198
 199     // If the client wanted to know, tell it about deleted instructions.
 200     if (DeadInst)
 201       DeadInst->push_back(I);
 202
 203     // Null out all of the instruction's operands to see if any operand becomes
 204     // dead as we go.
 205     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 206       Value *OpV = I->getOperand(i);
 207       I->setOperand(i, 0);
 208
 209       if (!OpV->use_empty()) continue;
 210
 211       // If the operand is an instruction that became dead as we nulled out the
 212       // operand, and if it is 'trivially' dead, delete it in a future loop
 213       // iteration.
 214       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
 215         if (isInstructionTriviallyDead(OpI))
 216           DeadInsts.push_back(OpI);
 217     }
 218
 219     I->eraseFromParent();
 220   }
 221 }
 222
 223
 224 //===----------------------------------------------------------------------===//
 225 //  Control Flow Graph Restructuring...
 226 //
 227
 228 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 229 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 230 /// between them, moving the instructions in the predecessor into DestBB and
 231 /// deleting the predecessor block.
 232 ///
 233 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB) {
 234   // If BB has single-entry PHI nodes, fold them.
 235   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
 236     Value *NewVal = PN->getIncomingValue(0);
 237     // Replace self referencing PHI with undef, it must be dead.
 238     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
 239     PN->replaceAllUsesWith(NewVal);
 240     PN->eraseFromParent();
 241   }
 242
 243   BasicBlock *PredBB = DestBB->getSinglePredecessor();
 244   assert(PredBB && "Block doesn't have a single predecessor!");
 245
 246   // Splice all the instructions from PredBB to DestBB.
 247   PredBB->getTerminator()->eraseFromParent();
 248   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
 249
 250   // Anything that branched to PredBB now branches to DestBB.
 251   PredBB->replaceAllUsesWith(DestBB);
 252
 253   // Nuke BB.
 254   PredBB->eraseFromParent();
 255 }
 256
 257 /// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used
 258 /// by DbgIntrinsics. If DbgInUses is specified then the vector is filled
 259 /// with the DbgInfoIntrinsic that use the instruction I.
 260 bool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I,
 261                                SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses) {
 262   if (DbgInUses)
 263     DbgInUses->clear();
 264
 265   for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
 266        ++UI) {
 267     if (DbgInfoIntrinsic *DI = dyn_cast<DbgInfoIntrinsic>(*UI)) {
 268       if (DbgInUses)
 269         DbgInUses->push_back(DI);
 270     } else {
 271       if (DbgInUses)
 272         DbgInUses->clear();
 273       return false;
 274     }
 275   }
 276   return true;
 277 }
 278
 279 /// UserIsDebugInfo - Return true if U is a constant expr used by
 280 /// llvm.dbg.variable or llvm.dbg.global_variable
 281 bool llvm::UserIsDebugInfo(User *U) {
 282   ConstantExpr *CE = dyn_cast<ConstantExpr>(U);
 283
 284   if (!CE || CE->getNumUses() != 1)
 285     return false;
 286
 287   Constant *Init = dyn_cast<Constant>(CE->use_back());
 288   if (!Init || Init->getNumUses() != 1)
 289     return false;
 290
 291   GlobalVariable *GV = dyn_cast<GlobalVariable>(Init->use_back());
 292   if (!GV || !GV->hasInitializer() || GV->getInitializer() != Init)
 293     return false;
 294
 295   DIVariable DV(GV);
 296   if (!DV.isNull())
 297     return true; // User is llvm.dbg.variable
 298
 299   DIGlobalVariable DGV(GV);
 300   if (!DGV.isNull())
 301     return true; // User is llvm.dbg.global_variable
 302
 303   return false;
 304 }
 305
 306 /// RemoveDbgInfoUser - Remove an User which is representing debug info.
 307 void llvm::RemoveDbgInfoUser(User *U) {
 308   assert (UserIsDebugInfo(U) && "Unexpected User!");
 309   ConstantExpr *CE = cast<ConstantExpr>(U);
 310   while (!CE->use_empty()) {
 311     Constant *C = cast<Constant>(CE->use_back());
 312     while (!C->use_empty()) {
 313       GlobalVariable *GV = cast<GlobalVariable>(C->use_back());
 314       GV->eraseFromParent();
 315     }
 316     C->destroyConstant();
 317   }
 318   CE->destroyConstant();
 319 }