For example,

((X & 255) != 0) && ((X & 15) == 8) -> ((X & 15) == 8).

((X & 7) != 0) && ((X & 15) == 8) -> false.

Differential D43835

Simplify more cases of logical ops of masked icmps.

Authored by **yamauchi** on Feb 27 2018, 2:43 PM.

Details

- Reviewers
davidxl - Commits
- rL327450: Simplify more cases of logical ops of masked icmps.

For example,

((X & 255) != 0) && ((X & 15) == 8) -> ((X & 15) == 8).

((X & 7) != 0) && ((X & 15) == 8) -> false.

Diff Detail

- Repository
- rL LLVM

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||||
---|---|---|---|---|

309 ↗ | (On Diff #137265) | Update the comment since return type changes. Also document parameters LHS, RHS, PredL and PredR. | ||

438 ↗ | (On Diff #137265) | Document this method with a small example. | ||

444 ↗ | (On Diff #137265) | && -> & | ||

448 ↗ | (On Diff #137265) |
| ||

551 ↗ | (On Diff #137265) | Add function documentation. | ||

test/Transforms/InstCombine/icmp-logical.ll | ||||

204 ↗ | (On Diff #137265) | x&&15 --> x&15 | ||

341 ↗ | (On Diff #137265) | && --> & Similarly, || --> | in other places. |

Comment Actions

Addressed comments.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

448 ↗ | (On Diff #137265) | What does this comment mean? |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

448 ↗ | (On Diff #137265) | Now I see what you meant. Done. It was formatted as a table :) |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

440 ↗ | (On Diff #137770) | icmp(A&B) ==/!= C |

450 ↗ | (On Diff #137770) | Do you have test case cover this when LSH and RHS are swapped? (icmp eq (A &D), E) & (icmp ne (A & B, 0)) |

454 ↗ | (On Diff #137770) | replace 0 with 'C' in the example. |

462 ↗ | (On Diff #137770) | Do you need to check CCst is Zero? |

474 ↗ | (On Diff #137770) | It seems to me, it is sufficient to do the following check: - check if mask B is a subset of mask D
- check if (E & B) != 0 is true
If both 1) and 2) are satisfied, the simplification is legal. |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

454 ↗ | (On Diff #137770) | LHS being of type Mask_NotAllZeroes means that LHS is or can be converted into the form "(icmp ne (A & B), 0)". I think 0 would be better here because the right hand side of the LHS isn't necessarily C. Note the case of Mask_NotAllZeroes where B==C and B is a power of two (see lines 216 and 269 above) where we get "(icmp eq (A & B), C)" (B==C) but interpret it as (equivalent) "(icmp ne (A & B), 0)". |

462 ↗ | (On Diff #137770) | Similarly, C isn't necessarily zero if Mask_NotAllZeroes is due to the case for B==C and B is a power of two. So, no. |

474 ↗ | (On Diff #137770) | I need a clarification on this. I think the case you are referring to, which is an important one, is covered by lines 552-553 below. But there are several other cases of simplifications below. There are simplifications we can do even when B isn't a subset of D below, eg. (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8). Do you mean we can drop the other cases? |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

450 ↗ | (On Diff #137770) | Added swapped tests. |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

499 ↗ | (On Diff #138040) | This check can probably be extended: - B's bitset subtracts the intersection of B and D contains only one bit
- B and D's intersection have zero values
In other words, D does not need to be power of 2 |

530 ↗ | (On Diff #138040) | Can you introduce a small lambda here to be reused here and other places? auto IsSubset = [](Value *V1, Value *V2) { .... }; if (IsSubset(BCst, DCst)) .... |

536 ↗ | (On Diff #138040) | Can you split the comment here for case in line 548 and line 552? |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

499 ↗ | (On Diff #138040) | Is there a chance that those two conditions you are referring to *are* what the current code is already checking here? To be more specific, Isn't the condition 1 equivalent to "(B & (B ^ D)).isPowerOf2()" that the current code checks? (I meant "(B & (B ^ D))" as the bits that are 1 in B but 0 in D.) For example, suppose B = 1100 and D = 0101. The condition 1 would say 1100 - (1100 & 0101) = 1100 - 0100 = 1000 while (B & (B ^ D)) = (1100 & (1100 ^ 0101)) = (1100 & 1001) = 1000. Also, isn't the condition 2 equivalent to "((B & D) & E) == 0" that the current code checks? (Note that in the current code, it's not D, but (B & (B ^ D)) that needs to be a power of 2.) Do you have an example that isn't handled by the current code but is handled by the suggested extension? |

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
---|---|---|

499 ↗ | (On Diff #138040) | You are right. Perhaps add a comment just before the condition to document the semantics of the check. |