NTTSolver: support more nuanced trip counts for objective weights #3633

#3625 added region support for the NTT solver. This includes an objective function that is aware of how many times an operation runs (if it's inside a loop nest). This uses a naive static trip count of the enclosing loop nest. That produces an overestimate, because branching conditionals within a loop can reduce the number of times that a particular op is actually executed compared to the loop bounds. It also doesn't support a loop nest whose inner bounds are a function of the outer loop's induction variable.

We recently merged #3520 which shows how to do static analysis of all affine loops (and some scf loops), including nested affine control flow, and determines, for each operation in a loop, exactly how many times it's executed. This issue is to support that more comprehensive trip count analysis for the NTT solver; that said, it would also require the input IR to the solver to use affine loops to get full fidelity.

Originally posted by @j2kun in #3625 (comment)