From patchwork Wed Jan 30 23:54:40 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Max Filippov X-Patchwork-Id: 1033843 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="PYrerDdn"; dkim-atps=neutral Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43qgHQ35JCz9s9h for ; Thu, 31 Jan 2019 10:56:02 +1100 (AEDT) Received: from localhost ([127.0.0.1]:45938 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gozi4-0002Dk-DV for incoming@patchwork.ozlabs.org; Wed, 30 Jan 2019 18:56:00 -0500 Received: from eggs.gnu.org ([209.51.188.92]:56171) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gozhN-0002Cl-BJ for qemu-devel@nongnu.org; Wed, 30 Jan 2019 18:55:20 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gozhL-0006vA-UL for qemu-devel@nongnu.org; Wed, 30 Jan 2019 18:55:17 -0500 Received: from mail-lj1-x242.google.com ([2a00:1450:4864:20::242]:38647) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gozhL-0006uh-KB for qemu-devel@nongnu.org; Wed, 30 Jan 2019 18:55:15 -0500 Received: by mail-lj1-x242.google.com with SMTP id c19-v6so1092810lja.5 for ; Wed, 30 Jan 2019 15:55:15 -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=CALC9WRjIDTDlZd/yG9HWhFgbsYtul3rV7fPyLW3Yck=; b=PYrerDdn5re6e8u7NvX50jvCjiLZ7CDnYLJYrzKMvPTNmyI5UqzbPaK2Qy8eVnMsvE WDf9DKRj/xsPNUk/I1KajOi4je0t0lk1/X+hHqhrVixmU0WUySHaWifQdDmZaqEzw4Dp T6zlM1W13nPcQ1TT/KzmqMWoSkHbJNYYfTD3oYX7U+3/XDnb+IKp14RACkttEFaaPmGj 6H5BgePFRYAbsskH4Wkz3cxX+h1e06kAriKE4joE3TP/xWTKUQrCkm6w3kX8UgL34fO+ /PS7C5bgHGMSLDNIpa+oSSBHsX2Syk0O3T8TEAN7MNb0V8r3xiQ1Z/F2hRQOOFkih2/B I9gw== 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=CALC9WRjIDTDlZd/yG9HWhFgbsYtul3rV7fPyLW3Yck=; b=AIgxVkF8Q/boAitHOk/jlNO9wy0Dk7tnZdSfOusopns3OCj3BgdDmsqNQHoUhaBFRm 4v4y3/peeJBVTPqjpk48PNbIF3apsiY3y24+36J5WBtGtk1lEUmPPGnuCNFaqp0BMtQq QrUTy6Airz3vgpIvqdOWbY812rMQ+yIg3J4mtaBM3YQeoIUmS99bZiBqbRuY7jpv7XKJ 5xPLQaZO5ONVU8mKTGudJYQ4c3XOXIQAOzAwwUjTTcvG9SDf+uFNHl9QnQCzm36hZgKo baAYFiEZo7TL73HhWWsKM+k4C9zm8vYrwZy6mhKffIl8LS4Z3wbmdXQakhCFMh9oqVwv CIug== X-Gm-Message-State: AHQUAuZlU6OyBsqIa1EWBuSNcrKvmUsCMFNV2lkQ042hHBqrhD3k2aW/ SKjBHC6qy2ocGyuzREYYvxQam82GTVw= X-Google-Smtp-Source: AHgI3IadD25b6F/Z8uL72cIvuTGWcv15Q6OA1BnKKEdfFbe+cnwB/mi7k8tYoHvi41mFG8kck42//A== X-Received: by 2002:a2e:5816:: with SMTP id m22-v6mr2297353ljb.177.1548892513842; Wed, 30 Jan 2019 15:55:13 -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 w9sm527752lfc.66.2019.01.30.15.55.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 30 Jan 2019 15:55:13 -0800 (PST) From: Max Filippov To: qemu-devel@nongnu.org Date: Wed, 30 Jan 2019 15:54:40 -0800 Message-Id: <20190130235442.2876-2-jcmvbkbc@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20190130235442.2876-1-jcmvbkbc@gmail.com> References: <20190130235442.2876-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::242 Subject: [Qemu-devel] [PATCH 1/3] 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 for now. Signed-off-by: Max Filippov --- target/xtensa/translate.c | 202 ++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 194 insertions(+), 8 deletions(-) diff --git a/target/xtensa/translate.c b/target/xtensa/translate.c index a068b6e8335d..b3718d33eec8 100644 --- a/target/xtensa/translate.c +++ b/target/xtensa/translate.c @@ -855,6 +855,138 @@ static inline unsigned xtensa_op0_insn_len(DisasContext *dc, uint8_t op0) return xtensa_isa_length_from_chars(dc->config->isa, &op0); } +struct slot_prop { + XtensaOpcodeOps *ops; + uint32_t arg[MAX_OPCODE_ARGS]; + uint32_t raw_arg[MAX_OPCODE_ARGS]; + uint32_t in[MAX_OPCODE_ARGS]; + uint32_t out[MAX_OPCODE_ARGS]; + unsigned n_in; + unsigned n_out; +}; + +enum resource_type { + XTENSA_CONTROL_FLOW, /* must be first, see op_depends_on */ + XTENSA_REGFILE, + XTENSA_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; +} + +static bool op_depends_on(const struct slot_prop *a, + const struct slot_prop *b) +{ + unsigned i = 0; + unsigned j = 0; + + if (a->n_out && a->out[0] == encode_resource(XTENSA_CONTROL_FLOW, 0, 0)) { + return true; + } + while (i < a->n_out && j < b->n_in) { + if (a->out[i] < b->in[j]) { + ++i; + } else if (a->out[i] > b->in[j]) { + ++j; + } else { + return true; + } + } + return false; +} + +static bool tsort(struct slot_prop *slot, + struct slot_prop *sorted[], + unsigned n) +{ + struct { + 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; + + 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 (i = 0; i < n_in; ++i) { + unsigned k = in[i]; + + sorted[n_out] = slot + k; + ++n_out; + for (j = 0; j < node[k].n_out_edge; ++j) { + --n_edge; + if (--node[node[k].out_edge[j]].n_in_edge == 0) { + in[n_in] = node[k].out_edge[j]; + ++n_in; + } + } + } + return n_edge == 0; +} + +static void opcode_add_resource(struct slot_prop *op, + uint32_t resource, char direction) +{ + switch (direction) { + case 'i': + assert(op->n_in < ARRAY_SIZE(op->in)); + op->in[op->n_in++] = resource; + break; + case 'o': + assert(op->n_out < ARRAY_SIZE(op->out)); + op->out[op->n_out++] = resource; + break; + case 'm': + assert(op->n_in < ARRAY_SIZE(op->in)); + assert(op->n_out < ARRAY_SIZE(op->out)); + op->in[op->n_in++] = resource; + op->out[op->n_out++] = resource; + break; + default: + g_assert_not_reached(); + } +} + +static int resource_compare(const void *a, const void *b) +{ + const uint32_t *pa = a; + const uint32_t *pb = b; + + return *pa < *pb ? -1 : (*pa > *pb ? 1 : 0); +} + static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) { xtensa_isa isa = dc->config->isa; @@ -864,11 +996,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; @@ -963,6 +1092,62 @@ static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) } } coprocessor |= ops->coprocessor; + + if (slots > 1) { + slot_prop[slot].n_in = 0; + slot_prop[slot].n_out = 0; + + opnds = xtensa_opcode_num_operands(isa, opc); + + for (opnd = 0; opnd < opnds; ++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(XTENSA_REGFILE, rf, v), + xtensa_operand_inout(isa, opc, opnd)); + } + } + + 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(XTENSA_STATE, 0, state), + xtensa_stateOperand_inout(isa, opc, opnd)); + } + 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)) { + opcode_add_resource(slot_prop + slot, + encode_resource(XTENSA_CONTROL_FLOW, 0, 0), + 'o'); + } + + qsort(slot_prop[slot].in, slot_prop[slot].n_in, sizeof(uint32_t), + resource_compare); + qsort(slot_prop[slot].out, slot_prop[slot].n_out, sizeof(uint32_t), + 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) && @@ -1011,10 +1196,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) {