LCOV - code coverage report
Current view: top level - src/compiler/backend - jump-threading.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 84 90 93.3 %
Date: 2019-04-17 Functions: 6 6 100.0 %

          Line data    Source code
       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/backend/jump-threading.h"
       6             : #include "src/compiler/backend/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             : namespace {
      18             : 
      19             : struct JumpThreadingState {
      20             :   bool forwarded;
      21             :   ZoneVector<RpoNumber>& result;
      22             :   ZoneStack<RpoNumber>& stack;
      23             : 
      24     5287545 :   void Clear(size_t count) { result.assign(count, unvisited()); }
      25    20482643 :   void PushIfUnvisited(RpoNumber num) {
      26    40965286 :     if (result[num.ToInt()] == unvisited()) {
      27    17994595 :       stack.push(num);
      28    35991162 :       result[num.ToInt()] = onstack();
      29             :     }
      30    20483629 :   }
      31    22970649 :   void Forward(RpoNumber to) {
      32    45941298 :     RpoNumber from = stack.top();
      33    45941298 :     RpoNumber to_to = result[to.ToInt()];
      34             :     bool pop = true;
      35    22970649 :     if (to == from) {
      36    16253201 :       TRACE("  xx %d\n", from.ToInt());
      37    32508134 :       result[from.ToInt()] = from;
      38     6717448 :     } else if (to_to == unvisited()) {
      39     2488003 :       TRACE("  fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
      40     2488003 :       stack.push(to);
      41     4976042 :       result[to.ToInt()] = onstack();
      42             :       pop = false;  // recurse.
      43     4229445 :     } else if (to_to == onstack()) {
      44          45 :       TRACE("  fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
      45          90 :       result[from.ToInt()] = to;  // break the cycle.
      46          45 :       forwarded = true;
      47             :     } else {
      48     4229400 :       TRACE("  fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
      49     8458818 :       result[from.ToInt()] = to_to;  // forward the block.
      50     4229409 :       forwarded = true;
      51             :     }
      52    22971542 :     if (pop) stack.pop();
      53    22971790 :   }
      54             :   RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
      55             :   RpoNumber onstack() { return RpoNumber::FromInt(-2); }
      56             : };
      57             : 
      58    22970934 : bool IsBlockWithBranchPoisoning(InstructionSequence* code,
      59             :                                 InstructionBlock* block) {
      60    22970934 :   if (block->PredecessorCount() != 1) return false;
      61    16262187 :   RpoNumber pred_rpo = (block->predecessors())[0];
      62    16262187 :   const InstructionBlock* pred = code->InstructionBlockAt(pred_rpo);
      63    16262170 :   if (pred->code_start() == pred->code_end()) return false;
      64    16262243 :   Instruction* instr = code->InstructionAt(pred->code_end() - 1);
      65    16261763 :   FlagsMode mode = FlagsModeField::decode(instr->opcode());
      66    16261763 :   return mode == kFlags_branch_and_poison;
      67             : }
      68             : 
      69             : }  // namespace
      70             : 
      71     2640838 : bool JumpThreading::ComputeForwarding(Zone* local_zone,
      72             :                                       ZoneVector<RpoNumber>& result,
      73             :                                       InstructionSequence* code,
      74             :                                       bool frame_at_start) {
      75     2640838 :   ZoneStack<RpoNumber> stack(local_zone);
      76     2644005 :   JumpThreadingState state = {false, result, stack};
      77     2644005 :   state.Clear(code->InstructionBlockCount());
      78             : 
      79             :   // Iterate over the blocks forward, pushing the blocks onto the stack.
      80    23127096 :   for (auto const block : code->instruction_blocks()) {
      81    20482919 :     RpoNumber current = block->rpo_number();
      82    20482919 :     state.PushIfUnvisited(current);
      83             : 
      84             :     // Process the stack, which implements DFS through empty blocks.
      85    66426435 :     while (!state.stack.empty()) {
      86    22971550 :       InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
      87             :       // Process the instructions in a block up to a non-empty instruction.
      88    22971860 :       TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
      89             :             block->rpo_number().ToInt());
      90    22971860 :       RpoNumber fw = block->rpo_number();
      91    22971860 :       if (!IsBlockWithBranchPoisoning(code, block)) {
      92             :         bool fallthru = true;
      93    51207977 :         for (int i = block->code_start(); i < block->code_end(); ++i) {
      94             :           Instruction* instr = code->InstructionAt(i);
      95    34447372 :           if (!instr->AreMovesRedundant()) {
      96             :             // can't skip instructions with non redundant moves.
      97     7155973 :             TRACE("  parallel move\n");
      98             :             fallthru = false;
      99    54582966 :           } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
     100             :             // can't skip instructions with flags continuations.
     101     1706425 :             TRACE("  flags\n");
     102             :             fallthru = false;
     103    25585058 :           } else if (instr->IsNop()) {
     104             :             // skip nops.
     105    14118705 :             TRACE("  nop\n");
     106             :             continue;
     107    11466353 :           } else if (instr->arch_opcode() == kArchJmp) {
     108             :             // try to forward the jump instruction.
     109     6731386 :             TRACE("  jmp\n");
     110             :             // if this block deconstructs the frame, we can't forward it.
     111             :             // TODO(mtrofin): we can still forward if we end up building
     112             :             // the frame at start. So we should move the decision of whether
     113             :             // to build a frame or not in the register allocator, and trickle it
     114             :             // here and to the code generator.
     115    13462768 :             if (frame_at_start || !(block->must_deconstruct_frame() ||
     116      471752 :                                     block->must_construct_frame())) {
     117     6717272 :               fw = code->InputRpo(instr, 0);
     118             :             }
     119             :             fallthru = false;
     120             :           } else {
     121             :             // can't skip other instructions.
     122     4734967 :             TRACE("  other\n");
     123             :             fallthru = false;
     124             :           }
     125             :           break;
     126             :         }
     127    22970811 :         if (fallthru) {
     128     2643321 :           int next = 1 + block->rpo_number().ToInt();
     129     2643321 :           if (next < code->InstructionBlockCount())
     130         272 :             fw = RpoNumber::FromInt(next);
     131             :         }
     132             :       }
     133    22970547 :       state.Forward(fw);
     134             :     }
     135             :   }
     136             : 
     137             : #ifdef DEBUG
     138             :   for (RpoNumber num : result) {
     139             :     DCHECK(num.IsValid());
     140             :   }
     141             : #endif
     142             : 
     143     2644177 :   if (FLAG_trace_turbo_jt) {
     144           0 :     for (int i = 0; i < static_cast<int>(result.size()); i++) {
     145           0 :       TRACE("B%d ", i);
     146           0 :       int to = result[i].ToInt();
     147           0 :       if (i != to) {
     148           0 :         TRACE("-> B%d\n", to);
     149             :       } else {
     150           0 :         TRACE("\n");
     151             :       }
     152             :     }
     153             :   }
     154             : 
     155     5288328 :   return state.forwarded;
     156             : }
     157             : 
     158      731224 : void JumpThreading::ApplyForwarding(Zone* local_zone,
     159             :                                     ZoneVector<RpoNumber>& result,
     160             :                                     InstructionSequence* code) {
     161      731224 :   if (!FLAG_turbo_jt) return;
     162             : 
     163      731224 :   ZoneVector<bool> skip(static_cast<int>(result.size()), false, local_zone);
     164             : 
     165             :   // Skip empty blocks when the previous block doesn't fall through.
     166             :   bool prev_fallthru = true;
     167    17262330 :   for (auto const block : code->instruction_blocks()) {
     168             :     int block_num = block->rpo_number().ToInt();
     169    30829002 :     skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
     170             : 
     171             :     bool fallthru = true;
     172   118908648 :     for (int i = block->code_start(); i < block->code_end(); ++i) {
     173             :       Instruction* instr = code->InstructionAt(i);
     174    51188880 :       FlagsMode mode = FlagsModeField::decode(instr->opcode());
     175    51188880 :       if (mode == kFlags_branch || mode == kFlags_branch_and_poison) {
     176             :         fallthru = false;  // branches don't fall through to the next block.
     177    45869582 :       } else if (instr->arch_opcode() == kArchJmp) {
     178     8979515 :         if (skip[block_num]) {
     179             :           // Overwrite a redundant jump with a nop.
     180     4050975 :           TRACE("jt-fw nop @%d\n", i);
     181             :           instr->OverwriteWithNop();
     182             :         }
     183             :         fallthru = false;  // jumps don't fall through to the next block.
     184             :       }
     185             :     }
     186             :     prev_fallthru = fallthru;
     187             :   }
     188             : 
     189             :   // Patch RPO immediates.
     190             :   InstructionSequence::Immediates& immediates = code->immediates();
     191    85876888 :   for (size_t i = 0; i < immediates.size(); i++) {
     192    42572724 :     Constant constant = immediates[i];
     193    42572724 :     if (constant.type() == Constant::kRpoNumber) {
     194             :       RpoNumber rpo = constant.ToRpoNumber();
     195    41036644 :       RpoNumber fw = result[rpo.ToInt()];
     196    25158351 :       if (!(fw == rpo)) immediates[i] = Constant(fw);
     197             :     }
     198             :   }
     199             : 
     200             :   // Renumber the blocks so that IsNextInAssemblyOrder() will return true,
     201             :   // even if there are skipped blocks in-between.
     202             :   int ao = 0;
     203    17260775 :   for (auto const block : code->ao_blocks()) {
     204             :     block->set_ao_number(RpoNumber::FromInt(ao));
     205    33058670 :     if (!skip[block->rpo_number().ToInt()]) ao++;
     206             :   }
     207             : }
     208             : 
     209             : #undef TRACE
     210             : 
     211             : }  // namespace compiler
     212             : }  // namespace internal
     213      121996 : }  // namespace v8

Generated by: LCOV version 1.10