blob: c09274ca2f4040ddf2b2ad186beb28e86f617ee7 [file] [log] [blame]
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/compiler/backend/jump-threading.h"
#include "src/compiler/backend/code-generator-impl.h"
namespace v8 {
namespace internal {
namespace compiler {
#define TRACE(...) \
do { \
if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
} while (false)
namespace {
struct JumpThreadingState {
bool forwarded;
ZoneVector<RpoNumber>& result;
ZoneStack<RpoNumber>& stack;
void Clear(size_t count) { result.assign(count, unvisited()); }
void PushIfUnvisited(RpoNumber num) {
if (result[num.ToInt()] == unvisited()) {
stack.push(num);
result[num.ToInt()] = onstack();
}
}
void Forward(RpoNumber to) {
RpoNumber from = stack.top();
RpoNumber to_to = result[to.ToInt()];
bool pop = true;
if (to == from) {
TRACE(" xx %d\n", from.ToInt());
result[from.ToInt()] = from;
} else if (to_to == unvisited()) {
TRACE(" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
stack.push(to);
result[to.ToInt()] = onstack();
pop = false; // recurse.
} else if (to_to == onstack()) {
TRACE(" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
result[from.ToInt()] = to; // break the cycle.
forwarded = true;
} else {
TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
result[from.ToInt()] = to_to; // forward the block.
forwarded = true;
}
if (pop) stack.pop();
}
RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
RpoNumber onstack() { return RpoNumber::FromInt(-2); }
};
bool IsBlockWithBranchPoisoning(InstructionSequence* code,
InstructionBlock* block) {
if (block->PredecessorCount() != 1) return false;
RpoNumber pred_rpo = (block->predecessors())[0];
const InstructionBlock* pred = code->InstructionBlockAt(pred_rpo);
if (pred->code_start() == pred->code_end()) return false;
Instruction* instr = code->InstructionAt(pred->code_end() - 1);
FlagsMode mode = FlagsModeField::decode(instr->opcode());
return mode == kFlags_branch_and_poison;
}
} // namespace
bool JumpThreading::ComputeForwarding(Zone* local_zone,
ZoneVector<RpoNumber>* result,
InstructionSequence* code,
bool frame_at_start) {
ZoneStack<RpoNumber> stack(local_zone);
JumpThreadingState state = {false, *result, stack};
state.Clear(code->InstructionBlockCount());
RpoNumber empty_deconstruct_frame_return_block = RpoNumber::Invalid();
int32_t empty_deconstruct_frame_return_size;
RpoNumber empty_no_deconstruct_frame_return_block = RpoNumber::Invalid();
int32_t empty_no_deconstruct_frame_return_size;
// Iterate over the blocks forward, pushing the blocks onto the stack.
for (auto const block : code->instruction_blocks()) {
RpoNumber current = block->rpo_number();
state.PushIfUnvisited(current);
// Process the stack, which implements DFS through empty blocks.
while (!state.stack.empty()) {
InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
// Process the instructions in a block up to a non-empty instruction.
TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
block->rpo_number().ToInt());
RpoNumber fw = block->rpo_number();
if (!IsBlockWithBranchPoisoning(code, block)) {
bool fallthru = true;
for (int i = block->code_start(); i < block->code_end(); ++i) {
Instruction* instr = code->InstructionAt(i);
if (!instr->AreMovesRedundant()) {
// can't skip instructions with non redundant moves.
TRACE(" parallel move\n");
fallthru = false;
} else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
// can't skip instructions with flags continuations.
TRACE(" flags\n");
fallthru = false;
} else if (instr->IsNop()) {
// skip nops.
TRACE(" nop\n");
continue;
} else if (instr->arch_opcode() == kArchJmp) {
// try to forward the jump instruction.
TRACE(" jmp\n");
// if this block deconstructs the frame, we can't forward it.
// TODO(mtrofin): we can still forward if we end up building
// the frame at start. So we should move the decision of whether
// to build a frame or not in the register allocator, and trickle it
// here and to the code generator.
if (frame_at_start || !(block->must_deconstruct_frame() ||
block->must_construct_frame())) {
fw = code->InputRpo(instr, 0);
}
fallthru = false;
} else if (instr->IsRet()) {
TRACE(" ret\n");
if (fallthru) {
CHECK_IMPLIES(block->must_construct_frame(),
block->must_deconstruct_frame());
// Only handle returns with immediate/constant operands, since
// they must always be the same for all returns in a function.
// Dynamic return values might use different registers at
// different return sites and therefore cannot be shared.
if (instr->InputAt(0)->IsImmediate()) {
int32_t return_size =
ImmediateOperand::cast(instr->InputAt(0))->inline_value();
// Instructions can be shared only for blocks that share
// the same |must_deconstruct_frame| attribute.
if (block->must_deconstruct_frame()) {
if (empty_deconstruct_frame_return_block ==
RpoNumber::Invalid()) {
empty_deconstruct_frame_return_block = block->rpo_number();
empty_deconstruct_frame_return_size = return_size;
} else if (empty_deconstruct_frame_return_size ==
return_size) {
fw = empty_deconstruct_frame_return_block;
block->clear_must_deconstruct_frame();
}
} else {
if (empty_no_deconstruct_frame_return_block ==
RpoNumber::Invalid()) {
empty_no_deconstruct_frame_return_block =
block->rpo_number();
empty_no_deconstruct_frame_return_size = return_size;
} else if (empty_no_deconstruct_frame_return_size ==
return_size) {
fw = empty_no_deconstruct_frame_return_block;
}
}
}
}
fallthru = false;
} else {
// can't skip other instructions.
TRACE(" other\n");
fallthru = false;
}
break;
}
if (fallthru) {
int next = 1 + block->rpo_number().ToInt();
if (next < code->InstructionBlockCount())
fw = RpoNumber::FromInt(next);
}
}
state.Forward(fw);
}
}
#ifdef DEBUG
for (RpoNumber num : *result) {
DCHECK(num.IsValid());
}
#endif
if (FLAG_trace_turbo_jt) {
for (int i = 0; i < static_cast<int>(result->size()); i++) {
TRACE("B%d ", i);
int to = (*result)[i].ToInt();
if (i != to) {
TRACE("-> B%d\n", to);
} else {
TRACE("\n");
}
}
}
return state.forwarded;
}
void JumpThreading::ApplyForwarding(Zone* local_zone,
ZoneVector<RpoNumber> const& result,
InstructionSequence* code) {
if (!FLAG_turbo_jt) return;
ZoneVector<bool> skip(static_cast<int>(result.size()), false, local_zone);
// Skip empty blocks when the previous block doesn't fall through.
bool prev_fallthru = true;
for (auto const block : code->instruction_blocks()) {
RpoNumber block_rpo = block->rpo_number();
int block_num = block_rpo.ToInt();
RpoNumber result_rpo = result[block_num];
skip[block_num] = !prev_fallthru && result_rpo != block_rpo;
if (result_rpo != block_rpo) {
// We need the handler information to be propagated, so that branch
// targets are annotated as necessary for control flow integrity
// checks (when enabled).
if (code->InstructionBlockAt(block_rpo)->IsHandler()) {
code->InstructionBlockAt(result_rpo)->MarkHandler();
}
}
bool fallthru = true;
for (int i = block->code_start(); i < block->code_end(); ++i) {
Instruction* instr = code->InstructionAt(i);
FlagsMode mode = FlagsModeField::decode(instr->opcode());
if (mode == kFlags_branch || mode == kFlags_branch_and_poison) {
fallthru = false; // branches don't fall through to the next block.
} else if (instr->arch_opcode() == kArchJmp ||
instr->arch_opcode() == kArchRet) {
if (skip[block_num]) {
// Overwrite a redundant jump with a nop.
TRACE("jt-fw nop @%d\n", i);
instr->OverwriteWithNop();
// If this block was marked as a handler, it can be unmarked now.
code->InstructionBlockAt(block_rpo)->UnmarkHandler();
}
fallthru = false; // jumps don't fall through to the next block.
}
}
prev_fallthru = fallthru;
}
// Patch RPO immediates.
InstructionSequence::Immediates& immediates = code->immediates();
for (size_t i = 0; i < immediates.size(); i++) {
Constant constant = immediates[i];
if (constant.type() == Constant::kRpoNumber) {
RpoNumber rpo = constant.ToRpoNumber();
RpoNumber fw = result[rpo.ToInt()];
if (!(fw == rpo)) immediates[i] = Constant(fw);
}
}
// Renumber the blocks so that IsNextInAssemblyOrder() will return true,
// even if there are skipped blocks in-between.
int ao = 0;
for (auto const block : code->ao_blocks()) {
block->set_ao_number(RpoNumber::FromInt(ao));
if (!skip[block->rpo_number().ToInt()]) ao++;
}
}
#undef TRACE
} // namespace compiler
} // namespace internal
} // namespace v8