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