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/Constants.h"
17 #include "llvm/Instructions.h"
18 #include "llvm/Intrinsics.h"
23 #if defined(__POWERPC__) && defined(__APPLE_CC__)
24 // FIXME: Currently it seems that isnan didn't make its way into the Apple
25 // C++ headers, although it IS in the C headers (which confuses autoconf
26 // in a big way). This is a quick fix to get things compiling, until one of
27 // us has time to write a more complicated autoconf test.
28 extern "C" int isnan (double d);
31 //===----------------------------------------------------------------------===//
32 // Local constant propagation...
35 /// doConstantPropagation - If an instruction references constants, try to fold
38 bool llvm::doConstantPropagation(BasicBlock::iterator &II) {
39 if (Constant *C = ConstantFoldInstruction(II)) {
40 // Replaces all of the uses of a variable with uses of the constant.
41 II->replaceAllUsesWith(C);
43 // Remove the instruction from the basic block...
44 II = II->getParent()->getInstList().erase(II);
51 /// ConstantFoldInstruction - Attempt to constant fold the specified
52 /// instruction. If successful, the constant result is returned, if not, null
53 /// is returned. Note that this function can only fail when attempting to fold
54 /// instructions like loads and stores, which have no constant expression form.
56 Constant *llvm::ConstantFoldInstruction(Instruction *I) {
57 if (PHINode *PN = dyn_cast<PHINode>(I)) {
58 if (PN->getNumIncomingValues() == 0)
59 return Constant::getNullValue(PN->getType());
61 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
62 if (Result == 0) return 0;
64 // Handle PHI nodes specially here...
65 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
66 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
67 return 0; // Not all the same incoming constants...
69 // If we reach here, all incoming values are the same constant.
71 } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
72 if (Function *F = CI->getCalledFunction())
73 if (canConstantFoldCallTo(F)) {
74 std::vector<Constant*> Args;
75 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
76 if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i)))
80 return ConstantFoldCall(F, Args);
85 Constant *Op0 = 0, *Op1 = 0;
86 switch (I->getNumOperands()) {
89 Op1 = dyn_cast<Constant>(I->getOperand(1));
90 if (Op1 == 0) return 0; // Not a constant?, can't fold
92 Op0 = dyn_cast<Constant>(I->getOperand(0));
93 if (Op0 == 0) return 0; // Not a constant?, can't fold
98 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
99 return ConstantExpr::get(I->getOpcode(), Op0, Op1);
101 switch (I->getOpcode()) {
103 case Instruction::Cast:
104 return ConstantExpr::getCast(Op0, I->getType());
105 case Instruction::Select:
106 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2)))
107 return ConstantExpr::getSelect(Op0, Op1, Op2);
109 case Instruction::GetElementPtr:
110 std::vector<Constant*> IdxList;
111 IdxList.reserve(I->getNumOperands()-1);
112 if (Op1) IdxList.push_back(Op1);
113 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i)
114 if (Constant *C = dyn_cast<Constant>(I->getOperand(i)))
115 IdxList.push_back(C);
117 return 0; // Non-constant operand
118 return ConstantExpr::getGetElementPtr(Op0, IdxList);
122 // ConstantFoldTerminator - If a terminator instruction is predicated on a
123 // constant value, convert it into an unconditional branch to the constant
126 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
127 TerminatorInst *T = BB->getTerminator();
129 // Branch - See if we are conditional jumping on constant
130 if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
131 if (BI->isUnconditional()) return false; // Can't optimize uncond branch
132 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
133 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
135 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
136 // Are we branching on constant?
137 // YES. Change to unconditional branch...
138 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
139 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1;
141 //cerr << "Function: " << T->getParent()->getParent()
142 // << "\nRemoving branch from " << T->getParent()
143 // << "\n\nTo: " << OldDest << endl;
145 // Let the basic block know that we are letting go of it. Based on this,
146 // it will adjust it's PHI nodes.
147 assert(BI->getParent() && "Terminator not inserted in block!");
148 OldDest->removePredecessor(BI->getParent());
150 // Set the unconditional destination, and change the insn to be an
151 // unconditional branch.
152 BI->setUnconditionalDest(Destination);
154 } else if (Dest2 == Dest1) { // Conditional branch to same location?
155 // This branch matches something like this:
156 // br bool %cond, label %Dest, label %Dest
157 // and changes it into: br label %Dest
159 // Let the basic block know that we are letting go of one copy of it.
160 assert(BI->getParent() && "Terminator not inserted in block!");
161 Dest1->removePredecessor(BI->getParent());
163 // Change a conditional branch to unconditional.
164 BI->setUnconditionalDest(Dest1);
167 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
168 // If we are switching on a constant, we can convert the switch into a
169 // single branch instruction!
170 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
171 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest
172 BasicBlock *DefaultDest = TheOnlyDest;
173 assert(TheOnlyDest == SI->getDefaultDest() &&
174 "Default destination is not successor #0?");
176 // Figure out which case it goes to...
177 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
178 // Found case matching a constant operand?
179 if (SI->getSuccessorValue(i) == CI) {
180 TheOnlyDest = SI->getSuccessor(i);
184 // Check to see if this branch is going to the same place as the default
185 // dest. If so, eliminate it as an explicit compare.
186 if (SI->getSuccessor(i) == DefaultDest) {
187 // Remove this entry...
188 DefaultDest->removePredecessor(SI->getParent());
190 --i; --e; // Don't skip an entry...
194 // Otherwise, check to see if the switch only branches to one destination.
195 // We do this by reseting "TheOnlyDest" to null when we find two non-equal
197 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
200 if (CI && !TheOnlyDest) {
201 // Branching on a constant, but not any of the cases, go to the default
203 TheOnlyDest = SI->getDefaultDest();
206 // If we found a single destination that we can fold the switch into, do so
209 // Insert the new branch..
210 new BranchInst(TheOnlyDest, SI);
211 BasicBlock *BB = SI->getParent();
213 // Remove entries from PHI nodes which we no longer branch to...
214 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
215 // Found case matching a constant operand?
216 BasicBlock *Succ = SI->getSuccessor(i);
217 if (Succ == TheOnlyDest)
218 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest
220 Succ->removePredecessor(BB);
223 // Delete the old switch...
224 BB->getInstList().erase(SI);
226 } else if (SI->getNumSuccessors() == 2) {
227 // Otherwise, we can fold this switch into a conditional branch
228 // instruction if it has only one non-default destination.
229 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(),
230 SI->getSuccessorValue(1), "cond", SI);
231 // Insert the new branch...
232 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
234 // Delete the old switch...
235 SI->getParent()->getInstList().erase(SI);
242 /// canConstantFoldCallTo - Return true if its even possible to fold a call to
243 /// the specified function.
244 bool llvm::canConstantFoldCallTo(Function *F) {
245 const std::string &Name = F->getName();
247 switch (F->getIntrinsicID()) {
248 case Intrinsic::isnan: return true;
249 case Intrinsic::isunordered: return true;
253 return Name == "sin" || Name == "cos" || Name == "tan" || Name == "sqrt" ||
254 Name == "log" || Name == "log10" || Name == "exp" || Name == "pow" ||
255 Name == "acos" || Name == "asin" || Name == "atan" || Name == "fmod";
258 static Constant *ConstantFoldFP(double (*NativeFP)(double), double V,
263 return ConstantFP::get(Ty, V);
267 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
268 /// with the specified arguments, returning null if unsuccessful.
269 Constant *llvm::ConstantFoldCall(Function *F,
270 const std::vector<Constant*> &Operands) {
271 const std::string &Name = F->getName();
272 const Type *Ty = F->getReturnType();
274 if (Operands.size() == 1) {
275 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) {
276 double V = Op->getValue();
277 if (Name == "llvm.isnan")
278 return ConstantBool::get(isnan(V));
279 else if (Name == "sin")
280 return ConstantFP::get(Ty, sin(V));
281 else if (Name == "cos")
282 return ConstantFP::get(Ty, cos(V));
283 else if (Name == "tan")
284 return ConstantFP::get(Ty, tan(V));
285 else if (Name == "sqrt" && V >= 0)
286 return ConstantFP::get(Ty, sqrt(V));
287 else if (Name == "exp")
288 return ConstantFP::get(Ty, exp(V));
289 else if (Name == "log" && V > 0)
290 return ConstantFP::get(Ty, log(V));
291 else if (Name == "log10")
292 return ConstantFoldFP(log10, V, Ty);
293 else if (Name == "acos")
294 return ConstantFoldFP(acos, V, Ty);
295 else if (Name == "asin")
296 return ConstantFoldFP(asin, V, Ty);
297 else if (Name == "atan")
298 return ConstantFP::get(Ty, atan(V));
300 } else if (Operands.size() == 2) {
301 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0]))
302 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
303 double Op1V = Op1->getValue(), Op2V = Op2->getValue();
305 if (Name == "llvm.isunordered")
306 return ConstantBool::get(isnan(Op1V) | isnan(Op2V));
307 else if (Name == "pow") {
309 double V = pow(Op1V, Op2V);
311 return ConstantFP::get(Ty, V);
312 } else if (Name == "fmod") {
314 double V = fmod(Op1V, Op2V);
316 return ConstantFP::get(Ty, V);
326 //===----------------------------------------------------------------------===//
327 // Local dead code elimination...
330 bool llvm::isInstructionTriviallyDead(Instruction *I) {
331 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I);
334 // dceInstruction - Inspect the instruction at *BBI and figure out if it's
335 // [trivially] dead. If so, remove the instruction and update the iterator
336 // to point to the instruction that immediately succeeded the original
339 bool llvm::dceInstruction(BasicBlock::iterator &BBI) {
340 // Look for un"used" definitions...
341 if (isInstructionTriviallyDead(BBI)) {
342 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye
348 //===----------------------------------------------------------------------===//
349 // PHI Instruction Simplification
352 /// hasConstantValue - If the specified PHI node always merges together the same
353 /// value, return the value, otherwise return null.
355 Value *llvm::hasConstantValue(PHINode *PN) {
356 // If the PHI node only has one incoming value, eliminate the PHI node...
357 if (PN->getNumIncomingValues() == 1)
358 return PN->getIncomingValue(0);
360 // Otherwise if all of the incoming values are the same for the PHI, replace
361 // the PHI node with the incoming value.
364 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
365 if (PN->getIncomingValue(i) != PN) // Not the PHI node itself...
366 if (InVal && PN->getIncomingValue(i) != InVal)
367 return 0; // Not the same, bail out.
369 InVal = PN->getIncomingValue(i);
371 // The only case that could cause InVal to be null is if we have a PHI node
372 // that only has entries for itself. In this case, there is no entry into the
373 // loop, so kill the PHI.
375 if (InVal == 0) InVal = Constant::getNullValue(PN->getType());
377 // All of the incoming values are the same, return the value now.