{"action":"opened","number":549,"pull_request":{"url":"https://api.github.com/repos/acl2/acl2/pulls/549","id":52205356,"html_url":"https://github.com/acl2/acl2/pull/549","diff_url":"https://github.com/acl2/acl2/pull/549.diff","patch_url":"https://github.com/acl2/acl2/pull/549.patch","issue_url":"https://api.github.com/repos/acl2/acl2/issues/549","number":549,"state":"open","locked":false,"title":"New FP instructions and libraries for reasoning about equivalence of x86 states","user":{"login":"shigoel","id":5995854,"avatar_url":"https://avatars.githubusercontent.com/u/5995854?v=3","gravatar_id":"","url":"https://api.github.com/users/shigoel","html_url":"https://github.com/shigoel","followers_url":"https://api.github.com/users/shigoel/followers","following_url":"https://api.github.com/users/shigoel/following{/other_user}","gists_url":"https://api.github.com/users/shigoel/gists{/gist_id}","starred_url":"https://api.github.com/users/shigoel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shigoel/subscriptions","organizations_url":"https://api.github.com/users/shigoel/orgs","repos_url":"https://api.github.com/users/shigoel/repos","events_url":"https://api.github.com/users/shigoel/events{/privacy}","received_events_url":"https://api.github.com/users/shigoel/received_events","type":"User","site_admin":false},"body":"This bunch of commits adds some new FP instructions and libraries to\r\nreason about paging data structures. A description of the changes is\r\nas follows.\r\n\r\n----------------------------------------------------------------------\r\nRe-organized the code proof libraries\r\n\r\nSeparated out proof libraries in proofs/utilities into two directories\r\n--- programmer-level-mode and system-level-mode.\r\n\r\n----------------------------------------------------------------------\r\nNew proof libraries to reason about paging data structures\r\n\r\nAn equivalence relation between two x86 states, called\r\nxlate-equiv-x86s, has been defined. This has been used to prove, using\r\ncongruence-based reasoning, that a walk of the paging data structures\r\ndoes not affect any future walks. See books in \r\nproofs/utilities/system-level-mode/paging-lib for details.\r\n\r\nAlternate definitions of paging data structure traversal functions\r\n(originally defined in machine/x86-ia32e-paging.lisp) have been\r\ndefined in x86-ia32e-paging-alt.lisp. These new functions do a paging\r\nstructure walk only if the structure is set up in a reasonable manner.\r\n\r\nBooks gather-paging-structures.lisp and\r\ngather-paging-structures-thms.lisp define the equivalence relation\r\nxlate-equiv-x86s and functions to gather all the paging data\r\nstructures.\r\n\r\nBooks paging-page-table-lemmas.lisp,\r\npaging-page-directory-lemmas.lisp,\r\npaging-page-dir-ptr-table-lemmas.lisp, and\r\npaging-pml4-table-lemmas.lisp include the theorems about independence\r\nof a paging structure walk from a past walk.\r\n\r\n----------------------------------------------------------------------\r\nModified the top-level definitions of memory accessor and updater\r\nfunctions\r\n\r\nAffected functions are rm16, wm16, rm32, wm32, rm64, wm64, rm128,\r\nwm128, write-canonical-address-to-memory.\r\n\r\nThe programmer-level mode behavior of these functions is the same as\r\nit was before, but these functions have changed in the system-level\r\nmode. We describe this change using the function rm16 as an example.\r\n\r\nPreviously, for (rm16 lin-addr r-w-x x86), we would figure out if both\r\nlin-addr and (1+ lin-addr) fall in the same physical page. If so, we\r\nwould walk the page tables to translate the lin-addr to its\r\ncorresponding physical address phy-addr, and the physical address\r\ncorresponding to (1+ lin-addr) would simply be (1+ phy-addr).  This\r\nhelped avoid a page table walk for the translation of (1+ lin-addr)\r\nand thus, increased the execution efficiency in the common case.\r\n\r\nNow, we explicitly perform the translation for both lin-addr and (1+\r\nlin-addr). This has definitely slowed down our simulation speed (but\r\nonly in the system-level mode). However, our optimizations were not\r\nstrictly correct. Because the second page walk was optimized away, our\r\nfunctions essentially said that the second page walk never modifies\r\nthe x86 state, when this is not the case because a page walk may\r\nmodify the accessed and/or dirty bits in the translation-governing\r\nentries of the paging data structures.\r\n\r\nWith this change, we lose on the execution efficiency in the\r\nsystem-level mode, but gain accuracy.\r\n\r\nSimulation speed in the System-Level Mode with identity page tables\r\n(1GB pages):\r\n\r\n  Old Model: Around 900K instructions/second\r\n  New Model: Around 795K instructions/second\r\n\r\nWe can imagine \"correctly\" optimizing away the page walks by\r\nperforming the accessed/dirty bit updates without actually walking the\r\npaging data structures, but that optimization will complicate\r\nreasoning and thus, we haven't implemented it for now.\r\n\r\n----------------------------------------------------------------------\r\nDecreased the initial memory footprint of the model\r\n\r\nI changed the constant *initial-mem-array-pages* in\r\nportcullis/sharp-dot-constants.lisp from 10 to 2.  Therefore, the\r\ninitial memory requirement for mem-array went down from 1.2 GB to 256\r\nMB. If more initial memory is needed, simply change the value of\r\n*initial-mem-array-pages* --- all the proofs should proceed smoothly.\r\n\r\nAlso sped up machine/x86-concrete-memory.lisp by reducing the number\r\nof local include-books.\r\n\r\n----------------------------------------------------------------------\r\nPorted over FP instructions added by @myall86  --- thanks a lot,\r\nCuong, for specifying so many instructions!\r\n\r\n@nadezhin and @myall86  independently contributed the\r\nspecifications of MOVSS/SD and CMPSS/SD instructions. This set of\r\ncommits incorporates both their contributions.\r\n\r\nThe only significant change that I made here was for the BSF\r\ninstruction (opcode 0F BC) --- I specified the undefined behavior for\r\nthe destination and flags, as appropriate.\r\n\r\nI extended utils/decoding-utilities.lisp and machine/x86.lisp to\r\nsupport decoding of instructions requiring mandatory prefixes in the\r\ntwo-byte opcode map.\r\n\r\nNOTE: @myall86 and I will probably make at least a couple of bug fixes\r\n(mostly in the FP flag computations but maybe in other places too) in\r\nthe next few days.\r\n\r\n----------------------------------------------------------------------\r\n@nadezhin pointed out typos in the :reg field of immediate OR\r\n(opcode 80) in the implemented-opcodes-table --- thanks, Dmitry! This\r\nset of commits fixes those typos.\r\n\r\n----------------------------------------------------------------------","created_at":"2015-12-01T01:37:52Z","updated_at":"2015-12-01T01:37:53Z","closed_at":null,"merged_at":null,"merge_commit_sha":"fe256d5aa1458e7beb4984bae754fa50ad673b89","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/acl2/acl2/pulls/549/commits","review_comments_url":"https://api.github.com/repos/acl2/acl2/pulls/549/comments","review_comment_url":"https://api.github.com/repos/acl2/acl2/pulls/comments{/number}","comments_url":"https://api.github.com/repos/acl2/acl2/issues/549/comments","statuses_url":"https://api.github.com/repos/acl2/acl2/statuses/cb31e773a490fb08811bacfea8bae3cd550ec8c8","head":{"label":"shigoel:pagingUtils","ref":"pagingUtils","sha":"cb31e773a490fb08811bacfea8bae3cd550ec8c8","user":{"login":"shigoel","id":5995854,"avatar_url":"https://avatars.githubusercontent.com/u/5995854?v=3","gravatar_id":"","url":"https://api.github.com/users/shigoel","html_url":"https://github.com/shigoel","followers_url":"https://api.github.com/users/shigoel/followers","following_url":"https://api.github.com/users/shigoel/following{/other_user}","gists_url":"https://api.github.com/users/shigoel/gists{/gist_id}","starred_url":"https://api.github.com/users/shigoel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shigoel/subscriptions","organizations_url":"https://api.github.com/users/shigoel/orgs","repos_url":"https://api.github.com/users/shigoel/repos","events_url":"https://api.github.com/users/shigoel/events{/privacy}","received_events_url":"https://api.github.com/users/shigoel/received_events","type":"User","site_admin":false},"repo":{"id":39860239,"name":"acl2","full_name":"shigoel/acl2","owner":{"login":"shigoel","id":5995854,"avatar_url":"https://avatars.githubusercontent.com/u/5995854?v=3","gravatar_id":"","url":"https://api.github.com/users/shigoel","html_url":"https://github.com/shigoel","followers_url":"https://api.github.com/users/shigoel/followers","following_url":"https://api.github.com/users/shigoel/following{/other_user}","gists_url":"https://api.github.com/users/shigoel/gists{/gist_id}","starred_url":"https://api.github.com/users/shigoel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shigoel/subscriptions","organizations_url":"https://api.github.com/users/shigoel/orgs","repos_url":"https://api.github.com/users/shigoel/repos","events_url":"https://api.github.com/users/shigoel/events{/privacy}","received_events_url":"https://api.github.com/users/shigoel/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/shigoel/acl2","description":"Shilpi's Fork of ACL2 System and Books","fork":true,"url":"https://api.github.com/repos/shigoel/acl2","forks_url":"https://api.github.com/repos/shigoel/acl2/forks","keys_url":"https://api.github.com/repos/shigoel/acl2/keys{/key_id}","collaborators_url":"https://api.github.com/repos/shigoel/acl2/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/shigoel/acl2/teams","hooks_url":"https://api.github.com/repos/shigoel/acl2/hooks","issue_events_url":"https://api.github.com/repos/shigoel/acl2/issues/events{/number}","events_url":"https://api.github.com/repos/shigoel/acl2/events","assignees_url":"https://api.github.com/repos/shigoel/acl2/assignees{/user}","branches_url":"https://api.github.com/repos/shigoel/acl2/branches{/branch}","tags_url":"https://api.github.com/repos/shigoel/acl2/tags","blobs_url":"https://api.github.com/repos/shigoel/acl2/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/shigoel/acl2/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/shigoel/acl2/git/refs{/sha}","trees_url":"https://api.github.com/repos/shigoel/acl2/git/trees{/sha}","statuses_url":"https://api.github.com/repos/shigoel/acl2/statuses/{sha}","languages_url":"https://api.github.com/repos/shigoel/acl2/languages","stargazers_url":"https://api.github.com/repos/shigoel/acl2/stargazers","contributors_url":"https://api.github.com/repos/shigoel/acl2/contributors","subscribers_url":"https://api.github.com/repos/shigoel/acl2/subscribers","subscription_url":"https://api.github.com/repos/shigoel/acl2/subscription","commits_url":"https://api.github.com/repos/shigoel/acl2/commits{/sha}","git_commits_url":"https://api.github.com/repos/shigoel/acl2/git/commits{/sha}","comments_url":"https://api.github.com/repos/shigoel/acl2/comments{/number}","issue_comment_url":"https://api.github.com/repos/shigoel/acl2/issues/comments{/number}","contents_url":"https://api.github.com/repos/shigoel/acl2/contents/{+path}","compare_url":"https://api.github.com/repos/shigoel/acl2/compare/{base}...{head}","merges_url":"https://api.github.com/repos/shigoel/acl2/merges","archive_url":"https://api.github.com/repos/shigoel/acl2/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/shigoel/acl2/downloads","issues_url":"https://api.github.com/repos/shigoel/acl2/issues{/number}","pulls_url":"https://api.github.com/repos/shigoel/acl2/pulls{/number}","milestones_url":"https://api.github.com/repos/shigoel/acl2/milestones{/number}","notifications_url":"https://api.github.com/repos/shigoel/acl2/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/shigoel/acl2/labels{/name}","releases_url":"https://api.github.com/repos/shigoel/acl2/releases{/id}","created_at":"2015-07-28T22:11:10Z","updated_at":"2015-08-30T16:45:17Z","pushed_at":"2015-12-01T00:55:49Z","git_url":"git://github.com/shigoel/acl2.git","ssh_url":"git@github.com:shigoel/acl2.git","clone_url":"https://github.com/shigoel/acl2.git","svn_url":"https://github.com/shigoel/acl2","homepage":"http://www.cs.utexas.edu/users/moore/acl2","size":157527,"stargazers_count":1,"watchers_count":1,"language":"Common Lisp","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"acl2:testing","ref":"testing","sha":"0820d70d7d4f93ab1b9a7fc8074ee5d90cc6358f","user":{"login":"acl2","id":5464462,"avatar_url":"https://avatars.githubusercontent.com/u/5464462?v=3","gravatar_id":"","url":"https://api.github.com/users/acl2","html_url":"https://github.com/acl2","followers_url":"https://api.github.com/users/acl2/followers","following_url":"https://api.github.com/users/acl2/following{/other_user}","gists_url":"https://api.github.com/users/acl2/gists{/gist_id}","starred_url":"https://api.github.com/users/acl2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/acl2/subscriptions","organizations_url":"https://api.github.com/users/acl2/orgs","repos_url":"https://api.github.com/users/acl2/repos","events_url":"https://api.github.com/users/acl2/events{/privacy}","received_events_url":"https://api.github.com/users/acl2/received_events","type":"Organization","site_admin":false},"repo":{"id":23556724,"name":"acl2","full_name":"acl2/acl2","owner":{"login":"acl2","id":5464462,"avatar_url":"https://avatars.githubusercontent.com/u/5464462?v=3","gravatar_id":"","url":"https://api.github.com/users/acl2","html_url":"https://github.com/acl2","followers_url":"https://api.github.com/users/acl2/followers","following_url":"https://api.github.com/users/acl2/following{/other_user}","gists_url":"https://api.github.com/users/acl2/gists{/gist_id}","starred_url":"https://api.github.com/users/acl2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/acl2/subscriptions","organizations_url":"https://api.github.com/users/acl2/orgs","repos_url":"https://api.github.com/users/acl2/repos","events_url":"https://api.github.com/users/acl2/events{/privacy}","received_events_url":"https://api.github.com/users/acl2/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/acl2/acl2","description":"ACL2 System and Books as Maintained by the Community","fork":false,"url":"https://api.github.com/repos/acl2/acl2","forks_url":"https://api.github.com/repos/acl2/acl2/forks","keys_url":"https://api.github.com/repos/acl2/acl2/keys{/key_id}","collaborators_url":"https://api.github.com/repos/acl2/acl2/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/acl2/acl2/teams","hooks_url":"https://api.github.com/repos/acl2/acl2/hooks","issue_events_url":"https://api.github.com/repos/acl2/acl2/issues/events{/number}","events_url":"https://api.github.com/repos/acl2/acl2/events","assignees_url":"https://api.github.com/repos/acl2/acl2/assignees{/user}","branches_url":"https://api.github.com/repos/acl2/acl2/branches{/branch}","tags_url":"https://api.github.com/repos/acl2/acl2/tags","blobs_url":"https://api.github.com/repos/acl2/acl2/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/acl2/acl2/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/acl2/acl2/git/refs{/sha}","trees_url":"https://api.github.com/repos/acl2/acl2/git/trees{/sha}","statuses_url":"https://api.github.com/repos/acl2/acl2/statuses/{sha}","languages_url":"https://api.github.com/repos/acl2/acl2/languages","stargazers_url":"https://api.github.com/repos/acl2/acl2/stargazers","contributors_url":"https://api.github.com/repos/acl2/acl2/contributors","subscribers_url":"https://api.github.com/repos/acl2/acl2/subscribers","subscription_url":"https://api.github.com/repos/acl2/acl2/subscription","commits_url":"https://api.github.com/repos/acl2/acl2/commits{/sha}","git_commits_url":"https://api.github.com/repos/acl2/acl2/git/commits{/sha}","comments_url":"https://api.github.com/repos/acl2/acl2/comments{/number}","issue_comment_url":"https://api.github.com/repos/acl2/acl2/issues/comments{/number}","contents_url":"https://api.github.com/repos/acl2/acl2/contents/{+path}","compare_url":"https://api.github.com/repos/acl2/acl2/compare/{base}...{head}","merges_url":"https://api.github.com/repos/acl2/acl2/merges","archive_url":"https://api.github.com/repos/acl2/acl2/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/acl2/acl2/downloads","issues_url":"https://api.github.com/repos/acl2/acl2/issues{/number}","pulls_url":"https://api.github.com/repos/acl2/acl2/pulls{/number}","milestones_url":"https://api.github.com/repos/acl2/acl2/milestones{/number}","notifications_url":"https://api.github.com/repos/acl2/acl2/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/acl2/acl2/labels{/name}","releases_url":"https://api.github.com/repos/acl2/acl2/releases{/id}","created_at":"2014-09-01T21:51:04Z","updated_at":"2015-11-30T20:27:49Z","pushed_at":"2015-12-01T01:37:53Z","git_url":"git://github.com/acl2/acl2.git","ssh_url":"git@github.com:acl2/acl2.git","clone_url":"https://github.com/acl2/acl2.git","svn_url":"https://github.com/acl2/acl2","homepage":"http://www.cs.utexas.edu/users/moore/acl2","size":157417,"stargazers_count":41,"watchers_count":41,"language":"Common Lisp","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":26,"mirror_url":null,"open_issues_count":91,"forks":26,"open_issues":91,"watchers":41,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/acl2/acl2/pulls/549"},"html":{"href":"https://github.com/acl2/acl2/pull/549"},"issue":{"href":"https://api.github.com/repos/acl2/acl2/issues/549"},"comments":{"href":"https://api.github.com/repos/acl2/acl2/issues/549/comments"},"review_comments":{"href":"https://api.github.com/repos/acl2/acl2/pulls/549/comments"},"review_comment":{"href":"https://api.github.com/repos/acl2/acl2/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/acl2/acl2/pulls/549/commits"},"statuses":{"href":"https://api.github.com/repos/acl2/acl2/statuses/cb31e773a490fb08811bacfea8bae3cd550ec8c8"}},"merged":false,"mergeable":true,"mergeable_state":"clean","merged_by":null,"comments":0,"review_comments":0,"commits":24,"additions":11068,"deletions":17685,"changed_files":55}}