From nobody Tue Feb 10 03:36:57 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=nongnu.org ARC-Seal: i=1; a=rsa-sha256; t=1732153793; cv=none; d=zohomail.com; s=zohoarc; b=BRKQUmNVKEXEVPbjQ4JZdWttggUNTJqo+Z9rSdH2jWGuG2XX/U+zIN9pyNbAok9olHzyvAoi2BD+z2ko8UIqcUTxOo6WsF2rwS9ktKUACiful0HH94jDb4PBpYhrtBzqQWBCIMUlL6nHl80zNXVXxIecnYKIgVaEzzNw8XSGzOQ= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1732153793; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Reply-To:Reply-To:References:Sender:Subject:Subject:To:To:Message-Id; bh=l7AFrdw6Z5v8pKLgQV4E0S1CKxSIr+1atnVYTuO0AmQ=; b=IjLPulbF3t+K0kgps+1hd6HDNFvvVJjlBvroLJc8Od0lLLJu/rHOnJyIcqmpqxcOLyGdEMEXtmVEQellQ505h5Six+1uAnuP084sr8EVfFCaE6Wa05j8zib/Vyas0BYjJXc3OLdrX9UPPtDaTztElH4JwEc5Slf7zWwhXLzYAM8= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 173215379338382.77535558137515; Wed, 20 Nov 2024 17:49:53 -0800 (PST) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1tDwI2-0001hV-E3; Wed, 20 Nov 2024 20:47:26 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1tDwI1-0001gk-6O for qemu-devel@nongnu.org; Wed, 20 Nov 2024 20:47:25 -0500 Received: from rev.ng ([94.130.142.21]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1tDwHx-0004aC-OZ for qemu-devel@nongnu.org; Wed, 20 Nov 2024 20:47:24 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=rev.ng; s=dkim; h=Content-Transfer-Encoding:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To:Content-Type:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive:List-Unsubscribe:List-Unsubscribe-Post: List-Help; bh=l7AFrdw6Z5v8pKLgQV4E0S1CKxSIr+1atnVYTuO0AmQ=; b=Uk1rkfoGtu0uxGu fUeAp9b6F9c6NIFrJ2WNUjf48zF9mk55+/KEUbGqSu2XbcLpWKB217uwsbRYhVO+dXCE9rkOn+Pq2 z1CgPIeLjCjeSMs3MmSlGdQXe1vF4xnLJawCTQswQtaKIV8UtnV6TvXVcB4OX2pcbyf0mMTCribMC ok=; To: qemu-devel@nongnu.org Cc: ale@rev.ng, ltaylorsimpson@gmail.com, bcain@quicinc.com, richard.henderson@linaro.org, philmd@linaro.org, alex.bennee@linaro.org Subject: [RFC PATCH v1 29/43] helper-to-tcg: Introduce TCG register allocation Date: Thu, 21 Nov 2024 02:49:33 +0100 Message-ID: <20241121014947.18666-30-anjo@rev.ng> In-Reply-To: <20241121014947.18666-1-anjo@rev.ng> References: <20241121014947.18666-1-anjo@rev.ng> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.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; Received-SPF: pass client-ip=94.130.142.21; envelope-from=anjo@rev.ng; helo=rev.ng X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_VALIDITY_RPBL_BLOCKED=0.001, RCVD_IN_VALIDITY_SAFE_BLOCKED=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-to: Anton Johansson From: Anton Johansson via Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: fail (Header signature does not verify) X-ZM-MESSAGEID: 1732153794557116600 Content-Type: text/plain; charset="utf-8" Based on the assumption of a cycle free IR, this commit adds a simple register allocator for emitted values in TCG. The goal of this pass is to reduce the number of temporaries required in the output code, which is especially important when dealing with gvec vectors as to not require very large amounts of temporary storage in CPUArchState. For each LLVM value in the IR, the allocator will assign a struct TcgV reprensenting a variable in the output TCG. Signed-off-by: Anton Johansson --- .../helper-to-tcg/include/CmdLineOptions.h | 2 + subprojects/helper-to-tcg/meson.build | 1 + .../passes/backend/TcgTempAllocationPass.cpp | 594 ++++++++++++++++++ .../passes/backend/TcgTempAllocationPass.h | 79 +++ .../helper-to-tcg/pipeline/Pipeline.cpp | 6 + 5 files changed, 682 insertions(+) create mode 100644 subprojects/helper-to-tcg/passes/backend/TcgTempAllocat= ionPass.cpp create mode 100644 subprojects/helper-to-tcg/passes/backend/TcgTempAllocat= ionPass.h diff --git a/subprojects/helper-to-tcg/include/CmdLineOptions.h b/subprojec= ts/helper-to-tcg/include/CmdLineOptions.h index 9553e26407..a5e467f8be 100644 --- a/subprojects/helper-to-tcg/include/CmdLineOptions.h +++ b/subprojects/helper-to-tcg/include/CmdLineOptions.h @@ -25,3 +25,5 @@ extern llvm::cl::list InputFiles; extern llvm::cl::opt TranslateAllHelpers; // Options for PrepareForTcgPass extern llvm::cl::opt TcgGlobalMappingsName; +// Options for TcgTempAllocation +extern llvm::cl::opt GuestPtrSize; diff --git a/subprojects/helper-to-tcg/meson.build b/subprojects/helper-to-= tcg/meson.build index 09caa74c63..ad3c307b6b 100644 --- a/subprojects/helper-to-tcg/meson.build +++ b/subprojects/helper-to-tcg/meson.build @@ -50,6 +50,7 @@ sources =3D [ 'passes/PrepareForTcgPass/TransformGEPs.cpp', 'passes/PrepareForTcgPass/CanonicalizeIR.cpp', 'passes/PrepareForTcgPass/IdentityMap.cpp', + 'passes/backend/TcgTempAllocationPass.cpp', ] =20 clang =3D bindir / 'clang' diff --git a/subprojects/helper-to-tcg/passes/backend/TcgTempAllocationPass= .cpp b/subprojects/helper-to-tcg/passes/backend/TcgTempAllocationPass.cpp new file mode 100644 index 0000000000..3ee679ec02 --- /dev/null +++ b/subprojects/helper-to-tcg/passes/backend/TcgTempAllocationPass.cpp @@ -0,0 +1,594 @@ +// +// Copyright(c) 2024 rev.ng Labs Srl. All Rights Reserved. +// +// This program is free software; you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation; either version 2 of the License, or +// (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, see . +// + +#include "TcgTempAllocationPass.h" +#include "PseudoInst.h" +#include "backend/TcgEmit.h" +#include "llvm-compat.h" +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace llvm; + +// Type to represent a list of free TcgV's that can be reused when +// we need a new temporary. Exists for the duration of a function, +// and is expected to be small <=3D 8 free TcgV's at any time. +// +// This justifies the type being an array, since iteration times to +// find a free element will be small. +using FreeListVector =3D SmallVector; + +// Finds the first TcgV in FreeList with a matching TcgSize and Kind +// Iterates over the FreeList to find a TcgV with matching TcgSize and Kind +static Optional findFreeTcgV(FreeListVector &FreeList, uint32_t TcgS= ize, + TcgVKind Kind) +{ + for (size_t i =3D 0; i < FreeList.size(); ++i) { + if (FreeList[i].TcgSize =3D=3D TcgSize and FreeList[i].Kind =3D=3D= Kind) { + TcgV Tcg =3D FreeList[i]; + // Swap-remove + FreeList[i] =3D FreeList.back(); + FreeList.pop_back(); + return Tcg; + } + } + return None; +} + +// +// Functions for mapping an LLVM Value to a TcgV +// + +// Provides a C string representation of a ConstantInt +static std::string constantIntToStr(const ConstantInt *C) +{ + SmallString<20> ResultStr; + auto *Int =3D cast(C); + const APInt Value =3D Int->getUniqueInteger(); + const char *SuffixStr =3D ""; + const bool Negative =3D Int->isNegative(); + if (Value.ugt(UINT32_MAX) or C->getBitWidth() =3D=3D 64) { + SuffixStr =3D Int->isNegative() ? "ll" : "ull"; + } + if (Int->getBitWidth() =3D=3D 1) { + ResultStr =3D (Value.getBoolValue()) ? "true" : "false"; + } else { + bool IsMax =3D (Negative) ? Value.isMaxSignedValue() : Value.isMax= Value(); + bool IsMin =3D Negative and Value.isMinSignedValue(); + unsigned Bitwidth =3D Value.getBitWidth(); + if (IsMax) { + return Twine("INT").concat(Twine(Bitwidth)).concat("_MAX").str= (); + } else if (IsMin) { + return Twine("INT").concat(Twine(Bitwidth)).concat("_MIN").str= (); + } else { + Value.toString(ResultStr, 10, Value.isNegative(), true); + } + } + return Twine(ResultStr).concat(SuffixStr).str(); +} + +// Given an integer LLVM value assign it to a TcgV, either by creating a n= ew +// one or finding a suitable one on the FreeList +static Expected mapInteger(TempAllocationData &TAD, + FreeListVector &FreeList, const Value *V) +{ + auto *Ty =3D cast(V->getType()); + + uint32_t LlvmSize =3D Ty->getBitWidth(); + if (LlvmSize > 64) { + return mkError("Bit widths > 64 are not supported: ", V); + } + + if (isa(V)) { + // Constant integer + auto Tcg =3D TcgV::makeImmediate(constantIntToStr(cast(V)), + llvmToTcgSize(LlvmSize), LlvmSize); + return TAD.map(V, Tcg); + } else if (isa(V)) { + // Argument + uint32_t TcgSize =3D llvmToTcgSize(LlvmSize); + auto ArgInfoIt =3D TAD.Args.ArgInfoMap.find(V); + if (ArgInfoIt !=3D TAD.Args.ArgInfoMap.end() and + ArgInfoIt->second =3D=3D ArgImmediate) { + auto Tcg =3D TcgV::makeImmediate(tcg::mkName("i"), TcgSize, Ll= vmSize); + return TAD.map(V, Tcg); + } else { + auto Tcg =3D TcgV::makeTemp(TcgSize, LlvmSize, IrValue); + return TAD.map(V, Tcg); + } + } else { + // Non-constant integer + uint32_t TcgSize =3D 0; + auto *ICmp =3D dyn_cast(V); + if (ICmp) { + // icmp's return i1's and are used as either 32-bit or 64-bit = TCGv + // in QEMU. Assume the TcgSize from operands. + assert(LlvmSize =3D=3D 1); + auto *IntTy0 =3D + dyn_cast(ICmp->getOperand(0)->getType()); + if (!IntTy0) { + return mkError("Icmp on non-integer type"); + } + TcgSize =3D llvmToTcgSize(IntTy0->getBitWidth()); + } else { + // Normal integer, get the TcgSize from the LlvmSize as for + // constants + TcgSize =3D llvmToTcgSize(LlvmSize); + } + + Optional Tcg =3D findFreeTcgV(FreeList, TcgSize, IrValue); + if (Tcg) { + // Found a TcgV of the corresponding TcgSize, update LlvmSize + Tcg->LlvmSize =3D LlvmSize; + return TAD.map(V, *Tcg); + } else { + // Otherwise, create a new value + const auto Tcg =3D TcgV::makeTemp(TcgSize, LlvmSize, IrValue); + return TAD.map(V, Tcg); + } + } +} + +// Given an vector LLVM value assign it to a TcgV, either by creating a new +// one or finding a suitable one on the FreeList. Special care is taken to +// map individual elements of constant vectors. +static Expected mapVector(TempAllocationData &TAD, + FreeListVector &FreeList, const Value *V, + VectorType *VecTy) +{ + auto *IntTy =3D dyn_cast(VecTy->getElementType()); + if (!IntTy) { + return mkError("Vectors of non-integer element type not supported!= \n"); + } + uint32_t ElementCount =3D compat::getVectorElementCount(VecTy); + uint32_t ElementWidth =3D IntTy->getBitWidth(); + + if (ElementWidth =3D=3D 1) { + return mkError("Invalid vector width"); + } + + auto *ICmp =3D dyn_cast(V); + if (ICmp) { + auto *VecTy =3D cast(ICmp->getOperand(0)->getType()); + auto *IntTy =3D cast(VecTy->getElementType()); + ElementWidth =3D IntTy->getBitWidth(); + } + + uint32_t VectorWidth =3D ElementCount * ElementWidth; + + // Create or find a TcgV + Optional Tcg =3D findFreeTcgV(FreeList, VectorWidth, IrPtrToOffs= et); + if (Tcg) { + Tcg->LlvmSize =3D ElementWidth; + Tcg->VectorElementCount =3D ElementCount; + } else { + Tcg =3D TcgV::makeVector(VectorWidth, ElementWidth, ElementCount); + } + + // For constant vectors, make sure all individual elements are mapped + auto *Const =3D dyn_cast(V); + if (Const) { + // Make sure all arguments being splatted are mapped + Constant *Splat =3D Const->getSplatValue(); + if (Splat) { + // Map single splatted value + // <32 x i32> + // or, + // <32 x i32> + assert(mapInteger(TAD, FreeList, Splat)); + } else { + // Map constant elements of vector where elements differ + // <32 x i32> + for (unsigned I =3D 0; I < Tcg->VectorElementCount; ++I) { + Value *V =3D Const->getAggregateElement(I); + assert(mapInteger(TAD, FreeList, V)); + } + } + } + + return TAD.map(V, *Tcg); +} + +// Given an pointer LLVM value assign it to a TcgV, either by creating a n= ew +// one or finding a suitable one on the FreeList. NOTE: Pointers may be m= apped +// to env via comparison with TempAllocationData::EnvPtr. +static Expected mapPointer(TempAllocationData &TAD, + FreeListVector &FreeList, const Value *V) +{ + auto *Ty =3D cast(V->getType()); + auto *ElTy =3D Ty->getPointerElementType(); + if (isa(V)) { + auto ArgInfoIt =3D TAD.Args.ArgInfoMap.find(V); + if (ArgInfoIt !=3D TAD.Args.ArgInfoMap.end() and + ArgInfoIt->second =3D=3D ArgPtrToOffset) { + const auto Tcg =3D TcgV::makeVector(GuestPtrSize, GuestPtrSize= , 1); + return TAD.map(V, Tcg); + } else { + auto IsEnv =3D (TAD.Args.EnvPtr.hasValue() && *TAD.Args.EnvPtr= =3D=3D V); + const auto Tcg =3D TcgV::makeTemp(GuestPtrSize, GuestPtrSize, + IsEnv ? IrEnv : IrPtr); + return TAD.map(V, Tcg); + } + } else if (isa(V)) { + // `alloca`s represent stack variables in LLVM IR and return + // pointers, we can simply map them to `IrValue`s + auto *IntTy =3D dyn_cast(ElTy); + if (!IntTy) { + return mkError("alloca with unsupported type: ", V); + } + + const uint32_t LlvmBitWidth =3D IntTy->getBitWidth(); + if (LlvmBitWidth > 64) { + return mkError("alloca with unsupported size: ", V); + } + const uint32_t TcgBitWidth =3D llvmToTcgSize(LlvmBitWidth); + + // find or create a new IrValue + Optional Tcg =3D findFreeTcgV(FreeList, TcgBitWidth, IrValue= ); + if (Tcg) { + return TAD.map(V, *Tcg); + } else { + const auto Tcg =3D TcgV::makeTemp(TcgBitWidth, LlvmBitWidth, I= rValue); + return TAD.map(V, Tcg); + } + } else if (isa(ElTy)) { + return mapVector(TAD, FreeList, V, cast(ElTy)); + } else { + // Otherwise, find or create a new IrPtr of the target pointer size + Optional Tcg =3D findFreeTcgV(FreeList, GuestPtrSize, IrPtr); + if (Tcg) { + return TAD.map(V, *Tcg); + } else { + auto Tcg =3D TcgV::makeTemp(GuestPtrSize, GuestPtrSize, IrPtr); + return TAD.map(V, Tcg); + } + } + + return mkError("Unable to map constant ", V); +} + +// Given a LLVM value, assigns a TcgV by type (integer, pointer, vector). = If +// the given value has already been mapped to a TcgV, return it. +static Expected mapValue(TempAllocationData &Data, + FreeListVector &FreeList, const Value *V) +{ + // Return previously mapped value + auto It =3D Data.Map.find(V); + if (It !=3D Data.Map.end()) { + return It->second; + } + + Type *Ty =3D V->getType(); + if (isa(Ty)) { + return mapInteger(Data, FreeList, V); + } else if (isa(Ty)) { + return mapPointer(Data, FreeList, V); + } else if (isa(Ty)) { + return mapVector(Data, FreeList, V, cast(Ty)); + } + + return mkError("Unable to map value ", V); +} + +static bool shouldSkipInstruction(const Instruction *const I, + bool SkipReturnMov) +{ + // Skip returns if we're skipping return mov's + if (isa(I) and SkipReturnMov) { + return true; + } + // Skip assertions + auto Call =3D dyn_cast(I); + if (!Call) { + return false; + } + Function *F =3D Call->getCalledFunction(); + if (!F) { + return false; + } + StringRef Name =3D F->getName(); + return (Name =3D=3D "__assert_fail" or Name =3D=3D "g_assertion_messag= e_expr" or + isa(I) or isa(I)); +} + +static bool shouldSkipValue(const Value *const V) +{ + return (isa(V) or isa(V) or isa= (V)); +} + +// Wrapper function to extract operands from GEP, call, +// and other instruction +static const iterator_range +getOperands(const Instruction *const I) +{ + switch (I->getOpcode()) { + case Instruction::GetElementPtr: + return cast(I)->operands(); + case Instruction::Call: + return cast(I)->args(); + default: + return I->operands(); + } +} + +// A mapping of the return TCG variable to the value RetV is valid +// if no use of an argument is found between the use of value (where +// IBegin/BbBegin starts) and it's definition +// use of an argument is found between the old mapping +// and the new. +static bool isRetMapValid(Arguments &Args, + po_iterator BbBegin, + po_iterator BbEnd, + BasicBlock::const_reverse_iterator IBegin, + BasicBlock::const_reverse_iterator IEnd, + const Value *RetV) +{ + auto BbIt =3D BbBegin; + auto IIt =3D IBegin; + + do { + do { + if (cast(&*IIt) =3D=3D RetV) { + return true; + } + + for (auto &V : getOperands(&*IIt)) { + if (isa(V) and Args.ArgInfoMap[V] !=3D ArgImmedi= ate) { + return false; + } + } + } while (++IIt !=3D IEnd); + + ++BbIt; + IEnd =3D (*BbIt)->rend(); + IIt =3D (*BbIt)->rbegin(); + } while (BbIt !=3D BbEnd); + + return false; +} + +Expected +allocateTemporaries(const Function &F, const AnnotationMapTy &Annotations) +{ + TempAllocationData Data; + FreeListVector FreeList; + + assert(!F.isDeclaration()); + + // Use function annotation data to force type of arguments + auto It =3D Annotations.find(&F); + if (It !=3D Annotations.end()) { + for (const Annotation &Ann : It->second) { + ArgumentKind Kind; + switch (Ann.Kind) { + case AnnotationKind::HelperToTcg: + continue; + case AnnotationKind::Immediate: + Kind =3D ArgImmediate; + break; + case AnnotationKind::PtrToOffset: + Kind =3D ArgPtrToOffset; + break; + default: + abort(); + } + + for (uint32_t i : Ann.ArgIndices) { + assert(i < F.arg_size()); + Data.Args.ArgInfoMap[F.getArg(i)] =3D Kind; + } + } + } + + for (const Argument &Arg : F.args()) { + // Check if argument corresponds to Env, if so set the special + // EnvPtr field. + auto Ptr =3D dyn_cast(Arg.getType()); + if (Ptr) { + auto *Struct =3D dyn_cast(Ptr->getPointerElementTy= pe()); + // TODO: Identifying Env in this way is a bit fragile to name + // changes in QEMU, and assumes any non-QEMU code will still a= dopt + // the CPUArchState naming convention. Better is to handle all + // pointer-to-struct args as env. + if (Struct and Struct->getName() =3D=3D "struct.CPUArchState")= { + assert(!Data.Args.EnvPtr.hasValue()); + Data.Args.EnvPtr =3D &Arg; + } + } + + // If we didn't force an argument kind via annotations, assume Arg= Temp + if (Data.Args.ArgInfoMap.find(&Arg) =3D=3D Data.Args.ArgInfoMap.en= d()) { + Data.Args.ArgInfoMap[&Arg] =3D ArgTemp; + } + + Data.Args.Args.insert(&Arg); + } + + // The PrepareForOptPass removes all functions with non-int/void return + // types, assert this assumption. + Type *RetTy =3D F.getReturnType(); + assert(isa(RetTy) or RetTy->isVoidTy()); + // Map integer return values + if (auto IntTy =3D dyn_cast(RetTy)) { + Data.ReturnValue =3D TcgV::makeTemp(llvmToTcgSize(IntTy->getBitWid= th()), + IntTy->getBitWidth(), IrValue); + } + + // Begin/end iterators over basic blocks in the function. Used for che= cking + // that the initial return value map is valid and later used for itera= ting + // over basic blocks. + auto ItBbBegin =3D po_begin(&F); + auto ItBbEnd =3D po_end(&F); + + // Skip mov's to return value if possible, results of previous + // instructions might have been assigned the return value. + // + // This is possible if: + // 1. The return value is not an argument. + // 2. The return value is not a constant. + // 3. No use of an argument has occured after the definition of the + // value being returned. + { + const Instruction &I =3D *ItBbBegin->rbegin(); + + auto Ret =3D dyn_cast(&I); + if (Ret and Ret->getNumOperands() =3D=3D 1) { + Value *RetV =3D Ret->getReturnValue(); + bool ValidRetV =3D !isa(RetV) and !isa(= RetV); + if (ValidRetV and isRetMapValid(Data.Args, ItBbBegin, ItBbEnd, + (*ItBbBegin)->rbegin(), + (*ItBbBegin)->rend(), RetV)) { + Data.Map.try_emplace(RetV, *Data.ReturnValue); + Data.SkipReturnMov =3D true; + } + } + } + + // Iterate over instructions in reverse and try to allocate TCG variab= les. + // + // The algorithm is very straight forward, we keep a FreeList of TCG + // variables we can reuse. Variables are allocated on first use and + // "freed" on definition. + // + // We allow reuse of the return TCG variable in order to save one vari= able + // and skip the return mov if possible. Since source and return varia= bles + // can overlap, when take the conservative route and only allow reuse = of + // the return variable if no arguments have been used. + + bool SeenArgUse =3D false; + + for (auto ItBb =3D ItBbBegin; ItBb !=3D ItBbEnd; ++ItBb) { + const BasicBlock *BB =3D *ItBb; + // Loop over instructions in the basic block in reverse + for (auto IIt =3D BB->rbegin(), IEnd =3D BB->rend(); IIt !=3D IEnd= ; ++IIt) { + const Instruction &I =3D *IIt; + if (shouldSkipInstruction(&I, Data.SkipReturnMov)) { + continue; + } + + // For calls to the identity mapping pseudo instruction + // we simply want to propagate the type allocated for the resu= lt of + // the call to the operand. + if (isa(&I)) { + auto *Call =3D cast(&I); + PseudoInst Inst =3D getPseudoInstFromCall(Call); + if (Inst =3D=3D IdentityMap) { + Value *Arg =3D Call->getArgOperand(0); + Expected Tcg =3D mapValue(Data, FreeList, Arg); + assert(Tcg); + + auto It =3D Data.Map.find(cast(&I)); + assert(It !=3D Data.Map.end()); + uint8_t LlvmSize =3D It->second.LlvmSize; + It->second =3D Tcg.get(); + It->second.LlvmSize =3D LlvmSize; + continue; + } + } + + // Check if we've encountered any non-immediate argument yet + for (const Use &U : getOperands(&I)) { + if (isa(U) and + Data.Args.ArgInfoMap[U] !=3D ArgImmediate) { + SeenArgUse =3D true; + } + } + + // Free up variables as they are defined, iteration is in post= order + // meaning uses of vars always occur before definitions. + bool IsArg =3D Data.Args.ArgInfoMap.find(cast(&I)) !=3D + Data.Args.ArgInfoMap.end(); + auto It =3D Data.Map.find(cast(&I)); + if (!IsArg and It !=3D Data.Map.end() and + !cast(&I)->getType()->isVoidTy()) { + TcgV &Tcg =3D It->second; + switch (Tcg.Kind) { + case IrValue: + case IrPtr: + case IrPtrToOffset: + FreeList.push_back(Tcg); + break; + case IrConst: + case IrEnv: + case IrImmediate: + break; + default: + abort(); + } + } + + // Loop over operands and assign TcgV's. On first encounter of= a + // given operand we assign a new TcgV from the FreeList. + for (const Use &V : getOperands(&I)) { + auto It =3D Data.Map.find(V); + if (It !=3D Data.Map.end() or shouldSkipValue(V)) { + continue; + } + + Expected Tcg =3D mapValue(Data, FreeList, V); + if (!Tcg) { + return Tcg.takeError(); + } + + // If our value V got mapped to the return value, + // make sure the mapping is valid + // + // A mapping to the return value is valid as long as + // an argument has not been used. This is to prevent clob= bering + // in the case that arguments and the return value overlap. + if (Data.ReturnValue.hasValue() and *Tcg =3D=3D *Data.Retu= rnValue) { + bool Valid =3D + isRetMapValid(Data.Args, ItBb, ItBbEnd, IIt, IEnd,= V); + if (!SeenArgUse and Valid) { + continue; + } + + // The mapping was not valid, erase it and assign a ne= w one + Data.Map.erase(V); + Expected Tcg =3D mapValue(Data, FreeList, V); + if (!Tcg) { + return Tcg.takeError(); + } + } + } + } + } + + // The above only maps arguments that are actually used, make a final = pass + // over the arguments to map unused and immediate arguments. + for (auto V : Data.Args.Args) { + Expected Arg =3D mapValue(Data, FreeList, V); + if (!Arg) { + return Arg.takeError(); + } + } + + return Data; +} diff --git a/subprojects/helper-to-tcg/passes/backend/TcgTempAllocationPass= .h b/subprojects/helper-to-tcg/passes/backend/TcgTempAllocationPass.h new file mode 100644 index 0000000000..fff60d1ff6 --- /dev/null +++ b/subprojects/helper-to-tcg/passes/backend/TcgTempAllocationPass.h @@ -0,0 +1,79 @@ +// +// Copyright(c) 2024 rev.ng Labs Srl. All Rights Reserved. +// +// This program is free software; you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation; either version 2 of the License, or +// (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, see . +// + +#pragma once + +#include "FunctionAnnotation.h" +#include "backend/TcgType.h" + +#include +#include +#include +#include + +// +// TcgTempAllocationPass +// +// Analysis over the IR that performs basic register allocation to assign +// identifiers representing TCGv's to all values in a given function. +// +// Note: Input code is assumed to be loop free, which drastically simplifi= es +// the register allocation. This assumption is reasonable as we expect code +// with loops to be either unrolled or vectorized, and we currently don't = emit +// for loops in C. +// +// This pass also contains the logic for mapping various LLVM values to a = TcgV +// struct, which is necessary in order to figure out what type we need for= in +// TCG. +// + +namespace llvm +{ +class Function; +} + +enum ArgumentKind { + ArgTemp, + ArgImmediate, + ArgPtrToOffset, +}; + +struct Arguments { + llvm::Optional EnvPtr; + llvm::DenseMap ArgInfoMap; + llvm::SmallSet Args; +}; + +struct TempAllocationData { + // Mapping of LLVM Values to the corresponding TcgV + llvm::DenseMap Map; + + // Whether or not the final mov in an instruction can safely + // be ignored or not. + bool SkipReturnMov =3D false; + llvm::Optional ReturnValue; + Arguments Args; + + inline TcgV map(const llvm::Value *V, const TcgV &T) + { + return Map.try_emplace(V, T).first->second; + } +}; + +llvm::Expected +allocateTemporaries(const llvm::Function &F, + const AnnotationMapTy &Annotations); diff --git a/subprojects/helper-to-tcg/pipeline/Pipeline.cpp b/subprojects/= helper-to-tcg/pipeline/Pipeline.cpp index a8df592af3..b933a7bb1a 100644 --- a/subprojects/helper-to-tcg/pipeline/Pipeline.cpp +++ b/subprojects/helper-to-tcg/pipeline/Pipeline.cpp @@ -62,6 +62,12 @@ cl::opt TcgGlobalMappingsName( "into a struct to TCG globals"), cl::init("mappings"), cl::cat(Cat)); =20 +// Options for TcgTempAllocation +cl::opt + GuestPtrSize("guest-ptr-size", + cl::desc("Pointer size of the guest architecture"), + cl::init(32), cl::cat(Cat)); + // Define a TargetTransformInfo (TTI) subclass, this allows for overriding // common per-llvm-target information expected by other LLVM passes, such // as the width of the largest scalar/vector registers. Needed for consis= tent --=20 2.45.2