Given below case: %y = shl %x, c0 %z = ashr %y, c1 when n = m, SCEV models it as sext(trunc(x)). This patch tries to handle the case where c0 > c1 by using sext(mul(trunc(x), 2^(c0-c1)))) as the SCEV expression.

# Details

# Diff Detail

- Repository
- rL LLVM

### Event Timeline

Please upload patches with full context (`-U1000000`).

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5276 | Maybe reorganize the code to look more like this (rough outline)? ConstantInt *LCI = dyn_cast<ConstantInt>(LOp1)); if (!LCI) break; if (ashr greater than shl) break; if (ashr less than than shl) { // Multiply SCEV } return sext(trunc(scev)); | |

test/Analysis/ScalarEvolution/sext-mul.ll | ||

5 | The loop induction variable (let's call it With your patch, |

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5333 | You have to check whether Amt == BitWidth before you call getTruncateExpr(); otherwise, you'll get an assertion failure in getTruncateExpr in edge cases like "ashr i32 %x, 0". | |

5366 | Typo: "Handle". | |

5378 | This TODO is suggesting an incorrect transformation; udiv doesn't preserve the sign. | |

test/Analysis/ScalarEvolution/sext-mul.ll | ||

42 | Maybe run opt -instnamer over the testcase, so it's easier to edit if we ever need to change it? |

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5266 | Maybe rename Amt and LOp1 to something which actually describes the values? | |

5267 | Maybe move this check earlier? You could do it before you even check that the LHS of the ashr is another shift: just "if (CI->isNullValue()) return getSCEV(BO->LHS)". | |

5290 | Hoist this variable definition, so you don't call CI->getZExtValue() twice. | |

5298 | "LShAmt - AShrAmt >= Amt" is equivalent to "LShAmt - AShrAmt >= BitWidth - AshrAmt", which is equivalent to "LShAmt >= BitWidth", which you already check earlier. | |

5300 | APInt::getOneBitSet? (The amount of the multiply could overflow "int".) |

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5271 | I think you meant to return | |

5304 | 64 might not be large enough, and getZExtValue() will assert if the value doesn't fit into a 64-bit integer. The right code is something like |

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5294 | To clarify my earlier comment about this: we can in fact transform |

Did you consider doing this same thing in two more general steps (with separate tests for each case):

- Lower
`ashr X C`as`sext(trunc(udiv(X, 1 << C)))`, irrespective of what`X`is - Add a separate rule that
`(A mul (1 << C0)) udiv (1 << C1)`is`sext(trunc(A mul (1 << (C0 - C1))))`if`C0 > C1`

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5299 |
| |

5316 | Please call this | |

test/Analysis/ScalarEvolution/sext-mul.ll | ||

14 | Please add some target test cases here (i.e. ones that check specific SCEV expressions for the patterns you want SCEV to catch). |

Sanjoy,

I'm not familiar with SCEV, can you clarify my questions below?

- Lower
ashr X Cassext(trunc(udiv(X, 1 << C))), irrespective of whatXis

This part should be done in const SCEV *ScalarEvolution::createSCEV(Value *V) as the patch is doing

- Add a separate rule that
(A mul (1 << C0)) udiv (1 << C1)issext(trunc(A mul (1 << (C0 - C1))))ifC0 > C1

Should this be done inside getMulExpr()?

Adding tranformation: AShr X, C --> sext(trunc(udiv(X, (1<<C))))

Will update test cases later.

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5367 |
| |

test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll | ||

6 ↗ | (On Diff #90903) | This is defeating the point of the test. I would guess SCEVExpander isn't realizing that sext(trunc(udiv))) is equivalent to an ashr? |

Removed ashr (X, C) -> sext(truc(udiv(X, 1<<C))) from previous revision.

This is causing a test failure and needs more work. I'd like to do it in another patch.

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5368 | This is failing test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll. See inlined comments of the test. | |

test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll | ||

6 ↗ | (On Diff #90903) | "%shr = ashr i32 %add, 16" becomes computable and SCEVExpander hoists its InsertPt to outer loop, causing FindValueInExprValueMap() to return {nullptr, nullptr}. |

This is failing test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll.

"%shr = ashr i32 %add, 16" becomes computable and SCEVExpander hoists its InsertPt to outer loop, causing FindValueInExprValueMap() to return {nullptr, nullptr}.

SCEVExpander then expands it literally and creates another 'select' instruction, failing the test.

- Add a separate rule that
(A mul (1 << C0)) udiv (1 << C1)issext(trunc(A mul (1 << (C0 - C1))))ifC0 > C1

For my test case, Shl is already lowered to a mul expr before processing AShr.

AShr can be lowered to udiv(1<<C1) but it's not easy to look for the pattern "(A mul (1 << C0)) udiv (1 << C1)".

lgtm modulo minor comments

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

5322 | I'd call this | |

5336 | IMO things would read a bit clearer if you just s/ | |

5346 | If you want to use // X = Shl A, n // Y = AShr X, m or use | |

5357 | Typo: | |

test/Analysis/ScalarEvolution/sext-mul.ll | ||

9 | Why not | |

test/Analysis/ScalarEvolution/sext-zero.ll | ||

7 | Please remove the |