<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/57506>57506</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Exploit transitivity of comparison operators
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:optimizations,
            missed-optimization
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          Kmeakin
      </td>
    </tr>
</table>

<pre>
    All of the integer and floating-point comparison operators, except for `!=`, (ie `==`, `<`, `<=`, `>`, `>=`) satisfy the property of *transitivity*: for all integers/floats `a`, `b`, `c`, `a op b && b op c` implies `a op c`.

This information can be used to remove an unnecessary third comparison ([godbolt](https://godbolt.org/z/ezcxY14oK), [alive](https://alive2.llvm.org/ce/z/Q9frxp)):
```c
bool src(uint32_t a, uint32_t b, uint32_t c) { return a < b && b < c && a < c; }

bool tgt(uint32_t a, uint32_t b, uint32_t c) { return a < b && b < c; }
```

The third comparison can be removed even if the operator is not the same as the first two ([godbolt](https://godbolt.org/z/8W7v91qbT), [alive](https://alive2.llvm.org/ce/z/nPAMNs)):
```c
bool src(uint32_t a, uint32_t b, uint32_t c) { return a == b && b == c && a <= c; }

bool tgt(uint32_t a, uint32_t b, uint32_t c) { return a == b && b == c; }
```

The transitivity property can even be used to rewrite the whole expression to a constant ([godbolt](https://godbolt.org/z/scaz8h3jd), [alive](https://alive2.llvm.org/ce/z/iqYMNn)):
```c
bool src(uint32_t a, uint32_t b, uint32_t c) { return a == b && b == c && a < c; }

bool tgt(uint32_t a, uint32_t b, uint32_t c) { return false; }
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzNVd9vmzAQ_mvgxWoEJpDwwEPSdC9Vq02qNPVpsuEI7gymtkmT_PU7O2kTtk6a2nWaRIK_O3N3333-wVW1KxZSElUT2wARnYU1aMK6itRSMSu69UWv0ExK1fZMC6M6onrQzCptAnpJYFtCb0mtNAmyKKBxkKz84JIEdC7AW9F0sjp8OQZj59UYHJ05MViPqXe-0l67KuzOVR7QhdWsM8KKjbA7hEGy8BUxpHbkhMV-8pSMi8tOKfhpWJ6GDFkSjqEzfHCAyHmJaHspwLxMccZJEK2CaHH4v2uEwZyYvcVysVsl6wgHMhioiFVEQ6s2gB0mQ9dBCcYw7SgJXZ33GHsXpMu1qriSNkhXiBtre4PMkAg-R9dE6TWiPf5gX27v46m6xl55FumSSbGB1772DjqRctMeI5RwDPMlr_W29zFyN__ADRvjn_KAuVKSGF1i4AEbnNBvljCX9AXxESqdfsFsifTtoDvCCMp-3l8Hy2d48JZBssRvVufd9Xnt2v7dvONEz1THqsKvGh2VPShaEdhAR8RhIz1vEYKLoVPW2wxrUXfjx7XQBq1P6i1Cz7_ONnn8yO_eJ3T3eXFza_6B0G7zj3vuLWO5veWDFP9dAX-o-9nZcjp3nPhe8dHeftLCglf4qVES8HTsNW5xdw6gn-Hq6YxleJy-QXZTsv28SR6q98kuHu9vbrv_RfYP0bxm0sDr4oZQxFlGozROpvOwKpIqT3IWWmElFFfbXiphx4rjBfPa3RcOWhY_SSZsM_AJzkbgWn98XeCieYDSuuYbM4C7itJZGmVhU_Ap47MqoQxLyucxZ9m8ovk8i6HmZUYhlIyDNAWKHVDqgyYL1VvRir2_XzAYPVy2tMXoUF2ce50zXYWioBGlUR7FcZam09mE8iybJkkOPGN4CdXBNIKWCfmyYkJd-NL5sDbolMJYc3IyXNLrDsCXhfHZYBuli-sW2HfRhZ5l4Sn-AL2feQ4">