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