Home | History | Annotate | Download | only in compiler 
      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 #define TRACE(...)                                \
     13   do {                                            \
     14     if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
     15   } while (false)
     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\n", static_cast<int>(stack.size()),
     74             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->AreMovesRedundant()) {
     80           // can't skip instructions with non redundant moves.
     81           TRACE("  parallel move\n");
     82           fallthru = false;
     83         } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
     84           // can't skip instructions with flags continuations.
     85           TRACE("  flags\n");
     86           fallthru = false;
     87         } else if (instr->IsNop()) {
     88           // skip nops.
     89           TRACE("  nop\n");
     90           continue;
     91         } else if (instr->arch_opcode() == kArchJmp) {
     92           // try to forward the jump instruction.
     93           TRACE("  jmp\n");
     94           fw = code->InputRpo(instr, 0);
     95           fallthru = false;
     96         } else {
     97           // can't skip other instructions.
     98           TRACE("  other\n");
     99           fallthru = false;
    100         }
    101         break;
    102       }
    103       if (fallthru) {
    104         int next = 1 + block->rpo_number().ToInt();
    105         if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
    106       }
    107       state.Forward(fw);
    108     }
    109   }
    110 
    111 #ifdef DEBUG
    112   for (RpoNumber num : result) {
    113     CHECK(num.IsValid());
    114   }
    115 #endif
    116 
    117   if (FLAG_trace_turbo_jt) {
    118     for (int i = 0; i < static_cast<int>(result.size()); i++) {
    119       TRACE("B%d ", i);
    120       int to = result[i].ToInt();
    121       if (i != to) {
    122         TRACE("-> B%d\n", to);
    123       } else {
    124         TRACE("\n");
    125       }
    126     }
    127   }
    128 
    129   return state.forwarded;
    130 }
    131 
    132 
    133 void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
    134                                     InstructionSequence* code) {
    135   if (!FLAG_turbo_jt) return;
    136 
    137   Zone local_zone;
    138   ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);
    139 
    140   // Skip empty blocks when the previous block doesn't fall through.
    141   bool prev_fallthru = true;
    142   for (auto const block : code->instruction_blocks()) {
    143     int block_num = block->rpo_number().ToInt();
    144     skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
    145 
    146     bool fallthru = true;
    147     for (int i = block->code_start(); i < block->code_end(); ++i) {
    148       Instruction* instr = code->InstructionAt(i);
    149       if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
    150         fallthru = false;  // branches don't fall through to the next block.
    151       } else if (instr->arch_opcode() == kArchJmp) {
    152         if (skip[block_num]) {
    153           // Overwrite a redundant jump with a nop.
    154           TRACE("jt-fw nop @%d\n", i);
    155           instr->OverwriteWithNop();
    156         }
    157         fallthru = false;  // jumps don't fall through to the next block.
    158       }
    159     }
    160     prev_fallthru = fallthru;
    161   }
    162 
    163   // Patch RPO immediates.
    164   InstructionSequence::Immediates& immediates = code->immediates();
    165   for (size_t i = 0; i < immediates.size(); i++) {
    166     Constant constant = immediates[i];
    167     if (constant.type() == Constant::kRpoNumber) {
    168       RpoNumber rpo = constant.ToRpoNumber();
    169       RpoNumber fw = result[rpo.ToInt()];
    170       if (!(fw == rpo)) immediates[i] = Constant(fw);
    171     }
    172   }
    173 
    174   // Recompute assembly order numbers.
    175   int ao = 0;
    176   for (auto const block : code->instruction_blocks()) {
    177     if (!block->IsDeferred()) {
    178       block->set_ao_number(RpoNumber::FromInt(ao));
    179       if (!skip[block->rpo_number().ToInt()]) ao++;
    180     }
    181   }
    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 }
    189 
    190 }  // namespace compiler
    191 }  // namespace internal
    192 }  // namespace v8
    193