Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1 | //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass performs a hybrid of global value numbering and partial redundancy |
| 11 | // elimination, known as GVN-PRE. It performs partial redundancy elimination on |
| 12 | // values, rather than lexical expressions, allowing a more comprehensive view |
| 13 | // the optimization. It replaces redundant values with uses of earlier |
| 14 | // occurences of the same value. While this is beneficial in that it eliminates |
| 15 | // unneeded computation, it also increases register pressure by creating large |
Owen Anderson | a7f916c | 2007-06-08 20:57:08 +0000 | [diff] [blame] | 16 | // live ranges, and should be used with caution on platforms that are very |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 17 | // sensitive to register pressure. |
| 18 | // |
Matthijs Kooijman | 845f524 | 2008-06-05 07:55:49 +0000 | [diff] [blame] | 19 | // Note that this pass does the value numbering itself, it does not use the |
| 20 | // ValueNumbering analysis passes. |
| 21 | // |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 22 | //===----------------------------------------------------------------------===// |
| 23 | |
| 24 | #define DEBUG_TYPE "gvnpre" |
| 25 | #include "llvm/Value.h" |
| 26 | #include "llvm/Transforms/Scalar.h" |
| 27 | #include "llvm/Instructions.h" |
| 28 | #include "llvm/Function.h" |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 29 | #include "llvm/DerivedTypes.h" |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 30 | #include "llvm/Analysis/Dominators.h" |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 31 | #include "llvm/ADT/BitVector.h" |
Owen Anderson | 4f703ec | 2007-06-19 23:23:54 +0000 | [diff] [blame] | 32 | #include "llvm/ADT/DenseMap.h" |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 33 | #include "llvm/ADT/DepthFirstIterator.h" |
Owen Anderson | 9030d38 | 2007-06-25 18:25:31 +0000 | [diff] [blame] | 34 | #include "llvm/ADT/PostOrderIterator.h" |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 35 | #include "llvm/ADT/SmallPtrSet.h" |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 36 | #include "llvm/ADT/SmallVector.h" |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 37 | #include "llvm/ADT/Statistic.h" |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 38 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 39 | #include "llvm/Support/CFG.h" |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 40 | #include "llvm/Support/Compiler.h" |
Owen Anderson | cdf8efd | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 41 | #include "llvm/Support/Debug.h" |
Torok Edwin | c25e758 | 2009-07-11 20:10:48 +0000 | [diff] [blame] | 42 | #include "llvm/Support/ErrorHandling.h" |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 43 | #include <algorithm> |
Owen Anderson | 243f348 | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 44 | #include <deque> |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 45 | #include <map> |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 46 | using namespace llvm; |
| 47 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 48 | //===----------------------------------------------------------------------===// |
| 49 | // ValueTable Class |
| 50 | //===----------------------------------------------------------------------===// |
| 51 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 52 | namespace { |
| 53 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 54 | /// This class holds the mapping between values and value numbers. It is used |
| 55 | /// as an efficient mechanism to determine the expression-wise equivalence of |
| 56 | /// two values. |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 57 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 58 | struct Expression { |
Dan Gohman | ae3a0be | 2009-06-04 22:49:04 +0000 | [diff] [blame] | 59 | enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL, |
| 60 | UDIV, SDIV, FDIV, UREM, SREM, |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 61 | FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, |
| 62 | ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, |
| 63 | ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, |
| 64 | FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, |
| 65 | FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, |
| 66 | FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, |
| 67 | SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, |
| 68 | FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, |
| 69 | PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, |
| 70 | TOMBSTONE }; |
| 71 | |
| 72 | ExpressionOpcode opcode; |
| 73 | const Type* type; |
| 74 | uint32_t firstVN; |
| 75 | uint32_t secondVN; |
| 76 | uint32_t thirdVN; |
| 77 | SmallVector<uint32_t, 4> varargs; |
| 78 | |
| 79 | Expression() { } |
Dan Gohman | 746767b | 2007-09-24 15:48:49 +0000 | [diff] [blame] | 80 | explicit Expression(ExpressionOpcode o) : opcode(o) { } |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 81 | |
| 82 | bool operator==(const Expression &other) const { |
| 83 | if (opcode != other.opcode) |
| 84 | return false; |
| 85 | else if (opcode == EMPTY || opcode == TOMBSTONE) |
| 86 | return true; |
| 87 | else if (type != other.type) |
| 88 | return false; |
| 89 | else if (firstVN != other.firstVN) |
| 90 | return false; |
| 91 | else if (secondVN != other.secondVN) |
| 92 | return false; |
| 93 | else if (thirdVN != other.thirdVN) |
| 94 | return false; |
| 95 | else { |
| 96 | if (varargs.size() != other.varargs.size()) |
| 97 | return false; |
| 98 | |
| 99 | for (size_t i = 0; i < varargs.size(); ++i) |
| 100 | if (varargs[i] != other.varargs[i]) |
| 101 | return false; |
| 102 | |
| 103 | return true; |
| 104 | } |
| 105 | } |
| 106 | |
| 107 | bool operator!=(const Expression &other) const { |
| 108 | if (opcode != other.opcode) |
| 109 | return true; |
| 110 | else if (opcode == EMPTY || opcode == TOMBSTONE) |
| 111 | return false; |
| 112 | else if (type != other.type) |
| 113 | return true; |
| 114 | else if (firstVN != other.firstVN) |
| 115 | return true; |
| 116 | else if (secondVN != other.secondVN) |
| 117 | return true; |
| 118 | else if (thirdVN != other.thirdVN) |
| 119 | return true; |
| 120 | else { |
| 121 | if (varargs.size() != other.varargs.size()) |
| 122 | return true; |
| 123 | |
| 124 | for (size_t i = 0; i < varargs.size(); ++i) |
| 125 | if (varargs[i] != other.varargs[i]) |
| 126 | return true; |
| 127 | |
| 128 | return false; |
| 129 | } |
| 130 | } |
| 131 | }; |
| 132 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 133 | } |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 134 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 135 | namespace { |
| 136 | class VISIBILITY_HIDDEN ValueTable { |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 137 | private: |
Owen Anderson | 4f703ec | 2007-06-19 23:23:54 +0000 | [diff] [blame] | 138 | DenseMap<Value*, uint32_t> valueNumbering; |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 139 | DenseMap<Expression, uint32_t> expressionNumbering; |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 140 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 141 | uint32_t nextValueNumber; |
| 142 | |
| 143 | Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); |
| 144 | Expression::ExpressionOpcode getOpcode(CmpInst* C); |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 145 | Expression::ExpressionOpcode getOpcode(CastInst* C); |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 146 | Expression create_expression(BinaryOperator* BO); |
| 147 | Expression create_expression(CmpInst* C); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 148 | Expression create_expression(ShuffleVectorInst* V); |
| 149 | Expression create_expression(ExtractElementInst* C); |
| 150 | Expression create_expression(InsertElementInst* V); |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 151 | Expression create_expression(SelectInst* V); |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 152 | Expression create_expression(CastInst* C); |
Owen Anderson | eb21686 | 2007-07-03 22:50:56 +0000 | [diff] [blame] | 153 | Expression create_expression(GetElementPtrInst* G); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 154 | public: |
| 155 | ValueTable() { nextValueNumber = 1; } |
| 156 | uint32_t lookup_or_add(Value* V); |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 157 | uint32_t lookup(Value* V) const; |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 158 | void add(Value* V, uint32_t num); |
| 159 | void clear(); |
Owen Anderson | 20cb51f | 2007-06-19 05:37:32 +0000 | [diff] [blame] | 160 | void erase(Value* v); |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 161 | unsigned size(); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 162 | }; |
| 163 | } |
| 164 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 165 | namespace llvm { |
Chris Lattner | 76c1b97 | 2007-09-17 18:34:04 +0000 | [diff] [blame] | 166 | template <> struct DenseMapInfo<Expression> { |
Owen Anderson | 9fed589 | 2007-08-02 18:20:52 +0000 | [diff] [blame] | 167 | static inline Expression getEmptyKey() { |
| 168 | return Expression(Expression::EMPTY); |
| 169 | } |
| 170 | |
| 171 | static inline Expression getTombstoneKey() { |
| 172 | return Expression(Expression::TOMBSTONE); |
| 173 | } |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 174 | |
| 175 | static unsigned getHashValue(const Expression e) { |
| 176 | unsigned hash = e.opcode; |
| 177 | |
| 178 | hash = e.firstVN + hash * 37; |
| 179 | hash = e.secondVN + hash * 37; |
| 180 | hash = e.thirdVN + hash * 37; |
| 181 | |
Anton Korobeynikov | 07e6e56 | 2008-02-20 11:26:25 +0000 | [diff] [blame] | 182 | hash = ((unsigned)((uintptr_t)e.type >> 4) ^ |
| 183 | (unsigned)((uintptr_t)e.type >> 9)) + |
| 184 | hash * 37; |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 185 | |
Owen Anderson | 9fed589 | 2007-08-02 18:20:52 +0000 | [diff] [blame] | 186 | for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), |
| 187 | E = e.varargs.end(); I != E; ++I) |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 188 | hash = *I + hash * 37; |
| 189 | |
| 190 | return hash; |
| 191 | } |
Chris Lattner | 76c1b97 | 2007-09-17 18:34:04 +0000 | [diff] [blame] | 192 | static bool isEqual(const Expression &LHS, const Expression &RHS) { |
| 193 | return LHS == RHS; |
| 194 | } |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 195 | static bool isPod() { return true; } |
| 196 | }; |
| 197 | } |
| 198 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 199 | //===----------------------------------------------------------------------===// |
| 200 | // ValueTable Internal Functions |
| 201 | //===----------------------------------------------------------------------===// |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 202 | Expression::ExpressionOpcode |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 203 | ValueTable::getOpcode(BinaryOperator* BO) { |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 204 | switch(BO->getOpcode()) { |
| 205 | case Instruction::Add: |
| 206 | return Expression::ADD; |
Dan Gohman | ae3a0be | 2009-06-04 22:49:04 +0000 | [diff] [blame] | 207 | case Instruction::FAdd: |
| 208 | return Expression::FADD; |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 209 | case Instruction::Sub: |
| 210 | return Expression::SUB; |
Dan Gohman | ae3a0be | 2009-06-04 22:49:04 +0000 | [diff] [blame] | 211 | case Instruction::FSub: |
| 212 | return Expression::FSUB; |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 213 | case Instruction::Mul: |
| 214 | return Expression::MUL; |
Dan Gohman | ae3a0be | 2009-06-04 22:49:04 +0000 | [diff] [blame] | 215 | case Instruction::FMul: |
| 216 | return Expression::FMUL; |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 217 | case Instruction::UDiv: |
| 218 | return Expression::UDIV; |
| 219 | case Instruction::SDiv: |
| 220 | return Expression::SDIV; |
| 221 | case Instruction::FDiv: |
| 222 | return Expression::FDIV; |
| 223 | case Instruction::URem: |
| 224 | return Expression::UREM; |
| 225 | case Instruction::SRem: |
| 226 | return Expression::SREM; |
| 227 | case Instruction::FRem: |
| 228 | return Expression::FREM; |
| 229 | case Instruction::Shl: |
| 230 | return Expression::SHL; |
| 231 | case Instruction::LShr: |
| 232 | return Expression::LSHR; |
| 233 | case Instruction::AShr: |
| 234 | return Expression::ASHR; |
| 235 | case Instruction::And: |
| 236 | return Expression::AND; |
| 237 | case Instruction::Or: |
| 238 | return Expression::OR; |
| 239 | case Instruction::Xor: |
| 240 | return Expression::XOR; |
| 241 | |
| 242 | // THIS SHOULD NEVER HAPPEN |
| 243 | default: |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 244 | llvm_unreachable("Binary operator with unknown opcode?"); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 245 | return Expression::ADD; |
| 246 | } |
| 247 | } |
| 248 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 249 | Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 250 | if (C->getOpcode() == Instruction::ICmp) { |
| 251 | switch (C->getPredicate()) { |
| 252 | case ICmpInst::ICMP_EQ: |
| 253 | return Expression::ICMPEQ; |
| 254 | case ICmpInst::ICMP_NE: |
| 255 | return Expression::ICMPNE; |
| 256 | case ICmpInst::ICMP_UGT: |
| 257 | return Expression::ICMPUGT; |
| 258 | case ICmpInst::ICMP_UGE: |
| 259 | return Expression::ICMPUGE; |
| 260 | case ICmpInst::ICMP_ULT: |
| 261 | return Expression::ICMPULT; |
| 262 | case ICmpInst::ICMP_ULE: |
| 263 | return Expression::ICMPULE; |
| 264 | case ICmpInst::ICMP_SGT: |
| 265 | return Expression::ICMPSGT; |
| 266 | case ICmpInst::ICMP_SGE: |
| 267 | return Expression::ICMPSGE; |
| 268 | case ICmpInst::ICMP_SLT: |
| 269 | return Expression::ICMPSLT; |
| 270 | case ICmpInst::ICMP_SLE: |
| 271 | return Expression::ICMPSLE; |
| 272 | |
| 273 | // THIS SHOULD NEVER HAPPEN |
| 274 | default: |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 275 | llvm_unreachable("Comparison with unknown predicate?"); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 276 | return Expression::ICMPEQ; |
| 277 | } |
| 278 | } else { |
| 279 | switch (C->getPredicate()) { |
| 280 | case FCmpInst::FCMP_OEQ: |
| 281 | return Expression::FCMPOEQ; |
| 282 | case FCmpInst::FCMP_OGT: |
| 283 | return Expression::FCMPOGT; |
| 284 | case FCmpInst::FCMP_OGE: |
| 285 | return Expression::FCMPOGE; |
| 286 | case FCmpInst::FCMP_OLT: |
| 287 | return Expression::FCMPOLT; |
| 288 | case FCmpInst::FCMP_OLE: |
| 289 | return Expression::FCMPOLE; |
| 290 | case FCmpInst::FCMP_ONE: |
| 291 | return Expression::FCMPONE; |
| 292 | case FCmpInst::FCMP_ORD: |
| 293 | return Expression::FCMPORD; |
| 294 | case FCmpInst::FCMP_UNO: |
| 295 | return Expression::FCMPUNO; |
| 296 | case FCmpInst::FCMP_UEQ: |
| 297 | return Expression::FCMPUEQ; |
| 298 | case FCmpInst::FCMP_UGT: |
| 299 | return Expression::FCMPUGT; |
| 300 | case FCmpInst::FCMP_UGE: |
| 301 | return Expression::FCMPUGE; |
| 302 | case FCmpInst::FCMP_ULT: |
| 303 | return Expression::FCMPULT; |
| 304 | case FCmpInst::FCMP_ULE: |
| 305 | return Expression::FCMPULE; |
| 306 | case FCmpInst::FCMP_UNE: |
| 307 | return Expression::FCMPUNE; |
| 308 | |
| 309 | // THIS SHOULD NEVER HAPPEN |
| 310 | default: |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 311 | llvm_unreachable("Comparison with unknown predicate?"); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 312 | return Expression::FCMPOEQ; |
Owen Anderson | 139fe84 | 2007-06-09 18:35:31 +0000 | [diff] [blame] | 313 | } |
| 314 | } |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 315 | } |
| 316 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 317 | Expression::ExpressionOpcode |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 318 | ValueTable::getOpcode(CastInst* C) { |
| 319 | switch(C->getOpcode()) { |
| 320 | case Instruction::Trunc: |
| 321 | return Expression::TRUNC; |
| 322 | case Instruction::ZExt: |
| 323 | return Expression::ZEXT; |
| 324 | case Instruction::SExt: |
| 325 | return Expression::SEXT; |
| 326 | case Instruction::FPToUI: |
| 327 | return Expression::FPTOUI; |
| 328 | case Instruction::FPToSI: |
| 329 | return Expression::FPTOSI; |
| 330 | case Instruction::UIToFP: |
| 331 | return Expression::UITOFP; |
| 332 | case Instruction::SIToFP: |
| 333 | return Expression::SITOFP; |
| 334 | case Instruction::FPTrunc: |
| 335 | return Expression::FPTRUNC; |
| 336 | case Instruction::FPExt: |
| 337 | return Expression::FPEXT; |
| 338 | case Instruction::PtrToInt: |
| 339 | return Expression::PTRTOINT; |
| 340 | case Instruction::IntToPtr: |
| 341 | return Expression::INTTOPTR; |
| 342 | case Instruction::BitCast: |
| 343 | return Expression::BITCAST; |
| 344 | |
| 345 | // THIS SHOULD NEVER HAPPEN |
| 346 | default: |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 347 | llvm_unreachable("Cast operator with unknown opcode?"); |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 348 | return Expression::BITCAST; |
| 349 | } |
| 350 | } |
| 351 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 352 | Expression ValueTable::create_expression(BinaryOperator* BO) { |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 353 | Expression e; |
| 354 | |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 355 | e.firstVN = lookup_or_add(BO->getOperand(0)); |
| 356 | e.secondVN = lookup_or_add(BO->getOperand(1)); |
| 357 | e.thirdVN = 0; |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 358 | e.type = BO->getType(); |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 359 | e.opcode = getOpcode(BO); |
| 360 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 361 | return e; |
| 362 | } |
| 363 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 364 | Expression ValueTable::create_expression(CmpInst* C) { |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 365 | Expression e; |
| 366 | |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 367 | e.firstVN = lookup_or_add(C->getOperand(0)); |
| 368 | e.secondVN = lookup_or_add(C->getOperand(1)); |
| 369 | e.thirdVN = 0; |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 370 | e.type = C->getType(); |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 371 | e.opcode = getOpcode(C); |
| 372 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 373 | return e; |
| 374 | } |
| 375 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 376 | Expression ValueTable::create_expression(CastInst* C) { |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 377 | Expression e; |
| 378 | |
| 379 | e.firstVN = lookup_or_add(C->getOperand(0)); |
| 380 | e.secondVN = 0; |
| 381 | e.thirdVN = 0; |
| 382 | e.type = C->getType(); |
| 383 | e.opcode = getOpcode(C); |
| 384 | |
| 385 | return e; |
| 386 | } |
| 387 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 388 | Expression ValueTable::create_expression(ShuffleVectorInst* S) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 389 | Expression e; |
| 390 | |
| 391 | e.firstVN = lookup_or_add(S->getOperand(0)); |
| 392 | e.secondVN = lookup_or_add(S->getOperand(1)); |
| 393 | e.thirdVN = lookup_or_add(S->getOperand(2)); |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 394 | e.type = S->getType(); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 395 | e.opcode = Expression::SHUFFLE; |
| 396 | |
| 397 | return e; |
| 398 | } |
| 399 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 400 | Expression ValueTable::create_expression(ExtractElementInst* E) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 401 | Expression e; |
| 402 | |
| 403 | e.firstVN = lookup_or_add(E->getOperand(0)); |
| 404 | e.secondVN = lookup_or_add(E->getOperand(1)); |
| 405 | e.thirdVN = 0; |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 406 | e.type = E->getType(); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 407 | e.opcode = Expression::EXTRACT; |
| 408 | |
| 409 | return e; |
| 410 | } |
| 411 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 412 | Expression ValueTable::create_expression(InsertElementInst* I) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 413 | Expression e; |
| 414 | |
| 415 | e.firstVN = lookup_or_add(I->getOperand(0)); |
| 416 | e.secondVN = lookup_or_add(I->getOperand(1)); |
| 417 | e.thirdVN = lookup_or_add(I->getOperand(2)); |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 418 | e.type = I->getType(); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 419 | e.opcode = Expression::INSERT; |
| 420 | |
| 421 | return e; |
| 422 | } |
| 423 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 424 | Expression ValueTable::create_expression(SelectInst* I) { |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 425 | Expression e; |
| 426 | |
| 427 | e.firstVN = lookup_or_add(I->getCondition()); |
| 428 | e.secondVN = lookup_or_add(I->getTrueValue()); |
| 429 | e.thirdVN = lookup_or_add(I->getFalseValue()); |
Owen Anderson | 40dc00e | 2007-06-29 00:40:05 +0000 | [diff] [blame] | 430 | e.type = I->getType(); |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 431 | e.opcode = Expression::SELECT; |
| 432 | |
| 433 | return e; |
| 434 | } |
| 435 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 436 | Expression ValueTable::create_expression(GetElementPtrInst* G) { |
Owen Anderson | eb21686 | 2007-07-03 22:50:56 +0000 | [diff] [blame] | 437 | Expression e; |
| 438 | |
| 439 | e.firstVN = lookup_or_add(G->getPointerOperand()); |
| 440 | e.secondVN = 0; |
| 441 | e.thirdVN = 0; |
| 442 | e.type = G->getType(); |
Owen Anderson | c9399be | 2007-07-20 08:19:20 +0000 | [diff] [blame] | 443 | e.opcode = Expression::GEP; |
Owen Anderson | eb21686 | 2007-07-03 22:50:56 +0000 | [diff] [blame] | 444 | |
| 445 | for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); |
| 446 | I != E; ++I) |
| 447 | e.varargs.push_back(lookup_or_add(*I)); |
| 448 | |
| 449 | return e; |
| 450 | } |
| 451 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 452 | //===----------------------------------------------------------------------===// |
| 453 | // ValueTable External Functions |
| 454 | //===----------------------------------------------------------------------===// |
| 455 | |
| 456 | /// lookup_or_add - Returns the value number for the specified value, assigning |
| 457 | /// it a new number if it did not have one before. |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 458 | uint32_t ValueTable::lookup_or_add(Value* V) { |
Owen Anderson | 4f703ec | 2007-06-19 23:23:54 +0000 | [diff] [blame] | 459 | DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 460 | if (VI != valueNumbering.end()) |
| 461 | return VI->second; |
Owen Anderson | 139fe84 | 2007-06-09 18:35:31 +0000 | [diff] [blame] | 462 | |
Owen Anderson | 139fe84 | 2007-06-09 18:35:31 +0000 | [diff] [blame] | 463 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 464 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { |
| 465 | Expression e = create_expression(BO); |
| 466 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 467 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 468 | if (EI != expressionNumbering.end()) { |
| 469 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 470 | return EI->second; |
| 471 | } else { |
| 472 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 473 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 474 | |
| 475 | return nextValueNumber++; |
| 476 | } |
| 477 | } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { |
| 478 | Expression e = create_expression(C); |
| 479 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 480 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 481 | if (EI != expressionNumbering.end()) { |
| 482 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 483 | return EI->second; |
| 484 | } else { |
| 485 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 486 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 487 | |
| 488 | return nextValueNumber++; |
| 489 | } |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 490 | } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { |
| 491 | Expression e = create_expression(U); |
| 492 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 493 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 494 | if (EI != expressionNumbering.end()) { |
| 495 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 496 | return EI->second; |
| 497 | } else { |
| 498 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 499 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 500 | |
| 501 | return nextValueNumber++; |
| 502 | } |
| 503 | } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { |
| 504 | Expression e = create_expression(U); |
| 505 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 506 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 507 | if (EI != expressionNumbering.end()) { |
| 508 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 509 | return EI->second; |
| 510 | } else { |
| 511 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 512 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 513 | |
| 514 | return nextValueNumber++; |
| 515 | } |
| 516 | } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { |
| 517 | Expression e = create_expression(U); |
| 518 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 519 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 520 | if (EI != expressionNumbering.end()) { |
| 521 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 522 | return EI->second; |
| 523 | } else { |
| 524 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 525 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 526 | |
| 527 | return nextValueNumber++; |
| 528 | } |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 529 | } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { |
| 530 | Expression e = create_expression(U); |
| 531 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 532 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 533 | if (EI != expressionNumbering.end()) { |
| 534 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 535 | return EI->second; |
| 536 | } else { |
| 537 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 538 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 539 | |
| 540 | return nextValueNumber++; |
| 541 | } |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 542 | } else if (CastInst* U = dyn_cast<CastInst>(V)) { |
| 543 | Expression e = create_expression(U); |
| 544 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 545 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | ca6c31c | 2007-06-29 00:51:03 +0000 | [diff] [blame] | 546 | if (EI != expressionNumbering.end()) { |
| 547 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 548 | return EI->second; |
| 549 | } else { |
| 550 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 551 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 552 | |
| 553 | return nextValueNumber++; |
| 554 | } |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 555 | } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { |
| 556 | Expression e = create_expression(U); |
| 557 | |
Owen Anderson | fb66541 | 2007-07-19 06:13:15 +0000 | [diff] [blame] | 558 | DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 559 | if (EI != expressionNumbering.end()) { |
| 560 | valueNumbering.insert(std::make_pair(V, EI->second)); |
| 561 | return EI->second; |
| 562 | } else { |
| 563 | expressionNumbering.insert(std::make_pair(e, nextValueNumber)); |
| 564 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 565 | |
| 566 | return nextValueNumber++; |
| 567 | } |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 568 | } else { |
| 569 | valueNumbering.insert(std::make_pair(V, nextValueNumber)); |
| 570 | return nextValueNumber++; |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 571 | } |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 572 | } |
| 573 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 574 | /// lookup - Returns the value number of the specified value. Fails if |
| 575 | /// the value has not yet been numbered. |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 576 | uint32_t ValueTable::lookup(Value* V) const { |
Owen Anderson | 4f703ec | 2007-06-19 23:23:54 +0000 | [diff] [blame] | 577 | DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 578 | if (VI != valueNumbering.end()) |
| 579 | return VI->second; |
| 580 | else |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 581 | llvm_unreachable("Value not numbered?"); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 582 | |
| 583 | return 0; |
| 584 | } |
| 585 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 586 | /// add - Add the specified value with the given value number, removing |
| 587 | /// its old number, if any |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 588 | void ValueTable::add(Value* V, uint32_t num) { |
Owen Anderson | 4f703ec | 2007-06-19 23:23:54 +0000 | [diff] [blame] | 589 | DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 590 | if (VI != valueNumbering.end()) |
| 591 | valueNumbering.erase(VI); |
| 592 | valueNumbering.insert(std::make_pair(V, num)); |
| 593 | } |
| 594 | |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 595 | /// clear - Remove all entries from the ValueTable |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 596 | void ValueTable::clear() { |
| 597 | valueNumbering.clear(); |
| 598 | expressionNumbering.clear(); |
| 599 | nextValueNumber = 1; |
| 600 | } |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 601 | |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 602 | /// erase - Remove a value from the value numbering |
Owen Anderson | 20cb51f | 2007-06-19 05:37:32 +0000 | [diff] [blame] | 603 | void ValueTable::erase(Value* V) { |
Owen Anderson | 20cb51f | 2007-06-19 05:37:32 +0000 | [diff] [blame] | 604 | valueNumbering.erase(V); |
Owen Anderson | 20cb51f | 2007-06-19 05:37:32 +0000 | [diff] [blame] | 605 | } |
| 606 | |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 607 | /// size - Return the number of assigned value numbers |
| 608 | unsigned ValueTable::size() { |
| 609 | // NOTE: zero is never assigned |
| 610 | return nextValueNumber; |
| 611 | } |
| 612 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 613 | namespace { |
| 614 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 615 | //===----------------------------------------------------------------------===// |
Owen Anderson | ab3fd05 | 2007-07-09 16:43:55 +0000 | [diff] [blame] | 616 | // ValueNumberedSet Class |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 617 | //===----------------------------------------------------------------------===// |
| 618 | |
| 619 | class ValueNumberedSet { |
| 620 | private: |
| 621 | SmallPtrSet<Value*, 8> contents; |
| 622 | BitVector numbers; |
| 623 | public: |
| 624 | ValueNumberedSet() { numbers.resize(1); } |
Owen Anderson | 81c2a6e | 2007-07-10 00:27:22 +0000 | [diff] [blame] | 625 | ValueNumberedSet(const ValueNumberedSet& other) { |
| 626 | numbers = other.numbers; |
| 627 | contents = other.contents; |
| 628 | } |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 629 | |
| 630 | typedef SmallPtrSet<Value*, 8>::iterator iterator; |
| 631 | |
| 632 | iterator begin() { return contents.begin(); } |
| 633 | iterator end() { return contents.end(); } |
| 634 | |
| 635 | bool insert(Value* v) { return contents.insert(v); } |
| 636 | void insert(iterator I, iterator E) { contents.insert(I, E); } |
| 637 | void erase(Value* v) { contents.erase(v); } |
Owen Anderson | a05a81b | 2007-07-10 00:09:25 +0000 | [diff] [blame] | 638 | unsigned count(Value* v) { return contents.count(v); } |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 639 | size_t size() { return contents.size(); } |
| 640 | |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 641 | void set(unsigned i) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 642 | if (i >= numbers.size()) |
| 643 | numbers.resize(i+1); |
| 644 | |
| 645 | numbers.set(i); |
| 646 | } |
| 647 | |
Owen Anderson | dfa2435 | 2007-07-09 22:29:50 +0000 | [diff] [blame] | 648 | void operator=(const ValueNumberedSet& other) { |
| 649 | contents = other.contents; |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 650 | numbers = other.numbers; |
| 651 | } |
| 652 | |
| 653 | void reset(unsigned i) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 654 | if (i < numbers.size()) |
| 655 | numbers.reset(i); |
| 656 | } |
| 657 | |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 658 | bool test(unsigned i) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 659 | if (i >= numbers.size()) |
| 660 | return false; |
| 661 | |
| 662 | return numbers.test(i); |
| 663 | } |
| 664 | |
| 665 | void clear() { |
| 666 | contents.clear(); |
| 667 | numbers.clear(); |
| 668 | } |
| 669 | }; |
| 670 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 671 | } |
| 672 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 673 | //===----------------------------------------------------------------------===// |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 674 | // GVNPRE Pass |
| 675 | //===----------------------------------------------------------------------===// |
| 676 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 677 | namespace { |
| 678 | |
| 679 | class VISIBILITY_HIDDEN GVNPRE : public FunctionPass { |
| 680 | bool runOnFunction(Function &F); |
| 681 | public: |
| 682 | static char ID; // Pass identification, replacement for typeid |
Dan Gohman | ae73dc1 | 2008-09-04 17:05:41 +0000 | [diff] [blame] | 683 | GVNPRE() : FunctionPass(&ID) {} |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 684 | |
| 685 | private: |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 686 | ValueTable VN; |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 687 | SmallVector<Instruction*, 8> createdExpressions; |
Owen Anderson | 8214d50 | 2007-05-31 00:42:15 +0000 | [diff] [blame] | 688 | |
Owen Anderson | 81c2a6e | 2007-07-10 00:27:22 +0000 | [diff] [blame] | 689 | DenseMap<BasicBlock*, ValueNumberedSet> availableOut; |
| 690 | DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn; |
| 691 | DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis; |
Owen Anderson | 71fcebc | 2007-06-12 22:43:57 +0000 | [diff] [blame] | 692 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 693 | // This transformation requires dominator postdominator info |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 694 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 695 | AU.setPreservesCFG(); |
Owen Anderson | 2c194e6 | 2007-07-06 18:12:36 +0000 | [diff] [blame] | 696 | AU.addRequiredID(BreakCriticalEdgesID); |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 697 | AU.addRequired<UnifyFunctionExitNodes>(); |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 698 | AU.addRequired<DominatorTree>(); |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 699 | } |
| 700 | |
| 701 | // Helper fuctions |
| 702 | // FIXME: eliminate or document these better |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 703 | void dump(ValueNumberedSet& s) const ; |
| 704 | void clean(ValueNumberedSet& set) ; |
| 705 | Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; |
| 706 | Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 707 | void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred, |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 708 | BasicBlock* succ, ValueNumberedSet& out) ; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 709 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 710 | void topo_sort(ValueNumberedSet& set, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 711 | SmallVector<Value*, 8>& vec) ; |
Owen Anderson | 243f348 | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 712 | |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 713 | void cleanup() ; |
| 714 | bool elimination() ; |
Owen Anderson | bbf1197 | 2007-06-18 04:42:29 +0000 | [diff] [blame] | 715 | |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 716 | void val_insert(ValueNumberedSet& s, Value* v) ; |
| 717 | void val_replace(ValueNumberedSet& s, Value* v) ; |
| 718 | bool dependsOnInvoke(Value* V) ; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 719 | void buildsets_availout(BasicBlock::iterator I, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 720 | ValueNumberedSet& currAvail, |
| 721 | ValueNumberedSet& currPhis, |
| 722 | ValueNumberedSet& currExps, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 723 | SmallPtrSet<Value*, 16>& currTemps); |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 724 | bool buildsets_anticout(BasicBlock* BB, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 725 | ValueNumberedSet& anticOut, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 726 | SmallPtrSet<BasicBlock*, 8>& visited); |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 727 | unsigned buildsets_anticin(BasicBlock* BB, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 728 | ValueNumberedSet& anticOut, |
| 729 | ValueNumberedSet& currExps, |
Owen Anderson | a20f35d | 2007-06-28 00:34:34 +0000 | [diff] [blame] | 730 | SmallPtrSet<Value*, 16>& currTemps, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 731 | SmallPtrSet<BasicBlock*, 8>& visited); |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 732 | void buildsets(Function& F) ; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 733 | |
| 734 | void insertion_pre(Value* e, BasicBlock* BB, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 735 | DenseMap<BasicBlock*, Value*>& avail, |
| 736 | std::map<BasicBlock*,ValueNumberedSet>& new_set); |
| 737 | unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList, |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 738 | df_iterator<DomTreeNode*>& D, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 739 | std::map<BasicBlock*, ValueNumberedSet>& new_set); |
Owen Anderson | b9eeb1a | 2007-07-09 07:56:55 +0000 | [diff] [blame] | 740 | bool insertion(Function& F) ; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 741 | |
| 742 | }; |
| 743 | |
| 744 | char GVNPRE::ID = 0; |
| 745 | |
| 746 | } |
| 747 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 748 | // createGVNPREPass - The public interface to this file... |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 749 | FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); } |
| 750 | |
Owen Anderson | 16a72bb | 2007-07-10 20:20:19 +0000 | [diff] [blame] | 751 | static RegisterPass<GVNPRE> X("gvnpre", |
Owen Anderson | 9fed589 | 2007-08-02 18:20:52 +0000 | [diff] [blame] | 752 | "Global Value Numbering/Partial Redundancy Elimination"); |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 753 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 754 | |
Owen Anderson | b8b873c | 2007-06-08 22:02:36 +0000 | [diff] [blame] | 755 | STATISTIC(NumInsertedVals, "Number of values inserted"); |
| 756 | STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted"); |
| 757 | STATISTIC(NumEliminated, "Number of redundant instructions eliminated"); |
| 758 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 759 | /// find_leader - Given a set and a value number, return the first |
| 760 | /// element of the set with that value number, or 0 if no such element |
| 761 | /// is present |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 762 | Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) { |
| 763 | if (!vals.test(v)) |
| 764 | return 0; |
| 765 | |
| 766 | for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 767 | I != E; ++I) |
| 768 | if (v == VN.lookup(*I)) |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 769 | return *I; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 770 | |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 771 | llvm_unreachable("No leader found, but present bit is set?"); |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 772 | return 0; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 773 | } |
| 774 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 775 | /// val_insert - Insert a value into a set only if there is not a value |
| 776 | /// with the same value number already in the set |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 777 | void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) { |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 778 | uint32_t num = VN.lookup(v); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 779 | if (!s.test(num)) |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 780 | s.insert(v); |
| 781 | } |
| 782 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 783 | /// val_replace - Insert a value into a set, replacing any values already in |
| 784 | /// the set that have the same value number |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 785 | void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) { |
Owen Anderson | b83e56f | 2007-07-19 19:57:13 +0000 | [diff] [blame] | 786 | if (s.count(v)) return; |
| 787 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 788 | uint32_t num = VN.lookup(v); |
| 789 | Value* leader = find_leader(s, num); |
Owen Anderson | dfa2435 | 2007-07-09 22:29:50 +0000 | [diff] [blame] | 790 | if (leader != 0) |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 791 | s.erase(leader); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 792 | s.insert(v); |
Owen Anderson | dfa2435 | 2007-07-09 22:29:50 +0000 | [diff] [blame] | 793 | s.set(num); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 794 | } |
| 795 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 796 | /// phi_translate - Given a value, its parent block, and a predecessor of its |
| 797 | /// parent, translate the value into legal for the predecessor block. This |
| 798 | /// means translating its operands (and recursively, their operands) through |
| 799 | /// any phi nodes in the parent into values available in the predecessor |
Owen Anderson | 71fcebc | 2007-06-12 22:43:57 +0000 | [diff] [blame] | 800 | Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) { |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 801 | if (V == 0) |
| 802 | return 0; |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 803 | |
| 804 | LLVMContext &Context = V->getContext(); |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 805 | |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 806 | // Unary Operations |
Owen Anderson | 3d6fac3 | 2007-07-03 19:01:42 +0000 | [diff] [blame] | 807 | if (CastInst* U = dyn_cast<CastInst>(V)) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 808 | Value* newOp1 = 0; |
| 809 | if (isa<Instruction>(U->getOperand(0))) |
| 810 | newOp1 = phi_translate(U->getOperand(0), pred, succ); |
| 811 | else |
| 812 | newOp1 = U->getOperand(0); |
| 813 | |
| 814 | if (newOp1 == 0) |
| 815 | return 0; |
| 816 | |
| 817 | if (newOp1 != U->getOperand(0)) { |
| 818 | Instruction* newVal = 0; |
| 819 | if (CastInst* C = dyn_cast<CastInst>(U)) |
Gabor Greif | 7cbd8a3 | 2008-05-16 19:29:10 +0000 | [diff] [blame] | 820 | newVal = CastInst::Create(C->getOpcode(), |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 821 | newOp1, C->getType(), |
| 822 | C->getName()+".expr"); |
| 823 | |
| 824 | uint32_t v = VN.lookup_or_add(newVal); |
| 825 | |
| 826 | Value* leader = find_leader(availableOut[pred], v); |
| 827 | if (leader == 0) { |
| 828 | createdExpressions.push_back(newVal); |
| 829 | return newVal; |
| 830 | } else { |
| 831 | VN.erase(newVal); |
| 832 | delete newVal; |
| 833 | return leader; |
| 834 | } |
| 835 | } |
| 836 | |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 837 | // Binary Operations |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 838 | } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) || |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 839 | isa<ExtractElementInst>(V)) { |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 840 | User* U = cast<User>(V); |
| 841 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 842 | Value* newOp1 = 0; |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 843 | if (isa<Instruction>(U->getOperand(0))) |
| 844 | newOp1 = phi_translate(U->getOperand(0), pred, succ); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 845 | else |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 846 | newOp1 = U->getOperand(0); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 847 | |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 848 | if (newOp1 == 0) |
| 849 | return 0; |
| 850 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 851 | Value* newOp2 = 0; |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 852 | if (isa<Instruction>(U->getOperand(1))) |
| 853 | newOp2 = phi_translate(U->getOperand(1), pred, succ); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 854 | else |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 855 | newOp2 = U->getOperand(1); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 856 | |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 857 | if (newOp2 == 0) |
| 858 | return 0; |
| 859 | |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 860 | if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) { |
| 861 | Instruction* newVal = 0; |
| 862 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U)) |
Gabor Greif | 7cbd8a3 | 2008-05-16 19:29:10 +0000 | [diff] [blame] | 863 | newVal = BinaryOperator::Create(BO->getOpcode(), |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 864 | newOp1, newOp2, |
| 865 | BO->getName()+".expr"); |
| 866 | else if (CmpInst* C = dyn_cast<CmpInst>(U)) |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 867 | newVal = CmpInst::Create(Context, C->getOpcode(), |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 868 | C->getPredicate(), |
| 869 | newOp1, newOp2, |
| 870 | C->getName()+".expr"); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 871 | else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U)) |
Eric Christopher | a3500da | 2009-07-25 02:28:41 +0000 | [diff] [blame^] | 872 | newVal = ExtractElementInst::Create(newOp1, newOp2, E->getName()+".expr"); |
Owen Anderson | 8338ff5 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 873 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 874 | uint32_t v = VN.lookup_or_add(newVal); |
Owen Anderson | 71fcebc | 2007-06-12 22:43:57 +0000 | [diff] [blame] | 875 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 876 | Value* leader = find_leader(availableOut[pred], v); |
Owen Anderson | 71fcebc | 2007-06-12 22:43:57 +0000 | [diff] [blame] | 877 | if (leader == 0) { |
Owen Anderson | 65d2862 | 2007-06-12 00:50:47 +0000 | [diff] [blame] | 878 | createdExpressions.push_back(newVal); |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 879 | return newVal; |
Owen Anderson | 8f862c8 | 2007-06-05 22:11:49 +0000 | [diff] [blame] | 880 | } else { |
Owen Anderson | 20cb51f | 2007-06-19 05:37:32 +0000 | [diff] [blame] | 881 | VN.erase(newVal); |
Owen Anderson | 8f862c8 | 2007-06-05 22:11:49 +0000 | [diff] [blame] | 882 | delete newVal; |
Owen Anderson | 71fcebc | 2007-06-12 22:43:57 +0000 | [diff] [blame] | 883 | return leader; |
Owen Anderson | 8f862c8 | 2007-06-05 22:11:49 +0000 | [diff] [blame] | 884 | } |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 885 | } |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 886 | |
| 887 | // Ternary Operations |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 888 | } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) || |
| 889 | isa<SelectInst>(V)) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 890 | User* U = cast<User>(V); |
| 891 | |
| 892 | Value* newOp1 = 0; |
| 893 | if (isa<Instruction>(U->getOperand(0))) |
| 894 | newOp1 = phi_translate(U->getOperand(0), pred, succ); |
| 895 | else |
| 896 | newOp1 = U->getOperand(0); |
| 897 | |
| 898 | if (newOp1 == 0) |
| 899 | return 0; |
| 900 | |
| 901 | Value* newOp2 = 0; |
| 902 | if (isa<Instruction>(U->getOperand(1))) |
| 903 | newOp2 = phi_translate(U->getOperand(1), pred, succ); |
| 904 | else |
| 905 | newOp2 = U->getOperand(1); |
| 906 | |
| 907 | if (newOp2 == 0) |
| 908 | return 0; |
| 909 | |
| 910 | Value* newOp3 = 0; |
| 911 | if (isa<Instruction>(U->getOperand(2))) |
| 912 | newOp3 = phi_translate(U->getOperand(2), pred, succ); |
| 913 | else |
| 914 | newOp3 = U->getOperand(2); |
| 915 | |
| 916 | if (newOp3 == 0) |
| 917 | return 0; |
| 918 | |
| 919 | if (newOp1 != U->getOperand(0) || |
| 920 | newOp2 != U->getOperand(1) || |
| 921 | newOp3 != U->getOperand(2)) { |
| 922 | Instruction* newVal = 0; |
| 923 | if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U)) |
| 924 | newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3, |
Gabor Greif | b1dbcd8 | 2008-05-15 10:04:30 +0000 | [diff] [blame] | 925 | S->getName() + ".expr"); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 926 | else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U)) |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 927 | newVal = InsertElementInst::Create(newOp1, newOp2, newOp3, |
Gabor Greif | b1dbcd8 | 2008-05-15 10:04:30 +0000 | [diff] [blame] | 928 | I->getName() + ".expr"); |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 929 | else if (SelectInst* I = dyn_cast<SelectInst>(U)) |
Gabor Greif | b1dbcd8 | 2008-05-15 10:04:30 +0000 | [diff] [blame] | 930 | newVal = SelectInst::Create(newOp1, newOp2, newOp3, |
| 931 | I->getName() + ".expr"); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 932 | |
| 933 | uint32_t v = VN.lookup_or_add(newVal); |
| 934 | |
| 935 | Value* leader = find_leader(availableOut[pred], v); |
| 936 | if (leader == 0) { |
| 937 | createdExpressions.push_back(newVal); |
| 938 | return newVal; |
| 939 | } else { |
| 940 | VN.erase(newVal); |
| 941 | delete newVal; |
| 942 | return leader; |
| 943 | } |
| 944 | } |
| 945 | |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 946 | // Varargs operators |
| 947 | } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { |
| 948 | Value* newOp1 = 0; |
| 949 | if (isa<Instruction>(U->getPointerOperand())) |
| 950 | newOp1 = phi_translate(U->getPointerOperand(), pred, succ); |
| 951 | else |
| 952 | newOp1 = U->getPointerOperand(); |
| 953 | |
| 954 | if (newOp1 == 0) |
| 955 | return 0; |
| 956 | |
| 957 | bool changed_idx = false; |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 958 | SmallVector<Value*, 4> newIdx; |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 959 | for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end(); |
| 960 | I != E; ++I) |
| 961 | if (isa<Instruction>(*I)) { |
| 962 | Value* newVal = phi_translate(*I, pred, succ); |
| 963 | newIdx.push_back(newVal); |
| 964 | if (newVal != *I) |
| 965 | changed_idx = true; |
| 966 | } else { |
| 967 | newIdx.push_back(*I); |
| 968 | } |
| 969 | |
| 970 | if (newOp1 != U->getPointerOperand() || changed_idx) { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 971 | Instruction* newVal = |
| 972 | GetElementPtrInst::Create(newOp1, |
| 973 | newIdx.begin(), newIdx.end(), |
| 974 | U->getName()+".expr"); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 975 | |
| 976 | uint32_t v = VN.lookup_or_add(newVal); |
| 977 | |
| 978 | Value* leader = find_leader(availableOut[pred], v); |
| 979 | if (leader == 0) { |
| 980 | createdExpressions.push_back(newVal); |
| 981 | return newVal; |
| 982 | } else { |
| 983 | VN.erase(newVal); |
| 984 | delete newVal; |
| 985 | return leader; |
| 986 | } |
| 987 | } |
| 988 | |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 989 | // PHI Nodes |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 990 | } else if (PHINode* P = dyn_cast<PHINode>(V)) { |
Owen Anderson | 65d2862 | 2007-06-12 00:50:47 +0000 | [diff] [blame] | 991 | if (P->getParent() == succ) |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 992 | return P->getIncomingValueForBlock(pred); |
| 993 | } |
| 994 | |
| 995 | return V; |
| 996 | } |
| 997 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 998 | /// phi_translate_set - Perform phi translation on every element of a set |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 999 | void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn, |
Owen Anderson | 65d2862 | 2007-06-12 00:50:47 +0000 | [diff] [blame] | 1000 | BasicBlock* pred, BasicBlock* succ, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1001 | ValueNumberedSet& out) { |
| 1002 | for (ValueNumberedSet::iterator I = anticIn.begin(), |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 1003 | E = anticIn.end(); I != E; ++I) { |
Owen Anderson | 71fcebc | 2007-06-12 22:43:57 +0000 | [diff] [blame] | 1004 | Value* V = phi_translate(*I, pred, succ); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1005 | if (V != 0 && !out.test(VN.lookup_or_add(V))) { |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 1006 | out.insert(V); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1007 | out.set(VN.lookup(V)); |
| 1008 | } |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1009 | } |
| 1010 | } |
| 1011 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1012 | /// dependsOnInvoke - Test if a value has an phi node as an operand, any of |
| 1013 | /// whose inputs is an invoke instruction. If this is true, we cannot safely |
| 1014 | /// PRE the instruction or anything that depends on it. |
Owen Anderson | bbf1197 | 2007-06-18 04:42:29 +0000 | [diff] [blame] | 1015 | bool GVNPRE::dependsOnInvoke(Value* V) { |
Owen Anderson | 52471b1 | 2007-06-19 23:07:16 +0000 | [diff] [blame] | 1016 | if (PHINode* p = dyn_cast<PHINode>(V)) { |
| 1017 | for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I) |
| 1018 | if (isa<InvokeInst>(*I)) |
Owen Anderson | bbf1197 | 2007-06-18 04:42:29 +0000 | [diff] [blame] | 1019 | return true; |
Owen Anderson | 52471b1 | 2007-06-19 23:07:16 +0000 | [diff] [blame] | 1020 | return false; |
| 1021 | } else { |
| 1022 | return false; |
Owen Anderson | 32bc789 | 2007-06-16 00:26:54 +0000 | [diff] [blame] | 1023 | } |
Owen Anderson | 32bc789 | 2007-06-16 00:26:54 +0000 | [diff] [blame] | 1024 | } |
| 1025 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1026 | /// clean - Remove all non-opaque values from the set whose operands are not |
| 1027 | /// themselves in the set, as well as all values that depend on invokes (see |
| 1028 | /// above) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1029 | void GVNPRE::clean(ValueNumberedSet& set) { |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1030 | SmallVector<Value*, 8> worklist; |
Owen Anderson | e8138ff | 2007-06-22 00:43:22 +0000 | [diff] [blame] | 1031 | worklist.reserve(set.size()); |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1032 | topo_sort(set, worklist); |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1033 | |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1034 | for (unsigned i = 0; i < worklist.size(); ++i) { |
| 1035 | Value* v = worklist[i]; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1036 | |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1037 | // Handle unary ops |
Owen Anderson | 3d6fac3 | 2007-07-03 19:01:42 +0000 | [diff] [blame] | 1038 | if (CastInst* U = dyn_cast<CastInst>(v)) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1039 | bool lhsValid = !isa<Instruction>(U->getOperand(0)); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1040 | lhsValid |= set.test(VN.lookup(U->getOperand(0))); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1041 | if (lhsValid) |
| 1042 | lhsValid = !dependsOnInvoke(U->getOperand(0)); |
| 1043 | |
| 1044 | if (!lhsValid) { |
| 1045 | set.erase(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1046 | set.reset(VN.lookup(U)); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1047 | } |
| 1048 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1049 | // Handle binary ops |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1050 | } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) || |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1051 | isa<ExtractElementInst>(v)) { |
| 1052 | User* U = cast<User>(v); |
| 1053 | |
| 1054 | bool lhsValid = !isa<Instruction>(U->getOperand(0)); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1055 | lhsValid |= set.test(VN.lookup(U->getOperand(0))); |
Owen Anderson | 60e1744 | 2007-06-18 04:30:44 +0000 | [diff] [blame] | 1056 | if (lhsValid) |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1057 | lhsValid = !dependsOnInvoke(U->getOperand(0)); |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 1058 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1059 | bool rhsValid = !isa<Instruction>(U->getOperand(1)); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1060 | rhsValid |= set.test(VN.lookup(U->getOperand(1))); |
Owen Anderson | 60e1744 | 2007-06-18 04:30:44 +0000 | [diff] [blame] | 1061 | if (rhsValid) |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1062 | rhsValid = !dependsOnInvoke(U->getOperand(1)); |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1063 | |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1064 | if (!lhsValid || !rhsValid) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1065 | set.erase(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1066 | set.reset(VN.lookup(U)); |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1067 | } |
Owen Anderson | 139fe84 | 2007-06-09 18:35:31 +0000 | [diff] [blame] | 1068 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1069 | // Handle ternary ops |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1070 | } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) || |
| 1071 | isa<SelectInst>(v)) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1072 | User* U = cast<User>(v); |
| 1073 | |
| 1074 | bool lhsValid = !isa<Instruction>(U->getOperand(0)); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1075 | lhsValid |= set.test(VN.lookup(U->getOperand(0))); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1076 | if (lhsValid) |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1077 | lhsValid = !dependsOnInvoke(U->getOperand(0)); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1078 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1079 | bool rhsValid = !isa<Instruction>(U->getOperand(1)); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1080 | rhsValid |= set.test(VN.lookup(U->getOperand(1))); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1081 | if (rhsValid) |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1082 | rhsValid = !dependsOnInvoke(U->getOperand(1)); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1083 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1084 | bool thirdValid = !isa<Instruction>(U->getOperand(2)); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1085 | thirdValid |= set.test(VN.lookup(U->getOperand(2))); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1086 | if (thirdValid) |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1087 | thirdValid = !dependsOnInvoke(U->getOperand(2)); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1088 | |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1089 | if (!lhsValid || !rhsValid || !thirdValid) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1090 | set.erase(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1091 | set.reset(VN.lookup(U)); |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1092 | } |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1093 | |
| 1094 | // Handle varargs ops |
| 1095 | } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) { |
| 1096 | bool ptrValid = !isa<Instruction>(U->getPointerOperand()); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1097 | ptrValid |= set.test(VN.lookup(U->getPointerOperand())); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1098 | if (ptrValid) |
| 1099 | ptrValid = !dependsOnInvoke(U->getPointerOperand()); |
| 1100 | |
| 1101 | bool varValid = true; |
| 1102 | for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end(); |
| 1103 | I != E; ++I) |
| 1104 | if (varValid) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1105 | varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I)); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1106 | varValid &= !dependsOnInvoke(*I); |
| 1107 | } |
| 1108 | |
| 1109 | if (!ptrValid || !varValid) { |
| 1110 | set.erase(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1111 | set.reset(VN.lookup(U)); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1112 | } |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 1113 | } |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1114 | } |
| 1115 | } |
| 1116 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1117 | /// topo_sort - Given a set of values, sort them by topological |
| 1118 | /// order into the provided vector. |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1119 | void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) { |
Owen Anderson | a20f35d | 2007-06-28 00:34:34 +0000 | [diff] [blame] | 1120 | SmallPtrSet<Value*, 16> visited; |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1121 | SmallVector<Value*, 8> stack; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1122 | for (ValueNumberedSet::iterator I = set.begin(), E = set.end(); |
Owen Anderson | 6475804 | 2007-06-22 21:31:16 +0000 | [diff] [blame] | 1123 | I != E; ++I) { |
| 1124 | if (visited.count(*I) == 0) |
| 1125 | stack.push_back(*I); |
| 1126 | |
| 1127 | while (!stack.empty()) { |
| 1128 | Value* e = stack.back(); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1129 | |
| 1130 | // Handle unary ops |
Owen Anderson | 3d6fac3 | 2007-07-03 19:01:42 +0000 | [diff] [blame] | 1131 | if (CastInst* U = dyn_cast<CastInst>(e)) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1132 | Value* l = find_leader(set, VN.lookup(U->getOperand(0))); |
| 1133 | |
| 1134 | if (l != 0 && isa<Instruction>(l) && |
| 1135 | visited.count(l) == 0) |
| 1136 | stack.push_back(l); |
| 1137 | else { |
| 1138 | vec.push_back(e); |
| 1139 | visited.insert(e); |
| 1140 | stack.pop_back(); |
| 1141 | } |
| 1142 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1143 | // Handle binary ops |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1144 | } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) || |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1145 | isa<ExtractElementInst>(e)) { |
| 1146 | User* U = cast<User>(e); |
| 1147 | Value* l = find_leader(set, VN.lookup(U->getOperand(0))); |
| 1148 | Value* r = find_leader(set, VN.lookup(U->getOperand(1))); |
Owen Anderson | 6475804 | 2007-06-22 21:31:16 +0000 | [diff] [blame] | 1149 | |
| 1150 | if (l != 0 && isa<Instruction>(l) && |
| 1151 | visited.count(l) == 0) |
| 1152 | stack.push_back(l); |
| 1153 | else if (r != 0 && isa<Instruction>(r) && |
| 1154 | visited.count(r) == 0) |
| 1155 | stack.push_back(r); |
| 1156 | else { |
| 1157 | vec.push_back(e); |
| 1158 | visited.insert(e); |
| 1159 | stack.pop_back(); |
| 1160 | } |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 1161 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1162 | // Handle ternary ops |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1163 | } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) || |
| 1164 | isa<SelectInst>(e)) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1165 | User* U = cast<User>(e); |
| 1166 | Value* l = find_leader(set, VN.lookup(U->getOperand(0))); |
| 1167 | Value* r = find_leader(set, VN.lookup(U->getOperand(1))); |
| 1168 | Value* m = find_leader(set, VN.lookup(U->getOperand(2))); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1169 | |
| 1170 | if (l != 0 && isa<Instruction>(l) && |
| 1171 | visited.count(l) == 0) |
| 1172 | stack.push_back(l); |
| 1173 | else if (r != 0 && isa<Instruction>(r) && |
| 1174 | visited.count(r) == 0) |
| 1175 | stack.push_back(r); |
| 1176 | else if (m != 0 && isa<Instruction>(m) && |
| 1177 | visited.count(m) == 0) |
Owen Anderson | df30b63 | 2007-07-04 18:26:18 +0000 | [diff] [blame] | 1178 | stack.push_back(m); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1179 | else { |
| 1180 | vec.push_back(e); |
| 1181 | visited.insert(e); |
| 1182 | stack.pop_back(); |
| 1183 | } |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1184 | |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1185 | // Handle vararg ops |
| 1186 | } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) { |
| 1187 | Value* p = find_leader(set, VN.lookup(U->getPointerOperand())); |
| 1188 | |
| 1189 | if (p != 0 && isa<Instruction>(p) && |
| 1190 | visited.count(p) == 0) |
| 1191 | stack.push_back(p); |
| 1192 | else { |
| 1193 | bool push_va = false; |
| 1194 | for (GetElementPtrInst::op_iterator I = U->idx_begin(), |
| 1195 | E = U->idx_end(); I != E; ++I) { |
| 1196 | Value * v = find_leader(set, VN.lookup(*I)); |
| 1197 | if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) { |
| 1198 | stack.push_back(v); |
| 1199 | push_va = true; |
| 1200 | } |
| 1201 | } |
| 1202 | |
| 1203 | if (!push_va) { |
| 1204 | vec.push_back(e); |
| 1205 | visited.insert(e); |
| 1206 | stack.pop_back(); |
| 1207 | } |
| 1208 | } |
| 1209 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1210 | // Handle opaque ops |
Owen Anderson | 6475804 | 2007-06-22 21:31:16 +0000 | [diff] [blame] | 1211 | } else { |
Owen Anderson | a724ac1 | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 1212 | visited.insert(e); |
Owen Anderson | 139fe84 | 2007-06-09 18:35:31 +0000 | [diff] [blame] | 1213 | vec.push_back(e); |
Owen Anderson | 6475804 | 2007-06-22 21:31:16 +0000 | [diff] [blame] | 1214 | stack.pop_back(); |
Owen Anderson | 139fe84 | 2007-06-09 18:35:31 +0000 | [diff] [blame] | 1215 | } |
Owen Anderson | 243f348 | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 1216 | } |
Owen Anderson | 6475804 | 2007-06-22 21:31:16 +0000 | [diff] [blame] | 1217 | |
| 1218 | stack.clear(); |
Owen Anderson | 243f348 | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 1219 | } |
| 1220 | } |
| 1221 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1222 | /// dump - Dump a set of values to standard error |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1223 | void GVNPRE::dump(ValueNumberedSet& s) const { |
Owen Anderson | cdf8efd | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 1224 | DOUT << "{ "; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1225 | for (ValueNumberedSet::iterator I = s.begin(), E = s.end(); |
Owen Anderson | 0fa6b37 | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 1226 | I != E; ++I) { |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1227 | DOUT << "" << VN.lookup(*I) << ": "; |
Owen Anderson | 0fa6b37 | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 1228 | DEBUG((*I)->dump()); |
| 1229 | } |
| 1230 | DOUT << "}\n\n"; |
| 1231 | } |
| 1232 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1233 | /// elimination - Phase 3 of the main algorithm. Perform full redundancy |
| 1234 | /// elimination by walking the dominator tree and removing any instruction that |
| 1235 | /// is dominated by another instruction with the same value number. |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1236 | bool GVNPRE::elimination() { |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1237 | bool changed_function = false; |
| 1238 | |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1239 | SmallVector<std::pair<Instruction*, Value*>, 8> replace; |
| 1240 | SmallVector<Instruction*, 8> erase; |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1241 | |
| 1242 | DominatorTree& DT = getAnalysis<DominatorTree>(); |
| 1243 | |
| 1244 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
| 1245 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 1246 | BasicBlock* BB = DI->getBlock(); |
| 1247 | |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1248 | for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); |
| 1249 | BI != BE; ++BI) { |
| 1250 | |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1251 | if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) || |
| 1252 | isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) || |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1253 | isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) || |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1254 | isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) { |
Owen Anderson | a05a81b | 2007-07-10 00:09:25 +0000 | [diff] [blame] | 1255 | |
Owen Anderson | 9fed589 | 2007-08-02 18:20:52 +0000 | [diff] [blame] | 1256 | if (availableOut[BB].test(VN.lookup(BI)) && |
| 1257 | !availableOut[BB].count(BI)) { |
Owen Anderson | a05a81b | 2007-07-10 00:09:25 +0000 | [diff] [blame] | 1258 | Value *leader = find_leader(availableOut[BB], VN.lookup(BI)); |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1259 | if (Instruction* Instr = dyn_cast<Instruction>(leader)) |
| 1260 | if (Instr->getParent() != 0 && Instr != BI) { |
| 1261 | replace.push_back(std::make_pair(BI, leader)); |
| 1262 | erase.push_back(BI); |
| 1263 | ++NumEliminated; |
| 1264 | } |
Owen Anderson | a05a81b | 2007-07-10 00:09:25 +0000 | [diff] [blame] | 1265 | } |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1266 | } |
| 1267 | } |
| 1268 | } |
| 1269 | |
| 1270 | while (!replace.empty()) { |
| 1271 | std::pair<Instruction*, Value*> rep = replace.back(); |
| 1272 | replace.pop_back(); |
| 1273 | rep.first->replaceAllUsesWith(rep.second); |
Owen Anderson | 0304b2b | 2007-06-20 18:30:20 +0000 | [diff] [blame] | 1274 | changed_function = true; |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1275 | } |
| 1276 | |
Owen Anderson | 9fed589 | 2007-08-02 18:20:52 +0000 | [diff] [blame] | 1277 | for (SmallVector<Instruction*, 8>::iterator I = erase.begin(), |
| 1278 | E = erase.end(); I != E; ++I) |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1279 | (*I)->eraseFromParent(); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1280 | |
| 1281 | return changed_function; |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1282 | } |
| 1283 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1284 | /// cleanup - Delete any extraneous values that were created to represent |
| 1285 | /// expressions without leaders. |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1286 | void GVNPRE::cleanup() { |
| 1287 | while (!createdExpressions.empty()) { |
| 1288 | Instruction* I = createdExpressions.back(); |
| 1289 | createdExpressions.pop_back(); |
| 1290 | |
| 1291 | delete I; |
| 1292 | } |
| 1293 | } |
| 1294 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1295 | /// buildsets_availout - When calculating availability, handle an instruction |
| 1296 | /// by inserting it into the appropriate sets |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1297 | void GVNPRE::buildsets_availout(BasicBlock::iterator I, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1298 | ValueNumberedSet& currAvail, |
| 1299 | ValueNumberedSet& currPhis, |
| 1300 | ValueNumberedSet& currExps, |
| 1301 | SmallPtrSet<Value*, 16>& currTemps) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1302 | // Handle PHI nodes |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1303 | if (PHINode* p = dyn_cast<PHINode>(I)) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1304 | unsigned num = VN.lookup_or_add(p); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1305 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1306 | currPhis.insert(p); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1307 | currPhis.set(num); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1308 | |
| 1309 | // Handle unary ops |
Owen Anderson | 3d6fac3 | 2007-07-03 19:01:42 +0000 | [diff] [blame] | 1310 | } else if (CastInst* U = dyn_cast<CastInst>(I)) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1311 | Value* leftValue = U->getOperand(0); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1312 | |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1313 | unsigned num = VN.lookup_or_add(U); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1314 | |
| 1315 | if (isa<Instruction>(leftValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1316 | if (!currExps.test(VN.lookup(leftValue))) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1317 | currExps.insert(leftValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1318 | currExps.set(VN.lookup(leftValue)); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1319 | } |
| 1320 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1321 | if (!currExps.test(num)) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1322 | currExps.insert(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1323 | currExps.set(num); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1324 | } |
| 1325 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1326 | // Handle binary ops |
| 1327 | } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || |
| 1328 | isa<ExtractElementInst>(I)) { |
| 1329 | User* U = cast<User>(I); |
| 1330 | Value* leftValue = U->getOperand(0); |
| 1331 | Value* rightValue = U->getOperand(1); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1332 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1333 | unsigned num = VN.lookup_or_add(U); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1334 | |
| 1335 | if (isa<Instruction>(leftValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1336 | if (!currExps.test(VN.lookup(leftValue))) { |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1337 | currExps.insert(leftValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1338 | currExps.set(VN.lookup(leftValue)); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1339 | } |
| 1340 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1341 | if (isa<Instruction>(rightValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1342 | if (!currExps.test(VN.lookup(rightValue))) { |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1343 | currExps.insert(rightValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1344 | currExps.set(VN.lookup(rightValue)); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1345 | } |
| 1346 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1347 | if (!currExps.test(num)) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1348 | currExps.insert(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1349 | currExps.set(num); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1350 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1351 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1352 | // Handle ternary ops |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1353 | } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) || |
| 1354 | isa<SelectInst>(I)) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1355 | User* U = cast<User>(I); |
| 1356 | Value* leftValue = U->getOperand(0); |
| 1357 | Value* rightValue = U->getOperand(1); |
| 1358 | Value* thirdValue = U->getOperand(2); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1359 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1360 | VN.lookup_or_add(U); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1361 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1362 | unsigned num = VN.lookup_or_add(U); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1363 | |
| 1364 | if (isa<Instruction>(leftValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1365 | if (!currExps.test(VN.lookup(leftValue))) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1366 | currExps.insert(leftValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1367 | currExps.set(VN.lookup(leftValue)); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1368 | } |
| 1369 | if (isa<Instruction>(rightValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1370 | if (!currExps.test(VN.lookup(rightValue))) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1371 | currExps.insert(rightValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1372 | currExps.set(VN.lookup(rightValue)); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1373 | } |
| 1374 | if (isa<Instruction>(thirdValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1375 | if (!currExps.test(VN.lookup(thirdValue))) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1376 | currExps.insert(thirdValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1377 | currExps.set(VN.lookup(thirdValue)); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1378 | } |
| 1379 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1380 | if (!currExps.test(num)) { |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1381 | currExps.insert(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1382 | currExps.set(num); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1383 | } |
| 1384 | |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1385 | // Handle vararg ops |
| 1386 | } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) { |
| 1387 | Value* ptrValue = U->getPointerOperand(); |
| 1388 | |
| 1389 | VN.lookup_or_add(U); |
| 1390 | |
| 1391 | unsigned num = VN.lookup_or_add(U); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1392 | |
| 1393 | if (isa<Instruction>(ptrValue)) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1394 | if (!currExps.test(VN.lookup(ptrValue))) { |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1395 | currExps.insert(ptrValue); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1396 | currExps.set(VN.lookup(ptrValue)); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1397 | } |
| 1398 | |
| 1399 | for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end(); |
| 1400 | OI != OE; ++OI) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1401 | if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) { |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1402 | currExps.insert(*OI); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1403 | currExps.set(VN.lookup(*OI)); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1404 | } |
| 1405 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1406 | if (!currExps.test(VN.lookup(U))) { |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1407 | currExps.insert(U); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1408 | currExps.set(num); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1409 | } |
| 1410 | |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1411 | // Handle opaque ops |
| 1412 | } else if (!I->isTerminator()){ |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1413 | VN.lookup_or_add(I); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1414 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1415 | currTemps.insert(I); |
| 1416 | } |
| 1417 | |
| 1418 | if (!I->isTerminator()) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1419 | if (!currAvail.test(VN.lookup(I))) { |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1420 | currAvail.insert(I); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1421 | currAvail.set(VN.lookup(I)); |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1422 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1423 | } |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1424 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1425 | /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT |
| 1426 | /// set as a function of the ANTIC_IN set of the block's predecessors |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1427 | bool GVNPRE::buildsets_anticout(BasicBlock* BB, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1428 | ValueNumberedSet& anticOut, |
Owen Anderson | b978198 | 2007-07-19 03:32:44 +0000 | [diff] [blame] | 1429 | SmallPtrSet<BasicBlock*, 8>& visited) { |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1430 | if (BB->getTerminator()->getNumSuccessors() == 1) { |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 1431 | if (BB->getTerminator()->getSuccessor(0) != BB && |
| 1432 | visited.count(BB->getTerminator()->getSuccessor(0)) == 0) { |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1433 | return true; |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 1434 | } |
| 1435 | else { |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1436 | phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)], |
| 1437 | BB, BB->getTerminator()->getSuccessor(0), anticOut); |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 1438 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1439 | } else if (BB->getTerminator()->getNumSuccessors() > 1) { |
| 1440 | BasicBlock* first = BB->getTerminator()->getSuccessor(0); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1441 | for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(), |
| 1442 | E = anticipatedIn[first].end(); I != E; ++I) { |
| 1443 | anticOut.insert(*I); |
| 1444 | anticOut.set(VN.lookup(*I)); |
| 1445 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1446 | |
| 1447 | for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) { |
| 1448 | BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1449 | ValueNumberedSet& succAnticIn = anticipatedIn[currSucc]; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1450 | |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1451 | SmallVector<Value*, 16> temp; |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 1452 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1453 | for (ValueNumberedSet::iterator I = anticOut.begin(), |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 1454 | E = anticOut.end(); I != E; ++I) |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1455 | if (!succAnticIn.test(VN.lookup(*I))) |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 1456 | temp.push_back(*I); |
| 1457 | |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1458 | for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end(); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1459 | I != E; ++I) { |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 1460 | anticOut.erase(*I); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1461 | anticOut.reset(VN.lookup(*I)); |
| 1462 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1463 | } |
| 1464 | } |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1465 | |
| 1466 | return false; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1467 | } |
| 1468 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1469 | /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for |
| 1470 | /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN |
| 1471 | /// sets populated in buildsets_availout |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1472 | unsigned GVNPRE::buildsets_anticin(BasicBlock* BB, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1473 | ValueNumberedSet& anticOut, |
| 1474 | ValueNumberedSet& currExps, |
Owen Anderson | a20f35d | 2007-06-28 00:34:34 +0000 | [diff] [blame] | 1475 | SmallPtrSet<Value*, 16>& currTemps, |
Owen Anderson | b978198 | 2007-07-19 03:32:44 +0000 | [diff] [blame] | 1476 | SmallPtrSet<BasicBlock*, 8>& visited) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1477 | ValueNumberedSet& anticIn = anticipatedIn[BB]; |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1478 | unsigned old = anticIn.size(); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1479 | |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1480 | bool defer = buildsets_anticout(BB, anticOut, visited); |
| 1481 | if (defer) |
| 1482 | return 0; |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 1483 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1484 | anticIn.clear(); |
Owen Anderson | 66fd906 | 2007-06-21 17:57:53 +0000 | [diff] [blame] | 1485 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1486 | for (ValueNumberedSet::iterator I = anticOut.begin(), |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1487 | E = anticOut.end(); I != E; ++I) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1488 | anticIn.insert(*I); |
| 1489 | anticIn.set(VN.lookup(*I)); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1490 | } |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1491 | for (ValueNumberedSet::iterator I = currExps.begin(), |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1492 | E = currExps.end(); I != E; ++I) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1493 | if (!anticIn.test(VN.lookup(*I))) { |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1494 | anticIn.insert(*I); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1495 | anticIn.set(VN.lookup(*I)); |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1496 | } |
| 1497 | } |
| 1498 | |
Owen Anderson | a20f35d | 2007-06-28 00:34:34 +0000 | [diff] [blame] | 1499 | for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(), |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1500 | E = currTemps.end(); I != E; ++I) { |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1501 | anticIn.erase(*I); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1502 | anticIn.reset(VN.lookup(*I)); |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1503 | } |
Owen Anderson | 2106f61 | 2007-06-22 18:27:04 +0000 | [diff] [blame] | 1504 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1505 | clean(anticIn); |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1506 | anticOut.clear(); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1507 | |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1508 | if (old != anticIn.size()) |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1509 | return 2; |
Owen Anderson | 68cb52e | 2007-06-27 17:38:29 +0000 | [diff] [blame] | 1510 | else |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1511 | return 1; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1512 | } |
| 1513 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1514 | /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT |
| 1515 | /// and the ANTIC_IN sets. |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1516 | void GVNPRE::buildsets(Function& F) { |
Owen Anderson | b978198 | 2007-07-19 03:32:44 +0000 | [diff] [blame] | 1517 | DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions; |
| 1518 | DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1519 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1520 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
| 1521 | |
Owen Anderson | 12112af | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 1522 | // Phase 1, Part 1: calculate AVAIL_OUT |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1523 | |
| 1524 | // Top-down walk of the dominator tree |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 1525 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1526 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 1527 | |
| 1528 | // Get the sets to update for this block |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1529 | ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()]; |
| 1530 | ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()]; |
Owen Anderson | a20f35d | 2007-06-28 00:34:34 +0000 | [diff] [blame] | 1531 | SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()]; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1532 | ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1533 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 1534 | BasicBlock* BB = DI->getBlock(); |
| 1535 | |
| 1536 | // A block inherits AVAIL_OUT from its dominator |
Owen Anderson | dfa2435 | 2007-07-09 22:29:50 +0000 | [diff] [blame] | 1537 | if (DI->getIDom() != 0) |
| 1538 | currAvail = availableOut[DI->getIDom()->getBlock()]; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1539 | |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 1540 | for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1541 | BI != BE; ++BI) |
Owen Anderson | 1240846 | 2007-06-22 03:14:03 +0000 | [diff] [blame] | 1542 | buildsets_availout(BI, currAvail, currPhis, currExps, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1543 | currTemps); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 1544 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1545 | } |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 1546 | |
| 1547 | // Phase 1, Part 2: calculate ANTIC_IN |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1548 | |
Owen Anderson | b978198 | 2007-07-19 03:32:44 +0000 | [diff] [blame] | 1549 | SmallPtrSet<BasicBlock*, 8> visited; |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1550 | SmallPtrSet<BasicBlock*, 4> block_changed; |
| 1551 | for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) |
| 1552 | block_changed.insert(FI); |
Owen Anderson | e3072b2 | 2007-05-29 23:26:30 +0000 | [diff] [blame] | 1553 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1554 | bool changed = true; |
| 1555 | unsigned iterations = 0; |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1556 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1557 | while (changed) { |
| 1558 | changed = false; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1559 | ValueNumberedSet anticOut; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1560 | |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1561 | // Postorder walk of the CFG |
Owen Anderson | 9030d38 | 2007-06-25 18:25:31 +0000 | [diff] [blame] | 1562 | for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()), |
| 1563 | BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) { |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 1564 | BasicBlock* BB = *BBI; |
Owen Anderson | 0e71466 | 2007-06-11 16:25:17 +0000 | [diff] [blame] | 1565 | |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1566 | if (block_changed.count(BB) != 0) { |
| 1567 | unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB], |
| 1568 | generatedTemporaries[BB], visited); |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1569 | |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1570 | if (ret == 0) { |
| 1571 | changed = true; |
| 1572 | continue; |
| 1573 | } else { |
| 1574 | visited.insert(BB); |
| 1575 | |
| 1576 | if (ret == 2) |
| 1577 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); |
| 1578 | PI != PE; ++PI) { |
| 1579 | block_changed.insert(*PI); |
| 1580 | } |
| 1581 | else |
| 1582 | block_changed.erase(BB); |
| 1583 | |
| 1584 | changed |= (ret == 2); |
Owen Anderson | f62c44a | 2007-06-25 05:41:12 +0000 | [diff] [blame] | 1585 | } |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1586 | } |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1587 | } |
Owen Anderson | 5ea069f | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 1588 | |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1589 | iterations++; |
| 1590 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1591 | } |
| 1592 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1593 | /// insertion_pre - When a partial redundancy has been identified, eliminate it |
| 1594 | /// by inserting appropriate values into the predecessors and a phi node in |
| 1595 | /// the main block |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1596 | void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1597 | DenseMap<BasicBlock*, Value*>& avail, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1598 | std::map<BasicBlock*, ValueNumberedSet>& new_sets) { |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1599 | LLVMContext &Context = e->getContext(); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1600 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { |
| 1601 | Value* e2 = avail[*PI]; |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1602 | if (!availableOut[*PI].test(VN.lookup(e2))) { |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1603 | User* U = cast<User>(e2); |
| 1604 | |
| 1605 | Value* s1 = 0; |
| 1606 | if (isa<BinaryOperator>(U->getOperand(0)) || |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1607 | isa<CmpInst>(U->getOperand(0)) || |
| 1608 | isa<ShuffleVectorInst>(U->getOperand(0)) || |
| 1609 | isa<ExtractElementInst>(U->getOperand(0)) || |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1610 | isa<InsertElementInst>(U->getOperand(0)) || |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1611 | isa<SelectInst>(U->getOperand(0)) || |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1612 | isa<CastInst>(U->getOperand(0)) || |
| 1613 | isa<GetElementPtrInst>(U->getOperand(0))) |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1614 | s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0))); |
| 1615 | else |
| 1616 | s1 = U->getOperand(0); |
| 1617 | |
| 1618 | Value* s2 = 0; |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1619 | |
| 1620 | if (isa<BinaryOperator>(U) || |
| 1621 | isa<CmpInst>(U) || |
| 1622 | isa<ShuffleVectorInst>(U) || |
| 1623 | isa<ExtractElementInst>(U) || |
| 1624 | isa<InsertElementInst>(U) || |
Anton Korobeynikov | 07e6e56 | 2008-02-20 11:26:25 +0000 | [diff] [blame] | 1625 | isa<SelectInst>(U)) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1626 | if (isa<BinaryOperator>(U->getOperand(1)) || |
| 1627 | isa<CmpInst>(U->getOperand(1)) || |
| 1628 | isa<ShuffleVectorInst>(U->getOperand(1)) || |
| 1629 | isa<ExtractElementInst>(U->getOperand(1)) || |
| 1630 | isa<InsertElementInst>(U->getOperand(1)) || |
| 1631 | isa<SelectInst>(U->getOperand(1)) || |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1632 | isa<CastInst>(U->getOperand(1)) || |
| 1633 | isa<GetElementPtrInst>(U->getOperand(1))) { |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1634 | s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1))); |
| 1635 | } else { |
| 1636 | s2 = U->getOperand(1); |
| 1637 | } |
Anton Korobeynikov | 07e6e56 | 2008-02-20 11:26:25 +0000 | [diff] [blame] | 1638 | } |
Owen Anderson | 7b317d2 | 2007-06-27 17:03:03 +0000 | [diff] [blame] | 1639 | |
| 1640 | // Ternary Operators |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1641 | Value* s3 = 0; |
| 1642 | if (isa<ShuffleVectorInst>(U) || |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1643 | isa<InsertElementInst>(U) || |
Anton Korobeynikov | 07e6e56 | 2008-02-20 11:26:25 +0000 | [diff] [blame] | 1644 | isa<SelectInst>(U)) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1645 | if (isa<BinaryOperator>(U->getOperand(2)) || |
| 1646 | isa<CmpInst>(U->getOperand(2)) || |
| 1647 | isa<ShuffleVectorInst>(U->getOperand(2)) || |
| 1648 | isa<ExtractElementInst>(U->getOperand(2)) || |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1649 | isa<InsertElementInst>(U->getOperand(2)) || |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1650 | isa<SelectInst>(U->getOperand(2)) || |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1651 | isa<CastInst>(U->getOperand(2)) || |
| 1652 | isa<GetElementPtrInst>(U->getOperand(2))) { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1653 | s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2))); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1654 | } else { |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1655 | s3 = U->getOperand(2); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1656 | } |
Anton Korobeynikov | 07e6e56 | 2008-02-20 11:26:25 +0000 | [diff] [blame] | 1657 | } |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1658 | |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1659 | // Vararg operators |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1660 | SmallVector<Value*, 4> sVarargs; |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1661 | if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) { |
| 1662 | for (GetElementPtrInst::op_iterator OI = G->idx_begin(), |
| 1663 | OE = G->idx_end(); OI != OE; ++OI) { |
| 1664 | if (isa<BinaryOperator>(*OI) || |
| 1665 | isa<CmpInst>(*OI) || |
| 1666 | isa<ShuffleVectorInst>(*OI) || |
| 1667 | isa<ExtractElementInst>(*OI) || |
| 1668 | isa<InsertElementInst>(*OI) || |
| 1669 | isa<SelectInst>(*OI) || |
| 1670 | isa<CastInst>(*OI) || |
| 1671 | isa<GetElementPtrInst>(*OI)) { |
| 1672 | sVarargs.push_back(find_leader(availableOut[*PI], |
| 1673 | VN.lookup(*OI))); |
| 1674 | } else { |
| 1675 | sVarargs.push_back(*OI); |
| 1676 | } |
| 1677 | } |
| 1678 | } |
| 1679 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1680 | Value* newVal = 0; |
| 1681 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U)) |
Gabor Greif | 7cbd8a3 | 2008-05-16 19:29:10 +0000 | [diff] [blame] | 1682 | newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2, |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1683 | BO->getName()+".gvnpre", |
| 1684 | (*PI)->getTerminator()); |
| 1685 | else if (CmpInst* C = dyn_cast<CmpInst>(U)) |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1686 | newVal = CmpInst::Create(Context, C->getOpcode(), |
Owen Anderson | 333c400 | 2009-07-09 23:48:35 +0000 | [diff] [blame] | 1687 | C->getPredicate(), s1, s2, |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1688 | C->getName()+".gvnpre", |
| 1689 | (*PI)->getTerminator()); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1690 | else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U)) |
| 1691 | newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre", |
| 1692 | (*PI)->getTerminator()); |
| 1693 | else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U)) |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 1694 | newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre", |
| 1695 | (*PI)->getTerminator()); |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1696 | else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U)) |
Eric Christopher | a3500da | 2009-07-25 02:28:41 +0000 | [diff] [blame^] | 1697 | newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre", |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1698 | (*PI)->getTerminator()); |
Owen Anderson | 890e1a0 | 2007-06-28 23:51:21 +0000 | [diff] [blame] | 1699 | else if (SelectInst* S = dyn_cast<SelectInst>(U)) |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 1700 | newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre", |
| 1701 | (*PI)->getTerminator()); |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1702 | else if (CastInst* C = dyn_cast<CastInst>(U)) |
Gabor Greif | 7cbd8a3 | 2008-05-16 19:29:10 +0000 | [diff] [blame] | 1703 | newVal = CastInst::Create(C->getOpcode(), s1, C->getType(), |
Owen Anderson | 216394f | 2007-07-03 18:37:08 +0000 | [diff] [blame] | 1704 | C->getName()+".gvnpre", |
| 1705 | (*PI)->getTerminator()); |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1706 | else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 1707 | newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(), |
| 1708 | G->getName()+".gvnpre", |
| 1709 | (*PI)->getTerminator()); |
| 1710 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1711 | VN.add(newVal, VN.lookup(U)); |
| 1712 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1713 | ValueNumberedSet& predAvail = availableOut[*PI]; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1714 | val_replace(predAvail, newVal); |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 1715 | val_replace(new_sets[*PI], newVal); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1716 | predAvail.set(VN.lookup(newVal)); |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1717 | |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1718 | DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1719 | if (av != avail.end()) |
| 1720 | avail.erase(av); |
| 1721 | avail.insert(std::make_pair(*PI, newVal)); |
| 1722 | |
| 1723 | ++NumInsertedVals; |
| 1724 | } |
| 1725 | } |
| 1726 | |
| 1727 | PHINode* p = 0; |
| 1728 | |
| 1729 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { |
| 1730 | if (p == 0) |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 1731 | p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin()); |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 1732 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1733 | p->addIncoming(avail[*PI], *PI); |
| 1734 | } |
| 1735 | |
| 1736 | VN.add(p, VN.lookup(e)); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1737 | val_replace(availableOut[BB], p); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1738 | availableOut[BB].set(VN.lookup(e)); |
Owen Anderson | ec5614b | 2007-07-06 20:29:43 +0000 | [diff] [blame] | 1739 | generatedPhis[BB].insert(p); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1740 | generatedPhis[BB].set(VN.lookup(e)); |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 1741 | new_sets[BB].insert(p); |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1742 | new_sets[BB].set(VN.lookup(e)); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1743 | |
| 1744 | ++NumInsertedPhis; |
| 1745 | } |
| 1746 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1747 | /// insertion_mergepoint - When walking the dom tree, check at each merge |
| 1748 | /// block for the possibility of a partial redundancy. If present, eliminate it |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1749 | unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList, |
Owen Anderson | 82575d8 | 2007-06-22 00:20:30 +0000 | [diff] [blame] | 1750 | df_iterator<DomTreeNode*>& D, |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1751 | std::map<BasicBlock*, ValueNumberedSet >& new_sets) { |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1752 | bool changed_function = false; |
| 1753 | bool new_stuff = false; |
| 1754 | |
| 1755 | BasicBlock* BB = D->getBlock(); |
| 1756 | for (unsigned i = 0; i < workList.size(); ++i) { |
| 1757 | Value* e = workList[i]; |
| 1758 | |
Owen Anderson | 62cf8ba | 2007-06-27 04:10:46 +0000 | [diff] [blame] | 1759 | if (isa<BinaryOperator>(e) || isa<CmpInst>(e) || |
| 1760 | isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) || |
Owen Anderson | 5653322 | 2007-07-03 23:51:19 +0000 | [diff] [blame] | 1761 | isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) || |
| 1762 | isa<GetElementPtrInst>(e)) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1763 | if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e))) |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1764 | continue; |
| 1765 | |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1766 | DenseMap<BasicBlock*, Value*> avail; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1767 | bool by_some = false; |
Owen Anderson | ec5614b | 2007-07-06 20:29:43 +0000 | [diff] [blame] | 1768 | bool all_same = true; |
| 1769 | Value * first_s = 0; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1770 | |
| 1771 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; |
| 1772 | ++PI) { |
| 1773 | Value *e2 = phi_translate(e, *PI, BB); |
| 1774 | Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2)); |
| 1775 | |
| 1776 | if (e3 == 0) { |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1777 | DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1778 | if (av != avail.end()) |
| 1779 | avail.erase(av); |
| 1780 | avail.insert(std::make_pair(*PI, e2)); |
Owen Anderson | ec5614b | 2007-07-06 20:29:43 +0000 | [diff] [blame] | 1781 | all_same = false; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1782 | } else { |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1783 | DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1784 | if (av != avail.end()) |
| 1785 | avail.erase(av); |
| 1786 | avail.insert(std::make_pair(*PI, e3)); |
| 1787 | |
| 1788 | by_some = true; |
Owen Anderson | ec5614b | 2007-07-06 20:29:43 +0000 | [diff] [blame] | 1789 | if (first_s == 0) |
| 1790 | first_s = e3; |
| 1791 | else if (first_s != e3) |
| 1792 | all_same = false; |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1793 | } |
| 1794 | } |
| 1795 | |
Owen Anderson | ec5614b | 2007-07-06 20:29:43 +0000 | [diff] [blame] | 1796 | if (by_some && !all_same && |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1797 | !generatedPhis[BB].test(VN.lookup(e))) { |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 1798 | insertion_pre(e, BB, avail, new_sets); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1799 | |
| 1800 | changed_function = true; |
| 1801 | new_stuff = true; |
| 1802 | } |
| 1803 | } |
| 1804 | } |
| 1805 | |
| 1806 | unsigned retval = 0; |
| 1807 | if (changed_function) |
| 1808 | retval += 1; |
| 1809 | if (new_stuff) |
| 1810 | retval += 2; |
| 1811 | |
| 1812 | return retval; |
| 1813 | } |
| 1814 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1815 | /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for |
| 1816 | /// merge points. When one is found, check for a partial redundancy. If one is |
| 1817 | /// present, eliminate it. Repeat this walk until no changes are made. |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1818 | bool GVNPRE::insertion(Function& F) { |
| 1819 | bool changed_function = false; |
| 1820 | |
| 1821 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1822 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1823 | std::map<BasicBlock*, ValueNumberedSet> new_sets; |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1824 | bool new_stuff = true; |
| 1825 | while (new_stuff) { |
| 1826 | new_stuff = false; |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1827 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
| 1828 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 1829 | BasicBlock* BB = DI->getBlock(); |
| 1830 | |
Owen Anderson | 0e71466 | 2007-06-11 16:25:17 +0000 | [diff] [blame] | 1831 | if (BB == 0) |
| 1832 | continue; |
| 1833 | |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1834 | ValueNumberedSet& availOut = availableOut[BB]; |
| 1835 | ValueNumberedSet& anticIn = anticipatedIn[BB]; |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1836 | |
| 1837 | // Replace leaders with leaders inherited from dominator |
| 1838 | if (DI->getIDom() != 0) { |
Owen Anderson | 0616dff | 2007-07-09 06:50:06 +0000 | [diff] [blame] | 1839 | ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()]; |
| 1840 | for (ValueNumberedSet::iterator I = dom_set.begin(), |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1841 | E = dom_set.end(); I != E; ++I) { |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 1842 | val_replace(new_sets[BB], *I); |
Owen Anderson | 086f5f3 | 2007-06-19 03:31:41 +0000 | [diff] [blame] | 1843 | val_replace(availOut, *I); |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1844 | } |
| 1845 | } |
| 1846 | |
| 1847 | // If there is more than one predecessor... |
| 1848 | if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) { |
Owen Anderson | 19bc4a8 | 2007-07-19 06:37:56 +0000 | [diff] [blame] | 1849 | SmallVector<Value*, 8> workList; |
Owen Anderson | e8138ff | 2007-06-22 00:43:22 +0000 | [diff] [blame] | 1850 | workList.reserve(anticIn.size()); |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1851 | topo_sort(anticIn, workList); |
| 1852 | |
Owen Anderson | 2a5c9d8 | 2007-07-05 23:11:26 +0000 | [diff] [blame] | 1853 | unsigned result = insertion_mergepoint(workList, DI, new_sets); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1854 | if (result & 1) |
| 1855 | changed_function = true; |
| 1856 | if (result & 2) |
| 1857 | new_stuff = true; |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1858 | } |
| 1859 | } |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1860 | } |
Owen Anderson | 12112af | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 1861 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1862 | return changed_function; |
| 1863 | } |
| 1864 | |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1865 | // GVNPRE::runOnFunction - This is the main transformation entry point for a |
| 1866 | // function. |
| 1867 | // |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1868 | bool GVNPRE::runOnFunction(Function &F) { |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1869 | // Clean out global sets from any previous functions |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1870 | VN.clear(); |
| 1871 | createdExpressions.clear(); |
| 1872 | availableOut.clear(); |
| 1873 | anticipatedIn.clear(); |
Owen Anderson | ec5614b | 2007-07-06 20:29:43 +0000 | [diff] [blame] | 1874 | generatedPhis.clear(); |
| 1875 | |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1876 | bool changed_function = false; |
| 1877 | |
| 1878 | // Phase 1: BuildSets |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1879 | // This phase calculates the AVAIL_OUT and ANTIC_IN sets |
Owen Anderson | 6032a5b | 2007-06-26 23:29:41 +0000 | [diff] [blame] | 1880 | buildsets(F); |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1881 | |
| 1882 | // Phase 2: Insert |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1883 | // This phase inserts values to make partially redundant values |
| 1884 | // fully redundant |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1885 | changed_function |= insertion(F); |
| 1886 | |
Owen Anderson | 12112af | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 1887 | // Phase 3: Eliminate |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1888 | // This phase performs trivial full redundancy elimination |
Owen Anderson | 3eaca71 | 2007-06-20 22:10:02 +0000 | [diff] [blame] | 1889 | changed_function |= elimination(); |
Owen Anderson | 8338ff5 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 1890 | |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1891 | // Phase 4: Cleanup |
Owen Anderson | 9cb5601 | 2007-06-21 00:19:05 +0000 | [diff] [blame] | 1892 | // This phase cleans up values that were created solely |
| 1893 | // as leaders for expressions |
Owen Anderson | 239e712 | 2007-06-12 16:57:50 +0000 | [diff] [blame] | 1894 | cleanup(); |
Owen Anderson | 397d405 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 1895 | |
Owen Anderson | 0304b2b | 2007-06-20 18:30:20 +0000 | [diff] [blame] | 1896 | return changed_function; |
Owen Anderson | ea12a06 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1897 | } |