[ { "@graph" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU", "@type" : [ "http://www.nanopub.org/nschema#Nanopublication" ], "http://www.nanopub.org/nschema#hasAssertion" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/assertion" } ], "http://www.nanopub.org/nschema#hasProvenance" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/provenance" } ], "http://www.nanopub.org/nschema#hasPublicationInfo" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/pubinfo" } ] } ], "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/Head" }, { "@graph" : [ { "@id" : "http://eurovoc.europa.eu/1835", "@type" : [ "http://schema.org/DefinedTerm" ], "http://schema.org/description" : [ { "@value" : "" } ], "http://schema.org/name" : [ { "@value" : "Mathematics" } ] }, { "@id" : "http://eurovoc.europa.eu/3925", "@type" : [ "http://schema.org/DefinedTerm" ], "http://schema.org/description" : [ { "@value" : "" } ], "http://schema.org/name" : [ { "@value" : "Information science" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/", "@type" : [ "http://purl.org/wf4ever/ro#ResearchObject", "http://purl.org/wf4ever/roevo#LiveRO", "http://schema.org/Dataset", "http://w3id.org/ro/earth-science#DataResearchObject", "https://w3id.org/ro/terms/earth-science#DataResearchObject" ], "http://schema.org/about" : [ { "@id" : "http://eurovoc.europa.eu/1835" }, { "@id" : "http://eurovoc.europa.eu/3925" } ], "http://schema.org/author" : [ { "@id" : "mailto:nico.reissmann@rohub.com" } ], "http://schema.org/contentSize" : [ { "@type" : "http://www.w3.org/2001/XMLSchema#integer", "@value" : "10521" } ], "http://schema.org/contentUrl" : [ { "@value" : "https://api.rohub.org/api/ros/1629b99a-a623-4b21-be4f-427330e04c36/crate/download/" } ], "http://schema.org/creator" : [ { "@id" : "mailto:georgehadib@gmail.com" } ], "http://schema.org/dateCreated" : [ { "@value" : "2022-03-22 00:54:16.326344+00:00" } ], "http://schema.org/dateModified" : [ { "@value" : "2025-03-05 01:14:06.760794+00:00" } ], "http://schema.org/datePublished" : [ { "@value" : "2022-03-22 00:54:16.326344+00:00" } ], "http://schema.org/description" : [ { "@value" : "Demand-based dependence graphs (DDGs), such as the (Regionalized) Value State Dependence Graph ((R)VSDG), are intermediate representations (IRs) well suited for a wide range of program transformations. They explicitly model the flow of data and state, and only implicitly represent a restricted form of control flow. These features make DDGs especially suitable for automatic parallelization and vectorization, but cannot be leveraged by practical compilers without efficient construction and destruction algorithms. Construction algorithms remodel the arbitrarily complex control flow of a procedure to make it amenable to DDG representation, whereas destruction algorithms reestablish control flow for generating efficient object code. Existing literature presents solutions to both problems, but these impose structural constraints on the generatable control flow, and omit qualitative evaluation.\n\nThe key contribution of this article is to show that there is no intrinsic structural limitation in the control flow directly extractable from RVSDGs. This fundamental result originates from an interpretation of loop repetition and decision predicates as computed continuations, leading to the introduction of the predicate continuation normal form. We provide an algorithm for constructing RVSDGs in predicate continuation form, and propose a novel destruction algorithm for RVSDGs in this form. Our destruction algorithm can generate arbitrarily complex control flow; we show this by proving that the original CFG an RVSDG was derived from can, apart from overspecific detail, be reconstructed perfectly. Additionally, we prove termination and correctness of these algorithms. Furthermore, we empirically evaluate the performance, the representational overhead at compile time, and the reduction in branch instructions compared to existing solutions. In contrast to previous work, our algorithms impose no additional overhead on the control flow of the produced object code. To our knowledge, this is the first scheme that allows the original control flow of a procedure to be recovered from a DDG representation.\n\nThis dataset contains the python implementation the experiments in the paper were conducted with as well as the extracted CFGs from the SPEC2006 benchmarks. It also contains the scripts for creating the plots of the paper." } ], "http://schema.org/encodingFormat" : [ { "@value" : "application/ld+json" } ], "http://schema.org/hasPart" : [ { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/2c6cb478-a2ed-4d78-a876-ca5597a4eeb7" }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/58632ef7-2917-48ed-a143-4c73bc3d1e49" }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/69ea857f-a29d-4b64-8e34-ebb019e7aad2" }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/c16de708-c318-4617-ae9c-1a59a3a19e9f" } ], "http://schema.org/identifier" : [ { "@value" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36" } ], "http://schema.org/license" : [ { "@id" : "https://choosealicense.com/no-permission/" } ], "http://schema.org/name" : [ { "@value" : "Perfect Reconstructability of Control Flow from Demand Dependence Graphs" } ], "http://w3id.org/ro-id/rohub/model#creation_mode" : [ { "@value" : "MANUAL" } ], "http://w3id.org/ro/earth-science#Concept" : [ { "@value" : "Python" }, { "@value" : "algorithm" }, { "@value" : "control condition" }, { "@value" : "dataset" }, { "@value" : "destruction" }, { "@value" : "graph" }, { "@value" : "object code" }, { "@value" : "sequel" }, { "@value" : "subroutine" }, { "@value" : "verb phrase" } ], "http://w3id.org/ro/earth-science#FieldOfResearch" : [ { "@value" : "earth sciences" } ], "http://w3id.org/ro/earth-science#IPTC" : [ { "@value" : "Literature" }, { "@value" : "Politics" } ], "http://w3id.org/ro/earth-science#Lemma" : [ { "@value" : "Dependence" }, { "@value" : "RVSDGs" }, { "@value" : "algorithm" }, { "@value" : "control" }, { "@value" : "destruction" }, { "@value" : "object code" }, { "@value" : "predicate" } ], "http://w3id.org/ro/earth-science#NASA" : [ { "@value" : "engineering" } ], "http://w3id.org/ro/earth-science#Phrase" : [ { "@value" : "construction algorithm" }, { "@value" : "control flow" }, { "@value" : "destruction algorithm" }, { "@value" : "intermediate representations" }, { "@value" : "value State Dependence graph" } ], "http://w3id.org/ro/earth-science#Sentence" : [ { "@value" : "Construction algorithms remodel the arbitrarily complex control flow of a procedure to make it amenable to DDG representation, whereas destruction algorithms reestablish control flow for generating efficient object code." }, { "@value" : "Demand-based dependence graphs (DDGs) such as the (Regionalized) Value State Dependence Graph (R)VSDG) are intermediate representations (IRs) well suited for a wide range of program transformations." }, { "@value" : "We provide an algorithm for constructing RVSDGs in predicate continuation form, and propose a novel destruction algorithm for RVSDGs in this form." } ], "https://w3id.org/contentdesc#Domain" : [ { "@value" : "computer programming" }, { "@value" : "computer science" }, { "@value" : "mathematics" }, { "@value" : "scientific terms" } ], "https://www.w3.org/ns/iana/link-relations/relation#cite-as" : [ { "@value" : "Nico Reissmann. \"Perfect Reconstructability of Control Flow from Demand Dependence Graphs.\" ROHub. Mar 22 ,2022. https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36." } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/#enrichment_service-account-enrichment", "@type" : [ "http://xmlns.com/foaf/0.1/Agent" ], "http://schema.org/name" : [ { "@value" : "service-account-enrichment" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/2c6cb478-a2ed-4d78-a876-ca5597a4eeb7", "@type" : [ "http://purl.org/wf4ever/wf4ever#Folder", "http://schema.org/Dataset" ], "http://schema.org/name" : [ { "@value" : "metadata" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/58632ef7-2917-48ed-a143-4c73bc3d1e49", "@type" : [ "http://purl.org/wf4ever/wf4ever#Folder", "http://schema.org/Dataset" ], "http://schema.org/name" : [ { "@value" : "raw data" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/69ea857f-a29d-4b64-8e34-ebb019e7aad2", "@type" : [ "http://purl.org/wf4ever/wf4ever#Folder", "http://schema.org/Dataset" ], "http://schema.org/hasPart" : [ { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/resources/ae04627c-6abe-4bd2-bfff-9723fda5c0ef" } ], "http://schema.org/name" : [ { "@value" : "biblio" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/folders/c16de708-c318-4617-ae9c-1a59a3a19e9f", "@type" : [ "http://purl.org/wf4ever/wf4ever#Folder", "http://schema.org/Dataset" ], "http://schema.org/hasPart" : [ { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/resources/e66bae04-855e-43f6-b3e4-d948ce5900ba" } ], "http://schema.org/name" : [ { "@value" : "data" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/resources/ae04627c-6abe-4bd2-bfff-9723fda5c0ef", "@type" : [ "http://purl.org/dc/terms/BibliographicResource", "http://purl.org/wf4ever/wf4ever#Resource", "http://schema.org/MediaObject" ], "http://schema.org/author" : [ { "@id" : "mailto:georgehadib@gmail.com" } ], "http://schema.org/contentUrl" : [ { "@value" : "https://doi.org/10.1145/2693261" } ], "http://schema.org/creator" : [ { "@id" : "mailto:georgehadib@gmail.com" } ], "http://schema.org/dateCreated" : [ { "@value" : "2022-03-22 00:54:25.569088+00:00" } ], "http://schema.org/dateModified" : [ { "@value" : "2022-03-22 00:54:25.692521+00:00" } ], "http://schema.org/license" : [ { "@id" : "https://choosealicense.com/no-permission/" } ], "http://schema.org/name" : [ { "@value" : "https://doi.org/10.1145/2693261" } ], "http://schema.org/sdDatePublished" : [ { "@value" : "2022-03-22 00:54:25.569088+00:00" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/resources/e66bae04-855e-43f6-b3e4-d948ce5900ba", "@type" : [ "http://purl.org/wf4ever/wf4ever#Dataset", "http://purl.org/wf4ever/wf4ever#Resource", "http://schema.org/MediaObject" ], "http://purl.org/dc/terms/bibliographicCitation" : [ { "@value" : "Reissmann, N. (2015).Perfect Reconstructability of Control Flow from Demand Dependence Graphs [Data set]. Norstore. https://doi.org/10.11582/2015.00010" } ], "http://purl.org/dc/terms/rightsHolder" : [ { "@value" : "Nico Reissmann" } ], "http://purl.org/dc/terms/type" : [ { "@value" : "Experiment" } ], "http://schema.org/author" : [ { "@id" : "mailto:georgehadib@gmail.com" } ], "http://schema.org/contentUrl" : [ { "@value" : "https://archive.sigma2.no/pages/public/datasetDetail.jsf?id=10.11582/2015.00010" } ], "http://schema.org/creator" : [ { "@id" : "mailto:georgehadib@gmail.com" } ], "http://schema.org/dateCreated" : [ { "@value" : "2015-03-24 00:00:00" } ], "http://schema.org/dateModified" : [ { "@value" : "2022-03-22 00:54:27.848176+00:00" } ], "http://schema.org/description" : [ { "@value" : "Demand-based dependence graphs (DDGs), such as the (Regionalized) Value State Dependence Graph ((R)VSDG), are intermediate representations (IRs) well suited for a wide range of program transformations. They explicitly model the flow of data and state, and only implicitly represent a restricted form of control flow. These features make DDGs especially suitable for automatic parallelization and vectorization, but cannot be leveraged by practical compilers without efficient construction and destruction algorithms. Construction algorithms remodel the arbitrarily complex control flow of a procedure to make it amenable to DDG representation, whereas destruction algorithms reestablish control flow for generating efficient object code. Existing literature presents solutions to both problems, but these impose structural constraints on the generatable control flow, and omit qualitative evaluation.\n\nThe key contribution of this article is to show that there is no intrinsic structural limitation in the control flow directly extractable from RVSDGs. This fundamental result originates from an interpretation of loop repetition and decision predicates as computed continuations, leading to the introduction of the predicate continuation normal form. We provide an algorithm for constructing RVSDGs in predicate continuation form, and propose a novel destruction algorithm for RVSDGs in this form. Our destruction algorithm can generate arbitrarily complex control flow; we show this by proving that the original CFG an RVSDG was derived from can, apart from overspecific detail, be reconstructed perfectly. Additionally, we prove termination and correctness of these algorithms. Furthermore, we empirically evaluate the performance, the representational overhead at compile time, and the reduction in branch instructions compared to existing solutions. In contrast to previous work, our algorithms impose no additional overhead on the control flow of the produced object code. To our knowledge, this is the first scheme that allows the original control flow of a procedure to be recovered from a DDG representation.\n\nThis dataset contains the python implementation the experiments in the paper were conducted with as well as the extracted CFGs from the SPEC2006 benchmarks. It also contains the scripts for creating the plots of the paper." } ], "http://schema.org/license" : [ { "@id" : "https://choosealicense.com/no-permission/" } ], "http://schema.org/name" : [ { "@value" : "Perfect Reconstructability of Control Flow from Demand Dependence Graphs" } ], "http://schema.org/sdDatePublished" : [ { "@value" : "2015-03-24 00:00:00" } ], "https://schema.org/maintainer" : [ { "@value" : "Nico Reissmann" } ] }, { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/ro-crate-metadata.json", "@type" : [ "http://schema.org/CreativeWork" ], "http://purl.org/dc/terms/conformsTo" : [ { "@id" : "https://w3id.org/ro/crate/1.1" } ], "http://schema.org/about" : [ { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/" } ] }, { "@id" : "mailto:georgehadib@gmail.com", "@type" : [ "http://xmlns.com/foaf/0.1/Agent" ], "http://schema.org/name" : [ { "@value" : "Geo H." } ] }, { "@id" : "mailto:nico.reissmann@rohub.com", "@type" : [ "http://xmlns.com/foaf/0.1/Agent" ], "http://schema.org/email" : [ { "@value" : "nico.reissmann@rohub.com" } ], "http://schema.org/name" : [ { "@value" : "Nico Reissmann" } ] } ], "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/assertion" }, { "@graph" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/assertion", "http://www.w3.org/ns/prov#wasDerivedFrom" : [ { "@id" : "https://api.rohub.org/api/ros/1629b99a-a623-4b21-be4f-427330e04c36/crate/download/ro-crate-metadata.json" } ] } ], "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/provenance" }, { "@graph" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU", "@type" : [ "http://purl.org/nanopub/x/RoCrateNanopub" ], "http://purl.org/dc/terms/created" : [ { "@type" : "http://www.w3.org/2001/XMLSchema#dateTime", "@value" : "2026-03-03T16:17:41.767+01:00" } ], "http://purl.org/dc/terms/creator" : [ { "@id" : "https://w3id.org/kpxl/gen/terms/RoCrateBot" } ], "http://purl.org/nanopub/x/introduces" : [ { "@id" : "https://w3id.org/ro-id/1629b99a-a623-4b21-be4f-427330e04c36/" } ], "http://www.w3.org/2000/01/rdf-schema#label" : [ { "@value" : "Perfect Reconstructability of Control Flow from Demand Dependence Graphs" } ] }, { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/sig", "http://purl.org/nanopub/x/hasAlgorithm" : [ { "@value" : "RSA" } ], "http://purl.org/nanopub/x/hasPublicKey" : [ { "@value" : "MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAxszSDYX5tuCSkP7UiCtftYPFNQVTjgNu0I5fwdML2DLRDlp0xzmsQXRk8oHuvwGvG1aMjj6cpUqO+0rz2Sg/wvHOgUpkRH8VJXvmlkhafMLCMtUtk5JIx7e+fkzCby+fnmD7kMkGLrT+OaExWwEDmNlCAt0TPKcHSdwsjso2isXjtAsGevyCMke8ufnFYpjs746JES1eNzVnHnn2Kp/lqcm60GM+J8dLgRZp7fX0anW098xhKym6+xXFzqeju0vYRIHBPerv+r7skWxwk+a7Sd8msqVeYEv6NTqnyWvyWb6Yh8cvj04N6qm/T6C5FUPLQhzSaQgMVMU6yLqjPuu9DwIDAQAB" } ], "http://purl.org/nanopub/x/hasSignature" : [ { "@value" : "a4QGsggLy5gC4RBHzRy6QtZvG5tDxgSlCZKztS7k0gjcbD/acbzv9gx8kp+IJjYeAv2e8eYyyWa9NuZBVyGZXsqBDV1NK8ldx0w6BLjEvABH6W+S/omtZJ7uju6quvreJycWiSk6kFZSiJHu+hL4lRm/kCHmnUZa236gjVs4OkBZQcQj9LCUaX5t/1H/3ykHzhrq/9691dZTDJH6wkXUan9MsC1+Aa1jy6KqBLRmrJj55023GJgMcJKfprVnUJryaEas5py25IObgPTlQ9OtMsDfftJqk6JYIQtaPdccsqp78fy6CoRhKsa8RAU3Ohfslju6AffDD3iycRTfeUfryA==" } ], "http://purl.org/nanopub/x/hasSignatureTarget" : [ { "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU" } ], "http://purl.org/nanopub/x/signedBy" : [ { "@id" : "https://w3id.org/kpxl/gen/terms/RoCrateBot" } ] } ], "@id" : "https://w3id.org/np/RAX1rcQJRZC4cvwe8pQWtoMzTOCmt86PxTZD47O6sxdFU/pubinfo" } ]