From patchwork Thu Feb 14 22:59:52 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Max Filippov X-Patchwork-Id: 1042507 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=nongnu.org (client-ip=209.51.188.17; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="eKOz0jYK"; dkim-atps=neutral Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 440snk2VRGz9s7h for ; Fri, 15 Feb 2019 10:20:42 +1100 (AEDT) Received: from localhost ([127.0.0.1]:56558 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1guQJ6-0002DK-AU for incoming@patchwork.ozlabs.org; Thu, 14 Feb 2019 18:20:40 -0500 Received: from eggs.gnu.org ([209.51.188.92]:49744) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1guQ8u-0003NE-0M for qemu-devel@nongnu.org; Thu, 14 Feb 2019 18:10:09 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1guQ05-00055C-LP for qemu-devel@nongnu.org; Thu, 14 Feb 2019 18:01:03 -0500 Received: from mail-lj1-x244.google.com ([2a00:1450:4864:20::244]:46938) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1guQ05-0004yg-6U for qemu-devel@nongnu.org; Thu, 14 Feb 2019 18:01:01 -0500 Received: by mail-lj1-x244.google.com with SMTP id v16so6706090ljg.13 for ; Thu, 14 Feb 2019 15:00:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=MLptY2Hxv+12eLdOb0ByI46lrMUuV2EpUmBfLSNydiQ=; b=eKOz0jYKwJ8Pp9HwazATwRkH/KF1TW6Ci9Qq5uaeZzPiMNTwUp95mt4E+ih4psq+eD 51Us6Dpf58eQx0eeq4RJ/tshS6ZDFmA0aplNZJYBoDmfp20BRWaivAHbCu6pqxUG0x+r dyXAl6wJup8HWxguClyGeouOyZ4DTfOnpij6e6gJ1rYLh4v8gpLZKanscibkucG9ktBM AimP99Ego+wYcx/0w3DXn3BCj9qL78+hB96moN8H684myMkbuA4d0mcefTP//aYWEK6u AChujkSgEo0m3pCLAE+XPz6RLxbLhy32jT6Qb9ZThE7pi7C772oJPCEN7I/0LmbXFOlg creA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=MLptY2Hxv+12eLdOb0ByI46lrMUuV2EpUmBfLSNydiQ=; b=K3vef2EOYup8N61dTOlLmtImFDFN9xJeokuqakBTcIFLZKT3wXHm+2Ijg2pe09jib6 BHT721x26c729froqK7Fic8yds4krUPOwKXFE6hMEE2P9vwjkigs0MxicnF2p749kk0p 1baL8x/QUO/FINZXWNiq/qadVd3RgG0AzcR59kiyMZ7uJEDilvT14ie16mxmoZoUzKgO 0Jp/dDlIztQx0T+Gfw6g19wsmTl3vJO5N1M986+vaKOsDm69fmwogDM4tXTZJ0blrtVU ZxXQY+65wrX0zlxxogqO1GK9B8Du3xsc9qRVnGZx/LM1b8ErSrYTqgZVLw2FYDf0goej TqFQ== X-Gm-Message-State: AHQUAuYwfPWY/t5M+81u+ECXzmci2f2Slc/WJf0neWXgH9qoA1Dnb/bf W2VuDmxJSI/mVIi4+QHj0nlk3qhcvd0= X-Google-Smtp-Source: AHgI3Ibuo1WYLFRT7STuUBcHeZsXWbVXSBSth3ZAKeMWi80+Nc5ucTQQGdsxwidvd9ArVEATOXDjaw== X-Received: by 2002:a2e:999a:: with SMTP id w26-v6mr3832427lji.169.1550185251245; Thu, 14 Feb 2019 15:00:51 -0800 (PST) Received: from octofox.cadence.com (jcmvbkbc-1-pt.tunnel.tserv24.sto1.ipv6.he.net. [2001:470:27:1fa::2]) by smtp.gmail.com with ESMTPSA id h123sm172384lfh.26.2019.02.14.15.00.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 14 Feb 2019 15:00:50 -0800 (PST) From: Max Filippov To: qemu-devel@nongnu.org Date: Thu, 14 Feb 2019 14:59:52 -0800 Message-Id: <20190214230000.24894-6-jcmvbkbc@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20190214230000.24894-1-jcmvbkbc@gmail.com> References: <20190214230000.24894-1-jcmvbkbc@gmail.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::244 Subject: [Qemu-devel] [PATCH 05/13] target/xtensa: sort FLIX instruction opcodes X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Max Filippov , Richard Henderson Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" Opcodes in different slots may read and write same resources (registers, states). In the absence of resource dependency loops it must be possible to sort opcodes to avoid interference. Record resources used by each opcode in the bundle. Build opcode dependency graph and use topological sort to order its nodes. In case of success translate opcodes in sort order. In case of failure report and raise invalid opcode exception. Signed-off-by: Max Filippov --- target/xtensa/cpu.h | 2 + target/xtensa/translate.c | 226 ++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 220 insertions(+), 8 deletions(-) diff --git a/target/xtensa/cpu.h b/target/xtensa/cpu.h index db8ee70a0386..c59f79e56326 100644 --- a/target/xtensa/cpu.h +++ b/target/xtensa/cpu.h @@ -373,6 +373,8 @@ enum { XTENSA_OP_EXIT_TB_0 = 0x800, XTENSA_OP_NAME_ARRAY = 0x8000, + + XTENSA_OP_CONTROL_FLOW = 0x10000, }; typedef struct XtensaOpcodeOps { diff --git a/target/xtensa/translate.c b/target/xtensa/translate.c index e8dddd32b3af..616ed8f57972 100644 --- a/target/xtensa/translate.c +++ b/target/xtensa/translate.c @@ -846,6 +846,156 @@ static inline unsigned xtensa_op0_insn_len(DisasContext *dc, uint8_t op0) return xtensa_isa_length_from_chars(dc->config->isa, &op0); } +struct opcode_arg_info { + uint32_t resource; + int index; +}; + +struct slot_prop { + XtensaOpcodeOps *ops; + uint32_t arg[MAX_OPCODE_ARGS]; + uint32_t raw_arg[MAX_OPCODE_ARGS]; + struct opcode_arg_info in[MAX_OPCODE_ARGS]; + struct opcode_arg_info out[MAX_OPCODE_ARGS]; + unsigned n_in; + unsigned n_out; + uint32_t op_flags; +}; + +enum resource_type { + RES_REGFILE, + RES_STATE, +}; + +static uint32_t encode_resource(enum resource_type r, unsigned g, unsigned n) +{ + assert(r < 256 && g < 256 && n < 65536); + return (r << 24) | (g << 16) | n; +} + +/* + * a depends on b if b must be executed before a, + * because a's side effects will destroy b's inputs. + */ +static bool op_depends_on(const struct slot_prop *a, + const struct slot_prop *b) +{ + unsigned i = 0; + unsigned j = 0; + + if (a->op_flags & XTENSA_OP_CONTROL_FLOW) { + return true; + } + while (i < a->n_out && j < b->n_in) { + if (a->out[i].resource < b->in[j].resource) { + ++i; + } else if (a->out[i].resource > b->in[j].resource) { + ++j; + } else { + return true; + } + } + return false; +} + +/* + * Calculate evaluation order for slot opcodes. + * Build opcode order graph and output its nodes in topological sort order. + * An edge a -> b in the graph means that opcode a must be followed by + * opcode b. + */ +static bool tsort(struct slot_prop *slot, + struct slot_prop *sorted[], + unsigned n) +{ + struct tsnode { + unsigned n_in_edge; + unsigned n_out_edge; + unsigned out_edge[MAX_INSN_SLOTS]; + } node[MAX_INSN_SLOTS]; + + unsigned in[MAX_INSN_SLOTS]; + unsigned i, j; + unsigned n_in = 0; + unsigned n_out = 0; + unsigned n_edge = 0; + unsigned in_idx; + + for (i = 0; i < n; ++i) { + node[i].n_in_edge = 0; + node[i].n_out_edge = 0; + } + + for (i = 0; i < n; ++i) { + unsigned n_out_edge = 0; + + for (j = 0; j < n; ++j) { + if (i != j && op_depends_on(slot + j, slot + i)) { + node[i].out_edge[n_out_edge] = j; + ++node[j].n_in_edge; + ++n_out_edge; + ++n_edge; + } + } + node[i].n_out_edge = n_out_edge; + } + + for (i = 0; i < n; ++i) { + if (!node[i].n_in_edge) { + in[n_in] = i; + ++n_in; + } + } + + for (in_idx = 0; in_idx < n_in; ++in_idx) { + i = in[in_idx]; + sorted[n_out] = slot + i; + ++n_out; + for (j = 0; j < node[i].n_out_edge; ++j) { + --n_edge; + if (--node[node[i].out_edge[j]].n_in_edge == 0) { + in[n_in] = node[i].out_edge[j]; + ++n_in; + } + } + } + return n_edge == 0; +} + +static void opcode_add_resource(struct slot_prop *op, + uint32_t resource, char direction, + int index) +{ + switch (direction) { + case 'm': + case 'i': + assert(op->n_in < ARRAY_SIZE(op->in)); + op->in[op->n_in].resource = resource; + op->in[op->n_in].index = index; + ++op->n_in; + /* fall through */ + case 'o': + if (direction == 'm' || direction == 'o') { + assert(op->n_out < ARRAY_SIZE(op->out)); + op->out[op->n_out].resource = resource; + op->out[op->n_out].index = index; + ++op->n_out; + } + break; + default: + g_assert_not_reached(); + } +} + +static int resource_compare(const void *a, const void *b) +{ + const struct opcode_arg_info *pa = a; + const struct opcode_arg_info *pb = b; + + return pa->resource < pb->resource ? + -1 : (pa->resource > pb->resource ? 1 : 0); +} + static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) { xtensa_isa isa = dc->config->isa; @@ -855,11 +1005,8 @@ static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) int slot, slots; unsigned i; uint32_t op_flags = 0; - struct { - XtensaOpcodeOps *ops; - uint32_t arg[MAX_OPCODE_ARGS]; - uint32_t raw_arg[MAX_OPCODE_ARGS]; - } slot_prop[MAX_INSN_SLOTS]; + struct slot_prop slot_prop[MAX_INSN_SLOTS]; + struct slot_prop *ordered[MAX_INSN_SLOTS]; uint32_t debug_cause = 0; uint32_t windowed_register = 0; uint32_t coprocessor = 0; @@ -954,6 +1101,68 @@ static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) windowed_register |= ops->test_overflow(dc, arg, ops->par); } coprocessor |= ops->coprocessor; + + if (slots > 1) { + slot_prop[slot].n_in = 0; + slot_prop[slot].n_out = 0; + slot_prop[slot].op_flags = 0; + + opnds = xtensa_opcode_num_operands(isa, opc); + + for (opnd = vopnd = 0; opnd < opnds; ++opnd) { + bool visible = xtensa_operand_is_visible(isa, opc, opnd); + + if (xtensa_operand_is_register(isa, opc, opnd)) { + xtensa_regfile rf = xtensa_operand_regfile(isa, opc, opnd); + uint32_t v = 0; + + xtensa_operand_get_field(isa, opc, opnd, fmt, slot, + dc->slotbuf, &v); + xtensa_operand_decode(isa, opc, opnd, &v); + opcode_add_resource(slot_prop + slot, + encode_resource(RES_REGFILE, rf, v), + xtensa_operand_inout(isa, opc, opnd), + visible ? vopnd : -1); + } + if (visible) { + ++vopnd; + } + } + + opnds = xtensa_opcode_num_stateOperands(isa, opc); + + for (opnd = 0; opnd < opnds; ++opnd) { + xtensa_state state = xtensa_stateOperand_state(isa, opc, opnd); + + opcode_add_resource(slot_prop + slot, + encode_resource(RES_STATE, 0, state), + xtensa_stateOperand_inout(isa, opc, opnd), + -1); + } + if (xtensa_opcode_is_branch(isa, opc) || + xtensa_opcode_is_jump(isa, opc) || + xtensa_opcode_is_loop(isa, opc) || + xtensa_opcode_is_call(isa, opc)) { + slot_prop[slot].op_flags |= XTENSA_OP_CONTROL_FLOW; + } + + qsort(slot_prop[slot].in, slot_prop[slot].n_in, + sizeof(slot_prop[slot].in[0]), resource_compare); + qsort(slot_prop[slot].out, slot_prop[slot].n_out, + sizeof(slot_prop[slot].out[0]), resource_compare); + } + } + + if (slots > 1) { + if (!tsort(slot_prop, ordered, slots)) { + qemu_log_mask(LOG_UNIMP, + "Circular resource dependencies (pc = %08x)\n", + dc->pc); + gen_exception_cause(dc, ILLEGAL_INSTRUCTION_CAUSE); + return; + } + } else { + ordered[0] = slot_prop + 0; } if ((op_flags & XTENSA_OP_PRIVILEGED) && @@ -1002,10 +1211,11 @@ static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) } for (slot = 0; slot < slots; ++slot) { - XtensaOpcodeOps *ops = slot_prop[slot].ops; + struct slot_prop *pslot = ordered[slot]; + XtensaOpcodeOps *ops = pslot->ops; - dc->raw_arg = slot_prop[slot].raw_arg; - ops->translate(dc, slot_prop[slot].arg, ops->par); + dc->raw_arg = pslot->raw_arg; + ops->translate(dc, pslot->arg, ops->par); } if (dc->base.is_jmp == DISAS_NEXT) {