Change cannonicalization rules: add X,X is represented as multiplies, multiplies
[oota-llvm.git] / lib / Transforms / Scalar / InstructionCombining.cpp
1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
2 //
3 // InstructionCombining - Combine instructions to form fewer, simple
4 // instructions.  This pass does not modify the CFG This pass is where algebraic
5 // simplification happens.
6 //
7 // This pass combines things like:
8 //    %Y = add int 1, %X
9 //    %Z = add int 1, %Y
10 // into:
11 //    %Z = add int 2, %X
12 //
13 // This is a simple worklist driven algorithm.
14 //
15 // This pass guarantees that the following cannonicalizations are performed on
16 // the program:
17 //    1. If a binary operator has a constant operand, it is moved to the RHS
18 //    2. Bitwise operators with constant operands are always grouped so that
19 //       shifts are performed first, then or's, then and's, then xor's.
20 //    3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible
21 //    4. All SetCC instructions on boolean values are replaced with logical ops
22 //    5. add X, X is represented as (X*2) => (X << 1)
23 //    6. Multiplies with a power-of-two constant argument are transformed into
24 //       shifts.
25 //    N. This list is incomplete
26 //
27 //===----------------------------------------------------------------------===//
28
29 #include "llvm/Transforms/Scalar.h"
30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
31 #include "llvm/Transforms/Utils/Local.h"
32 #include "llvm/Instructions.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Constants.h"
35 #include "llvm/ConstantHandling.h"
36 #include "llvm/DerivedTypes.h"
37 #include "llvm/GlobalVariable.h"
38 #include "llvm/Support/InstIterator.h"
39 #include "llvm/Support/InstVisitor.h"
40 #include "llvm/Support/CallSite.h"
41 #include "Support/Statistic.h"
42 #include <algorithm>
43
44 namespace {
45   Statistic<> NumCombined ("instcombine", "Number of insts combined");
46   Statistic<> NumConstProp("instcombine", "Number of constant folds");
47   Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
48
49   class InstCombiner : public FunctionPass,
50                        public InstVisitor<InstCombiner, Instruction*> {
51     // Worklist of all of the instructions that need to be simplified.
52     std::vector<Instruction*> WorkList;
53
54     void AddUsesToWorkList(Instruction &I) {
55       // The instruction was simplified, add all users of the instruction to
56       // the work lists because they might get more simplified now...
57       //
58       for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
59            UI != UE; ++UI)
60         WorkList.push_back(cast<Instruction>(*UI));
61     }
62
63     // removeFromWorkList - remove all instances of I from the worklist.
64     void removeFromWorkList(Instruction *I);
65   public:
66     virtual bool runOnFunction(Function &F);
67
68     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
69       AU.setPreservesCFG();
70     }
71
72     // Visitation implementation - Implement instruction combining for different
73     // instruction types.  The semantics are as follows:
74     // Return Value:
75     //    null        - No change was made
76     //     I          - Change was made, I is still valid, I may be dead though
77     //   otherwise    - Change was made, replace I with returned instruction
78     //   
79     Instruction *visitAdd(BinaryOperator &I);
80     Instruction *visitSub(BinaryOperator &I);
81     Instruction *visitMul(BinaryOperator &I);
82     Instruction *visitDiv(BinaryOperator &I);
83     Instruction *visitRem(BinaryOperator &I);
84     Instruction *visitAnd(BinaryOperator &I);
85     Instruction *visitOr (BinaryOperator &I);
86     Instruction *visitXor(BinaryOperator &I);
87     Instruction *visitSetCondInst(BinaryOperator &I);
88     Instruction *visitShiftInst(ShiftInst &I);
89     Instruction *visitCastInst(CastInst &CI);
90     Instruction *visitCallInst(CallInst &CI);
91     Instruction *visitInvokeInst(InvokeInst &II);
92     Instruction *visitPHINode(PHINode &PN);
93     Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
94     Instruction *visitAllocationInst(AllocationInst &AI);
95     Instruction *visitLoadInst(LoadInst &LI);
96     Instruction *visitBranchInst(BranchInst &BI);
97
98     // visitInstruction - Specify what to return for unhandled instructions...
99     Instruction *visitInstruction(Instruction &I) { return 0; }
100
101   private:
102     bool transformConstExprCastCall(CallSite CS);
103
104     // InsertNewInstBefore - insert an instruction New before instruction Old
105     // in the program.  Add the new instruction to the worklist.
106     //
107     void InsertNewInstBefore(Instruction *New, Instruction &Old) {
108       assert(New && New->getParent() == 0 &&
109              "New instruction already inserted into a basic block!");
110       BasicBlock *BB = Old.getParent();
111       BB->getInstList().insert(&Old, New);  // Insert inst
112       WorkList.push_back(New);              // Add to worklist
113     }
114
115     // ReplaceInstUsesWith - This method is to be used when an instruction is
116     // found to be dead, replacable with another preexisting expression.  Here
117     // we add all uses of I to the worklist, replace all uses of I with the new
118     // value, then return I, so that the inst combiner will know that I was
119     // modified.
120     //
121     Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
122       AddUsesToWorkList(I);         // Add all modified instrs to worklist
123       I.replaceAllUsesWith(V);
124       return &I;
125     }
126
127     /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
128     /// InsertBefore instruction.  This is specialized a bit to avoid inserting
129     /// casts that are known to not do anything...
130     ///
131     Value *InsertOperandCastBefore(Value *V, const Type *DestTy,
132                                    Instruction *InsertBefore);
133
134     // SimplifyCommutative - This performs a few simplifications for commutative
135     // operators...
136     bool SimplifyCommutative(BinaryOperator &I);
137   };
138
139   RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
140 }
141
142 // getComplexity:  Assign a complexity or rank value to LLVM Values...
143 //   0 -> Constant, 1 -> Other, 2 -> Argument, 2 -> Unary, 3 -> OtherInst
144 static unsigned getComplexity(Value *V) {
145   if (isa<Instruction>(V)) {
146     if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
147       return 2;
148     return 3;
149   }
150   if (isa<Argument>(V)) return 2;
151   return isa<Constant>(V) ? 0 : 1;
152 }
153
154 // isOnlyUse - Return true if this instruction will be deleted if we stop using
155 // it.
156 static bool isOnlyUse(Value *V) {
157   return V->use_size() == 1 || isa<Constant>(V);
158 }
159
160 // SimplifyCommutative - This performs a few simplifications for commutative
161 // operators:
162 //
163 //  1. Order operands such that they are listed from right (least complex) to
164 //     left (most complex).  This puts constants before unary operators before
165 //     binary operators.
166 //
167 //  2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
168 //  3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
169 //
170 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
171   bool Changed = false;
172   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
173     Changed = !I.swapOperands();
174   
175   if (!I.isAssociative()) return Changed;
176   Instruction::BinaryOps Opcode = I.getOpcode();
177   if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
178     if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
179       if (isa<Constant>(I.getOperand(1))) {
180         Constant *Folded = ConstantExpr::get(I.getOpcode(),
181                                              cast<Constant>(I.getOperand(1)),
182                                              cast<Constant>(Op->getOperand(1)));
183         I.setOperand(0, Op->getOperand(0));
184         I.setOperand(1, Folded);
185         return true;
186       } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
187         if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
188             isOnlyUse(Op) && isOnlyUse(Op1)) {
189           Constant *C1 = cast<Constant>(Op->getOperand(1));
190           Constant *C2 = cast<Constant>(Op1->getOperand(1));
191
192           // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
193           Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
194           Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
195                                                     Op1->getOperand(0),
196                                                     Op1->getName(), &I);
197           WorkList.push_back(New);
198           I.setOperand(0, New);
199           I.setOperand(1, Folded);
200           return true;
201         }      
202     }
203   return Changed;
204 }
205
206 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
207 // if the LHS is a constant zero (which is the 'negate' form).
208 //
209 static inline Value *dyn_castNegVal(Value *V) {
210   if (BinaryOperator::isNeg(V))
211     return BinaryOperator::getNegArgument(cast<BinaryOperator>(V));
212
213   // Constants can be considered to be negated values if they can be folded...
214   if (Constant *C = dyn_cast<Constant>(V))
215     return ConstantExpr::get(Instruction::Sub,
216                              Constant::getNullValue(V->getType()), C);
217   return 0;
218 }
219
220 static inline Value *dyn_castNotVal(Value *V) {
221   if (BinaryOperator::isNot(V))
222     return BinaryOperator::getNotArgument(cast<BinaryOperator>(V));
223
224   // Constants can be considered to be not'ed values...
225   if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
226     return ConstantExpr::get(Instruction::Xor,
227                              ConstantIntegral::getAllOnesValue(C->getType()),C);
228   return 0;
229 }
230
231 // dyn_castFoldableMul - If this value is a multiply that can be folded into
232 // other computations (because it has a constant operand), return the
233 // non-constant operand of the multiply.
234 //
235 static inline Value *dyn_castFoldableMul(Value *V) {
236   if (V->use_size() == 1 && V->getType()->isInteger())
237     if (Instruction *I = dyn_cast<Instruction>(V))
238       if (I->getOpcode() == Instruction::Mul)
239         if (isa<Constant>(I->getOperand(1)))
240           return I->getOperand(0);
241   return 0;
242 }
243
244 // dyn_castMaskingAnd - If this value is an And instruction masking a value with
245 // a constant, return the constant being anded with.
246 //
247 template<class ValueType>
248 static inline Constant *dyn_castMaskingAnd(ValueType *V) {
249   if (Instruction *I = dyn_cast<Instruction>(V))
250     if (I->getOpcode() == Instruction::And)
251       return dyn_cast<Constant>(I->getOperand(1));
252
253   // If this is a constant, it acts just like we were masking with it.
254   return dyn_cast<Constant>(V);
255 }
256
257 // Log2 - Calculate the log base 2 for the specified value if it is exactly a
258 // power of 2.
259 static unsigned Log2(uint64_t Val) {
260   assert(Val > 1 && "Values 0 and 1 should be handled elsewhere!");
261   unsigned Count = 0;
262   while (Val != 1) {
263     if (Val & 1) return 0;    // Multiple bits set?
264     Val >>= 1;
265     ++Count;
266   }
267   return Count;
268 }
269
270 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
271   bool Changed = SimplifyCommutative(I);
272   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
273
274   // Eliminate 'add int %X, 0'
275   if (RHS == Constant::getNullValue(I.getType()))
276     return ReplaceInstUsesWith(I, LHS);
277
278   // Convert 'add X, X' to 'shl X, 1'
279   if (LHS == RHS && I.getType()->isInteger())
280     return new ShiftInst(Instruction::Shl, LHS,
281                          ConstantInt::get(Type::UByteTy, 1));
282
283   // -A + B  -->  B - A
284   if (Value *V = dyn_castNegVal(LHS))
285     return BinaryOperator::create(Instruction::Sub, RHS, V);
286
287   // A + -B  -->  A - B
288   if (!isa<Constant>(RHS))
289     if (Value *V = dyn_castNegVal(RHS))
290       return BinaryOperator::create(Instruction::Sub, LHS, V);
291
292   // X*C + X --> X * (C+1)
293   if (dyn_castFoldableMul(LHS) == RHS) {
294     Constant *CP1 =
295       ConstantExpr::get(Instruction::Add, 
296                         cast<Constant>(cast<Instruction>(LHS)->getOperand(1)),
297                         ConstantInt::get(I.getType(), 1));
298     return BinaryOperator::create(Instruction::Mul, RHS, CP1);
299   }
300
301   // X + X*C --> X * (C+1)
302   if (dyn_castFoldableMul(RHS) == LHS) {
303     Constant *CP1 =
304       ConstantExpr::get(Instruction::Add,
305                         cast<Constant>(cast<Instruction>(RHS)->getOperand(1)),
306                         ConstantInt::get(I.getType(), 1));
307     return BinaryOperator::create(Instruction::Mul, LHS, CP1);
308   }
309
310   // (A & C1)+(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
311   if (Constant *C1 = dyn_castMaskingAnd(LHS))
312     if (Constant *C2 = dyn_castMaskingAnd(RHS))
313       if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue())
314         return BinaryOperator::create(Instruction::Or, LHS, RHS);
315
316   return Changed ? &I : 0;
317 }
318
319 // isSignBit - Return true if the value represented by the constant only has the
320 // highest order bit set.
321 static bool isSignBit(ConstantInt *CI) {
322   unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
323   return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1));
324 }
325
326 static unsigned getTypeSizeInBits(const Type *Ty) {
327   return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8;
328 }
329
330 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
331   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
332
333   if (Op0 == Op1)         // sub X, X  -> 0
334     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
335
336   // If this is a 'B = x-(-A)', change to B = x+A...
337   if (Value *V = dyn_castNegVal(Op1))
338     return BinaryOperator::create(Instruction::Add, Op0, V);
339
340   // Replace (-1 - A) with (~A)...
341   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0))
342     if (C->isAllOnesValue())
343       return BinaryOperator::createNot(Op1);
344
345   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
346     if (Op1I->use_size() == 1) {
347       // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
348       // is not used by anyone else...
349       //
350       if (Op1I->getOpcode() == Instruction::Sub) {
351         // Swap the two operands of the subexpr...
352         Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
353         Op1I->setOperand(0, IIOp1);
354         Op1I->setOperand(1, IIOp0);
355         
356         // Create the new top level add instruction...
357         return BinaryOperator::create(Instruction::Add, Op0, Op1);
358       }
359
360       // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
361       //
362       if (Op1I->getOpcode() == Instruction::And &&
363           (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
364         Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
365
366         Instruction *NewNot = BinaryOperator::createNot(OtherOp, "B.not", &I);
367         return BinaryOperator::create(Instruction::And, Op0, NewNot);
368       }
369
370       // X - X*C --> X * (1-C)
371       if (dyn_castFoldableMul(Op1I) == Op0) {
372         Constant *CP1 =
373           ConstantExpr::get(Instruction::Sub,
374                             ConstantInt::get(I.getType(), 1),
375                          cast<Constant>(cast<Instruction>(Op1)->getOperand(1)));
376         assert(CP1 && "Couldn't constant fold 1-C?");
377         return BinaryOperator::create(Instruction::Mul, Op0, CP1);
378       }
379     }
380
381   // X*C - X --> X * (C-1)
382   if (dyn_castFoldableMul(Op0) == Op1) {
383     Constant *CP1 =
384       ConstantExpr::get(Instruction::Sub,
385                         cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
386                         ConstantInt::get(I.getType(), 1));
387     assert(CP1 && "Couldn't constant fold C - 1?");
388     return BinaryOperator::create(Instruction::Mul, Op1, CP1);
389   }
390
391   return 0;
392 }
393
394 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
395   bool Changed = SimplifyCommutative(I);
396   Value *Op0 = I.getOperand(0);
397
398   // Simplify mul instructions with a constant RHS...
399   if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
400     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
401
402       // ((X << C1)*C2) == (X * (C2 << C1))
403       if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
404         if (SI->getOpcode() == Instruction::Shl)
405           if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
406             return BinaryOperator::create(Instruction::Mul, SI->getOperand(0),
407                                           *CI << *ShOp);
408
409       const Type *Ty = CI->getType();
410       int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue();
411       switch (Val) {
412       case -1:                               // X * -1 -> -X
413         return BinaryOperator::createNeg(Op0, I.getName());
414       case 0:
415         return ReplaceInstUsesWith(I, Op1);  // Eliminate 'mul double %X, 0'
416       case 1:
417         return ReplaceInstUsesWith(I, Op0);  // Eliminate 'mul int %X, 1'
418       }
419
420       if (uint64_t C = Log2(Val))            // Replace X*(2^C) with X << C
421         return new ShiftInst(Instruction::Shl, Op0,
422                              ConstantUInt::get(Type::UByteTy, C));
423     } else {
424       ConstantFP *Op1F = cast<ConstantFP>(Op1);
425       if (Op1F->isNullValue())
426         return ReplaceInstUsesWith(I, Op1);
427
428       // "In IEEE floating point, x*1 is not equivalent to x for nans.  However,
429       // ANSI says we can drop signals, so we can do this anyway." (from GCC)
430       if (Op1F->getValue() == 1.0)
431         return ReplaceInstUsesWith(I, Op0);  // Eliminate 'mul double %X, 1.0'
432     }
433   }
434
435   if (Value *Op0v = dyn_castNegVal(Op0))     // -X * -Y = X*Y
436     if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
437       return BinaryOperator::create(Instruction::Mul, Op0v, Op1v);
438
439   return Changed ? &I : 0;
440 }
441
442 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
443   // div X, 1 == X
444   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
445     if (RHS->equalsInt(1))
446       return ReplaceInstUsesWith(I, I.getOperand(0));
447
448     // Check to see if this is an unsigned division with an exact power of 2,
449     // if so, convert to a right shift.
450     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
451       if (uint64_t Val = C->getValue())    // Don't break X / 0
452         if (uint64_t C = Log2(Val))
453           return new ShiftInst(Instruction::Shr, I.getOperand(0),
454                                ConstantUInt::get(Type::UByteTy, C));
455   }
456
457   // 0 / X == 0, we don't need to preserve faults!
458   if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
459     if (LHS->equalsInt(0))
460       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
461
462   return 0;
463 }
464
465
466 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
467   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
468     if (RHS->equalsInt(1))  // X % 1 == 0
469       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
470
471     // Check to see if this is an unsigned remainder with an exact power of 2,
472     // if so, convert to a bitwise and.
473     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
474       if (uint64_t Val = C->getValue())    // Don't break X % 0 (divide by zero)
475         if (Log2(Val))
476           return BinaryOperator::create(Instruction::And, I.getOperand(0),
477                                         ConstantUInt::get(I.getType(), Val-1));
478   }
479
480   // 0 % X == 0, we don't need to preserve faults!
481   if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
482     if (LHS->equalsInt(0))
483       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
484
485   return 0;
486 }
487
488 // isMaxValueMinusOne - return true if this is Max-1
489 static bool isMaxValueMinusOne(const ConstantInt *C) {
490   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
491     // Calculate -1 casted to the right type...
492     unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
493     uint64_t Val = ~0ULL;                // All ones
494     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
495     return CU->getValue() == Val-1;
496   }
497
498   const ConstantSInt *CS = cast<ConstantSInt>(C);
499   
500   // Calculate 0111111111..11111
501   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
502   int64_t Val = INT64_MAX;             // All ones
503   Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
504   return CS->getValue() == Val-1;
505 }
506
507 // isMinValuePlusOne - return true if this is Min+1
508 static bool isMinValuePlusOne(const ConstantInt *C) {
509   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
510     return CU->getValue() == 1;
511
512   const ConstantSInt *CS = cast<ConstantSInt>(C);
513   
514   // Calculate 1111111111000000000000 
515   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
516   int64_t Val = -1;                    // All ones
517   Val <<= TypeBits-1;                  // Shift over to the right spot
518   return CS->getValue() == Val+1;
519 }
520
521
522 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
523   bool Changed = SimplifyCommutative(I);
524   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
525
526   // and X, X = X   and X, 0 == 0
527   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
528     return ReplaceInstUsesWith(I, Op1);
529
530   // and X, -1 == X
531   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
532     if (RHS->isAllOnesValue())
533       return ReplaceInstUsesWith(I, Op0);
534
535     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
536       Value *X = Op0I->getOperand(0);
537       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
538         if (Op0I->getOpcode() == Instruction::Xor) {
539           if ((*RHS & *Op0CI)->isNullValue()) {
540             // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
541             return BinaryOperator::create(Instruction::And, X, RHS);
542           } else if (isOnlyUse(Op0)) {
543             // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
544             std::string Op0Name = Op0I->getName(); Op0I->setName("");
545             Instruction *And = BinaryOperator::create(Instruction::And,
546                                                       X, RHS, Op0Name);
547             InsertNewInstBefore(And, I);
548             return BinaryOperator::create(Instruction::Xor, And, *RHS & *Op0CI);
549           }
550         } else if (Op0I->getOpcode() == Instruction::Or) {
551           // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
552           if ((*RHS & *Op0CI)->isNullValue())
553             return BinaryOperator::create(Instruction::And, X, RHS);
554
555           Constant *Together = *RHS & *Op0CI;
556           if (Together == RHS) // (X | C) & C --> C
557             return ReplaceInstUsesWith(I, RHS);
558
559           if (isOnlyUse(Op0)) {
560             if (Together != Op0CI) {
561               // (X | C1) & C2 --> (X | (C1&C2)) & C2
562               std::string Op0Name = Op0I->getName(); Op0I->setName("");
563               Instruction *Or = BinaryOperator::create(Instruction::Or, X,
564                                                        Together, Op0Name);
565               InsertNewInstBefore(Or, I);
566               return BinaryOperator::create(Instruction::And, Or, RHS);
567             }
568           }
569         }
570     }
571   }
572
573   Value *Op0NotVal = dyn_castNotVal(Op0);
574   Value *Op1NotVal = dyn_castNotVal(Op1);
575
576   // (~A & ~B) == (~(A | B)) - Demorgan's Law
577   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
578     Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal,
579                                              Op1NotVal,I.getName()+".demorgan");
580     InsertNewInstBefore(Or, I);
581     return BinaryOperator::createNot(Or);
582   }
583
584   if (Op0NotVal == Op1 || Op1NotVal == Op0)  // A & ~A  == ~A & A == 0
585     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
586
587   return Changed ? &I : 0;
588 }
589
590
591
592 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
593   bool Changed = SimplifyCommutative(I);
594   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
595
596   // or X, X = X   or X, 0 == X
597   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
598     return ReplaceInstUsesWith(I, Op0);
599
600   // or X, -1 == -1
601   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
602     if (RHS->isAllOnesValue())
603       return ReplaceInstUsesWith(I, Op1);
604
605     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
606       // (X & C1) | C2 --> (X | C2) & (C1|C2)
607       if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0))
608         if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
609           std::string Op0Name = Op0I->getName(); Op0I->setName("");
610           Instruction *Or = BinaryOperator::create(Instruction::Or,
611                                                    Op0I->getOperand(0), RHS,
612                                                    Op0Name);
613           InsertNewInstBefore(Or, I);
614           return BinaryOperator::create(Instruction::And, Or, *RHS | *Op0CI);
615         }
616
617       // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
618       if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0))
619         if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
620           std::string Op0Name = Op0I->getName(); Op0I->setName("");
621           Instruction *Or = BinaryOperator::create(Instruction::Or,
622                                                    Op0I->getOperand(0), RHS,
623                                                    Op0Name);
624           InsertNewInstBefore(Or, I);
625           return BinaryOperator::create(Instruction::Xor, Or, *Op0CI & *~*RHS);
626         }
627     }
628   }
629
630   // (A & C1)|(A & C2) == A & (C1|C2)
631   if (Instruction *LHS = dyn_cast<BinaryOperator>(Op0))
632     if (Instruction *RHS = dyn_cast<BinaryOperator>(Op1))
633       if (LHS->getOperand(0) == RHS->getOperand(0))
634         if (Constant *C0 = dyn_castMaskingAnd(LHS))
635           if (Constant *C1 = dyn_castMaskingAnd(RHS))
636             return BinaryOperator::create(Instruction::And, LHS->getOperand(0),
637                                           *C0 | *C1);            
638
639   Value *Op0NotVal = dyn_castNotVal(Op0);
640   Value *Op1NotVal = dyn_castNotVal(Op1);
641
642   if (Op1 == Op0NotVal)   // ~A | A == -1
643     return ReplaceInstUsesWith(I, 
644                                ConstantIntegral::getAllOnesValue(I.getType()));
645
646   if (Op0 == Op1NotVal)   // A | ~A == -1
647     return ReplaceInstUsesWith(I, 
648                                ConstantIntegral::getAllOnesValue(I.getType()));
649
650   // (~A | ~B) == (~(A & B)) - Demorgan's Law
651   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
652     Instruction *And = BinaryOperator::create(Instruction::And, Op0NotVal,
653                                               Op1NotVal,I.getName()+".demorgan",
654                                               &I);
655     WorkList.push_back(And);
656     return BinaryOperator::createNot(And);
657   }
658
659   return Changed ? &I : 0;
660 }
661
662
663
664 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
665   bool Changed = SimplifyCommutative(I);
666   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
667
668   // xor X, X = 0
669   if (Op0 == Op1)
670     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
671
672   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
673     // xor X, 0 == X
674     if (RHS->isNullValue())
675       return ReplaceInstUsesWith(I, Op0);
676
677     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
678       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
679       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
680         if (RHS == ConstantBool::True && SCI->use_size() == 1)
681           return new SetCondInst(SCI->getInverseCondition(),
682                                  SCI->getOperand(0), SCI->getOperand(1));
683           
684       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
685         if (Op0I->getOpcode() == Instruction::And) {
686           // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
687           if ((*RHS & *Op0CI)->isNullValue())
688             return BinaryOperator::create(Instruction::Or, Op0, RHS);
689         } else if (Op0I->getOpcode() == Instruction::Or) {
690           // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
691           if ((*RHS & *Op0CI) == RHS)
692             return BinaryOperator::create(Instruction::And, Op0, ~*RHS);
693         }
694     }
695   }
696
697   if (Value *X = dyn_castNotVal(Op0))   // ~A ^ A == -1
698     if (X == Op1)
699       return ReplaceInstUsesWith(I,
700                                 ConstantIntegral::getAllOnesValue(I.getType()));
701
702   if (Value *X = dyn_castNotVal(Op1))   // A ^ ~A == -1
703     if (X == Op0)
704       return ReplaceInstUsesWith(I,
705                                 ConstantIntegral::getAllOnesValue(I.getType()));
706
707   if (Instruction *Op1I = dyn_cast<Instruction>(Op1))
708     if (Op1I->getOpcode() == Instruction::Or)
709       if (Op1I->getOperand(0) == Op0) {              // B^(B|A) == (A|B)^B
710         cast<BinaryOperator>(Op1I)->swapOperands();
711         I.swapOperands();
712         std::swap(Op0, Op1);
713       } else if (Op1I->getOperand(1) == Op0) {       // B^(A|B) == (A|B)^B
714         I.swapOperands();
715         std::swap(Op0, Op1);
716       }
717
718   if (Instruction *Op0I = dyn_cast<Instruction>(Op0))
719     if (Op0I->getOpcode() == Instruction::Or && Op0I->use_size() == 1) {
720       if (Op0I->getOperand(0) == Op1)                // (B|A)^B == (A|B)^B
721         cast<BinaryOperator>(Op0I)->swapOperands();
722       if (Op0I->getOperand(1) == Op1) {              // (A|B)^B == A & ~B
723         Value *NotB = BinaryOperator::createNot(Op1, Op1->getName()+".not", &I);
724         WorkList.push_back(cast<Instruction>(NotB));
725         return BinaryOperator::create(Instruction::And, Op0I->getOperand(0),
726                                       NotB);
727       }
728     }
729
730   // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0
731   if (Constant *C1 = dyn_castMaskingAnd(Op0))
732     if (Constant *C2 = dyn_castMaskingAnd(Op1))
733       if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue())
734         return BinaryOperator::create(Instruction::Or, Op0, Op1);
735
736   return Changed ? &I : 0;
737 }
738
739 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
740 static Constant *AddOne(ConstantInt *C) {
741   Constant *Result = ConstantExpr::get(Instruction::Add, C,
742                                        ConstantInt::get(C->getType(), 1));
743   assert(Result && "Constant folding integer addition failed!");
744   return Result;
745 }
746 static Constant *SubOne(ConstantInt *C) {
747   Constant *Result = ConstantExpr::get(Instruction::Sub, C,
748                                        ConstantInt::get(C->getType(), 1));
749   assert(Result && "Constant folding integer addition failed!");
750   return Result;
751 }
752
753 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
754 // true when both operands are equal...
755 //
756 static bool isTrueWhenEqual(Instruction &I) {
757   return I.getOpcode() == Instruction::SetEQ ||
758          I.getOpcode() == Instruction::SetGE ||
759          I.getOpcode() == Instruction::SetLE;
760 }
761
762 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
763   bool Changed = SimplifyCommutative(I);
764   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
765   const Type *Ty = Op0->getType();
766
767   // setcc X, X
768   if (Op0 == Op1)
769     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
770
771   // setcc <global*>, 0 - Global value addresses are never null!
772   if (isa<GlobalValue>(Op0) && isa<ConstantPointerNull>(Op1))
773     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
774
775   // setcc's with boolean values can always be turned into bitwise operations
776   if (Ty == Type::BoolTy) {
777     // If this is <, >, or !=, we can change this into a simple xor instruction
778     if (!isTrueWhenEqual(I))
779       return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName());
780
781     // Otherwise we need to make a temporary intermediate instruction and insert
782     // it into the instruction stream.  This is what we are after:
783     //
784     //  seteq bool %A, %B -> ~(A^B)
785     //  setle bool %A, %B -> ~A | B
786     //  setge bool %A, %B -> A | ~B
787     //
788     if (I.getOpcode() == Instruction::SetEQ) {  // seteq case
789       Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
790                                                 I.getName()+"tmp");
791       InsertNewInstBefore(Xor, I);
792       return BinaryOperator::createNot(Xor, I.getName());
793     }
794
795     // Handle the setXe cases...
796     assert(I.getOpcode() == Instruction::SetGE ||
797            I.getOpcode() == Instruction::SetLE);
798
799     if (I.getOpcode() == Instruction::SetGE)
800       std::swap(Op0, Op1);                   // Change setge -> setle
801
802     // Now we just have the SetLE case.
803     Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
804     InsertNewInstBefore(Not, I);
805     return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName());
806   }
807
808   // Check to see if we are doing one of many comparisons against constant
809   // integers at the end of their ranges...
810   //
811   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
812     // Simplify seteq and setne instructions...
813     if (I.getOpcode() == Instruction::SetEQ ||
814         I.getOpcode() == Instruction::SetNE) {
815       bool isSetNE = I.getOpcode() == Instruction::SetNE;
816
817       if (CI->isNullValue()) {   // Simplify [seteq|setne] X, 0
818         CastInst *Val = new CastInst(Op0, Type::BoolTy, I.getName()+".not");
819         if (isSetNE) return Val;
820
821         // seteq X, 0 -> not (cast X to bool)
822         InsertNewInstBefore(Val, I);
823         return BinaryOperator::createNot(Val, I.getName());
824       }
825
826       // If the first operand is (and|or|xor) with a constant, and the second
827       // operand is a constant, simplify a bit.
828       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
829         if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1)))
830           if (BO->getOpcode() == Instruction::Or) {
831             // If bits are being or'd in that are not present in the constant we
832             // are comparing against, then the comparison could never succeed!
833             if (!(*BOC & *~*CI)->isNullValue())
834               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
835           } else if (BO->getOpcode() == Instruction::And) {
836             // If bits are being compared against that are and'd out, then the
837             // comparison can never succeed!
838             if (!(*CI & *~*BOC)->isNullValue())
839               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
840           } else if (BO->getOpcode() == Instruction::Xor) {
841             // For the xor case, we can always just xor the two constants
842             // together, potentially eliminating the explicit xor.
843             return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
844                                           *CI ^ *BOC);
845           }
846     }
847
848     // Check to see if we are comparing against the minimum or maximum value...
849     if (CI->isMinValue()) {
850       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
851         return ReplaceInstUsesWith(I, ConstantBool::False);
852       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
853         return ReplaceInstUsesWith(I, ConstantBool::True);
854       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
855         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
856       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
857         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
858
859     } else if (CI->isMaxValue()) {
860       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
861         return ReplaceInstUsesWith(I, ConstantBool::False);
862       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
863         return ReplaceInstUsesWith(I, ConstantBool::True);
864       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
865         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
866       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
867         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
868
869       // Comparing against a value really close to min or max?
870     } else if (isMinValuePlusOne(CI)) {
871       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
872         return BinaryOperator::create(Instruction::SetEQ, Op0,
873                                       SubOne(CI), I.getName());
874       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
875         return BinaryOperator::create(Instruction::SetNE, Op0,
876                                       SubOne(CI), I.getName());
877
878     } else if (isMaxValueMinusOne(CI)) {
879       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
880         return BinaryOperator::create(Instruction::SetEQ, Op0,
881                                       AddOne(CI), I.getName());
882       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
883         return BinaryOperator::create(Instruction::SetNE, Op0,
884                                       AddOne(CI), I.getName());
885     }
886   }
887
888   return Changed ? &I : 0;
889 }
890
891
892
893 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
894   assert(I.getOperand(1)->getType() == Type::UByteTy);
895   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
896   bool isLeftShift = I.getOpcode() == Instruction::Shl;
897
898   // shl X, 0 == X and shr X, 0 == X
899   // shl 0, X == 0 and shr 0, X == 0
900   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
901       Op0 == Constant::getNullValue(Op0->getType()))
902     return ReplaceInstUsesWith(I, Op0);
903
904   // shr int -1, X = -1   (for any arithmetic shift rights of ~0)
905   if (!isLeftShift)
906     if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
907       if (CSI->isAllOnesValue())
908         return ReplaceInstUsesWith(I, CSI);
909
910   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
911     // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
912     // of a signed value.
913     //
914     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
915     if (CUI->getValue() >= TypeBits &&
916         (!Op0->getType()->isSigned() || isLeftShift))
917       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
918
919     // ((X*C1) << C2) == (X * (C1 << C2))
920     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
921       if (BO->getOpcode() == Instruction::Mul && isLeftShift)
922         if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
923           return BinaryOperator::create(Instruction::Mul, BO->getOperand(0),
924                                         *BOOp << *CUI);
925     
926
927     // If the operand is an bitwise operator with a constant RHS, and the
928     // shift is the only use, we can pull it out of the shift.
929     if (Op0->use_size() == 1)
930       if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
931         if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
932           bool isValid = true;     // Valid only for And, Or, Xor
933           bool highBitSet = false; // Transform if high bit of constant set?
934
935           switch (Op0BO->getOpcode()) {
936           default: isValid = false; break;   // Do not perform transform!
937           case Instruction::Or:
938           case Instruction::Xor:
939             highBitSet = false;
940             break;
941           case Instruction::And:
942             highBitSet = true;
943             break;
944           }
945
946           // If this is a signed shift right, and the high bit is modified
947           // by the logical operation, do not perform the transformation.
948           // The highBitSet boolean indicates the value of the high bit of
949           // the constant which would cause it to be modified for this
950           // operation.
951           //
952           if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
953             uint64_t Val = Op0C->getRawValue();
954             isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
955           }
956
957           if (isValid) {
958             Constant *NewRHS =
959               ConstantFoldShiftInstruction(I.getOpcode(), Op0C, CUI);
960
961             Instruction *NewShift =
962               new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
963                             Op0BO->getName());
964             Op0BO->setName("");
965             InsertNewInstBefore(NewShift, I);
966
967             return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
968                                           NewRHS);
969           }
970         }
971
972     // If this is a shift of a shift, see if we can fold the two together...
973     if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
974       if (ConstantUInt *ShiftAmt1C =
975                                  dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
976         unsigned ShiftAmt1 = ShiftAmt1C->getValue();
977         unsigned ShiftAmt2 = CUI->getValue();
978         
979         // Check for (A << c1) << c2   and   (A >> c1) >> c2
980         if (I.getOpcode() == Op0SI->getOpcode()) {
981           unsigned Amt = ShiftAmt1+ShiftAmt2;   // Fold into one big shift...
982           return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
983                                ConstantUInt::get(Type::UByteTy, Amt));
984         }
985         
986         // Check for (A << c1) >> c2 or visaversa.  If we are dealing with
987         // signed types, we can only support the (A >> c1) << c2 configuration,
988         // because it can not turn an arbitrary bit of A into a sign bit.
989         if (I.getType()->isUnsigned() || isLeftShift) {
990           // Calculate bitmask for what gets shifted off the edge...
991           Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
992           if (isLeftShift)
993             C = ConstantExpr::getShift(Instruction::Shl, C, ShiftAmt1C);
994           else
995             C = ConstantExpr::getShift(Instruction::Shr, C, ShiftAmt1C);
996           
997           Instruction *Mask =
998             BinaryOperator::create(Instruction::And, Op0SI->getOperand(0),
999                                    C, Op0SI->getOperand(0)->getName()+".mask");
1000           InsertNewInstBefore(Mask, I);
1001           
1002           // Figure out what flavor of shift we should use...
1003           if (ShiftAmt1 == ShiftAmt2)
1004             return ReplaceInstUsesWith(I, Mask);  // (A << c) >> c  === A & c2
1005           else if (ShiftAmt1 < ShiftAmt2) {
1006             return new ShiftInst(I.getOpcode(), Mask,
1007                          ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
1008           } else {
1009             return new ShiftInst(Op0SI->getOpcode(), Mask,
1010                          ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
1011           }
1012         }
1013       }
1014   }
1015
1016   return 0;
1017 }
1018
1019
1020 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
1021 // instruction.
1022 //
1023 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
1024                                           const Type *DstTy) {
1025
1026   // It is legal to eliminate the instruction if casting A->B->A if the sizes
1027   // are identical and the bits don't get reinterpreted (for example 
1028   // int->float->int would not be allowed)
1029   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
1030     return true;
1031
1032   // Allow free casting and conversion of sizes as long as the sign doesn't
1033   // change...
1034   if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
1035     unsigned SrcSize = SrcTy->getPrimitiveSize();
1036     unsigned MidSize = MidTy->getPrimitiveSize();
1037     unsigned DstSize = DstTy->getPrimitiveSize();
1038
1039     // Cases where we are monotonically decreasing the size of the type are
1040     // always ok, regardless of what sign changes are going on.
1041     //
1042     if (SrcSize >= MidSize && MidSize >= DstSize)
1043       return true;
1044
1045     // Cases where the source and destination type are the same, but the middle
1046     // type is bigger are noops.
1047     //
1048     if (SrcSize == DstSize && MidSize > SrcSize)
1049       return true;
1050
1051     // If we are monotonically growing, things are more complex.
1052     //
1053     if (SrcSize <= MidSize && MidSize <= DstSize) {
1054       // We have eight combinations of signedness to worry about. Here's the
1055       // table:
1056       static const int SignTable[8] = {
1057         // CODE, SrcSigned, MidSigned, DstSigned, Comment
1058         1,     //   U          U          U       Always ok
1059         1,     //   U          U          S       Always ok
1060         3,     //   U          S          U       Ok iff SrcSize != MidSize
1061         3,     //   U          S          S       Ok iff SrcSize != MidSize
1062         0,     //   S          U          U       Never ok
1063         2,     //   S          U          S       Ok iff MidSize == DstSize
1064         1,     //   S          S          U       Always ok
1065         1,     //   S          S          S       Always ok
1066       };
1067
1068       // Choose an action based on the current entry of the signtable that this
1069       // cast of cast refers to...
1070       unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
1071       switch (SignTable[Row]) {
1072       case 0: return false;              // Never ok
1073       case 1: return true;               // Always ok
1074       case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
1075       case 3:                            // Ok iff SrcSize != MidSize
1076         return SrcSize != MidSize || SrcTy == Type::BoolTy;
1077       default: assert(0 && "Bad entry in sign table!");
1078       }
1079     }
1080   }
1081
1082   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
1083   // like:  short -> ushort -> uint, because this can create wrong results if
1084   // the input short is negative!
1085   //
1086   return false;
1087 }
1088
1089 static bool ValueRequiresCast(const Value *V, const Type *Ty) {
1090   if (V->getType() == Ty || isa<Constant>(V)) return false;
1091   if (const CastInst *CI = dyn_cast<CastInst>(V))
1092     if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty))
1093       return false;
1094   return true;
1095 }
1096
1097 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
1098 /// InsertBefore instruction.  This is specialized a bit to avoid inserting
1099 /// casts that are known to not do anything...
1100 ///
1101 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
1102                                              Instruction *InsertBefore) {
1103   if (V->getType() == DestTy) return V;
1104   if (Constant *C = dyn_cast<Constant>(V))
1105     return ConstantExpr::getCast(C, DestTy);
1106
1107   CastInst *CI = new CastInst(V, DestTy, V->getName());
1108   InsertNewInstBefore(CI, *InsertBefore);
1109   return CI;
1110 }
1111
1112 // CastInst simplification
1113 //
1114 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
1115   Value *Src = CI.getOperand(0);
1116
1117   // If the user is casting a value to the same type, eliminate this cast
1118   // instruction...
1119   if (CI.getType() == Src->getType())
1120     return ReplaceInstUsesWith(CI, Src);
1121
1122   // If casting the result of another cast instruction, try to eliminate this
1123   // one!
1124   //
1125   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {
1126     if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(),
1127                                CSrc->getType(), CI.getType())) {
1128       // This instruction now refers directly to the cast's src operand.  This
1129       // has a good chance of making CSrc dead.
1130       CI.setOperand(0, CSrc->getOperand(0));
1131       return &CI;
1132     }
1133
1134     // If this is an A->B->A cast, and we are dealing with integral types, try
1135     // to convert this into a logical 'and' instruction.
1136     //
1137     if (CSrc->getOperand(0)->getType() == CI.getType() &&
1138         CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
1139         CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
1140         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
1141       assert(CSrc->getType() != Type::ULongTy &&
1142              "Cannot have type bigger than ulong!");
1143       uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
1144       Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
1145       return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
1146                                     AndOp);
1147     }
1148   }
1149
1150   // If casting the result of a getelementptr instruction with no offset, turn
1151   // this into a cast of the original pointer!
1152   //
1153   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
1154     bool AllZeroOperands = true;
1155     for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
1156       if (!isa<Constant>(GEP->getOperand(i)) ||
1157           !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
1158         AllZeroOperands = false;
1159         break;
1160       }
1161     if (AllZeroOperands) {
1162       CI.setOperand(0, GEP->getOperand(0));
1163       return &CI;
1164     }
1165   }
1166
1167   // If this is a cast to bool (which is effectively a "!=0" test), then we can
1168   // perform a few optimizations...
1169   //
1170   if (CI.getType() == Type::BoolTy) {
1171     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Src)) {
1172       Value *Op0 = BO->getOperand(0), *Op1 = BO->getOperand(1);
1173
1174       switch (BO->getOpcode()) {
1175       case Instruction::Sub:
1176       case Instruction::Xor:
1177         // Replace (cast ([sub|xor] A, B) to bool) with (setne A, B)
1178         return new SetCondInst(Instruction::SetNE, Op0, Op1);
1179
1180       // Replace (cast (add A, B) to bool) with (setne A, -B) if B is
1181       // efficiently invertible, or if the add has just this one use.
1182       case Instruction::Add:
1183         if (Value *NegVal = dyn_castNegVal(Op1))
1184           return new SetCondInst(Instruction::SetNE, Op0, NegVal);
1185         else if (Value *NegVal = dyn_castNegVal(Op0))
1186           return new SetCondInst(Instruction::SetNE, NegVal, Op1);
1187         else if (BO->use_size() == 1) {
1188           Instruction *Neg = BinaryOperator::createNeg(Op1, BO->getName());
1189           BO->setName("");
1190           InsertNewInstBefore(Neg, CI);
1191           return new SetCondInst(Instruction::SetNE, Op0, Neg);
1192         }
1193         break;
1194
1195       case Instruction::And:
1196         // Replace (cast (and X, (1 << size(X)-1)) to bool) with x < 0,
1197         // converting X to be a signed value as appropriate.  Don't worry about
1198         // bool values, as they will be optimized other ways if they occur in
1199         // this configuration.
1200         if (ConstantInt *CInt = dyn_cast<ConstantInt>(Op1))
1201           if (isSignBit(CInt)) {
1202             // If 'X' is not signed, insert a cast now...
1203             if (!CInt->getType()->isSigned()) {
1204               const Type *DestTy;
1205               switch (CInt->getType()->getPrimitiveID()) {
1206               case Type::UByteTyID:  DestTy = Type::SByteTy; break;
1207               case Type::UShortTyID: DestTy = Type::ShortTy; break;
1208               case Type::UIntTyID:   DestTy = Type::IntTy;   break;
1209               case Type::ULongTyID:  DestTy = Type::LongTy;  break;
1210               default: assert(0 && "Invalid unsigned integer type!"); abort();
1211               }
1212               CastInst *NewCI = new CastInst(Op0, DestTy,
1213                                              Op0->getName()+".signed");
1214               InsertNewInstBefore(NewCI, CI);
1215               Op0 = NewCI;
1216             }
1217             return new SetCondInst(Instruction::SetLT, Op0,
1218                                    Constant::getNullValue(Op0->getType()));
1219           }
1220         break;
1221       default: break;
1222       }
1223     }
1224   }
1225
1226   // If the source value is an instruction with only this use, we can attempt to
1227   // propagate the cast into the instruction.  Also, only handle integral types
1228   // for now.
1229   if (Instruction *SrcI = dyn_cast<Instruction>(Src))
1230     if (SrcI->use_size() == 1 && Src->getType()->isIntegral() &&
1231         CI.getType()->isInteger()) {  // Don't mess with casts to bool here
1232       const Type *DestTy = CI.getType();
1233       unsigned SrcBitSize = getTypeSizeInBits(Src->getType());
1234       unsigned DestBitSize = getTypeSizeInBits(DestTy);
1235
1236       Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
1237       Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
1238
1239       switch (SrcI->getOpcode()) {
1240       case Instruction::Add:
1241       case Instruction::Mul:
1242       case Instruction::And:
1243       case Instruction::Or:
1244       case Instruction::Xor:
1245         // If we are discarding information, or just changing the sign, rewrite.
1246         if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
1247           // Don't insert two casts if they cannot be eliminated.  We allow two
1248           // casts to be inserted if the sizes are the same.  This could only be
1249           // converting signedness, which is a noop.
1250           if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) ||
1251               !ValueRequiresCast(Op0, DestTy)) {
1252             Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
1253             Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
1254             return BinaryOperator::create(cast<BinaryOperator>(SrcI)
1255                              ->getOpcode(), Op0c, Op1c);
1256           }
1257         }
1258         break;
1259       case Instruction::Shl:
1260         // Allow changing the sign of the source operand.  Do not allow changing
1261         // the size of the shift, UNLESS the shift amount is a constant.  We
1262         // mush not change variable sized shifts to a smaller size, because it
1263         // is undefined to shift more bits out than exist in the value.
1264         if (DestBitSize == SrcBitSize ||
1265             (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
1266           Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
1267           return new ShiftInst(Instruction::Shl, Op0c, Op1);
1268         }
1269         break;
1270       }
1271     }
1272   
1273   return 0;
1274 }
1275
1276 // CallInst simplification
1277 //
1278 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
1279   if (transformConstExprCastCall(&CI)) return 0;
1280   return 0;
1281 }
1282
1283 // InvokeInst simplification
1284 //
1285 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
1286   if (transformConstExprCastCall(&II)) return 0;
1287   return 0;
1288 }
1289
1290 // getPromotedType - Return the specified type promoted as it would be to pass
1291 // though a va_arg area...
1292 static const Type *getPromotedType(const Type *Ty) {
1293   switch (Ty->getPrimitiveID()) {
1294   case Type::SByteTyID:
1295   case Type::ShortTyID:  return Type::IntTy;
1296   case Type::UByteTyID:
1297   case Type::UShortTyID: return Type::UIntTy;
1298   case Type::FloatTyID:  return Type::DoubleTy;
1299   default:               return Ty;
1300   }
1301 }
1302
1303 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
1304 // attempt to move the cast to the arguments of the call/invoke.
1305 //
1306 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
1307   if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
1308   ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
1309   if (CE->getOpcode() != Instruction::Cast ||
1310       !isa<ConstantPointerRef>(CE->getOperand(0)))
1311     return false;
1312   ConstantPointerRef *CPR = cast<ConstantPointerRef>(CE->getOperand(0));
1313   if (!isa<Function>(CPR->getValue())) return false;
1314   Function *Callee = cast<Function>(CPR->getValue());
1315   Instruction *Caller = CS.getInstruction();
1316
1317   // Okay, this is a cast from a function to a different type.  Unless doing so
1318   // would cause a type conversion of one of our arguments, change this call to
1319   // be a direct call with arguments casted to the appropriate types.
1320   //
1321   const FunctionType *FT = Callee->getFunctionType();
1322   const Type *OldRetTy = Caller->getType();
1323
1324   if (Callee->isExternal() &&
1325       !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()))
1326     return false;   // Cannot transform this return value...
1327
1328   unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
1329   unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
1330                                     
1331   CallSite::arg_iterator AI = CS.arg_begin();
1332   for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
1333     const Type *ParamTy = FT->getParamType(i);
1334     bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
1335     if (Callee->isExternal() && !isConvertible) return false;    
1336   }
1337
1338   if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
1339       Callee->isExternal())
1340     return false;   // Do not delete arguments unless we have a function body...
1341
1342   // Okay, we decided that this is a safe thing to do: go ahead and start
1343   // inserting cast instructions as necessary...
1344   std::vector<Value*> Args;
1345   Args.reserve(NumActualArgs);
1346
1347   AI = CS.arg_begin();
1348   for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
1349     const Type *ParamTy = FT->getParamType(i);
1350     if ((*AI)->getType() == ParamTy) {
1351       Args.push_back(*AI);
1352     } else {
1353       Instruction *Cast = new CastInst(*AI, ParamTy, "tmp");
1354       InsertNewInstBefore(Cast, *Caller);
1355       Args.push_back(Cast);
1356     }
1357   }
1358
1359   // If the function takes more arguments than the call was taking, add them
1360   // now...
1361   for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
1362     Args.push_back(Constant::getNullValue(FT->getParamType(i)));
1363
1364   // If we are removing arguments to the function, emit an obnoxious warning...
1365   if (FT->getNumParams() < NumActualArgs)
1366     if (!FT->isVarArg()) {
1367       std::cerr << "WARNING: While resolving call to function '"
1368                 << Callee->getName() << "' arguments were dropped!\n";
1369     } else {
1370       // Add all of the arguments in their promoted form to the arg list...
1371       for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
1372         const Type *PTy = getPromotedType((*AI)->getType());
1373         if (PTy != (*AI)->getType()) {
1374           // Must promote to pass through va_arg area!
1375           Instruction *Cast = new CastInst(*AI, PTy, "tmp");
1376           InsertNewInstBefore(Cast, *Caller);
1377           Args.push_back(Cast);
1378         } else {
1379           Args.push_back(*AI);
1380         }
1381       }
1382     }
1383
1384   if (FT->getReturnType() == Type::VoidTy)
1385     Caller->setName("");   // Void type should not have a name...
1386
1387   Instruction *NC;
1388   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
1389     NC = new InvokeInst(Callee, II->getNormalDest(), II->getExceptionalDest(),
1390                         Args, Caller->getName(), Caller);
1391   } else {
1392     NC = new CallInst(Callee, Args, Caller->getName(), Caller);
1393   }
1394
1395   // Insert a cast of the return type as necessary...
1396   Value *NV = NC;
1397   if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
1398     if (NV->getType() != Type::VoidTy) {
1399       NV = NC = new CastInst(NC, Caller->getType(), "tmp");
1400       InsertNewInstBefore(NC, *Caller);
1401       AddUsesToWorkList(*Caller);
1402     } else {
1403       NV = Constant::getNullValue(Caller->getType());
1404     }
1405   }
1406
1407   if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
1408     Caller->replaceAllUsesWith(NV);
1409   Caller->getParent()->getInstList().erase(Caller);
1410   removeFromWorkList(Caller);
1411   return true;
1412 }
1413
1414
1415
1416 // PHINode simplification
1417 //
1418 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
1419   // If the PHI node only has one incoming value, eliminate the PHI node...
1420   if (PN.getNumIncomingValues() == 1)
1421     return ReplaceInstUsesWith(PN, PN.getIncomingValue(0));
1422   
1423   // Otherwise if all of the incoming values are the same for the PHI, replace
1424   // the PHI node with the incoming value.
1425   //
1426   Value *InVal = 0;
1427   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1428     if (PN.getIncomingValue(i) != &PN)  // Not the PHI node itself...
1429       if (InVal && PN.getIncomingValue(i) != InVal)
1430         return 0;  // Not the same, bail out.
1431       else
1432         InVal = PN.getIncomingValue(i);
1433
1434   // The only case that could cause InVal to be null is if we have a PHI node
1435   // that only has entries for itself.  In this case, there is no entry into the
1436   // loop, so kill the PHI.
1437   //
1438   if (InVal == 0) InVal = Constant::getNullValue(PN.getType());
1439
1440   // All of the incoming values are the same, replace the PHI node now.
1441   return ReplaceInstUsesWith(PN, InVal);
1442 }
1443
1444
1445 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
1446   // Is it 'getelementptr %P, long 0'  or 'getelementptr %P'
1447   // If so, eliminate the noop.
1448   if ((GEP.getNumOperands() == 2 &&
1449        GEP.getOperand(1) == Constant::getNullValue(Type::LongTy)) ||
1450       GEP.getNumOperands() == 1)
1451     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
1452
1453   // Combine Indices - If the source pointer to this getelementptr instruction
1454   // is a getelementptr instruction, combine the indices of the two
1455   // getelementptr instructions into a single instruction.
1456   //
1457   if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
1458     std::vector<Value *> Indices;
1459   
1460     // Can we combine the two pointer arithmetics offsets?
1461     if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) &&
1462         isa<Constant>(GEP.getOperand(1))) {
1463       // Replace: gep (gep %P, long C1), long C2, ...
1464       // With:    gep %P, long (C1+C2), ...
1465       Value *Sum = ConstantExpr::get(Instruction::Add,
1466                                      cast<Constant>(Src->getOperand(1)),
1467                                      cast<Constant>(GEP.getOperand(1)));
1468       assert(Sum && "Constant folding of longs failed!?");
1469       GEP.setOperand(0, Src->getOperand(0));
1470       GEP.setOperand(1, Sum);
1471       AddUsesToWorkList(*Src);   // Reduce use count of Src
1472       return &GEP;
1473     } else if (Src->getNumOperands() == 2) {
1474       // Replace: gep (gep %P, long B), long A, ...
1475       // With:    T = long A+B; gep %P, T, ...
1476       //
1477       Value *Sum = BinaryOperator::create(Instruction::Add, Src->getOperand(1),
1478                                           GEP.getOperand(1),
1479                                           Src->getName()+".sum", &GEP);
1480       GEP.setOperand(0, Src->getOperand(0));
1481       GEP.setOperand(1, Sum);
1482       WorkList.push_back(cast<Instruction>(Sum));
1483       return &GEP;
1484     } else if (*GEP.idx_begin() == Constant::getNullValue(Type::LongTy) &&
1485                Src->getNumOperands() != 1) { 
1486       // Otherwise we can do the fold if the first index of the GEP is a zero
1487       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
1488       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
1489     } else if (Src->getOperand(Src->getNumOperands()-1) == 
1490                Constant::getNullValue(Type::LongTy)) {
1491       // If the src gep ends with a constant array index, merge this get into
1492       // it, even if we have a non-zero array index.
1493       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end()-1);
1494       Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
1495     }
1496
1497     if (!Indices.empty())
1498       return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
1499
1500   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
1501     // GEP of global variable.  If all of the indices for this GEP are
1502     // constants, we can promote this to a constexpr instead of an instruction.
1503
1504     // Scan for nonconstants...
1505     std::vector<Constant*> Indices;
1506     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
1507     for (; I != E && isa<Constant>(*I); ++I)
1508       Indices.push_back(cast<Constant>(*I));
1509
1510     if (I == E) {  // If they are all constants...
1511       Constant *CE =
1512         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
1513
1514       // Replace all uses of the GEP with the new constexpr...
1515       return ReplaceInstUsesWith(GEP, CE);
1516     }
1517   }
1518
1519   return 0;
1520 }
1521
1522 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
1523   // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
1524   if (AI.isArrayAllocation())    // Check C != 1
1525     if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
1526       const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
1527       AllocationInst *New = 0;
1528
1529       // Create and insert the replacement instruction...
1530       if (isa<MallocInst>(AI))
1531         New = new MallocInst(NewTy, 0, AI.getName(), &AI);
1532       else {
1533         assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
1534         New = new AllocaInst(NewTy, 0, AI.getName(), &AI);
1535       }
1536       
1537       // Scan to the end of the allocation instructions, to skip over a block of
1538       // allocas if possible...
1539       //
1540       BasicBlock::iterator It = New;
1541       while (isa<AllocationInst>(*It)) ++It;
1542
1543       // Now that I is pointing to the first non-allocation-inst in the block,
1544       // insert our getelementptr instruction...
1545       //
1546       std::vector<Value*> Idx(2, Constant::getNullValue(Type::LongTy));
1547       Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It);
1548
1549       // Now make everything use the getelementptr instead of the original
1550       // allocation.
1551       ReplaceInstUsesWith(AI, V);
1552       return &AI;
1553     }
1554   return 0;
1555 }
1556
1557 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
1558 /// constantexpr, return the constant value being addressed by the constant
1559 /// expression, or null if something is funny.
1560 ///
1561 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
1562   if (CE->getOperand(1) != Constant::getNullValue(Type::LongTy))
1563     return 0;  // Do not allow stepping over the value!
1564
1565   // Loop over all of the operands, tracking down which value we are
1566   // addressing...
1567   for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
1568     if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
1569       ConstantStruct *CS = cast<ConstantStruct>(C);
1570       if (CU->getValue() >= CS->getValues().size()) return 0;
1571       C = cast<Constant>(CS->getValues()[CU->getValue()]);
1572     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
1573       ConstantArray *CA = cast<ConstantArray>(C);
1574       if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0;
1575       C = cast<Constant>(CA->getValues()[CS->getValue()]);
1576     } else 
1577       return 0;
1578   return C;
1579 }
1580
1581 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
1582   Value *Op = LI.getOperand(0);
1583   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Op))
1584     Op = CPR->getValue();
1585
1586   // Instcombine load (constant global) into the value loaded...
1587   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
1588     if (GV->isConstant() && !GV->isExternal())
1589       return ReplaceInstUsesWith(LI, GV->getInitializer());
1590
1591   // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded...
1592   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
1593     if (CE->getOpcode() == Instruction::GetElementPtr)
1594       if (ConstantPointerRef *G=dyn_cast<ConstantPointerRef>(CE->getOperand(0)))
1595         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getValue()))
1596           if (GV->isConstant() && !GV->isExternal())
1597             if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
1598               return ReplaceInstUsesWith(LI, V);
1599   return 0;
1600 }
1601
1602
1603 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
1604   // Change br (not X), label True, label False to: br X, label False, True
1605   if (BI.isConditional() && !isa<Constant>(BI.getCondition()))
1606     if (Value *V = dyn_castNotVal(BI.getCondition())) {
1607       BasicBlock *TrueDest = BI.getSuccessor(0);
1608       BasicBlock *FalseDest = BI.getSuccessor(1);
1609       // Swap Destinations and condition...
1610       BI.setCondition(V);
1611       BI.setSuccessor(0, FalseDest);
1612       BI.setSuccessor(1, TrueDest);
1613       return &BI;
1614     }
1615   return 0;
1616 }
1617
1618
1619 void InstCombiner::removeFromWorkList(Instruction *I) {
1620   WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
1621                  WorkList.end());
1622 }
1623
1624 bool InstCombiner::runOnFunction(Function &F) {
1625   bool Changed = false;
1626
1627   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
1628
1629   while (!WorkList.empty()) {
1630     Instruction *I = WorkList.back();  // Get an instruction from the worklist
1631     WorkList.pop_back();
1632
1633     // Check to see if we can DCE or ConstantPropagate the instruction...
1634     // Check to see if we can DIE the instruction...
1635     if (isInstructionTriviallyDead(I)) {
1636       // Add operands to the worklist...
1637       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1638         if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
1639           WorkList.push_back(Op);
1640
1641       ++NumDeadInst;
1642       BasicBlock::iterator BBI = I;
1643       if (dceInstruction(BBI)) {
1644         removeFromWorkList(I);
1645         continue;
1646       }
1647     } 
1648
1649     // Instruction isn't dead, see if we can constant propagate it...
1650     if (Constant *C = ConstantFoldInstruction(I)) {
1651       // Add operands to the worklist...
1652       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1653         if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
1654           WorkList.push_back(Op);
1655       ReplaceInstUsesWith(*I, C);
1656
1657       ++NumConstProp;
1658       BasicBlock::iterator BBI = I;
1659       if (dceInstruction(BBI)) {
1660         removeFromWorkList(I);
1661         continue;
1662       }
1663     }
1664     
1665     // Now that we have an instruction, try combining it to simplify it...
1666     if (Instruction *Result = visit(*I)) {
1667       ++NumCombined;
1668       // Should we replace the old instruction with a new one?
1669       if (Result != I) {
1670         // Instructions can end up on the worklist more than once.  Make sure
1671         // we do not process an instruction that has been deleted.
1672         removeFromWorkList(I);
1673         ReplaceInstWithInst(I, Result);
1674       } else {
1675         BasicBlock::iterator II = I;
1676
1677         // If the instruction was modified, it's possible that it is now dead.
1678         // if so, remove it.
1679         if (dceInstruction(II)) {
1680           // Instructions may end up in the worklist more than once.  Erase them
1681           // all.
1682           removeFromWorkList(I);
1683           Result = 0;
1684         }
1685       }
1686
1687       if (Result) {
1688         WorkList.push_back(Result);
1689         AddUsesToWorkList(*Result);
1690       }
1691       Changed = true;
1692     }
1693   }
1694
1695   return Changed;
1696 }
1697
1698 Pass *createInstructionCombiningPass() {
1699   return new InstCombiner();
1700 }