• 浪潮孙丕恕从信息时代到智能时代 人工智能价值将爆发式释放 2019-12-21
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
    • / 20
    • 下载费用:30 金币  

    重庆时时彩稳赚大底: 一种无损压缩系统依赖图的方法及装置.pdf

    关 键 词:
    一种 无损 压缩 系统 依赖 方法 装置
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201210584770.6

    申请日:

    2012.12.28

    公开号:

    CN103902273A

    公开日:

    2014.07.02

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 9/44申请日:20121228|||公开
    IPC分类号: G06F9/44 主分类号: G06F9/44
    申请人: 华为技术有限公司; 中国科学院计算技术研究所
    发明人: 李丰; 霍玮; 陈聪明; 衷璐洁; 张兆庆; 冯晓兵
    地址: 518129 广东省深圳市龙岗区坂田华为总部办公楼
    优先权:
    专利代理机构: 北京中博世达专利商标代理有限公司 11274 代理人: 申健
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201210584770.6

    授权公告号:

    103902273B||||||

    法律状态公告日:

    2017.07.07|||2014.07.30|||2014.07.02

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明的实施例提供一种无损压缩系统依赖图的方法及装置,涉及计算机领域,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。其方法为:首先提取程序中所有变量之间的等价关系,而后通过该等价关系将程序中所有变量分为不同的等价类,并根据这些等价类为系统依赖图中的节点设置键值,而后根据系统依赖图中的节点的键值压缩系统依赖图。本发明实施例用于对系统依赖图进行压缩。

    权利要求书

    权利要求书
    1.  一种无损压缩系统依赖图的方法,其特征在于,包括:
    根据别名分析信息获取程序中所有变量间的等价关系,并根据所述等价关系将所有变量分为不同的等价类;其中,所述别名分析信息是根据别名分析算法得到的;
    根据系统依赖图中的各个节点所代表的变量所属的等价类为所述系统依赖图中的各个节点设置键值;
    根据所述系统依赖图中的各个节点的键值对所述系统依赖图进行压缩。

    2.  根据权利要求1所述的无损压缩系统依赖图的方法,其特征在于,所述根据别名分析信息获取程序中所有变量间的等价关系,并根据所述等价关系将所有变量分为不同的等价类包括:
    根据所述别名分析信息建立从第一变量集合到指向所述变量集合中每个变量的指针集合的幂集的映射f,所述第一变量集合为程序中所有变量的集合;
    根据所述映射f建立从所述指针集合的幂集到第二变量集合的映射f′,将所有变量分为不同的等价类;所述第二变量集合为被同一组指针所指向的变量的集合。

    3.  根据权利要求2所述的无损压缩系统依赖图的方法,其特征在于,所述根据所述别名分析信息建立从第一变量集合到指向所述变量集合中每个变量的指针集合的幂集的映射f包括:
    为程序中的每个指针变量建立一个由该指针变量所指向的变量构成的指向集,为所有指向集中出现的每个变量建立一个空集合;
    将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到所述映射f。

    4.  根据权利要求2所述的无损压缩系统依赖图的方法,其特征在于,根据所述映射f建立从所述指针集合的幂集到第二变量集合的映射f′,将所有变量分为不同的等价类包括:
    建立第i个空集合,将所述映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到所述第i个空集合中,得到第i个等价类,并对所述第i个等价类设置编号,并从所述映射f的定义域中删除添加到所述第i个空集合中的变量,直至映射f的定义域中的变量个数 为0;其中,i的起始值为1,所述变量var表示映射f的定义域中的任意一个变量。

    5.  根据权利要求1至4任意一项所述的无损压缩系统依赖图的方法,其特征在于,所述根据系统依赖图中的各个节点所代表的变量所属的等价类为所述系统依赖图中的各个节点设置键值包括:
    将所述系统依赖图上的各个节点所代表的变量所属的等价类的编号对应设置为所述各个节点的键值。

    6.  根据权利要求1至5任意一项所述的无损压缩系统依赖图的方法,其特征在于,所述根据所述系统依赖图中的各个节点的键值对所述系统依赖图进行压缩包括:
    若所述系统依赖图上的任意一个节点的前驱节点集合或者后继节点集合中的任意两个节点拥有相同的键值,并且所述任意两个节点中有一个是副作用节点,则将所述任意两个节点中的副作用节点的出入边依次转化为所述任意两个节点中另外一个节点的出入边;
    删除所述系统依赖图中所有孤立的节点;
    合并所述系统依赖图上具有相同的源点和汇点的有向边。

    7.  一种系统依赖图无损压缩装置,其特征在于,包括:
    等价类获取???,用于根据别名分析信息获取程序中所有变量间的等价关系,并根据所述等价关系将所有变量分为不同的等价类,其中,所述别名分析信息是根据别名分析算法得到的;
    键值设置???,用于根据系统依赖图中的各个节点所代表的变量所属的等价类为所述系统依赖图中的各个节点设置键值;
    依赖图压缩???,用于根据所述系统依赖图中的各个节点的键值对所述系统依赖图进行压缩。

    8.  根据权利要求7所述的系统依赖图无损压缩装置,其特征在于,所述等价类获取??榘ǎ?BR>映射建立子???,用于根据所述别名分析信息建立从第一变量集合到指向所述变量集合中每个变量的指针集合的幂集的映射f,所述第一变量集合为程序中所有变量的集合;
    等价类获取子???,用于根据所述映射f建立从所述指针集合的幂集到第二变量集合的映射f′,所述第二变量集合为被同一组指针所指 向的变量的集合。

    9.  根据权利要求8所述的系统依赖图无损压缩装置,其特征在于,所述映射建立子??榫咛逵糜冢?BR>为程序中的每个指针变量建立一个由该指针变量所指向的变量构成的指向集,为所有指向集中出现的每个变量建立一个空集合;
    将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到所述映射f。

    10.  根据权利要求8所述的系统依赖图无损压缩装置,其特征在于,所述等价类获取子??榫咛逵糜冢?BR>建立第i个空集合,将所述映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到所述第i个空集合中,得到第i个等价类,并对所述第i个等价类设置编号,并从所述映射f的定义域中删除添加到所述第i个空集合中的变量,直至映射f的定义域中的变量个数为0;其中,i的起始值为1,所述变量var表示映射f的定义域中的任意一个变量。

    11.  根据权利要求7至10任意一项所述的系统依赖图无损压缩装置,其特征在于,所述键值设置??榫咛逵糜冢?BR>将所述系统依赖图上的各个节点所代表的变量所属的等价类的编号对应设置为所述各个节点的键值。

    12.  根据权利要求7至11任意一项所述的系统依赖图无损压缩装置,其特征在于,所述依赖图压缩??榘ǎ?BR>出入边转化子???,用于若系统依赖图上的某个节点的前驱节点集合或者后继节点集合中的任意两个节点拥有相同的键值,并且所述任意两个节点中有一个是副作用节点,则将所述任意两个节点中的副作用节点的出入边依次转化为所述任意两个节点中另外一个节点的出入边;
    节点删除子???,用于删除系统依赖图中所有孤立的节点;
    合并子???,用于合并系统依赖图上具有相同的源点和汇点的有向边。

    说明书

    说明书一种无损压缩系统依赖图的方法及装置
    技术领域
    本发明涉及计算机领域,尤其涉及一种无损压缩系统依赖图的方法及装置。
    背景技术
    程序静态切片是一种重要的程序分析技术,广泛应用于程序理解、测试、调试、验证、维护,能够帮助程序员提取所关注代码,降低程序分析、错误验证、维护等领域。目前,主流的切片工具均采用基于系统依赖图的图可达算法。
    系统依赖图(System Dependence Graph,SDG)是一个有向图,是对程序依赖图(Program Dependence Graph,PDG)的扩展。以系统依赖图为基础的程序切片算法,是通过遍历系统依赖图,从中提取出可能影响某个变量在程序中某个位置上的取值的程序代码。但是现有的切片算法开销与精度都无法满足大规模使用程序的需求。
    因此,为了解决上述问题,现有技术通常采用的技术包括:一、通过提高别名分析精度降低SDG的规模,因为SDG的规模不仅决定其自身的计算与存储的时空开销,还直接影响切片的效率。其中,别名分析,也称指针分析,是一种识别程序中可能用两种以上的方法访问的存储位置的静态分析技术。别名分析所得出的结果是基于SDG的程序切片技术中用于创建系统依赖图时所需的输入之一。二、通过限制切片算法的上下文敏感性(Context Sensitivity)来减少切片算法遍历SDG的开销。
    在实现上述降低SDG规模和减少切片算法的时空开销的过程中,发明人发现现有技术中至少存在如下问题:
    提高指针分析的精度虽然可以适度降低SDG的规模,但高精度的指针分析算法本身不仅需要高昂的时空开销,也几乎无助于切片精度的提高。而采用限制切片算法的上下文敏感性来缓解遍历SDG的开销,会使切片的精度降低。
    发明内容
    本发明的实施例提供一种无损压缩系统依赖图的方法及装置,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。
    为达到上述目的,本发明的实施例采用如下技术方案:
    第一方面,提供一种无损压缩系统依赖图的方法,包括:
    根据别名分析信息获取程序中所有变量间的等价关系,并根据所述等价关系将所有变量分为不同的等价类,其中,所述别名分析信息是根据别名分析算法得到的;
    根据系统依赖图中的各个节点所代表的变量所属的等价类为所述系统依赖图中的各个节点设置键值;
    根据所述系统依赖图中的各个节点的键值对所述系统依赖图进行压缩。
    在第一种可能的实现方式中,结合第一方面,所述根据别名分析信息获取程序中所有变量间的等价关系,并根据所述等价关系将所有变量分为不同的等价类包括:
    根据所述别名分析信息建立从第一变量集合到指向所述变量集合中每个变量的指针集合的幂集的映射f,所述第一变量集合为程序中所有变量的集合;
    根据所述映射f建立从所述指针集合的幂集到第二变量集合的映射f′,以将所有变量分为不同的等价类;所述第二变量集合为被同一组指针所指向的变量的集合。
    在第二种可能的实现方式中,结合第一方面或第一方面的第一种可能的实现方式,所述根据所述别名分析信息建立从第一变量集合到指向所述变量集合中每个变量的指针集合的幂集的映射f包括:
    为程序中的每个指针变量建立一个由该指针变量所指向的变量构成的指向集,为所有指向集中出现的每个变量建立一个空集合;
    将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到所述映射f。
    在第三种可能的实现方式中,结合第一方面或第一方面的第一种 可能的实现方式或第一方面的第二种可能的实现方式,根据所述映射f建立从所述指针集合的幂集到第二变量集合的映射f′,以将所有变量分为不同的等价类包括:
    建立第i个空集合,将所述映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到所述第i个空集合中,得到第i个等价类,并对所述第i个等价类设置唯一的编号,并从所述映射f的定义域中删除添加到所述第i个空集合中的变量,直至映射f的定义域中的变量个数为0;其中,i的起始值为1,所述变量var表示映射f的定义域中的任意一个变量。
    在第四种可能的实现方式中,结合第一方面或第一方面的第一种可能的实现方式至第一方面的第三种可能的实现方式,所述根据系统依赖图中的各个节点所代表的变量所属的等价类为所述系统依赖图中的各个节点设置键值包括:
    将所述系统依赖图上的各个节点所代表的变量所属的等价类的编号对应设置为所述各个节点的键值。
    在第五种可能的实现方式中,结合第一方面或第一方面的第一种可能的实现方式至第一方面的第四种可能的实现方式,所述根据所述系统依赖图中的各个节点的键值对所述系统依赖图进行压缩包括:
    若所述系统依赖图上的任意一个节点的前驱节点集合或者后继节点集合中的任意两个节点拥有相同的键值,并且所述任意两个节点中有一个是副作用节点,则将所述任意两个节点中的副作用节点的出入边依次转化为所述任意两个节点中另外一个节点的出入边;
    删除所述系统依赖图中所有孤立的节点;
    合并所述系统依赖图上具有相同的源点和汇点的有向边。
    第二方面,提供一种系统依赖图无损压缩装置,包括:
    等价类获取???,用于根据别名分析信息获取程序中所有变量间的等价关系,并根据所述等价关系将所有变量分为不同的等价类,其中,所述别名分析信息是根据别名分析算法得到的;
    键值设置???,用于根据系统依赖图中的各个节点所代表的变量所属的等价类为所述系统依赖图中的各个节点设置键值;
    依赖图压缩???,用于根据所述系统依赖图中的各个节点的键值对所述系统依赖图进行压缩。
    在第一种可能的实现方式中,结合第二方面,所述等价类获取??榘ǎ?
    映射建立子???,用于根据所述别名分析信息建立从第一变量集合到指向所述变量集合中每个变量的指针集合的幂集的映射f,所述第一变量集合为程序中所有变量的集合;
    等价类获取子???,用于根据所述映射f建立从所述指针集合的幂集到第二变量集合的映射f′,所述第二变量集合为被同一组指针所指向的变量的集合。
    在第二种可能的实现方式中,结合第二方面或第二方面的第一种可能的实现方式,所述映射建立子??榫咛逵糜冢?
    为程序中的每个指针变量建立一个由该指针变量所指向的变量构成的指向集,为所有指向集中出现的每个变量建立一个空集合;
    将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到所述映射f。
    在第三种可能的实现方式中,结合第二方面或第二方面的第一种可能的实现方式或第二方面的第二种可能的实现方式,所述等价类获取子??榫咛逵糜冢?
    建立第i个空集合,将所述映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到所述第i个空集合中,得到第i个等价类,并对所述第i个等价类设置唯一的编号,并从所述映射f的定义域中删除添加到所述第i个空集合中的变量,直至映射f的定义域中的变量个数为0;其中,i的起始值为1,所述变量var表示映射f的定义域中的任意一个变量。
    在第四种可能的实现方式中,结合第二方面或第二方面的第一种可能的实现方式至第二方面的第三种可能的实现方式,所述键值设置??榫咛逵糜冢?
    将所述系统依赖图上的各个节点所代表的变量所属的等价类的编号对应设置为所述各个节点的键值。
    在第五种可能的实现方式中,结合第二方面或第二方面的第一种可能的实现方式至第二方面的第四种可能的实现方式,所述依赖图压缩??榘ǎ?
    出入边转化子???,用于若系统依赖图上的某个节点的前驱节点集合或者后继节点集合中的任意两个节点拥有相同的键值,并且所述任意两个节点中有一个是副作用节点,则将所述任意两个节点中的副作用节点的出入边依次转化为所述任意两个节点中另外一个节点的出入边;
    节点删除子???,用于删除系统依赖图中所有孤立的节点;
    合并子???,用于合并系统依赖图上具有相同的源点和汇点的有向边。
    本发明的实施例提供一种无损压缩系统依赖图的方法及装置,首先提取程序中变量间的等价关系,而后通过该等价关系将程序中变量分为不同的等价类,并根据这些等价类为系统依赖图中的节点设置键值,而后根据系统依赖图中的节点的键值压缩系统依赖图,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。
    附图说明
    为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍,显而易见地,下面描述中的附图仅仅是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。
    图1为本发明实施例提供的一种无损压缩系统依赖图的方法的流程示意图;
    图2为本发明另一实施例提供的一种无损压缩系统依赖图的方法的流程示意图;
    图3为本发明实施例提供的程序片段示意图;
    图4为本发明实施例提供的未经压缩的系统依赖图;
    图5为本发明实施例提供的系统依赖图压缩过程示意图一;
    图6为本发明实施例提供的系统依赖图压缩过程示意图二;
    图7为本发明实施例提供的经过压缩后的系统依赖图;
    图8为本发明实施例提供的一种系统依赖图无损压缩装置的结构示意图;
    图9为本发明实施例提供的另一种系统依赖图无损压缩装置的结构示意图;
    图10为本发明实施例提供的又一种系统依赖图无损压缩装置的结构示意图;
    图11为本发明另一实施例提供的一种系统依赖图无损压缩装置的结构示意图。
    具体实施方式
    下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅仅是本发明一部分实施例,而不是全部的实施例?;诒痉⒚髦械氖凳├?,本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例,都属于本发明?;さ姆段?。
    本发明实施例提供一种无损压缩系统依赖图的方法,如图1所示,该方法包括:
    S101、根据别名分析信息获取程序中所有变量间的等价关系,并根据等价关系将所有变量分为不同的等价类,其中,别名分析信息是根据别名分析算法得到的。
    S102、根据系统依赖图中的各个节点所代表的变量所属的等价类为系统依赖图中的各个节点设置键值。
    S103、根据系统依赖图中的各个节点的键值对系统依赖图进行压缩。
    其中,本发明中的系统依赖图节点之间可以定义为:
    系统依赖图上两个节点u和v等价(记做u~v),当且仅当,除u本身的后向切片外,以来途中任一包含u的切片也必然包含v,反 之亦然。
    故假设如果合并了节点u和v后,得到的系统依赖图上至少存在一个切片与合并前的系统依赖图上由相同切片标准得到的切片不同,则合并前的切片一定不同时包括u和v,而合并的前提是u和v等价,这样就出现了矛盾,故按照等价关系合并后得到的系统依赖图上的切片精度与合并前一致,这样也就实现了系统依赖图的无损压缩。
    本发明的实施例提供一种无损压缩系统依赖图的方法,首先提取程序中变量间的等价关系,而后通过该等价关系将程序中变量分为不同的等价类,并根据这些等价类为系统依赖图中的节点设置键值,而后根据系统依赖图中的节点的键值压缩系统依赖图,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。
    本发明另一实施例提供一种无损压缩系统依赖图的方法,如图2所示,该方法包括:
    S201、根据别名分析信息建立从第一变量集合到指向变量集合中每个变量的指针集合的幂集的映射f,第一变量集合为程序中所有变量的集合。其中,别名分析信息是,根据别名分析算法得到的。
    具体的,可以通过以下步骤实现:
    第一步,根据别名分析算法为程序中的每个指针变量(可以记为ptr)建立一个由该指针变量所指向的变量构成的指向集(可以记为ptr_to_set),为所有指向集中出现的每个变量建立一个空集合(可以记为Svar);
    第二步,将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到映射f。
    示例性的,得到映射f的过程可以通过以下伪码表示:


    S202、根据映射f建立从指针集合的幂集到第二变量集合的映射f′,以将所有变量分为不同的等价类,并为每个等价类生成唯一的编号。
    具体的,可以通过以下方法实现:
    建立第i个空集合,将映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到第i个空集合中,得到第i个等价类,并对第i个等价类设置唯一的编号,并从映射f的定义域中删除添加到第i个空集合中的变量,直至映射f的定义域中的变量个数为0;其中,i的起始值为1,变量var表示映射f的定义域中的任意一个变量。
    示例性的,得到映射f′的过程可以通过以下伪码表示:


    示例性的,映射f和映射f′的获得过程可以通过以下示例进一步说明:
    假设程序中的变量包括:A、B、C、D、E、F,指针变量包括:ptr1、ptr2、ptr3、ptr4;
    假设ptr1指向A、B、C;ptr2指向B、C、D;ptr3指向C、D、E、F;ptr4指向D、E、F;
    为变量A到F各自建立空集合SA、SB、SC、SD、SE、SF,并将所有包含各自的指针变量添加到各自的空集合中,则SA为{ptr1},SB为{ptr1、ptr2},SC为{ptr1、ptr2、ptr3},SD为{ptr2、ptr3、ptr4},SE为{ptr3、ptr4},SF为{ptr3、ptr4};即得到了映射f;
    新建一个空集合S1,在映射f的定义域中任意提取一个变量元素,假定提取变量A,加入S1中,并将所有能够被映射到f(A)的变量元素也添加到S1中,通过观察我们发现,能够被映射到f(A)的变量还有B和C,因此S1为{A、B、C},最后在f的定义域中删除A;
    再新建一个空集合S2,在映射f的定义域中任意提取一个变量元素,假定提取变量B,加入S2中,并将所有能够被映射到f(B)的变量元素也添加到S2中,通过观察我们发现,能够被映射到f(B)的变量还有C,因此S2为{B、C},最后在f的定义域中删除B;
    再新建一个空集合S3,在映射f的定义域中任意提取一个变量元 素,假定提取变量C,加入S3中,并将所有能够被映射到f(C)的变量元素也添加到S3中,通过观察我们发现,没有能够被映射到f(C)的变量,因此S3为{C},最后在f的定义域中删除C;
    再新建一个空集合S4,在映射f的定义域中任意提取一个变量元素,假定提取变量D,加入S4中,并将所有能够被映射到f(D)的变量元素也添加到S4中,通过观察我们发现,没有能够被映射到f(D)的变量,因此S4为{D},最后在f的定义域中删除D;
    再新建一个空集合S5,在映射f的定义域中任意提取一个变量元素,假定提取变量E,加入S5中,并将所有能够被映射到f(E)的变量元素也添加到S5中,通过观察我们发现,能够被映射到f(E)的变量还有F,因此S5为{E、F},最后在f的定义域中删除E;
    再新建一个空集合S6,在映射f的定义域中任意提取一个变量元素,假定提取变量F,加入S6中,并将所有能够被映射到f(F)的变量元素也添加到S6中,通过观察我们发现,没有能够被映射到f(F)的变量,因此S6为{F},最后在f的定义域中删除F;
    目前f的定义域中的元素个数为0,则映射f′计算完毕,集合S1到S6即为6个不同的等价类。
    S203、根据系统依赖图上的各个节点所代表的变量所属的等价类的编号对应设置为各个节点的键值。
    示例性的,如图3中所示的程序片段,图4所示为该程序片段未经压缩的系统依赖图,边框加粗的节点表示此节点为副作用节点,假设通过上述所有变量等价类的获取方法得知变量x和y为一个等价类,在图3所示的程序片段中,指针组{p、q、ptr}均可指向变量x和y,因此变量x和y为一个等价类;
    则在图4中,节点V2、V3、V5、V6为等价的节点,拥有相同的键值,如果等价类{x、y}的编号设置为i,则将节点V2、V3、V5、V6的键值也都设置为i。
    S204、根据系统依赖图上各个节点的键值,合并系统依赖图上等价的节点。
    具体的,可以通过以下步骤实现:
    第一步,对于系统依赖图上某个节点的前驱节点集合中的任意两个节点(记为u和v),如果其中之一(此处假定为v)是副作用节点,并且u和v拥有相同的键值,则将v的所有出入边依次转化为u的出入边;
    第二步,对于系统依赖图上某个节点的后续节点集合中的任意两个节点(记为m和n),如果其中之一(此处假定为n)是副作用节点,并且m和n拥有相同的键值,则将n的所有出入边依次转化为m的出入边;
    示例性的,如图4所示,节点V2和V3是节点V1的后继结点,并且V2和V3拥有相同的键值,其中V3是副作用节点,则将V3的入边e2和e7转化为V2的入边e2’和e7’,e2’和e7’如图5所示,将V3的出边e10转化为V2的出边e10’,e10’如图5所示;
    节点V5和V6是节点V4的后继结点,并且V5和V6拥有相同的键值,其中V5是副作用节点,则将V5的入边e4、e8和e10’转化为V6的入边e4’、e8’和e11,e4’、e8’和e11如图6所示。
    第三步,删除系统依赖图中所有的孤立节点;
    示例性的,如图6所示,将节点V3的出入边转化为V2的出入边,并且将V5的出入边转化为V6的出入边后,节点V3和V5成为了没有出入边的孤立节点,将V3和V5两个孤立节点从依赖图中删除。
    第四步,合并系统依赖图上具有相同源点和汇点的有向边。
    对于一条有向边,该有向边起始的节点为该有向边的源点,该有向边所指向的节点为该有向边的汇点;
    示例性的,如图6所示,有向边e1和e2’的源点都为V1,汇点者为V2,有向边e3和e4’的源点者为V4,汇点者为V6,有向边e9和e11的源点者为V2,汇点者为V6,将具有相同源点和汇点的有向边合并,则得到压缩后的系统依赖图,如图7所示。
    综上所述,由于找出了系统变量中等价的变量,并将等价的变量归类,而后根据系统依赖图中各节点所代表的变量所属的等价类,找出系统依赖图中等价的节点,并将等价节点合并,从而实现了系统依 赖图的无损压缩。
    本发明的实施例提供一种无损压缩系统依赖图的方法,首先提取程序中变量间的等价关系,而后通过该等价关系将程序中变量分为不同的等价类,并根据这些等价类为系统依赖图中的节点设置键值,而后根据系统依赖图中的节点的键值压缩系统依赖图,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。
    本发明的另一实施例提供一种系统依赖图无损压缩装置01,如图8所示,包括:
    等价类获取???11,用于根据别名分析信息获取程序中所有变量间的等价关系,并根据等价关系将所有变量分为不同的等价类,其中,别名分析信息是根据别名分析算法得到的,别名分析算法为分析结果表示为等价类或者指向集的别名分析算法;
    键值设置???12,用于从等价类获取???11获取所有变量间的等价关系,根据系统依赖图中的各个节点所代表的变量所属的等价类为系统依赖图中的各个节点设置键值;
    依赖图压缩???13,用于从键值设置???12中获得各个节点的键值,根据系统依赖图中的各个节点的键值对系统依赖图进行压缩。
    进一步的,如图9所示,等价类获取???11可以包括:
    映射建立子???111,用于根据别名分析信息建立从第一变量集合到指向变量集合中每个变量的指针集合的幂集的映射f,第一变量集合为程序中所有变量的集合,并将得到的映射f发送到等价类获取子???112;
    等价类获取子???112,用于从映射建立子???111中获取映射f,根据映射f建立从指针集合的幂集到第二变量集合的映射f′,第二变量集合为被同一组指针所指向的变量的集合。
    再进一步的,映射建立子???111可以具体用于:
    为程序中的每个指针变量建立一个由该指针变量所指向的变量构成的指向集,为所有指向集中出现的每个变量建立一个空集合;
    将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到映射f。
    等价类获取子???112可以具体用于:
    建立第i个空集合,将映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到第i个空集合中,得到第i个等价类,并对第i个等价类设置唯一的编号,并从映射f的定义域中删除添加到第i个空集合中的变量,直至映射f的定义域中的变量个数为0;其中,i的起始值为1,变量var表示映射f的定义域中的任意一个变量。
    更进一步的,如图10所示,依赖图压缩???13可以包括:
    出入边转化子???131,用于若系统依赖图上的某个节点的前驱节点集合或者后继节点集合中的任意两个节点拥有相同的键值,并且任意两个节点中有一个是副作用节点,则将任意两个节点中的副作用节点的出入边依次转化为任意两个节点中另外一个节点的出入边,将等价节点出入边转化完成后的系统依赖图送至节点删除子???132;
    节点删除子???132,用于从出入边转化子???131获取等价节点出入边转化完成后的系统依赖图,删除系统依赖图中所有孤立的节点,将删除了孤立节点后的系统依赖图送至合并子???133;
    合并子???133,用于从节点删除子???132获得删除了孤立节点后的系统依赖图,合并系统依赖图上具有相同的源点和汇点的有向边。
    本发明的实施例提供一种系统依赖图无损压缩装置,首先将所有变量划分为不同的等价类,而后根据系统依赖图上各个节点所代表的变量所属的等价类为系统依赖图上各个节点设置键值,最后将系统依赖图上拥有相同键值的节点进行合并,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。
    本发明又一实施例提供一种系统依赖图无损压缩装置02,包括接收机021、存储器022、发射机023、总线024,如图11所示,服务器02还包括:
    处理器025,用于根据别名分析信息获取程序中所有变量间的等价关系,并根据等价关系将所有变量分为不同的等价类,其中,别名分析信息是根据别名分析算法得到的,别名分析算法为分析结果表示为等价类或者指向集的别名分析算法;
    处理器025还用于根据系统依赖图中的各个节点所代表的变量所属的等价类为系统依赖图中的各个节点设置键值;
    处理器025还用于根据系统依赖图中的各个节点的键值对系统依赖图进行压缩。
    进一步的,在将所有变量分为不同的等价类时,处理器025还具体用于:
    根据别名分析信息建立从第一变量集合到指向变量集合中每个变量的指针集合的幂集的映射f,第一变量集合为程序中所有变量的集合;
    根据映射f建立从指针集合的幂集到第二变量集合的映射f′,第二变量集合为被同一组指针所指向的变量的集合。
    再进一步的,建立映射f时,处理器025具体用于:
    为程序中的每个指针变量建立一个由该指针变量所指向的变量构成的指向集,为所有指向集中出现的每个变量建立一个空集合;
    将每个指针变量添加到该指针变量所指向的变量对应的空集合中,以得到映射f。
    再进一步的,建立映射f′时,处理器025具体用于:
    建立第i个空集合,将映射f的定义域中一个变量var,以及所有被映射到f(var)的变量添加到第i个空集合中,得到第i个等价类,并对第i个等价类设置唯一的编号,并从映射f的定义域中删除添加到第i个空集合中的变量,直至映射f的定义域中的变量个数为0;其中,i的起始值为1,变量var表示映射f的定义域中的任意一个变量。
    再进一步的,为节点设置键值时,处理器025还可以具体用于:
    将系统依赖图上的各个节点所代表的变量所属的等价类的编号对应设置为各个节点的键值。
    更进一步的,在压缩系统依赖图时,处理器025可以具体用于:
    若系统依赖图上的某个节点的前驱节点集合或者后继节点集合中的任意两个节点拥有相同的键值,并且任意两个节点中有一个是副作用节点,则将任意两个节点中的副作用节点的出入边依次转化为任意两个节点中另外一个节点的出入边;
    删除系统依赖图中所有孤立的节点;
    合并系统依赖图上具有相同的源点和汇点的有向边。
    本发明的实施例提供一种系统依赖图无损压缩装置,首先将所有变量划分为不同的等价类,而后根据系统依赖图上各个节点所代表的变量所属的等价类为系统依赖图上各个节点设置键值,最后将系统依赖图上拥有相同键值的节点进行合并,能够实现系统依赖图的无损压缩,并降低系统依赖图的规模,从而降低以系统依赖图为基础的切片算法的开销。
    在本申请所提供的几个实施例中,应该理解到,所揭露的方法和装置,可以通过其它的方式实现。例如,以上所描述的装置实施例仅仅是示意性的,例如,所述单元的划分,仅仅为一种逻辑功能划分,实际实现时可以有另外的划分方式,例如多个单元或组件可以结合或者可以集成到另一个系统,或一些特征可以忽略,或不执行。另一点,所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口,装置或单元的间接耦合或通信连接,可以是电性,机械或其它的形式。
    所述作为分离部件说明的单元可以是或者也可以不是物理上分开的,作为单元显示的部件可以是或者也可以不是物理单元,即可以位于一个地方,或者也可以分布到多个网络单元上??梢愿菔导实男枰≡衿渲械牟糠只蛘呷康ピ词迪直臼凳├桨傅哪康?。
    另外,在本发明各个实施例中的各功能单元可以集成在一个处理单元中,也可以是各个单元单独物理包括,也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现,也可以采用硬件加软件功能单元的形式实现。
    上述以软件功能单元的形式实现的集成的单元,可以存储在一个计算机可读取存储介质中。上述软件功能单元存储在一个存储介质中,包括若 干指令用以使得一台计算机设备(可以是个人计算机,服务器,或者网络设备等)执行本发明各个实施例所述方法的部分步骤。而前述的存储介质包括:U盘、移动硬盘、只读存储器(Read-Only Memory,简称ROM)、随机存取存储器(Random Access Memory,简称RAM)、磁碟或者光盘等各种可以存储程序代码的介质。
    以上所述,仅为本发明的具体实施方式,但本发明的?;し段Р⒉痪窒抻诖?,任何熟悉本技术领域的技术人员在本发明揭露的技术范围内,可轻易想到变化或替换,都应涵盖在本发明的?;し段е?。因此,本发明的?;し段вσ运鋈ɡ蟮谋;し段??!  ∧谌堇醋宰ɡ鴚ww.www.4mum.com.cn转载请标明出处

    关于本文
    本文标题:一种无损压缩系统依赖图的方法及装置.pdf
    链接地址://www.4mum.com.cn/p-6120493.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 浪潮孙丕恕从信息时代到智能时代 人工智能价值将爆发式释放 2019-12-21
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 535棋牌娱乐平台 福建11选5今日开奖 新疆时时彩走势图 酷狗彩票网址 黑龙江快乐10分开奖记录 复式投注 7m篮球比分即时比分 pk10牛牛 电子游艺娱乐平台 极速快乐十分 00年香港赛马会第01期 大乐透 重庆快乐10分 吉林11选5大小 足彩进球彩软件 快乐十分任四中三个号