[Unity][Pass] Fixpoint simplification #15474

slyubomirsky · 2023-08-03T19:10:51Z

This PR implements a simple simplification pass that applies various other simplification passes until fixpoint (i.e., apply them until the module stops changing). This probably should not be part of the standard compilation, since it has the potential to repeat passes many times, but I doubt that we would be in danger of having it happen that much. I am certain that it terminates, since all of the passes included either make the module "more simplified" or leave it unchanged if they cannot find any opportunities to make changes (i.e., no pass has the potential to undo the work of other passes). Nevertheless, the pass includes an iteration limit in case passes are later added that in some situations do not converge (not recommended).

Incidentally, it also fixes a bug that I happened to discover in the binding canonicalization pass: It did not handle the case of a non-dataflow var being bound to a dataflow var and gave a segfault if it was encountered.

A few points of discussion:

I wasn't sure if constant folding should be included in this. I am not sure new opportunities for constant folding could arise with these passes, though maybe it's possible (if we could come up with an example).
There are many normalizations happening between each round but I encountered a bug when I tried to go function-by-function (StructInfo would not update correctly), so this manner of implementation ensures fewer headaches. Passes all assume that the input has been normalized so not doing it every time has the potential to cause unexpected errors.
Are there more simplifications we would like to throw in here? Lots of little passes like the dataflow block output folding behavior would now be a lot more feasible to just throw in here and see some use.

tvm-bot · 2023-08-03T19:10:54Z

Thanks for contributing to TVM! Please refer to the contributing guidelines https://tvm.apache.org/docs/contribute/ for useful information and tips. Please request code reviews from Reviewers by @-ing them in a comment.

cc @quic-sanirudh _{See #10317 for details}

_{Generated by tvm-bot}

tvm-bot · 2023-08-03T19:10:54Z

Thanks for contributing to TVM! Please refer to the contributing guidelines https://tvm.apache.org/docs/contribute/ for useful information and tips. Please request code reviews from Reviewers by @-ing them in a comment.

cc @quic-sanirudh _{See #10317 for details}

_{Generated by tvm-bot}

slyubomirsky · 2023-08-09T17:27:29Z

Looks like a spurious/flaky test failure

slyubomirsky · 2023-08-09T17:27:35Z

@tvm-bot rerun

github-actions · 2023-08-09T17:27:59Z

Failed to re-run CI in https://github.com/apache/tvm/actions/runs/5812197184

Details

Traceback (most recent call last):
  File "ci/scripts/github/github_tvmbot.py", line 594, in comment_failure
    raise item
  File "ci/scripts/github/github_tvmbot.py", line 700, in run
    pr.rerun_jenkins_ci()
  File "ci/scripts/github/github_tvmbot.py", line 553, in rerun_jenkins_ci
    post(url, auth=("tvm-bot", TVM_BOT_JENKINS_TOKEN))
  File "/home/runner/work/tvm/tvm/ci/scripts/jenkins/git_utils.py", line 53, in post
    with request.urlopen(req, data) as response:
  File "/usr/lib/python3.8/urllib/request.py", line 222, in urlopen
    return opener.open(url, data, timeout)
  File "/usr/lib/python3.8/urllib/request.py", line 531, in open
    response = meth(req, response)
  File "/usr/lib/python3.8/urllib/request.py", line 640, in http_response
    response = self.parent.error(
  File "/usr/lib/python3.8/urllib/request.py", line 569, in error
    return self._call_chain(*args)
  File "/usr/lib/python3.8/urllib/request.py", line 502, in _call_chain
    result = func(*args)
  File "/usr/lib/python3.8/urllib/request.py", line 649, in http_error_default
    raise HTTPError(req.full_url, code, msg, hdrs, fp)
urllib.error.HTTPError: HTTP Error 500: Server Error

with response


  
  <!DOCTYPE html><html><head resURL="/static/bb039fcf" data-rooturl="" data-resurl="/static/bb039fcf" data-extensions-available="true" data-unit-test="false" data-imagesurl="/static/bb039fcf/images" data-crumb-header="Jenkins-Crumb" data-crumb-value="1ff938864061d8319ee8ecc9528fd8d6b8fbff3445538eab3bfd2e240e92950b4626db6712f33e5d8d3c185695b03adb95bb052089379cd9486c327c0fc0018f">
    
    

    <title>Jenkins [Jenkins]</title><link rel="stylesheet" href="/static/bb039fcf/jsbundles/styles.css" type="text/css"><link rel="stylesheet" href="/static/bb039fcf/css/responsive-grid.css" type="text/css"><link rel="shortcut icon" href="/static/bb039fcf/favicon.ico" type="image/vnd.microsoft.icon"><script src="/static/bb039fcf/scripts/prototype.js" type="text/javascript"></script><script src="/static/bb039fcf/scripts/behavior.js" type="text/javascript"></script><script src='/adjuncts/bb039fcf/org/kohsuke/stapler/bind.js' type='text/javascript'></script><script src="/static/bb039fcf/scripts/yui/yahoo/yahoo-min.js"></script><script src="/static/bb039fcf/scripts/yui/dom/dom-min.js"></script><script src="/static/bb039fcf/scripts/yui/event/event-min.js"></script><script src="/static/bb039fcf/scripts/yui/animation/animation-min.js"></script><script src="/static/bb039fcf/scripts/yui/dragdrop/dragdrop-min.js"></script><script src="/static/bb039fcf/scripts/yui/container/container-min.js"></script><script src="/static/bb039fcf/scripts/yui/connection/connection-min.js"></script><script src="/static/bb039fcf/scripts/yui/datasource/datasource-min.js"></script><script src="/static/bb039fcf/scripts/yui/autocomplete/autocomplete-min.js"></script><script src="/static/bb039fcf/scripts/yui/menu/menu-min.js"></script><script src="/static/bb039fcf/scripts/yui/element/element-min.js"></script><script src="/static/bb039fcf/scripts/yui/button/button-min.js"></script><script src="/static/bb039fcf/scripts/yui/storage/storage-min.js"></script><script src="/static/bb039fcf/scripts/hudson-behavior.js" type="text/javascript"></script><script src="/static/bb039fcf/scripts/sortable.js" type="text/javascript"></script><link rel="stylesheet" href="/static/bb039fcf/scripts/yui/container/assets/container.css" type="text/css"><link rel="stylesheet" href="/static/bb039fcf/scripts/yui/container/assets/skins/sam/container.css" type="text/css"><link rel="stylesheet" href="/static/bb039fcf/scripts/yui/menu/assets/skins/sam/menu.css" type="text/css"><link rel="search" href="/opensearch.xml" type="application/opensearchdescription+xml" title="Jenkins"><meta name="ROBOTS" content="INDEX,NOFOLLOW"><meta name="viewport" content="width=device-width, initial-scale=1"><script src="/static/bb039fcf/jsbundles/vendors.js" type="text/javascript"></script><script src="/static/bb039fcf/jsbundles/page-init.js" type="text/javascript"></script><script src="/static/bb039fcf/jsbundles/sortable-drag-drop.js" type="text/javascript"></script></head><body data-model-type="hudson.model.Hudson" id="jenkins" class="yui-skin-sam one-column jenkins-2.361.2" data-version="2.361.2"><a href="#skip2content" class="skiplink">Skip to content</a><header id="page-header" class="page-header"><div class="page-header__brand"><div class="logo"><a id="jenkins-home-link" href="/"><img src="/static/bb039fcf/images/svgs/logo.svg" alt="[Jenkins]" id="jenkins-head-icon"><img src="/static/bb039fcf/images/title.svg" alt="Jenkins" width="139" id="jenkins-name-icon" height="34"></a></div><a href="/" class="page-header__brand-link"><img src="/static/bb039fcf/images/svgs/logo.svg" alt="[Jenkins]" class="page-header__brand-image"><span class="page-header__brand-name">Jenkins</span></a></div><div class="searchbox hidden-xs"><form role="search" method="get" name="search" action="/search/" style="position:relative;" class="no-json"><div id="search-box-sizer"></div><div id="searchform"><input role="searchbox" name="q" placeholder="Search" id="search-box" class="main-search__input"><span class="main-search__icon-leading"><svg class="" class="" aria-hidden="true" xmlns="http://www.w3.org/2000/svg" class="" viewBox="0 0 512 512"><title></title><path d="M221.09 64a157.09 157.09 0 10157.09 157.09A157.1 157.1 0 00221.09 64z" fill="none" stroke="currentColor" stroke-miterlimit="10" stroke-width="32"/><path fill="none" stroke="currentColor" stroke-linecap="round" stroke-miterlimit="10" stroke-width="32" d="M338.29 338.29L448 448"/></svg></span><a href="https://www.jenkins.io/redirect/search-box" class="main-search__icon-trailing"><svg class="" class="" aria-hidden="true" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path d="M256 40a216 216 0 10216 216A216 216 0 00256 40z" fill="none" stroke="currentColor" stroke-miterlimit="10" stroke-width="38"/><path d="M200 202.29s.84-17.5 19.57-32.57C230.68 160.77 244 158.18 256 158c10.93-.14 20.69 1.67 26.53 4.45 10 4.76 29.47 16.38 29.47 41.09 0 26-17 37.81-36.37 50.8S251 281.43 251 296" fill="none" stroke="currentColor" stroke-linecap="round" stroke-miterlimit="10" stroke-width="38"/><circle cx="250" cy="360" r="25" fill="currentColor"/></svg></a><div id="search-box-completion" data-search-url="/search/"></div><script src='/adjuncts/bb039fcf/jenkins/views/JenkinsHeader/search-box.js' type='text/javascript'></script></div></form></div><div class="login page-header__hyperlinks"><div id="visible-am-insertion" class="page-header__am-wrapper"></div><div id="visible-sec-am-insertion" class="page-header__am-wrapper"></div><a href="/securityRealm/commenceLogin?from=%2Fjob%2Ftvm-arm%2Fjob%2FPR-15474%2FbuildWithParameters"><b>log in</b></a></div></header><script src="/static/bb039fcf/jsbundles/keyboard-shortcuts.js" type="text/javascript"></script><div id="breadcrumbBar"><script src='/adjuncts/bb039fcf/lib/layout/breadcrumbs.js' type='text/javascript'></script><div class="top-sticker noedge"><div class="top-sticker-inner"><div class="jenkins-breadcrumbs"><ul id="breadcrumbs"><li class="item"><a href="/" class="model-link">Dashboard</a></li><li href="/" class="children"></li></ul><div id="breadcrumb-menu-target"></div></div></div></div></div><div id="page-body" class="clear"><div id="main-panel"><a name="skip2content"></a><h1 style="text-align: center"><img src="/static/bb039fcf/images/rage.svg" width="154" height="179"><span style="font-size:50px"> Oops!</span></h1><div id="error-description"><h2 style="text-align: center">A problem occurred while processing the request.</h2><p style="text-align: center">Logging ID=b8bf3caf-1bb2-448d-8408-f8ce3794ae53</div></div></div><footer class="page-footer"><div class="container-fluid"><div class="page-footer__flex-row"><div class="page-footer__footer-id-placeholder" id="footer"></div><div class="page-footer__links rest_api hidden-xs"><a href="api/">REST API</a></div><div class="page-footer__links page-footer__links--white jenkins_ver"><a rel="noopener noreferrer" href="https://www.jenkins.io/" target="_blank">Jenkins 2.361.2</a></div></div></div></footer></body></html>

kparzysz-quic · 2023-08-10T17:37:35Z

All of this should be doable in a single execution of a sequence of optimizations. If we don't get it. we should examine our passes for deficiencies. Doing fixed point transformations is (IMO) a warning sign to look at what we're missing that we're trying to make up for with repeated iterations.

Even in the pattern matching pass (where repetition is justifiable) we should have a max number of iterations to perform.

slyubomirsky · 2023-08-10T17:52:15Z

It's a tradeoff between increasing the complexity of the individual passes to handle more cases versus rerunning existing passes. I agree that running to fixpoint is a bit of a lazy "shotgun approach" but it could be useful in that it would allow for easily throwing in new passes to handle small transformations.

kparzysz-quic · 2023-08-10T18:15:08Z

I disagree with this approach. This is not the right way to compose transformations.

slyubomirsky · 2023-08-10T18:20:54Z

I'd be happy to discuss how the passes included should be modified to produce the behavior shown in the test cases, in that case. My concern is avoiding code duplication and mission creep for certain passes.

kparzysz-quic · 2023-08-10T18:29:32Z

Sure. I'll be out on vacation in the next 2 weeks, but I'd be happy to propose/work on improvements after I'm back.

slyubomirsky · 2023-08-10T18:40:09Z

I'll split the bugfix into its own PR then and we can leave this open for further discussion.

slyubomirsky · 2023-11-17T02:21:48Z

The specific motivation for this one has been superseded by later PRs like #15791 so there is no reason to keep this around.

slyubomirsky added the branch: unity label Aug 3, 2023

slyubomirsky mentioned this pull request Aug 10, 2023

[Unity][Bugfix] Handle assignment of non-dataflow var to a dataflow var in CanonicalizeBindings #15523

Merged

slyubomirsky added 6 commits August 11, 2023 13:46

Implement fixpoint simplification pass

fca1570

Do not repeatedly compute the same hash

1d73818

Fix test function name

267c83f

Even more whitespace

c7e87be

Include limit on the number of iterations for safety

56e0938

Change doc comments (to retrigger CI)

2b0b4ca

slyubomirsky force-pushed the fixpoint-simplification branch from 3403be8 to 2b0b4ca Compare August 11, 2023 17:47

slyubomirsky mentioned this pull request Sep 20, 2023

[Unity][Pass] Include FoldDataflowBlockOutput in CanonicalizeBindings #15791

Merged

slyubomirsky closed this Nov 17, 2023

[Unity][Pass] Fixpoint simplification #15474

[Unity][Pass] Fixpoint simplification #15474

Uh oh!

Conversation

slyubomirsky commented Aug 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tvm-bot commented Aug 3, 2023

Uh oh!

tvm-bot commented Aug 3, 2023

Uh oh!

slyubomirsky commented Aug 9, 2023

Uh oh!

slyubomirsky commented Aug 9, 2023

Uh oh!

github-actions bot commented Aug 9, 2023

Uh oh!

kparzysz-quic commented Aug 10, 2023

Uh oh!

slyubomirsky commented Aug 10, 2023

Uh oh!

kparzysz-quic commented Aug 10, 2023

Uh oh!

slyubomirsky commented Aug 10, 2023

Uh oh!

kparzysz-quic commented Aug 10, 2023

Uh oh!

slyubomirsky commented Aug 10, 2023

Uh oh!

slyubomirsky commented Nov 17, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

slyubomirsky commented Aug 3, 2023 •

edited

Loading