1 //===-- Local.cpp - Functions to perform local transformations ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This family of functions perform various local transformations to the
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/Local.h"
16 #include "llvm/iTerminators.h"
17 #include "llvm/iOperators.h"
18 #include "llvm/iPHINode.h"
19 #include "llvm/ConstantHandling.h"
22 //===----------------------------------------------------------------------===//
23 // Local constant propagation...
26 /// doConstantPropagation - If an instruction references constants, try to fold
29 bool llvm::doConstantPropagation(BasicBlock::iterator &II) {
30 if (Constant *C = ConstantFoldInstruction(II)) {
31 // Replaces all of the uses of a variable with uses of the constant.
32 II->replaceAllUsesWith(C);
34 // Remove the instruction from the basic block...
35 II = II->getParent()->getInstList().erase(II);
42 /// ConstantFoldInstruction - Attempt to constant fold the specified
43 /// instruction. If successful, the constant result is returned, if not, null
44 /// is returned. Note that this function can only fail when attempting to fold
45 /// instructions like loads and stores, which have no constant expression form.
47 Constant *llvm::ConstantFoldInstruction(Instruction *I) {
48 if (PHINode *PN = dyn_cast<PHINode>(I)) {
49 if (PN->getNumIncomingValues() == 0)
50 return Constant::getNullValue(PN->getType());
52 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
53 if (Result == 0) return 0;
55 // Handle PHI nodes specially here...
56 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
57 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
58 return 0; // Not all the same incoming constants...
60 // If we reach here, all incoming values are the same constant.
64 Constant *Op0 = 0, *Op1 = 0;
65 switch (I->getNumOperands()) {
68 Op1 = dyn_cast<Constant>(I->getOperand(1));
69 if (Op1 == 0) return 0; // Not a constant?, can't fold
71 Op0 = dyn_cast<Constant>(I->getOperand(0));
72 if (Op0 == 0) return 0; // Not a constant?, can't fold
77 if (isa<BinaryOperator>(I))
78 return ConstantExpr::get(I->getOpcode(), Op0, Op1);
80 switch (I->getOpcode()) {
82 case Instruction::Cast:
83 return ConstantExpr::getCast(Op0, I->getType());
84 case Instruction::Shl:
85 case Instruction::Shr:
86 return ConstantExpr::getShift(I->getOpcode(), Op0, Op1);
87 case Instruction::GetElementPtr:
88 std::vector<Constant*> IdxList;
89 IdxList.reserve(I->getNumOperands()-1);
90 if (Op1) IdxList.push_back(Op1);
91 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i)
92 if (Constant *C = dyn_cast<Constant>(I->getOperand(i)))
95 return 0; // Non-constant operand
96 return ConstantExpr::getGetElementPtr(Op0, IdxList);
100 // ConstantFoldTerminator - If a terminator instruction is predicated on a
101 // constant value, convert it into an unconditional branch to the constant
104 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
105 TerminatorInst *T = BB->getTerminator();
107 // Branch - See if we are conditional jumping on constant
108 if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
109 if (BI->isUnconditional()) return false; // Can't optimize uncond branch
110 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
111 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
113 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
114 // Are we branching on constant?
115 // YES. Change to unconditional branch...
116 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
117 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1;
119 //cerr << "Function: " << T->getParent()->getParent()
120 // << "\nRemoving branch from " << T->getParent()
121 // << "\n\nTo: " << OldDest << endl;
123 // Let the basic block know that we are letting go of it. Based on this,
124 // it will adjust it's PHI nodes.
125 assert(BI->getParent() && "Terminator not inserted in block!");
126 OldDest->removePredecessor(BI->getParent());
128 // Set the unconditional destination, and change the insn to be an
129 // unconditional branch.
130 BI->setUnconditionalDest(Destination);
132 } else if (Dest2 == Dest1) { // Conditional branch to same location?
133 // This branch matches something like this:
134 // br bool %cond, label %Dest, label %Dest
135 // and changes it into: br label %Dest
137 // Let the basic block know that we are letting go of one copy of it.
138 assert(BI->getParent() && "Terminator not inserted in block!");
139 Dest1->removePredecessor(BI->getParent());
141 // Change a conditional branch to unconditional.
142 BI->setUnconditionalDest(Dest1);
145 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
146 // If we are switching on a constant, we can convert the switch into a
147 // single branch instruction!
148 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
149 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest
150 BasicBlock *DefaultDest = TheOnlyDest;
151 assert(TheOnlyDest == SI->getDefaultDest() &&
152 "Default destination is not successor #0?");
154 // Figure out which case it goes to...
155 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
156 // Found case matching a constant operand?
157 if (SI->getSuccessorValue(i) == CI) {
158 TheOnlyDest = SI->getSuccessor(i);
162 // Check to see if this branch is going to the same place as the default
163 // dest. If so, eliminate it as an explicit compare.
164 if (SI->getSuccessor(i) == DefaultDest) {
165 // Remove this entry...
166 DefaultDest->removePredecessor(SI->getParent());
168 --i; --e; // Don't skip an entry...
172 // Otherwise, check to see if the switch only branches to one destination.
173 // We do this by reseting "TheOnlyDest" to null when we find two non-equal
175 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
178 if (CI && !TheOnlyDest) {
179 // Branching on a constant, but not any of the cases, go to the default
181 TheOnlyDest = SI->getDefaultDest();
184 // If we found a single destination that we can fold the switch into, do so
187 // Insert the new branch..
188 new BranchInst(TheOnlyDest, SI);
189 BasicBlock *BB = SI->getParent();
191 // Remove entries from PHI nodes which we no longer branch to...
192 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
193 // Found case matching a constant operand?
194 BasicBlock *Succ = SI->getSuccessor(i);
195 if (Succ == TheOnlyDest)
196 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest
198 Succ->removePredecessor(BB);
201 // Delete the old switch...
202 BB->getInstList().erase(SI);
204 } else if (SI->getNumSuccessors() == 2) {
205 // Otherwise, we can fold this switch into a conditional branch
206 // instruction if it has only one non-default destination.
207 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(),
208 SI->getSuccessorValue(1), "cond", SI);
209 // Insert the new branch...
210 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
212 // Delete the old switch...
213 SI->getParent()->getInstList().erase(SI);
222 //===----------------------------------------------------------------------===//
223 // Local dead code elimination...
226 bool llvm::isInstructionTriviallyDead(Instruction *I) {
227 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I);
230 // dceInstruction - Inspect the instruction at *BBI and figure out if it's
231 // [trivially] dead. If so, remove the instruction and update the iterator
232 // to point to the instruction that immediately succeeded the original
235 bool llvm::dceInstruction(BasicBlock::iterator &BBI) {
236 // Look for un"used" definitions...
237 if (isInstructionTriviallyDead(BBI)) {
238 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye
244 //===----------------------------------------------------------------------===//
245 // PHI Instruction Simplification
248 /// hasConstantValue - If the specified PHI node always merges together the same
249 /// value, return the value, otherwise return null.
251 Value *llvm::hasConstantValue(PHINode *PN) {
252 // If the PHI node only has one incoming value, eliminate the PHI node...
253 if (PN->getNumIncomingValues() == 1)
254 return PN->getIncomingValue(0);
256 // Otherwise if all of the incoming values are the same for the PHI, replace
257 // the PHI node with the incoming value.
260 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
261 if (PN->getIncomingValue(i) != PN) // Not the PHI node itself...
262 if (InVal && PN->getIncomingValue(i) != InVal)
263 return 0; // Not the same, bail out.
265 InVal = PN->getIncomingValue(i);
267 // The only case that could cause InVal to be null is if we have a PHI node
268 // that only has entries for itself. In this case, there is no entry into the
269 // loop, so kill the PHI.
271 if (InVal == 0) InVal = Constant::getNullValue(PN->getType());
273 // All of the incoming values are the same, return the value now.