基于规则的运行时程序生成语言Mumbo的介绍

$））'generate（），initialState）。换句话说，这个操作用于将Mumbo程序传递给Mumbo编译器。图1中给出了说明。用括号括起来预处理new defineClass（“c”，.new defineField（“f”，“int”），new defineMethod（“m”，...））使用编译器类课程介绍eval发送generate（）低空Fig. 1. 编译一个Mumbo类。4.5分析仪和变压器对于普通程序，编译器执行的源代码级优化很少是有效的。然而，在Mumbo中，它是优化运行时代码生成器的主要方法。这些由编译器的代码（'Code类等）组成 简而言之，这是一个源代码级优化可以有效的环境在本节中，我们将解释Mumbo的源代码级优化器通过等式逻辑和匹配，Maude使遍历程序的语法树变得容易。有两种基本的遍历：分析器和转换器。分析器遍历语法树并收集信息;转换器修改树9.为了方便地定义这些遍历，我们首先定义了一个叫做VISIT的模块，它定义了一个叫做visit的操作：op访问：MRewRule MExp MRewData -> MExpListDataPair。在[20]中，变压器被分为纯变压器和收集信息的变压器我们不做区分。$C类field f：intmethod m. >$C类field f：intmethod m.B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）3143这个操作的第一个参数是我们希望在语法树节点上应用的操作的名称（例如：constantPropagation）。第二个参数是要遍历的节点。最后一个参数是数据。当我们想在节点之间传递信息时，会用到这个参数。visit返回一对表达式和数据。返回的表达式可用于替换现有表达式;返回的数据可用于各种目的。访问操作足够通用，可以用来转换树、分析树，或者同时进行转换和分析它类似于[20]的遍历函数和[9]的访问者模式。遍历的默认行为在IDENTITY模块中定义 对于每个语法成分，我们定义访问递归地应用于节点的子树。默认情况下，它以自上而下、从左到右的顺序遍历树，而不更改树中的任何内容（因此命名为IDENTITY）。为了说明，让我们看看它是如何定义加法的：var R：MRewRule。变量E E ' E1 E2：MExp.变量D D1 D2：MRewData。ceq访视（R， E ++如果{E1，D1}：=访视（R，E，D）/\{E2，D2}：=访视（R，首先，通过向左操作数传递传入数据来访问左操作数。然后遍历右操作数，但这次我们传递从左操作数获得的信息这些数据可能与原始数据不同。在右操作数也被访问之后，从该遍历获得的最终数据与新操作数一起返回，新操作数可能由于变换而不同于原始操作数visit的默认行为以同样的方式定义其他语法单元。请注意，默认的遍历行为具有[otherwise]属性。这是一个关键点，当我们想让一个遍历函数在树上做一些特定的工作时，我们只需要为我们感兴趣的节点定义它的行为。对于其他节点，将应用默认行为。下面是一个例子：eqvisit（replace，E，replaceData（E，{E'，replaceData（E，E'）}。此操作在模块REPLACE中定义，它将一个表达式替换为另一个表达式。要替换的表达式是replaceData的第一个元素。它的第二个参数是将替换旧参数的表达式。我们只需要定义上面的等式（以及常量replace和replaceData）就可以让这个Transformer工作。当我们遍历我们想要替换的表达式E时，Maude应用这个等式并返回E对于其他表达式，应用恒等函数。这种遍历策略是通过使用[otherwise]44B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）31属性优化器需要关于程序的信息以便能够转换程序。例如，需要use-def分析来传播常量。因此，我们希望能够在节点上存储信息。为此，我们定义一个新的语法树节点：操作信息：MExp MInfoData-> MExp.info是一个闭包，它包含一个表达式和相关数据，并替换表达式。各种元素可以作为封装数据的一部分存储，包括use-def、gen-kill和类型信息。因此，分析器在遍历树时，只在访问过的节点上留下一些信息，然后继续遍历。例如，标记分析器为程序中的循环分配唯一的编号。然后我们使用这些标签来区分展开时的循环。我们在TAG模块中定义以下等式：varInfD：MInfoData. 我不知道。varsE BE E ' BE ' ：MExp.变量D1 D2：MRewData。ceqvisit（tag， info（doE while BE，InfD），tagData（N））={info（doE/\{这个等式匹配一个循环，从传入的数据中获取当前的数字，递增数字并递归地遍历主体和条件，最后将标记作为封装信息的一部分。我们定义了与程序分析相关的各种遍历器：• FreeVars：在方法体中查找自由变量• Info：将表达式封装在信息包中。需要在节点上保存信息。• 标记：为名称、循环和方法调用分配唯一的编号。标签用于在展开循环、内联方法和使用定义分析时进行识别。• 取消标签：取消标签。• 类型：在表达式上显示类型信息。尽可能缩小类型。• IsLocal：确定变量是局部变量还是字段。• IsFinal：确定所访问的字段是否最终。• CollectDefs：收集树中的所有定义。• GetDefs：查找特定变量的定义。• MayHaveAUse：确定一个变量在程序中是否有用。B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）3145• Escapes：确定特定变量是否从当前方法中转义• GenKill：计算表达式的gen-kill集。看《易经》的时候，就可以知道易经是怎样炼成的，怎样炼成的，怎样炼成的。• UD：计算use-def链。 能做may或must分析。• 重置：重新计算到目前为止收集的分析结果，并通过按给定顺序运行Tag、Type、IsLocal、IsFinal、GenKill和UD与分析仪类似，我们定义变压器。变压器主要有两种：需要分析结果的变压器和其他变压器。需要分析的变压器列表如下。• Replace：用给定的表达式替换特定的表达式• 内联：如果可能，内联一个特定的方法调用。• 展开：展开一个特定的循环。• CopyAssignment：如果可能，将一个变量赋值给另一个变量.• ConstantPropagation：删除常量。• NilCheck：如果保证E不是NIL，则将E等于NIL替换为False。• UselessDef：无用的定义。• UselessDecl：从方法头中删除无用的变量声明• FieldValue：如果可能，从对象中提取最终字段的值• UselessNew：如果一个未使用的对象的构造函数是无侧边引用的，则禁止创建该对象。回想一下，编译器是以一种无侧边引用的风格实现的。因此，UselessNew可以在优化方面提供很大• 在 一 个 固 定 点 迭 代 中 ， 按 照 给 定 的 顺 序 ， 执 行 Reset 、ConstantPropagation 、 CopyAssignment 、 NilCheck 、 FieldValue 、UselessDef、UselessNew和UselessDecl这些都不是代码扩展。因此，清理是保证终止。• Auto：在固定点迭代中自动内联方法和展开循环。• SpecializeClass：使用Auto和Rename创建一个优化版本的'Code类，它专门用于特定的SpecializeClass是顶级操作。它直接或间接地使用其他操作来生成优化的类。其他变压器不需要分析结果（即，它们不需要上下文外的信息）。删除冗余块并减少-46B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）31声明就是这样的例子由于Maude的匹配能力我们不提供完整的集合，但提供其中一些如下：等式{Elb;{Elb 2} }={Elb;Elb 2}。eqifTruethenEelse E ' = E.如果是，则E = {BE;E}。等式E和True = E。等式E ** 1 = E。在变形金刚中，汽车似乎很危险。它会自动内联方法并展开循环，直到代码不再更改。为了防止陷入无限循环，我们使用了一些技巧。例如，如果循环已经展开并且没有减少，我们就不 当一个循环被展开时，它会嵌套在一个if语句中：做E而做BE成为如果是，则执行E，否则执行0。因此，如果一个循环直接在if语句中，我们可以断定它是展开的，我们不展开它。内联的启发式如下：如果方法是递归的，我们内联它，只有当目标和参数是可定义的。一个表达式被称为可定义的，如果它包含的所有变量都是可定义的。一个变量是可定义的，如果它的定义存在于我们所处的方法中，并且如果这个定义的右边也是可定义的。例如，我们说一个变量是不可定义的，如果它是一个参数，并且它在传递给它的方法中没有赋值在第5节中，我们将看到，使用给定的优化规则集，可以将代码生成器简化为第1节中描述的形式。5优化我们在4.5节中提供的分析和转换是众所周知的，有很好的文档记录[1，15]，并且存在于许多编译器中。我们认为，给定的设置是足够的程序生成器在源代码级别的大幅优化。我们展示了几个例子。回想一下我们的目标：获得看起来像第1节中手写的程序生成器的代码。我们的第一个例子是一个程序片段，它定义了一个没有自由变量的方法。$method>$预处理阶段将其转换为以下表达式：B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）3147newnewnew'LinkedList（NIL，NIL），-没有声明的变量[’int],-下面的方法的主体：mult。对于两个名为“ x ” 和 “ xn e w ” 的 变 量 b i n O p C o d e （ [ “ m u l ” ] ，newnew此构造函数调用创建“defineMethodCode "类（”Code“的子类）的对象当表示的引用代码要转换为低级代码时，调用“defineMethodCode "对象的 因 此 ， 我 们 需 要 优 化 的 正 是 这 种 方 法 。 下 面 是 'eval in'defineMethodCode的定义-[’lowlevel{-为此方法setsetset-遍历paramList 以在LowLevelset'param = 'paramList中形成参数列表while（sendsetset}的情况;- 以'entry basic block set 'lowlevel = 'lowlevel #[”）{ 'entry：“]开始函数体-评估身体set-连接所有内容并返回set#（send}我们无法优化这种方法本身。 但它将发生在一个新的创建的类（由SpecializeClass模块生成），其中一些final字段已被赋予值-特别是，...））. 在这个特殊类的上下文中，“eval”代码可以是基本的48B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）31经过优化。具体来说，SpecializeClass创建了一个名为-2786与“defineMethodCode”相同，上面对“defineMethodCode "构造函数的调用newdefineMethodCode-2786（）的方法[’lowlevel{setset“）set#[”br}这是当此对象将被编译为低级代码这就是我们在第一节中所要达到的目标。 请注意，它还没有准备好发出代码：我们仍然需要知道封闭类的名称来给出函数但这是我们能得到的最好的。以重写次数衡量，这段代码的速度大约是未优化版本的四倍如果我们在代码中有一个漏洞，我们将不得不离开它的'eval'方法，如。我们的下一个例子是一个带孔的引用表达式$^我们省略了乘法运算符的eval方法的定义优化后方法[’tempCode{setsetset#B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）3149#["，“]#new}在这种方法中，我们在前面提到，通过对普通代码进行源代码级优化来获得显著的性能改进是困难的，原因很简单，程序员已经对代码进行了优化，使其满意。那么，为什么我们能够如此有效地优化这个源代码呢？我们正在优化的代码在程序员操作的语义级别--编写引用的代码片段--不可能优化代码。我们通过这些优化所实现的是允许程序员在那个级别上操作，而不是在优化代码所代表的级别上操作-机器指令的级别。5.1优化的局限性在前面的例子中，我们成功地获得了我们所期望的代码。现在，我们处理一个现有优化无法产生理想代码的示例。下面是一个例子：$此表达式的优化编译代码如下（伪代码）：if’leftelseif’left其他误差然而，我们可以使用现有的优化集生成的代码看起来像这样：if’left =’left误差if50B. Aktemur，S.Kamin/Electronic Notes in Theoretical Computer Science 147（2006）31’right =’right误差’result = emit code to multiply ’left and在这个代码中，我们有两倍于理想代码中的条件。这表明，在当前的优化中，例如，我们不能使用这样的信息：如果有了下面这样的等式，我们就能够实现理想的代码。[[如果be则e1elsee2;eb;如果be则e3elsee4]][[ifbethen{e1;eb;e3}else{e2;eb;e4}]]if（be）sidel