src/v8/src/compiler/machine-operator-reducer.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/machine-operator-reducer.h"
   6
   7 #include "src/compiler/common-node-cache.h"
   8 #include "src/compiler/generic-node-inl.h"
   9 #include "src/compiler/graph.h"
  10 #include "src/compiler/node-matchers.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14 namespace compiler {
  15
  16 MachineOperatorReducer::MachineOperatorReducer(Graph* graph)
  17     : graph_(graph),
  18       cache_(new (graph->zone()) CommonNodeCache(graph->zone())),
  19       common_(graph->zone()),
  20       machine_(graph->zone()) {}
  21
  22
  23 MachineOperatorReducer::MachineOperatorReducer(Graph* graph,
  24                                                CommonNodeCache* cache)
  25     : graph_(graph),
  26       cache_(cache),
  27       common_(graph->zone()),
  28       machine_(graph->zone()) {}
  29
  30
  31 Node* MachineOperatorReducer::Int32Constant(int32_t value) {
  32   Node** loc = cache_->FindInt32Constant(value);
  33   if (*loc == NULL) {
  34     *loc = graph_->NewNode(common_.Int32Constant(value));
  35   }
  36   return *loc;
  37 }
  38
  39
  40 Node* MachineOperatorReducer::Float64Constant(volatile double value) {
  41   Node** loc = cache_->FindFloat64Constant(value);
  42   if (*loc == NULL) {
  43     *loc = graph_->NewNode(common_.Float64Constant(value));
  44   }
  45   return *loc;
  46 }
  47
  48
  49 // Perform constant folding and strength reduction on machine operators.
  50 Reduction MachineOperatorReducer::Reduce(Node* node) {
  51   switch (node->opcode()) {
  52     case IrOpcode::kWord32And: {
  53       Int32BinopMatcher m(node);
  54       if (m.right().Is(0)) return Replace(m.right().node());  // x & 0  => 0
  55       if (m.right().Is(-1)) return Replace(m.left().node());  // x & -1 => x
  56       if (m.IsFoldable()) {                                   // K & K  => K
  57         return ReplaceInt32(m.left().Value() & m.right().Value());
  58       }
  59       if (m.LeftEqualsRight()) return Replace(m.left().node());  // x & x => x
  60       break;
  61     }
  62     case IrOpcode::kWord32Or: {
  63       Int32BinopMatcher m(node);
  64       if (m.right().Is(0)) return Replace(m.left().node());    // x | 0  => x
  65       if (m.right().Is(-1)) return Replace(m.right().node());  // x | -1 => -1
  66       if (m.IsFoldable()) {                                    // K | K  => K
  67         return ReplaceInt32(m.left().Value() | m.right().Value());
  68       }
  69       if (m.LeftEqualsRight()) return Replace(m.left().node());  // x | x => x
  70       break;
  71     }
  72     case IrOpcode::kWord32Xor: {
  73       Int32BinopMatcher m(node);
  74       if (m.right().Is(0)) return Replace(m.left().node());  // x ^ 0 => x
  75       if (m.IsFoldable()) {                                  // K ^ K => K
  76         return ReplaceInt32(m.left().Value() ^ m.right().Value());
  77       }
  78       if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x ^ x => 0
  79       break;
  80     }
  81     case IrOpcode::kWord32Shl: {
  82       Int32BinopMatcher m(node);
  83       if (m.right().Is(0)) return Replace(m.left().node());  // x << 0 => x
  84       if (m.IsFoldable()) {                                  // K << K => K
  85         return ReplaceInt32(m.left().Value() << m.right().Value());
  86       }
  87       break;
  88     }
  89     case IrOpcode::kWord32Shr: {
  90       Uint32BinopMatcher m(node);
  91       if (m.right().Is(0)) return Replace(m.left().node());  // x >>> 0 => x
  92       if (m.IsFoldable()) {                                  // K >>> K => K
  93         return ReplaceInt32(m.left().Value() >> m.right().Value());
  94       }
  95       break;
  96     }
  97     case IrOpcode::kWord32Sar: {
  98       Int32BinopMatcher m(node);
  99       if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
 100       if (m.IsFoldable()) {                                  // K >> K => K
 101         return ReplaceInt32(m.left().Value() >> m.right().Value());
 102       }
 103       break;
 104     }
 105     case IrOpcode::kWord32Equal: {
 106       Int32BinopMatcher m(node);
 107       if (m.IsFoldable()) {  // K == K => K
 108         return ReplaceBool(m.left().Value() == m.right().Value());
 109       }
 110       if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y == 0 => x == y
 111         Int32BinopMatcher msub(m.left().node());
 112         node->ReplaceInput(0, msub.left().node());
 113         node->ReplaceInput(1, msub.right().node());
 114         return Changed(node);
 115       }
 116       // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
 117       if (m.LeftEqualsRight()) return ReplaceBool(true);  // x == x => true
 118       break;
 119     }
 120     case IrOpcode::kInt32Add: {
 121       Int32BinopMatcher m(node);
 122       if (m.right().Is(0)) return Replace(m.left().node());  // x + 0 => x
 123       if (m.IsFoldable()) {                                  // K + K => K
 124         return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) +
 125                             static_cast<uint32_t>(m.right().Value()));
 126       }
 127       break;
 128     }
 129     case IrOpcode::kInt32Sub: {
 130       Int32BinopMatcher m(node);
 131       if (m.right().Is(0)) return Replace(m.left().node());  // x - 0 => x
 132       if (m.IsFoldable()) {                                  // K - K => K
 133         return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) -
 134                             static_cast<uint32_t>(m.right().Value()));
 135       }
 136       if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x - x => 0
 137       break;
 138     }
 139     case IrOpcode::kInt32Mul: {
 140       Int32BinopMatcher m(node);
 141       if (m.right().Is(0)) return Replace(m.right().node());  // x * 0 => 0
 142       if (m.right().Is(1)) return Replace(m.left().node());   // x * 1 => x
 143       if (m.IsFoldable()) {                                   // K * K => K
 144         return ReplaceInt32(m.left().Value() * m.right().Value());
 145       }
 146       if (m.right().Is(-1)) {  // x * -1 => 0 - x
 147         graph_->ChangeOperator(node, machine_.Int32Sub());
 148         node->ReplaceInput(0, Int32Constant(0));
 149         node->ReplaceInput(1, m.left().node());
 150         return Changed(node);
 151       }
 152       if (m.right().IsPowerOf2()) {  // x * 2^n => x << n
 153         graph_->ChangeOperator(node, machine_.Word32Shl());
 154         node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
 155         return Changed(node);
 156       }
 157       break;
 158     }
 159     case IrOpcode::kInt32Div: {
 160       Int32BinopMatcher m(node);
 161       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1 => x
 162       // TODO(turbofan): if (m.left().Is(0))
 163       // TODO(turbofan): if (m.right().IsPowerOf2())
 164       // TODO(turbofan): if (m.right().Is(0))
 165       // TODO(turbofan): if (m.LeftEqualsRight())
 166       if (m.IsFoldable() && !m.right().Is(0)) {  // K / K => K
 167         if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value());
 168         return ReplaceInt32(m.left().Value() / m.right().Value());
 169       }
 170       if (m.right().Is(-1)) {  // x / -1 => 0 - x
 171         graph_->ChangeOperator(node, machine_.Int32Sub());
 172         node->ReplaceInput(0, Int32Constant(0));
 173         node->ReplaceInput(1, m.left().node());
 174         return Changed(node);
 175       }
 176       break;
 177     }
 178     case IrOpcode::kInt32UDiv: {
 179       Uint32BinopMatcher m(node);
 180       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1 => x
 181       // TODO(turbofan): if (m.left().Is(0))
 182       // TODO(turbofan): if (m.right().Is(0))
 183       // TODO(turbofan): if (m.LeftEqualsRight())
 184       if (m.IsFoldable() && !m.right().Is(0)) {  // K / K => K
 185         return ReplaceInt32(m.left().Value() / m.right().Value());
 186       }
 187       if (m.right().IsPowerOf2()) {  // x / 2^n => x >> n
 188         graph_->ChangeOperator(node, machine_.Word32Shr());
 189         node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
 190         return Changed(node);
 191       }
 192       break;
 193     }
 194     case IrOpcode::kInt32Mod: {
 195       Int32BinopMatcher m(node);
 196       if (m.right().Is(1)) return ReplaceInt32(0);   // x % 1  => 0
 197       if (m.right().Is(-1)) return ReplaceInt32(0);  // x % -1 => 0
 198       // TODO(turbofan): if (m.left().Is(0))
 199       // TODO(turbofan): if (m.right().IsPowerOf2())
 200       // TODO(turbofan): if (m.right().Is(0))
 201       // TODO(turbofan): if (m.LeftEqualsRight())
 202       if (m.IsFoldable() && !m.right().Is(0)) {  // K % K => K
 203         return ReplaceInt32(m.left().Value() % m.right().Value());
 204       }
 205       break;
 206     }
 207     case IrOpcode::kInt32UMod: {
 208       Uint32BinopMatcher m(node);
 209       if (m.right().Is(1)) return ReplaceInt32(0);  // x % 1 => 0
 210       // TODO(turbofan): if (m.left().Is(0))
 211       // TODO(turbofan): if (m.right().Is(0))
 212       // TODO(turbofan): if (m.LeftEqualsRight())
 213       if (m.IsFoldable() && !m.right().Is(0)) {  // K % K => K
 214         return ReplaceInt32(m.left().Value() % m.right().Value());
 215       }
 216       if (m.right().IsPowerOf2()) {  // x % 2^n => x & 2^n-1
 217         graph_->ChangeOperator(node, machine_.Word32And());
 218         node->ReplaceInput(1, Int32Constant(m.right().Value() - 1));
 219         return Changed(node);
 220       }
 221       break;
 222     }
 223     case IrOpcode::kInt32LessThan: {
 224       Int32BinopMatcher m(node);
 225       if (m.IsFoldable()) {  // K < K => K
 226         return ReplaceBool(m.left().Value() < m.right().Value());
 227       }
 228       if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y < 0 => x < y
 229         Int32BinopMatcher msub(m.left().node());
 230         node->ReplaceInput(0, msub.left().node());
 231         node->ReplaceInput(1, msub.right().node());
 232         return Changed(node);
 233       }
 234       if (m.left().Is(0) && m.right().IsInt32Sub()) {  // 0 < x - y => y < x
 235         Int32BinopMatcher msub(m.right().node());
 236         node->ReplaceInput(0, msub.right().node());
 237         node->ReplaceInput(1, msub.left().node());
 238         return Changed(node);
 239       }
 240       if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
 241       break;
 242     }
 243     case IrOpcode::kInt32LessThanOrEqual: {
 244       Int32BinopMatcher m(node);
 245       if (m.IsFoldable()) {  // K <= K => K
 246         return ReplaceBool(m.left().Value() <= m.right().Value());
 247       }
 248       if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y <= 0 => x <= y
 249         Int32BinopMatcher msub(m.left().node());
 250         node->ReplaceInput(0, msub.left().node());
 251         node->ReplaceInput(1, msub.right().node());
 252         return Changed(node);
 253       }
 254       if (m.left().Is(0) && m.right().IsInt32Sub()) {  // 0 <= x - y => y <= x
 255         Int32BinopMatcher msub(m.right().node());
 256         node->ReplaceInput(0, msub.right().node());
 257         node->ReplaceInput(1, msub.left().node());
 258         return Changed(node);
 259       }
 260       if (m.LeftEqualsRight()) return ReplaceBool(true);  // x <= x => true
 261       break;
 262     }
 263     case IrOpcode::kUint32LessThan: {
 264       Uint32BinopMatcher m(node);
 265       if (m.left().Is(kMaxUInt32)) return ReplaceBool(false);  // M < x => false
 266       if (m.right().Is(0)) return ReplaceBool(false);          // x < 0 => false
 267       if (m.IsFoldable()) {                                    // K < K => K
 268         return ReplaceBool(m.left().Value() < m.right().Value());
 269       }
 270       if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
 271       break;
 272     }
 273     case IrOpcode::kUint32LessThanOrEqual: {
 274       Uint32BinopMatcher m(node);
 275       if (m.left().Is(0)) return ReplaceBool(true);            // 0 <= x => true
 276       if (m.right().Is(kMaxUInt32)) return ReplaceBool(true);  // x <= M => true
 277       if (m.IsFoldable()) {                                    // K <= K => K
 278         return ReplaceBool(m.left().Value() <= m.right().Value());
 279       }
 280       if (m.LeftEqualsRight()) return ReplaceBool(true);  // x <= x => true
 281       break;
 282     }
 283     case IrOpcode::kFloat64Add: {
 284       Float64BinopMatcher m(node);
 285       if (m.IsFoldable()) {  // K + K => K
 286         return ReplaceFloat64(m.left().Value() + m.right().Value());
 287       }
 288       break;
 289     }
 290     case IrOpcode::kFloat64Sub: {
 291       Float64BinopMatcher m(node);
 292       if (m.IsFoldable()) {  // K - K => K
 293         return ReplaceFloat64(m.left().Value() - m.right().Value());
 294       }
 295       break;
 296     }
 297     case IrOpcode::kFloat64Mul: {
 298       Float64BinopMatcher m(node);
 299       if (m.right().Is(1)) return Replace(m.left().node());  // x * 1.0 => x
 300       if (m.right().IsNaN()) {                               // x * NaN => NaN
 301         return Replace(m.right().node());
 302       }
 303       if (m.IsFoldable()) {  // K * K => K
 304         return ReplaceFloat64(m.left().Value() * m.right().Value());
 305       }
 306       break;
 307     }
 308     case IrOpcode::kFloat64Div: {
 309       Float64BinopMatcher m(node);
 310       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1.0 => x
 311       if (m.right().IsNaN()) {                               // x / NaN => NaN
 312         return Replace(m.right().node());
 313       }
 314       if (m.left().IsNaN()) {  // NaN / x => NaN
 315         return Replace(m.left().node());
 316       }
 317       if (m.IsFoldable()) {  // K / K => K
 318         return ReplaceFloat64(m.left().Value() / m.right().Value());
 319       }
 320       break;
 321     }
 322     case IrOpcode::kFloat64Mod: {
 323       Float64BinopMatcher m(node);
 324       if (m.right().IsNaN()) {  // x % NaN => NaN
 325         return Replace(m.right().node());
 326       }
 327       if (m.left().IsNaN()) {  // NaN % x => NaN
 328         return Replace(m.left().node());
 329       }
 330       if (m.IsFoldable()) {  // K % K => K
 331         return ReplaceFloat64(modulo(m.left().Value(), m.right().Value()));
 332       }
 333       break;
 334     }
 335     // TODO(turbofan): strength-reduce and fold floating point operations.
 336     default:
 337       break;
 338   }
 339   return NoChange();
 340 }
 341 }
 342 }
 343 }  // namespace v8::internal::compiler