deps/v8/src/compiler/jump-threading.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/jump-threading.h"
   6 #include "src/compiler/code-generator-impl.h"
   7
   8 namespace v8 {
   9 namespace internal {
  10 namespace compiler {
  11
  12 typedef BasicBlock::RpoNumber RpoNumber;
  13
  14 #define TRACE(x) \
  15   if (FLAG_trace_turbo_jt) PrintF x
  16
  17 struct JumpThreadingState {
  18   bool forwarded;
  19   ZoneVector<RpoNumber>& result;
  20   ZoneStack<RpoNumber>& stack;
  21
  22   void Clear(size_t count) { result.assign(count, unvisited()); }
  23   void PushIfUnvisited(RpoNumber num) {
  24     if (result[num.ToInt()] == unvisited()) {
  25       stack.push(num);
  26       result[num.ToInt()] = onstack();
  27     }
  28   }
  29   void Forward(RpoNumber to) {
  30     RpoNumber from = stack.top();
  31     RpoNumber to_to = result[to.ToInt()];
  32     bool pop = true;
  33     if (to == from) {
  34       TRACE(("  xx %d\n", from.ToInt()));
  35       result[from.ToInt()] = from;
  36     } else if (to_to == unvisited()) {
  37       TRACE(("  fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt()));
  38       stack.push(to);
  39       result[to.ToInt()] = onstack();
  40       pop = false;  // recurse.
  41     } else if (to_to == onstack()) {
  42       TRACE(("  fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt()));
  43       result[from.ToInt()] = to;  // break the cycle.
  44       forwarded = true;
  45     } else {
  46       TRACE(("  fw %d -> %d (forward)\n", from.ToInt(), to.ToInt()));
  47       result[from.ToInt()] = to_to;  // forward the block.
  48       forwarded = true;
  49     }
  50     if (pop) stack.pop();
  51   }
  52   RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
  53   RpoNumber onstack() { return RpoNumber::FromInt(-2); }
  54 };
  55
  56
  57 bool JumpThreading::ComputeForwarding(Zone* local_zone,
  58                                       ZoneVector<RpoNumber>& result,
  59                                       InstructionSequence* code) {
  60   ZoneStack<RpoNumber> stack(local_zone);
  61   JumpThreadingState state = {false, result, stack};
  62   state.Clear(code->InstructionBlockCount());
  63
  64   // Iterate over the blocks forward, pushing the blocks onto the stack.
  65   for (auto const block : code->instruction_blocks()) {
  66     RpoNumber current = block->rpo_number();
  67     state.PushIfUnvisited(current);
  68
  69     // Process the stack, which implements DFS through empty blocks.
  70     while (!state.stack.empty()) {
  71       InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
  72       // Process the instructions in a block up to a non-empty instruction.
  73       TRACE(("jt [%d] B%d RPO%d\n", static_cast<int>(stack.size()),
  74              block->id().ToInt(), block->rpo_number().ToInt()));
  75       bool fallthru = true;
  76       RpoNumber fw = block->rpo_number();
  77       for (int i = block->code_start(); i < block->code_end(); ++i) {
  78         Instruction* instr = code->InstructionAt(i);
  79         if (instr->IsGapMoves() && GapInstruction::cast(instr)->IsRedundant()) {
  80           // skip redundant gap moves.
  81           TRACE(("  nop gap\n"));
  82           continue;
  83         } else if (instr->IsSourcePosition()) {
  84           // skip source positions.
  85           TRACE(("  src pos\n"));
  86           continue;
  87         } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
  88           // can't skip instructions with flags continuations.
  89           TRACE(("  flags\n"));
  90           fallthru = false;
  91         } else if (instr->IsNop()) {
  92           // skip nops.
  93           TRACE(("  nop\n"));
  94           continue;
  95         } else if (instr->arch_opcode() == kArchJmp) {
  96           // try to forward the jump instruction.
  97           TRACE(("  jmp\n"));
  98           fw = code->InputRpo(instr, 0);
  99           fallthru = false;
 100         } else {
 101           // can't skip other instructions.
 102           TRACE(("  other\n"));
 103           fallthru = false;
 104         }
 105         break;
 106       }
 107       if (fallthru) {
 108         int next = 1 + block->rpo_number().ToInt();
 109         if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
 110       }
 111       state.Forward(fw);
 112     }
 113   }
 114
 115 #ifdef DEBUG
 116   for (RpoNumber num : result) {
 117     CHECK(num.IsValid());
 118   }
 119 #endif
 120
 121   if (FLAG_trace_turbo_jt) {
 122     for (int i = 0; i < static_cast<int>(result.size()); i++) {
 123       TRACE(("RPO%d B%d ", i,
 124              code->InstructionBlockAt(RpoNumber::FromInt(i))->id().ToInt()));
 125       int to = result[i].ToInt();
 126       if (i != to) {
 127         TRACE(("-> B%d\n",
 128                code->InstructionBlockAt(RpoNumber::FromInt(to))->id().ToInt()));
 129       } else {
 130         TRACE(("\n"));
 131       }
 132     }
 133   }
 134
 135   return state.forwarded;
 136 }
 137
 138
 139 void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
 140                                     InstructionSequence* code) {
 141   if (!FLAG_turbo_jt) return;
 142
 143   Zone local_zone;
 144   ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);
 145
 146   // Skip empty blocks when the previous block doesn't fall through.
 147   bool prev_fallthru = true;
 148   for (auto const block : code->instruction_blocks()) {
 149     int block_num = block->rpo_number().ToInt();
 150     skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
 151
 152     bool fallthru = true;
 153     for (int i = block->code_start(); i < block->code_end(); ++i) {
 154       Instruction* instr = code->InstructionAt(i);
 155       if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
 156         fallthru = false;  // branches don't fall through to the next block.
 157       } else if (instr->arch_opcode() == kArchJmp) {
 158         if (skip[block_num]) {
 159           // Overwrite a redundant jump with a nop.
 160           TRACE(("jt-fw nop @%d\n", i));
 161           instr->OverwriteWithNop();
 162         }
 163         fallthru = false;  // jumps don't fall through to the next block.
 164       }
 165     }
 166     prev_fallthru = fallthru;
 167   }
 168
 169   // Patch RPO immediates.
 170   InstructionSequence::Immediates& immediates = code->immediates();
 171   for (size_t i = 0; i < immediates.size(); i++) {
 172     Constant constant = immediates[i];
 173     if (constant.type() == Constant::kRpoNumber) {
 174       RpoNumber rpo = constant.ToRpoNumber();
 175       RpoNumber fw = result[rpo.ToInt()];
 176       if (!(fw == rpo)) immediates[i] = Constant(fw);
 177     }
 178   }
 179
 180   // Recompute assembly order numbers.
 181   int ao = 0;
 182   for (auto const block : code->instruction_blocks()) {
 183     if (!block->IsDeferred()) {
 184       block->set_ao_number(RpoNumber::FromInt(ao));
 185       if (!skip[block->rpo_number().ToInt()]) ao++;
 186     }
 187   }
 188   for (auto const block : code->instruction_blocks()) {
 189     if (block->IsDeferred()) {
 190       block->set_ao_number(RpoNumber::FromInt(ao));
 191       if (!skip[block->rpo_number().ToInt()]) ao++;
 192     }
 193   }
 194 }
 195
 196 }  // namespace compiler
 197 }  // namespace internal
 198 }  // namespace v8