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->mayHaveSideEffects()) return true;
 169
 170   // Special case intrinsics that "may have side effects" but can be deleted
 171   // when 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   return false;
 177 }
 178
 179 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 180 /// trivially dead instruction, delete it.  If that makes any of its operands
 181 /// trivially dead, delete them too, recursively.
 182 void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) {
 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.pop_back_val();
 192
 193     // Null out all of the instruction's operands to see if any operand becomes
 194     // dead as we go.
 195     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 196       Value *OpV = I->getOperand(i);
 197       I->setOperand(i, 0);
 198
 199       if (!OpV->use_empty()) continue;
 200
 201       // If the operand is an instruction that became dead as we nulled out the
 202       // operand, and if it is 'trivially' dead, delete it in a future loop
 203       // iteration.
 204       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
 205         if (isInstructionTriviallyDead(OpI))
 206           DeadInsts.push_back(OpI);
 207     }
 208
 209     I->eraseFromParent();
 210   }
 211 }
 212
 213 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
 214 /// dead PHI node, due to being a def-use chain of single-use nodes that
 215 /// either forms a cycle or is terminated by a trivially dead instruction,
 216 /// delete it.  If that makes any of its operands trivially dead, delete them
 217 /// too, recursively.
 218 void
 219 llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) {
 220
 221   // We can remove a PHI if it is on a cycle in the def-use graph
 222   // where each node in the cycle has degree one, i.e. only one use,
 223   // and is an instruction with no side effects.
 224   if (!PN->hasOneUse())
 225     return;
 226
 227   SmallPtrSet<PHINode *, 4> PHIs;
 228   PHIs.insert(PN);
 229   for (Instruction *J = cast<Instruction>(*PN->use_begin());
 230        J->hasOneUse() && !J->mayHaveSideEffects();
 231        J = cast<Instruction>(*J->use_begin()))
 232     // If we find a PHI more than once, we're on a cycle that
 233     // won't prove fruitful.
 234     if (PHINode *JP = dyn_cast<PHINode>(J))
 235       if (!PHIs.insert(cast<PHINode>(JP))) {
 236         // Break the cycle and delete the PHI and its operands.
 237         JP->replaceAllUsesWith(UndefValue::get(JP->getType()));
 238         RecursivelyDeleteTriviallyDeadInstructions(JP);
 239         break;
 240       }
 241 }
 242
 243 //===----------------------------------------------------------------------===//
 244 //  Control Flow Graph Restructuring...
 245 //
 246
 247 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 248 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 249 /// between them, moving the instructions in the predecessor into DestBB and
 250 /// deleting the predecessor block.
 251 ///
 252 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB) {
 253   // If BB has single-entry PHI nodes, fold them.
 254   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
 255     Value *NewVal = PN->getIncomingValue(0);
 256     // Replace self referencing PHI with undef, it must be dead.
 257     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
 258     PN->replaceAllUsesWith(NewVal);
 259     PN->eraseFromParent();
 260   }
 261
 262   BasicBlock *PredBB = DestBB->getSinglePredecessor();
 263   assert(PredBB && "Block doesn't have a single predecessor!");
 264
 265   // Splice all the instructions from PredBB to DestBB.
 266   PredBB->getTerminator()->eraseFromParent();
 267   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
 268
 269   // Anything that branched to PredBB now branches to DestBB.
 270   PredBB->replaceAllUsesWith(DestBB);
 271
 272   // Nuke BB.
 273   PredBB->eraseFromParent();
 274 }
 275
 276 /// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used
 277 /// by DbgIntrinsics. If DbgInUses is specified then the vector is filled
 278 /// with the DbgInfoIntrinsic that use the instruction I.
 279 bool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I,
 280                                SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses) {
 281   if (DbgInUses)
 282     DbgInUses->clear();
 283
 284   for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
 285        ++UI) {
 286     if (DbgInfoIntrinsic *DI = dyn_cast<DbgInfoIntrinsic>(*UI)) {
 287       if (DbgInUses)
 288         DbgInUses->push_back(DI);
 289     } else {
 290       if (DbgInUses)
 291         DbgInUses->clear();
 292       return false;
 293     }
 294   }
 295   return true;
 296 }
 297
 298 /// UserIsDebugInfo - Return true if U is a constant expr used by
 299 /// llvm.dbg.variable or llvm.dbg.global_variable
 300 bool llvm::UserIsDebugInfo(User *U) {
 301   ConstantExpr *CE = dyn_cast<ConstantExpr>(U);
 302
 303   if (!CE || CE->getNumUses() != 1)
 304     return false;
 305
 306   Constant *Init = dyn_cast<Constant>(CE->use_back());
 307   if (!Init || Init->getNumUses() != 1)
 308     return false;
 309
 310   GlobalVariable *GV = dyn_cast<GlobalVariable>(Init->use_back());
 311   if (!GV || !GV->hasInitializer() || GV->getInitializer() != Init)
 312     return false;
 313
 314   DIVariable DV(GV);
 315   if (!DV.isNull())
 316     return true; // User is llvm.dbg.variable
 317
 318   DIGlobalVariable DGV(GV);
 319   if (!DGV.isNull())
 320     return true; // User is llvm.dbg.global_variable
 321
 322   return false;
 323 }
 324
 325 /// RemoveDbgInfoUser - Remove an User which is representing debug info.
 326 void llvm::RemoveDbgInfoUser(User *U) {
 327   assert (UserIsDebugInfo(U) && "Unexpected User!");
 328   ConstantExpr *CE = cast<ConstantExpr>(U);
 329   while (!CE->use_empty()) {
 330     Constant *C = cast<Constant>(CE->use_back());
 331     while (!C->use_empty()) {
 332       GlobalVariable *GV = cast<GlobalVariable>(C->use_back());
 333       GV->eraseFromParent();
 334     }
 335     C->destroyConstant();
 336   }
 337   CE->destroyConstant();
 338 }