From nobody Sun Feb 8 05:08:59 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=gmail.com Return-Path: Received: from lists.gnu.org (209.51.188.17 [209.51.188.17]) by mx.zohomail.com with SMTPS id 1548892620223744.9558025037065; Wed, 30 Jan 2019 15:57:00 -0800 (PST) Received: from localhost ([127.0.0.1]:45947 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1goziw-000390-3F for importer@patchew.org; Wed, 30 Jan 2019 18:56:54 -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) 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) 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) 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+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" 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(DisasConte= xt *dc, uint8_t op0) return xtensa_isa_length_from_chars(dc->config->isa, &op0); } =20 +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 =3D 0; + unsigned j =3D 0; + + if (a->n_out && a->out[0] =3D=3D 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 =3D 0; + unsigned n_out =3D 0; + unsigned n_edge =3D 0; + + for (i =3D 0; i < n; ++i) { + node[i].n_in_edge =3D 0; + node[i].n_out_edge =3D 0; + } + + for (i =3D 0; i < n; ++i) { + unsigned n_out_edge =3D 0; + + for (j =3D 0; j < n; ++j) { + if (i !=3D j && op_depends_on(slot + j, slot + i)) { + node[i].out_edge[n_out_edge] =3D j; + ++node[j].n_in_edge; + ++n_out_edge; + ++n_edge; + } + } + node[i].n_out_edge =3D n_out_edge; + } + + for (i =3D 0; i < n; ++i) { + if (!node[i].n_in_edge) { + in[n_in] =3D i; + ++n_in; + } + } + + for (i =3D 0; i < n_in; ++i) { + unsigned k =3D in[i]; + + sorted[n_out] =3D slot + k; + ++n_out; + for (j =3D 0; j < node[k].n_out_edge; ++j) { + --n_edge; + if (--node[node[k].out_edge[j]].n_in_edge =3D=3D 0) { + in[n_in] =3D node[k].out_edge[j]; + ++n_in; + } + } + } + return n_edge =3D=3D 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++] =3D resource; + break; + case 'o': + assert(op->n_out < ARRAY_SIZE(op->out)); + op->out[op->n_out++] =3D 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++] =3D resource; + op->out[op->n_out++] =3D resource; + break; + default: + g_assert_not_reached(); + } +} + +static int resource_compare(const void *a, const void *b) +{ + const uint32_t *pa =3D a; + const uint32_t *pb =3D b; + + return *pa < *pb ? -1 : (*pa > *pb ? 1 : 0); +} + static void disas_xtensa_insn(CPUXtensaState *env, DisasContext *dc) { xtensa_isa isa =3D dc->config->isa; @@ -864,11 +996,8 @@ static void disas_xtensa_insn(CPUXtensaState *env, Dis= asContext *dc) int slot, slots; unsigned i; uint32_t op_flags =3D 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 =3D 0; uint32_t windowed_register =3D 0; uint32_t coprocessor =3D 0; @@ -963,6 +1092,62 @@ static void disas_xtensa_insn(CPUXtensaState *env, Di= sasContext *dc) } } coprocessor |=3D ops->coprocessor; + + if (slots > 1) { + slot_prop[slot].n_in =3D 0; + slot_prop[slot].n_out =3D 0; + + opnds =3D xtensa_opcode_num_operands(isa, opc); + + for (opnd =3D 0; opnd < opnds; ++opnd) { + if (xtensa_operand_is_register(isa, opc, opnd)) { + xtensa_regfile rf =3D xtensa_operand_regfile(isa, opc,= opnd); + uint32_t v =3D 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, opn= d)); + } + } + + opnds =3D xtensa_opcode_num_stateOperands(isa, opc); + + for (opnd =3D 0; opnd < opnds; ++opnd) { + xtensa_state state =3D xtensa_stateOperand_state(isa, opc,= opnd); + + opcode_add_resource(slot_prop + slot, + encode_resource(XTENSA_STATE, 0, state= ), + xtensa_stateOperand_inout(isa, opc, op= nd)); + } + 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(uint3= 2_t), + resource_compare); + } + } + + if (slots > 1) { + if (!tsort(slot_prop, ordered, slots)) { + qemu_log_mask(LOG_UNIMP, + "Circular resource dependencies (pc =3D %08x)\n", + dc->pc); + gen_exception_cause(dc, ILLEGAL_INSTRUCTION_CAUSE); + return; + } + } else { + ordered[0] =3D slot_prop + 0; } =20 if ((op_flags & XTENSA_OP_PRIVILEGED) && @@ -1011,10 +1196,11 @@ static void disas_xtensa_insn(CPUXtensaState *env, = DisasContext *dc) } =20 for (slot =3D 0; slot < slots; ++slot) { - XtensaOpcodeOps *ops =3D slot_prop[slot].ops; + struct slot_prop *pslot =3D ordered[slot]; + XtensaOpcodeOps *ops =3D pslot->ops; =20 - dc->raw_arg =3D slot_prop[slot].raw_arg; - ops->translate(dc, slot_prop[slot].arg, ops->par); + dc->raw_arg =3D pslot->raw_arg; + ops->translate(dc, pslot->arg, ops->par); } =20 if (dc->base.is_jmp =3D=3D DISAS_NEXT) { --=20 2.11.0