Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 1 | //===- InstructionCombining.cpp - Combine multiple instructions -----------===// |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 2 | // |
| 3 | // InstructionCombining - Combine instructions to form fewer, simple |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 4 | // instructions. This pass does not modify the CFG This pass is where algebraic |
| 5 | // simplification happens. |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 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 | //===----------------------------------------------------------------------===// |
| 16 | |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 497c60c | 2002-05-07 18:12:18 +0000 | [diff] [blame] | 18 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 19 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 968ddc9 | 2002-04-08 20:18:09 +0000 | [diff] [blame] | 20 | #include "llvm/ConstantHandling.h" |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 21 | #include "llvm/iMemory.h" |
Chris Lattner | 8d70cd9 | 2002-04-15 19:45:29 +0000 | [diff] [blame] | 22 | #include "llvm/iOther.h" |
Chris Lattner | 473945d | 2002-05-06 18:06:38 +0000 | [diff] [blame] | 23 | #include "llvm/iPHINode.h" |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 24 | #include "llvm/iOperators.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 25 | #include "llvm/Pass.h" |
Chris Lattner | 221d688 | 2002-02-12 21:07:25 +0000 | [diff] [blame] | 26 | #include "llvm/Support/InstIterator.h" |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 27 | #include "llvm/Support/InstVisitor.h" |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 28 | #include "Support/StatisticReporter.h" |
Chris Lattner | b3bc8fa | 2002-05-14 15:24:07 +0000 | [diff] [blame] | 29 | #include <algorithm> |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 30 | |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 31 | static Statistic<> NumCombined ("instcombine\t- Number of insts combined"); |
| 32 | static Statistic<> NumConstProp("instcombine\t- Number of constant folds"); |
| 33 | static Statistic<> NumDeadInst ("instcombine\t- Number of dead inst eliminate"); |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 34 | |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 35 | namespace { |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 36 | class InstCombiner : public FunctionPass, |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 37 | public InstVisitor<InstCombiner, Instruction*> { |
| 38 | // Worklist of all of the instructions that need to be simplified. |
| 39 | std::vector<Instruction*> WorkList; |
| 40 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 41 | void AddUsesToWorkList(Instruction &I) { |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 42 | // The instruction was simplified, add all users of the instruction to |
| 43 | // the work lists because they might get more simplified now... |
| 44 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 45 | for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 46 | UI != UE; ++UI) |
| 47 | WorkList.push_back(cast<Instruction>(*UI)); |
| 48 | } |
| 49 | |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 50 | // removeFromWorkList - remove all instances of I from the worklist. |
| 51 | void removeFromWorkList(Instruction *I); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 52 | public: |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 53 | virtual bool runOnFunction(Function &F); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 54 | |
Chris Lattner | 97e52e4 | 2002-04-28 21:27:06 +0000 | [diff] [blame] | 55 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 56 | AU.preservesCFG(); |
| 57 | } |
| 58 | |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 59 | // Visitation implementation - Implement instruction combining for different |
| 60 | // instruction types. The semantics are as follows: |
| 61 | // Return Value: |
| 62 | // null - No change was made |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 63 | // I - Change was made, I is still valid, I may be dead though |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 64 | // otherwise - Change was made, replace I with returned instruction |
| 65 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 66 | Instruction *visitAdd(BinaryOperator &I); |
| 67 | Instruction *visitSub(BinaryOperator &I); |
| 68 | Instruction *visitMul(BinaryOperator &I); |
| 69 | Instruction *visitDiv(BinaryOperator &I); |
| 70 | Instruction *visitRem(BinaryOperator &I); |
| 71 | Instruction *visitAnd(BinaryOperator &I); |
| 72 | Instruction *visitOr (BinaryOperator &I); |
| 73 | Instruction *visitXor(BinaryOperator &I); |
| 74 | Instruction *visitSetCondInst(BinaryOperator &I); |
| 75 | Instruction *visitShiftInst(Instruction &I); |
| 76 | Instruction *visitCastInst(CastInst &CI); |
| 77 | Instruction *visitPHINode(PHINode &PN); |
| 78 | Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 79 | |
| 80 | // visitInstruction - Specify what to return for unhandled instructions... |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 81 | Instruction *visitInstruction(Instruction &I) { return 0; } |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 82 | |
| 83 | // InsertNewInstBefore - insert an instruction New before instruction Old |
| 84 | // in the program. Add the new instruction to the worklist. |
| 85 | // |
| 86 | void InsertNewInstBefore(Instruction *New, Instruction &Old) { |
Chris Lattner | e6f9a91 | 2002-08-23 18:32:43 +0000 | [diff] [blame] | 87 | assert(New && New->getParent() == 0 && |
| 88 | "New instruction already inserted into a basic block!"); |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 89 | BasicBlock *BB = Old.getParent(); |
| 90 | BB->getInstList().insert(&Old, New); // Insert inst |
| 91 | WorkList.push_back(New); // Add to worklist |
| 92 | } |
| 93 | |
| 94 | // ReplaceInstUsesWith - This method is to be used when an instruction is |
| 95 | // found to be dead, replacable with another preexisting expression. Here |
| 96 | // we add all uses of I to the worklist, replace all uses of I with the new |
| 97 | // value, then return I, so that the inst combiner will know that I was |
| 98 | // modified. |
| 99 | // |
| 100 | Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) { |
| 101 | AddUsesToWorkList(I); // Add all modified instrs to worklist |
| 102 | I.replaceAllUsesWith(V); |
| 103 | return &I; |
| 104 | } |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 105 | }; |
Chris Lattner | f629309 | 2002-07-23 18:06:35 +0000 | [diff] [blame] | 106 | |
Chris Lattner | a6275cc | 2002-07-26 21:12:46 +0000 | [diff] [blame] | 107 | RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions"); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 108 | } |
| 109 | |
| 110 | |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 111 | // Make sure that this instruction has a constant on the right hand side if it |
| 112 | // has any constant arguments. If not, fix it an return true. |
| 113 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 114 | static bool SimplifyBinOp(BinaryOperator &I) { |
| 115 | if (isa<Constant>(I.getOperand(0)) && !isa<Constant>(I.getOperand(1))) |
| 116 | return !I.swapOperands(); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 117 | return false; |
| 118 | } |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 119 | |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 120 | // dyn_castNegInst - Given a 'sub' instruction, return the RHS of the |
| 121 | // instruction if the LHS is a constant zero (which is the 'negate' form). |
| 122 | // |
| 123 | static inline Value *dyn_castNegInst(Value *V) { |
| 124 | Instruction *I = dyn_cast<Instruction>(V); |
| 125 | if (!I || I->getOpcode() != Instruction::Sub) return 0; |
| 126 | |
| 127 | if (I->getOperand(0) == Constant::getNullValue(I->getType())) |
| 128 | return I->getOperand(1); |
| 129 | return 0; |
| 130 | } |
| 131 | |
Chris Lattner | af2930e | 2002-08-14 17:51:49 +0000 | [diff] [blame] | 132 | static inline Value *dyn_castNotInst(Value *V) { |
| 133 | Instruction *I = dyn_cast<Instruction>(V); |
| 134 | if (!I || I->getOpcode() != Instruction::Xor) return 0; |
| 135 | |
| 136 | if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(I->getOperand(1))) |
| 137 | if (CI->isAllOnesValue()) |
| 138 | return I->getOperand(0); |
| 139 | return 0; |
| 140 | } |
| 141 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 142 | Instruction *InstCombiner::visitAdd(BinaryOperator &I) { |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 143 | bool Changed = SimplifyBinOp(I); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 144 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 145 | |
| 146 | // Eliminate 'add int %X, 0' |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 147 | if (RHS == Constant::getNullValue(I.getType())) |
| 148 | return ReplaceInstUsesWith(I, LHS); |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 149 | |
Chris Lattner | 5c4afb9 | 2002-05-08 22:46:53 +0000 | [diff] [blame] | 150 | // -A + B --> B - A |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 151 | if (Value *V = dyn_castNegInst(LHS)) |
Chris Lattner | 5c4afb9 | 2002-05-08 22:46:53 +0000 | [diff] [blame] | 152 | return BinaryOperator::create(Instruction::Sub, RHS, V); |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 153 | |
| 154 | // A + -B --> A - B |
| 155 | if (Value *V = dyn_castNegInst(RHS)) |
Chris Lattner | 5c4afb9 | 2002-05-08 22:46:53 +0000 | [diff] [blame] | 156 | return BinaryOperator::create(Instruction::Sub, LHS, V); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 157 | |
| 158 | // Simplify add instructions with a constant RHS... |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 159 | if (Constant *Op2 = dyn_cast<Constant>(RHS)) { |
| 160 | if (BinaryOperator *ILHS = dyn_cast<BinaryOperator>(LHS)) { |
| 161 | if (ILHS->getOpcode() == Instruction::Add && |
| 162 | isa<Constant>(ILHS->getOperand(1))) { |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 163 | // Fold: |
| 164 | // %Y = add int %X, 1 |
| 165 | // %Z = add int %Y, 1 |
| 166 | // into: |
| 167 | // %Z = add int %X, 2 |
| 168 | // |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 169 | if (Constant *Val = *Op2 + *cast<Constant>(ILHS->getOperand(1))) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 170 | I.setOperand(0, ILHS->getOperand(0)); |
| 171 | I.setOperand(1, Val); |
| 172 | return &I; |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 173 | } |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 174 | } |
| 175 | } |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 176 | } |
| 177 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 178 | return Changed ? &I : 0; |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 179 | } |
| 180 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 181 | Instruction *InstCombiner::visitSub(BinaryOperator &I) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 182 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 183 | |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 184 | if (Op0 == Op1) // sub X, X -> 0 |
| 185 | return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 186 | |
| 187 | // If this is a subtract instruction with a constant RHS, convert it to an add |
| 188 | // instruction of a negative constant |
| 189 | // |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 190 | if (Constant *Op2 = dyn_cast<Constant>(Op1)) |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 191 | if (Constant *RHS = *Constant::getNullValue(I.getType()) - *Op2) // 0 - RHS |
| 192 | return BinaryOperator::create(Instruction::Add, Op0, RHS, I.getName()); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 193 | |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 194 | // If this is a 'B = x-(-A)', change to B = x+A... |
Chris Lattner | 5c4afb9 | 2002-05-08 22:46:53 +0000 | [diff] [blame] | 195 | if (Value *V = dyn_castNegInst(Op1)) |
| 196 | return BinaryOperator::create(Instruction::Add, Op0, V); |
Chris Lattner | b35dde1 | 2002-05-06 16:49:18 +0000 | [diff] [blame] | 197 | |
Chris Lattner | 4037171 | 2002-05-09 01:29:19 +0000 | [diff] [blame] | 198 | // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression is |
| 199 | // not used by anyone else... |
| 200 | // |
| 201 | if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) |
Chris Lattner | 86c25fd | 2002-05-14 16:44:07 +0000 | [diff] [blame] | 202 | if (Op1I->use_size() == 1 && Op1I->getOpcode() == Instruction::Sub) { |
Chris Lattner | 4037171 | 2002-05-09 01:29:19 +0000 | [diff] [blame] | 203 | // Swap the two operands of the subexpr... |
| 204 | Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1); |
| 205 | Op1I->setOperand(0, IIOp1); |
| 206 | Op1I->setOperand(1, IIOp0); |
| 207 | |
| 208 | // Create the new top level add instruction... |
| 209 | return BinaryOperator::create(Instruction::Add, Op0, Op1); |
| 210 | } |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 211 | return 0; |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 212 | } |
| 213 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 214 | Instruction *InstCombiner::visitMul(BinaryOperator &I) { |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 215 | bool Changed = SimplifyBinOp(I); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 216 | Value *Op1 = I.getOperand(0); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 217 | |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 218 | // Simplify mul instructions with a constant RHS... |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 219 | if (Constant *Op2 = dyn_cast<Constant>(I.getOperand(1))) { |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame^] | 220 | if (I.getType()->isInteger() && cast<ConstantInt>(Op2)->equalsInt(1)) |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 221 | return ReplaceInstUsesWith(I, Op1); // Eliminate 'mul int %X, 1' |
Chris Lattner | 6c1ce21 | 2002-04-29 22:24:47 +0000 | [diff] [blame] | 222 | |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame^] | 223 | if (I.getType()->isInteger() && cast<ConstantInt>(Op2)->equalsInt(2)) |
Chris Lattner | 6c1ce21 | 2002-04-29 22:24:47 +0000 | [diff] [blame] | 224 | // Convert 'mul int %X, 2' to 'add int %X, %X' |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 225 | return BinaryOperator::create(Instruction::Add, Op1, Op1, I.getName()); |
Chris Lattner | 6c1ce21 | 2002-04-29 22:24:47 +0000 | [diff] [blame] | 226 | |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 227 | if (Op2->isNullValue()) |
| 228 | return ReplaceInstUsesWith(I, Op2); // Eliminate 'mul int %X, 0' |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 229 | } |
| 230 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 231 | return Changed ? &I : 0; |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 232 | } |
| 233 | |
| 234 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 235 | Instruction *InstCombiner::visitDiv(BinaryOperator &I) { |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 236 | // div X, 1 == X |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 237 | if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 238 | if (RHS->equalsInt(1)) |
| 239 | return ReplaceInstUsesWith(I, I.getOperand(0)); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 240 | return 0; |
| 241 | } |
| 242 | |
| 243 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 244 | Instruction *InstCombiner::visitRem(BinaryOperator &I) { |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 245 | // rem X, 1 == 0 |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 246 | if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 247 | if (RHS->equalsInt(1)) |
| 248 | return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); |
| 249 | |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 250 | return 0; |
| 251 | } |
| 252 | |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 253 | // isMaxValueMinusOne - return true if this is Max-1 |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 254 | static bool isMaxValueMinusOne(const ConstantInt *C) { |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 255 | if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) { |
| 256 | // Calculate -1 casted to the right type... |
| 257 | unsigned TypeBits = C->getType()->getPrimitiveSize()*8; |
| 258 | uint64_t Val = ~0ULL; // All ones |
| 259 | Val >>= 64-TypeBits; // Shift out unwanted 1 bits... |
| 260 | return CU->getValue() == Val-1; |
| 261 | } |
| 262 | |
| 263 | const ConstantSInt *CS = cast<ConstantSInt>(C); |
| 264 | |
| 265 | // Calculate 0111111111..11111 |
| 266 | unsigned TypeBits = C->getType()->getPrimitiveSize()*8; |
| 267 | int64_t Val = INT64_MAX; // All ones |
| 268 | Val >>= 64-TypeBits; // Shift out unwanted 1 bits... |
| 269 | return CS->getValue() == Val-1; |
| 270 | } |
| 271 | |
| 272 | // isMinValuePlusOne - return true if this is Min+1 |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 273 | static bool isMinValuePlusOne(const ConstantInt *C) { |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 274 | if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) |
| 275 | return CU->getValue() == 1; |
| 276 | |
| 277 | const ConstantSInt *CS = cast<ConstantSInt>(C); |
| 278 | |
| 279 | // Calculate 1111111111000000000000 |
| 280 | unsigned TypeBits = C->getType()->getPrimitiveSize()*8; |
| 281 | int64_t Val = -1; // All ones |
| 282 | Val <<= TypeBits-1; // Shift over to the right spot |
| 283 | return CS->getValue() == Val+1; |
| 284 | } |
| 285 | |
| 286 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 287 | Instruction *InstCombiner::visitAnd(BinaryOperator &I) { |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 288 | bool Changed = SimplifyBinOp(I); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 289 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 290 | |
| 291 | // and X, X = X and X, 0 == 0 |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 292 | if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType())) |
| 293 | return ReplaceInstUsesWith(I, Op1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 294 | |
| 295 | // and X, -1 == X |
Chris Lattner | 572f4a0 | 2002-08-13 17:50:24 +0000 | [diff] [blame] | 296 | if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 297 | if (RHS->isAllOnesValue()) |
| 298 | return ReplaceInstUsesWith(I, Op0); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 299 | |
Chris Lattner | e6f9a91 | 2002-08-23 18:32:43 +0000 | [diff] [blame] | 300 | // and (not A), (not B) == not (or A, B) |
| 301 | if (Op0->use_size() == 1 && Op1->use_size() == 1) |
| 302 | if (Value *A = dyn_castNotInst(Op0)) |
| 303 | if (Value *B = dyn_castNotInst(Op1)) { |
| 304 | Instruction *Or = BinaryOperator::create(Instruction::Or, A, B, |
| 305 | I.getName()+".demorgan"); |
| 306 | InsertNewInstBefore(Or, I); |
| 307 | return BinaryOperator::createNot(Or, I.getName()); |
| 308 | } |
| 309 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 310 | return Changed ? &I : 0; |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 311 | } |
| 312 | |
| 313 | |
| 314 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 315 | Instruction *InstCombiner::visitOr(BinaryOperator &I) { |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 316 | bool Changed = SimplifyBinOp(I); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 317 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 318 | |
| 319 | // or X, X = X or X, 0 == X |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 320 | if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType())) |
| 321 | return ReplaceInstUsesWith(I, Op0); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 322 | |
| 323 | // or X, -1 == -1 |
Chris Lattner | 572f4a0 | 2002-08-13 17:50:24 +0000 | [diff] [blame] | 324 | if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 325 | if (RHS->isAllOnesValue()) |
| 326 | return ReplaceInstUsesWith(I, Op1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 327 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 328 | return Changed ? &I : 0; |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 329 | } |
| 330 | |
| 331 | |
| 332 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 333 | Instruction *InstCombiner::visitXor(BinaryOperator &I) { |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 334 | bool Changed = SimplifyBinOp(I); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 335 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 336 | |
| 337 | // xor X, X = 0 |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 338 | if (Op0 == Op1) |
| 339 | return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 340 | |
Chris Lattner | 572f4a0 | 2002-08-13 17:50:24 +0000 | [diff] [blame] | 341 | if (ConstantIntegral *Op1C = dyn_cast<ConstantIntegral>(Op1)) { |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 342 | // xor X, 0 == X |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 343 | if (Op1C->isNullValue()) |
| 344 | return ReplaceInstUsesWith(I, Op0); |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 345 | |
Chris Lattner | 05bd1b2 | 2002-08-20 18:24:26 +0000 | [diff] [blame] | 346 | // Is this a "NOT" instruction? |
| 347 | if (Op1C->isAllOnesValue()) { |
| 348 | // xor (xor X, -1), -1 = not (not X) = X |
Chris Lattner | af2930e | 2002-08-14 17:51:49 +0000 | [diff] [blame] | 349 | if (Value *X = dyn_castNotInst(Op0)) |
| 350 | return ReplaceInstUsesWith(I, X); |
Chris Lattner | 05bd1b2 | 2002-08-20 18:24:26 +0000 | [diff] [blame] | 351 | |
| 352 | // xor (setcc A, B), true = not (setcc A, B) = setncc A, B |
| 353 | if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0)) |
| 354 | if (SCI->use_size() == 1) |
| 355 | return new SetCondInst(SCI->getInverseCondition(), |
| 356 | SCI->getOperand(0), SCI->getOperand(1)); |
| 357 | } |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 358 | } |
| 359 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 360 | return Changed ? &I : 0; |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 361 | } |
| 362 | |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 363 | // AddOne, SubOne - Add or subtract a constant one from an integer constant... |
| 364 | static Constant *AddOne(ConstantInt *C) { |
| 365 | Constant *Result = *C + *ConstantInt::get(C->getType(), 1); |
| 366 | assert(Result && "Constant folding integer addition failed!"); |
| 367 | return Result; |
| 368 | } |
| 369 | static Constant *SubOne(ConstantInt *C) { |
| 370 | Constant *Result = *C - *ConstantInt::get(C->getType(), 1); |
| 371 | assert(Result && "Constant folding integer addition failed!"); |
| 372 | return Result; |
| 373 | } |
| 374 | |
Chris Lattner | 53a5b57 | 2002-05-09 20:11:54 +0000 | [diff] [blame] | 375 | // isTrueWhenEqual - Return true if the specified setcondinst instruction is |
| 376 | // true when both operands are equal... |
| 377 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 378 | static bool isTrueWhenEqual(Instruction &I) { |
| 379 | return I.getOpcode() == Instruction::SetEQ || |
| 380 | I.getOpcode() == Instruction::SetGE || |
| 381 | I.getOpcode() == Instruction::SetLE; |
Chris Lattner | 53a5b57 | 2002-05-09 20:11:54 +0000 | [diff] [blame] | 382 | } |
| 383 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 384 | Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 385 | bool Changed = SimplifyBinOp(I); |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 386 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
| 387 | const Type *Ty = Op0->getType(); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 388 | |
| 389 | // setcc X, X |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 390 | if (Op0 == Op1) |
| 391 | return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I))); |
Chris Lattner | 53a5b57 | 2002-05-09 20:11:54 +0000 | [diff] [blame] | 392 | |
| 393 | // setcc <global*>, 0 - Global value addresses are never null! |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 394 | if (isa<GlobalValue>(Op0) && isa<ConstantPointerNull>(Op1)) |
| 395 | return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I))); |
| 396 | |
| 397 | // setcc's with boolean values can always be turned into bitwise operations |
| 398 | if (Ty == Type::BoolTy) { |
| 399 | // If this is <, >, or !=, we can change this into a simple xor instruction |
| 400 | if (!isTrueWhenEqual(I)) |
| 401 | return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName()); |
| 402 | |
| 403 | // Otherwise we need to make a temporary intermediate instruction and insert |
| 404 | // it into the instruction stream. This is what we are after: |
| 405 | // |
| 406 | // seteq bool %A, %B -> ~(A^B) |
| 407 | // setle bool %A, %B -> ~A | B |
| 408 | // setge bool %A, %B -> A | ~B |
| 409 | // |
| 410 | if (I.getOpcode() == Instruction::SetEQ) { // seteq case |
| 411 | Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1, |
| 412 | I.getName()+"tmp"); |
| 413 | InsertNewInstBefore(Xor, I); |
Chris Lattner | af2930e | 2002-08-14 17:51:49 +0000 | [diff] [blame] | 414 | return BinaryOperator::createNot(Xor, I.getName()); |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 415 | } |
| 416 | |
| 417 | // Handle the setXe cases... |
| 418 | assert(I.getOpcode() == Instruction::SetGE || |
| 419 | I.getOpcode() == Instruction::SetLE); |
| 420 | |
| 421 | if (I.getOpcode() == Instruction::SetGE) |
| 422 | std::swap(Op0, Op1); // Change setge -> setle |
| 423 | |
| 424 | // Now we just have the SetLE case. |
Chris Lattner | af2930e | 2002-08-14 17:51:49 +0000 | [diff] [blame] | 425 | Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp"); |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 426 | InsertNewInstBefore(Not, I); |
| 427 | return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName()); |
| 428 | } |
| 429 | |
| 430 | // Check to see if we are doing one of many comparisons against constant |
| 431 | // integers at the end of their ranges... |
| 432 | // |
| 433 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { |
| 434 | // Check to see if we are comparing against the minimum or maximum value... |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 435 | if (CI->isMinValue()) { |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 436 | if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE |
| 437 | return ReplaceInstUsesWith(I, ConstantBool::False); |
| 438 | if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE |
| 439 | return ReplaceInstUsesWith(I, ConstantBool::True); |
| 440 | if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN |
| 441 | return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName()); |
| 442 | if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN |
| 443 | return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName()); |
| 444 | |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 445 | } else if (CI->isMaxValue()) { |
Chris Lattner | 8b17094 | 2002-08-09 23:47:40 +0000 | [diff] [blame] | 446 | if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE |
| 447 | return ReplaceInstUsesWith(I, ConstantBool::False); |
| 448 | if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE |
| 449 | return ReplaceInstUsesWith(I, ConstantBool::True); |
| 450 | if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX |
| 451 | return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName()); |
| 452 | if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX |
| 453 | return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName()); |
| 454 | |
| 455 | // Comparing against a value really close to min or max? |
| 456 | } else if (isMinValuePlusOne(CI)) { |
| 457 | if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN |
| 458 | return BinaryOperator::create(Instruction::SetEQ, Op0, |
| 459 | SubOne(CI), I.getName()); |
| 460 | if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN |
| 461 | return BinaryOperator::create(Instruction::SetNE, Op0, |
| 462 | SubOne(CI), I.getName()); |
| 463 | |
| 464 | } else if (isMaxValueMinusOne(CI)) { |
| 465 | if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX |
| 466 | return BinaryOperator::create(Instruction::SetEQ, Op0, |
| 467 | AddOne(CI), I.getName()); |
| 468 | if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX |
| 469 | return BinaryOperator::create(Instruction::SetNE, Op0, |
| 470 | AddOne(CI), I.getName()); |
| 471 | } |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 472 | } |
| 473 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 474 | return Changed ? &I : 0; |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 475 | } |
| 476 | |
| 477 | |
| 478 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 479 | Instruction *InstCombiner::visitShiftInst(Instruction &I) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 480 | assert(I.getOperand(1)->getType() == Type::UByteTy); |
| 481 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 482 | |
| 483 | // shl X, 0 == X and shr X, 0 == X |
| 484 | // shl 0, X == 0 and shr 0, X == 0 |
| 485 | if (Op1 == Constant::getNullValue(Type::UByteTy) || |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 486 | Op0 == Constant::getNullValue(Op0->getType())) |
| 487 | return ReplaceInstUsesWith(I, Op0); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 488 | |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 489 | // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr of |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 490 | // a signed value. |
| 491 | // |
| 492 | if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) { |
| 493 | unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8; |
| 494 | if (CUI->getValue() >= TypeBits && |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 495 | !(Op0->getType()->isSigned() && I.getOpcode() == Instruction::Shr)) |
| 496 | return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); |
Chris Lattner | 3f5b877 | 2002-05-06 16:14:14 +0000 | [diff] [blame] | 497 | } |
| 498 | return 0; |
| 499 | } |
| 500 | |
| 501 | |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 502 | // isEliminableCastOfCast - Return true if it is valid to eliminate the CI |
| 503 | // instruction. |
| 504 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 505 | static inline bool isEliminableCastOfCast(const CastInst &CI, |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 506 | const CastInst *CSrc) { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 507 | assert(CI.getOperand(0) == CSrc); |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 508 | const Type *SrcTy = CSrc->getOperand(0)->getType(); |
| 509 | const Type *MidTy = CSrc->getType(); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 510 | const Type *DstTy = CI.getType(); |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 511 | |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 512 | // It is legal to eliminate the instruction if casting A->B->A if the sizes |
| 513 | // are identical and the bits don't get reinterpreted (for example |
Chris Lattner | 5cf6f11 | 2002-08-14 23:21:10 +0000 | [diff] [blame] | 514 | // int->float->int would not be allowed) |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 515 | if (SrcTy == DstTy && SrcTy->isLosslesslyConvertableTo(MidTy)) |
| 516 | return true; |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 517 | |
| 518 | // Allow free casting and conversion of sizes as long as the sign doesn't |
| 519 | // change... |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame^] | 520 | if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) { |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 521 | unsigned SrcSize = SrcTy->getPrimitiveSize(); |
| 522 | unsigned MidSize = MidTy->getPrimitiveSize(); |
| 523 | unsigned DstSize = DstTy->getPrimitiveSize(); |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 524 | |
Chris Lattner | 3ecce66 | 2002-08-15 16:15:25 +0000 | [diff] [blame] | 525 | // Cases where we are monotonically decreasing the size of the type are |
| 526 | // always ok, regardless of what sign changes are going on. |
| 527 | // |
Chris Lattner | 5cf6f11 | 2002-08-14 23:21:10 +0000 | [diff] [blame] | 528 | if (SrcSize >= MidSize && MidSize >= DstSize) |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 529 | return true; |
Chris Lattner | 3ecce66 | 2002-08-15 16:15:25 +0000 | [diff] [blame] | 530 | |
| 531 | // If we are monotonically growing, things are more complex. |
| 532 | // |
| 533 | if (SrcSize <= MidSize && MidSize <= DstSize) { |
| 534 | // We have eight combinations of signedness to worry about. Here's the |
| 535 | // table: |
| 536 | static const int SignTable[8] = { |
| 537 | // CODE, SrcSigned, MidSigned, DstSigned, Comment |
| 538 | 1, // U U U Always ok |
| 539 | 1, // U U S Always ok |
| 540 | 3, // U S U Ok iff SrcSize != MidSize |
| 541 | 3, // U S S Ok iff SrcSize != MidSize |
| 542 | 0, // S U U Never ok |
| 543 | 2, // S U S Ok iff MidSize == DstSize |
| 544 | 1, // S S U Always ok |
| 545 | 1, // S S S Always ok |
| 546 | }; |
| 547 | |
| 548 | // Choose an action based on the current entry of the signtable that this |
| 549 | // cast of cast refers to... |
| 550 | unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned(); |
| 551 | switch (SignTable[Row]) { |
| 552 | case 0: return false; // Never ok |
| 553 | case 1: return true; // Always ok |
| 554 | case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize |
| 555 | case 3: // Ok iff SrcSize != MidSize |
| 556 | return SrcSize != MidSize || SrcTy == Type::BoolTy; |
| 557 | default: assert(0 && "Bad entry in sign table!"); |
| 558 | } |
Chris Lattner | 3ecce66 | 2002-08-15 16:15:25 +0000 | [diff] [blame] | 559 | } |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 560 | } |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 561 | |
| 562 | // Otherwise, we cannot succeed. Specifically we do not want to allow things |
| 563 | // like: short -> ushort -> uint, because this can create wrong results if |
| 564 | // the input short is negative! |
| 565 | // |
| 566 | return false; |
| 567 | } |
| 568 | |
| 569 | |
| 570 | // CastInst simplification |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 571 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 572 | Instruction *InstCombiner::visitCastInst(CastInst &CI) { |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 573 | // If the user is casting a value to the same type, eliminate this cast |
| 574 | // instruction... |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 575 | if (CI.getType() == CI.getOperand(0)->getType()) |
| 576 | return ReplaceInstUsesWith(CI, CI.getOperand(0)); |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 577 | |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 578 | // If casting the result of another cast instruction, try to eliminate this |
| 579 | // one! |
| 580 | // |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 581 | if (CastInst *CSrc = dyn_cast<CastInst>(CI.getOperand(0))) { |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 582 | if (isEliminableCastOfCast(CI, CSrc)) { |
| 583 | // This instruction now refers directly to the cast's src operand. This |
| 584 | // has a good chance of making CSrc dead. |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 585 | CI.setOperand(0, CSrc->getOperand(0)); |
| 586 | return &CI; |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 587 | } |
| 588 | |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 589 | // If this is an A->B->A cast, and we are dealing with integral types, try |
| 590 | // to convert this into a logical 'and' instruction. |
| 591 | // |
| 592 | if (CSrc->getOperand(0)->getType() == CI.getType() && |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame^] | 593 | CI.getType()->isInteger() && CSrc->getType()->isInteger() && |
Chris Lattner | 8fd217c | 2002-08-02 20:00:25 +0000 | [diff] [blame] | 594 | CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() && |
| 595 | CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){ |
| 596 | assert(CSrc->getType() != Type::ULongTy && |
| 597 | "Cannot have type bigger than ulong!"); |
| 598 | unsigned AndValue = (1U << CSrc->getType()->getPrimitiveSize()*8)-1; |
| 599 | Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue); |
| 600 | return BinaryOperator::create(Instruction::And, CSrc->getOperand(0), |
| 601 | AndOp); |
| 602 | } |
| 603 | } |
| 604 | |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 605 | return 0; |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 606 | } |
| 607 | |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 608 | |
Chris Lattner | 473945d | 2002-05-06 18:06:38 +0000 | [diff] [blame] | 609 | // PHINode simplification |
| 610 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 611 | Instruction *InstCombiner::visitPHINode(PHINode &PN) { |
Chris Lattner | 473945d | 2002-05-06 18:06:38 +0000 | [diff] [blame] | 612 | // If the PHI node only has one incoming value, eliminate the PHI node... |
Chris Lattner | f02c468 | 2002-08-20 15:35:35 +0000 | [diff] [blame] | 613 | if (PN.getNumIncomingValues() == 0) |
| 614 | return ReplaceInstUsesWith(PN, Constant::getNullValue(PN.getType())); |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 615 | if (PN.getNumIncomingValues() == 1) |
| 616 | return ReplaceInstUsesWith(PN, PN.getIncomingValue(0)); |
Chris Lattner | f02c468 | 2002-08-20 15:35:35 +0000 | [diff] [blame] | 617 | |
| 618 | // Otherwise if all of the incoming values are the same for the PHI, replace |
| 619 | // the PHI node with the incoming value. |
| 620 | // |
Chris Lattner | c20e245 | 2002-08-22 20:22:01 +0000 | [diff] [blame] | 621 | Value *InVal = 0; |
| 622 | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) |
| 623 | if (PN.getIncomingValue(i) != &PN) // Not the PHI node itself... |
| 624 | if (InVal && PN.getIncomingValue(i) != InVal) |
| 625 | return 0; // Not the same, bail out. |
| 626 | else |
| 627 | InVal = PN.getIncomingValue(i); |
| 628 | |
| 629 | // The only case that could cause InVal to be null is if we have a PHI node |
| 630 | // that only has entries for itself. In this case, there is no entry into the |
| 631 | // loop, so kill the PHI. |
| 632 | // |
| 633 | if (InVal == 0) InVal = Constant::getNullValue(PN.getType()); |
Chris Lattner | 473945d | 2002-05-06 18:06:38 +0000 | [diff] [blame] | 634 | |
Chris Lattner | f02c468 | 2002-08-20 15:35:35 +0000 | [diff] [blame] | 635 | // All of the incoming values are the same, replace the PHI node now. |
| 636 | return ReplaceInstUsesWith(PN, InVal); |
Chris Lattner | 473945d | 2002-05-06 18:06:38 +0000 | [diff] [blame] | 637 | } |
| 638 | |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 639 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 640 | Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 641 | // Is it 'getelementptr %P, uint 0' or 'getelementptr %P' |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 642 | // If so, eliminate the noop. |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 643 | if ((GEP.getNumOperands() == 2 && |
| 644 | GEP.getOperand(1) == Constant::getNullValue(Type::UIntTy)) || |
Chris Lattner | 233f7dc | 2002-08-12 21:17:25 +0000 | [diff] [blame] | 645 | GEP.getNumOperands() == 1) |
| 646 | return ReplaceInstUsesWith(GEP, GEP.getOperand(0)); |
Chris Lattner | a1be566 | 2002-05-02 17:06:02 +0000 | [diff] [blame] | 647 | |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 648 | // Combine Indices - If the source pointer to this getelementptr instruction |
| 649 | // is a getelementptr instruction, combine the indices of the two |
| 650 | // getelementptr instructions into a single instruction. |
| 651 | // |
Chris Lattner | 9b76123 | 2002-08-17 22:21:59 +0000 | [diff] [blame] | 652 | if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) { |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 653 | std::vector<Value *> Indices; |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 654 | |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 655 | // Can we combine the two pointer arithmetics offsets? |
| 656 | if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) && |
| 657 | isa<Constant>(GEP.getOperand(1))) { |
| 658 | // Replace the index list on this GEP with the index on the getelementptr |
| 659 | Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end()); |
| 660 | Indices[0] = *cast<Constant>(Src->getOperand(1)) + |
| 661 | *cast<Constant>(GEP.getOperand(1)); |
| 662 | assert(Indices[0] != 0 && "Constant folding of uint's failed!?"); |
| 663 | |
| 664 | } else if (*GEP.idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) { |
| 665 | // Otherwise we can do the fold if the first index of the GEP is a zero |
| 666 | Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end()); |
| 667 | Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end()); |
| 668 | } |
| 669 | |
| 670 | if (!Indices.empty()) |
| 671 | return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName()); |
Chris Lattner | 9b76123 | 2002-08-17 22:21:59 +0000 | [diff] [blame] | 672 | |
| 673 | } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) { |
| 674 | // GEP of global variable. If all of the indices for this GEP are |
| 675 | // constants, we can promote this to a constexpr instead of an instruction. |
| 676 | |
| 677 | // Scan for nonconstants... |
| 678 | std::vector<Constant*> Indices; |
| 679 | User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); |
| 680 | for (; I != E && isa<Constant>(*I); ++I) |
| 681 | Indices.push_back(cast<Constant>(*I)); |
| 682 | |
| 683 | if (I == E) { // If they are all constants... |
| 684 | ConstantExpr *CE = |
| 685 | ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices); |
| 686 | |
| 687 | // Replace all uses of the GEP with the new constexpr... |
| 688 | return ReplaceInstUsesWith(GEP, CE); |
| 689 | } |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 690 | } |
| 691 | |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 692 | return 0; |
| 693 | } |
| 694 | |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 695 | |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 696 | void InstCombiner::removeFromWorkList(Instruction *I) { |
| 697 | WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I), |
| 698 | WorkList.end()); |
| 699 | } |
| 700 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 701 | bool InstCombiner::runOnFunction(Function &F) { |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 702 | bool Changed = false; |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 703 | |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 704 | WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F)); |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 705 | |
| 706 | while (!WorkList.empty()) { |
| 707 | Instruction *I = WorkList.back(); // Get an instruction from the worklist |
| 708 | WorkList.pop_back(); |
| 709 | |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 710 | // Check to see if we can DCE or ConstantPropogate the instruction... |
| 711 | // Check to see if we can DIE the instruction... |
| 712 | if (isInstructionTriviallyDead(I)) { |
| 713 | // Add operands to the worklist... |
| 714 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 715 | if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i))) |
| 716 | WorkList.push_back(Op); |
| 717 | |
| 718 | ++NumDeadInst; |
| 719 | BasicBlock::iterator BBI = I; |
| 720 | if (dceInstruction(BBI)) { |
| 721 | removeFromWorkList(I); |
| 722 | continue; |
| 723 | } |
| 724 | } |
| 725 | |
| 726 | // Instruction isn't dead, see if we can constant propogate it... |
| 727 | if (Constant *C = ConstantFoldInstruction(I)) { |
| 728 | // Add operands to the worklist... |
| 729 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 730 | if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i))) |
| 731 | WorkList.push_back(Op); |
| 732 | I->replaceAllUsesWith(C); |
| 733 | ++NumConstProp; |
| 734 | BasicBlock::iterator BBI = I; |
| 735 | if (dceInstruction(BBI)) { |
| 736 | removeFromWorkList(I); |
| 737 | continue; |
| 738 | } |
| 739 | } |
| 740 | |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 741 | // Now that we have an instruction, try combining it to simplify it... |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 742 | if (Instruction *Result = visit(*I)) { |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 743 | ++NumCombined; |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 744 | // Should we replace the old instruction with a new one? |
Chris Lattner | b3bc8fa | 2002-05-14 15:24:07 +0000 | [diff] [blame] | 745 | if (Result != I) { |
| 746 | // Instructions can end up on the worklist more than once. Make sure |
| 747 | // we do not process an instruction that has been deleted. |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 748 | removeFromWorkList(I); |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 749 | ReplaceInstWithInst(I, Result); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 750 | } else { |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 751 | BasicBlock::iterator II = I; |
| 752 | |
| 753 | // If the instruction was modified, it's possible that it is now dead. |
| 754 | // if so, remove it. |
| 755 | if (dceInstruction(II)) { |
| 756 | // Instructions may end up in the worklist more than once. Erase them |
| 757 | // all. |
Chris Lattner | 62b14df | 2002-09-02 04:59:56 +0000 | [diff] [blame] | 758 | removeFromWorkList(I); |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 759 | Result = 0; |
| 760 | } |
Chris Lattner | b3bc8fa | 2002-05-14 15:24:07 +0000 | [diff] [blame] | 761 | } |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 762 | |
Chris Lattner | 90ac28c | 2002-08-02 19:29:35 +0000 | [diff] [blame] | 763 | if (Result) { |
| 764 | WorkList.push_back(Result); |
| 765 | AddUsesToWorkList(*Result); |
| 766 | } |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 767 | Changed = true; |
Chris Lattner | 8a2a311 | 2001-12-14 16:52:21 +0000 | [diff] [blame] | 768 | } |
| 769 | } |
| 770 | |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 771 | return Changed; |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 772 | } |
| 773 | |
| 774 | Pass *createInstructionCombiningPass() { |
Chris Lattner | dd841ae | 2002-04-18 17:39:14 +0000 | [diff] [blame] | 775 | return new InstCombiner(); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 776 | } |