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