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