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