4 ms·

> If your static analysis is over SSA, then generally the static analysis is easier and (potentially) storing facts is easier. This is due to this property call

> If your static analysis is over SSA, then generally the static analysis is easier and (potentially) storing facts is easier. This is due to this property called sparseness. Where a static analysis over non-SSA programs has to store facts about all variables at all program points, an analysis over SSA need only store facts about all variables, independent of context. Not sure what this has to do with SSA or not? Maybe you're saying if you don't have SSA then value numbering requires extra book-keeping to keep track of the names? that's true but the book-keeping only kicks when a name is updated, not at every program point. > If we want to keep our information sparse, though, we have to add a new definition to the IR. I mean this isn't like a law of nature, it's just a design point - a question of whether the facts have to be serializable for some reason. If they don't (and in general, I can't think of a reason they would have to be), you can just keep things in-memory in general and do either sparse or dense analysis on an as-needed basis. To wit MLIR, an SSA IR, handily supports both sparse and dense dataflow analysis: https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h#L177-L181 https://github.com/llvm/llvm-project/blob/main/mlir/include/... https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h#L60-L63 https://github.com/llvm/llvm-project/blob/main/mlir/include/... Note, both analyses propagate lattices which support meet and join. > Anyway, SSA only stores type information about instructions and does not encode information that we might later learn in the IR. With basic SSA, there’s not a good way to encode refinements… This is true of course but I struggle to think of a reasonable semantic that would enable you to refine/change/alter the type of a value that wasn't an operation. The conditional example is specious but could be rectified if it were modeled correctly: the conditional is an operation which has operands and two regions, each with a basic block with basic block args and it's the types of the bb args that can show as "refined". MLIR's scf.if isn't "isolated from above" and its bbs don't have args but it could have both such things and such an operation would model what you want precisely and in the IR/types themselves.

pizlonator 1y ago
> Not sure what this has to do with SSA or not? Maybe you're saying if you don't have SSA then value numbering requires extra book-keeping to keep track of the names? that's true but the book-keeping only kicks when a name is updated, not at every program point. It is the case that if you do a flow-insensitive analysis of variables over SSA, it will be equivalent to a flow-sensitive analysis of variables, because of the static single assignment property. I think that's what the author is trying to say, and I agree. > To wit MLIR, an SSA IR, handily supports both sparse and dense dataflow analysis: I don't think dense vs sparse analysis is the same thing as the use of the word "sparse" in the post. > This is true of course but I struggle to think of a reasonable semantic that would enable you to refine/change/alter the type of a value that wasn't an operation. If you're compiling a dynamically typed language, for example.
- almostgotcaught 1y ago
  > It is the case that if you do a flow-insensitive analysis of variables over SSA, it will be equivalent to a flow-sensitive analysis of variables, because of the static single assignment property. you're saying the same thing i'm saying - the question/issue arises from value numbering and naming. see "engineering a compiler" page ~400 where they discuss the benefits of SSA for value numbering: https://imgur.com/a/bPabq7D https://imgur.com/a/bPabq7D > I don't think dense vs sparse analysis is the same thing as the use of the word "sparse" in the post. it is - the allusion/claim in the post is that SSA is sparse because you don't need to keep track of facts/metadata for all variables at all program points. that's because of the same thing: SSA uniquely locates/identifies values and therefore you can uniquely map between SSA ids and metadata. so you don't need to have a table of stuff that's updated at every program point (like you do in dense analysis), just along control-flow/operand/result edges.
  - pizlonator 1y ago
    > you're saying the same thing i'm saying - the question/issue arises from value numbering and naming. see "engineering a compiler" page ~400 where they discuss the benefits of SSA for value numbering: https://imgur.com/a/bPabq7D https://imgur.com/a/bPabq7D We're definitely not saying the same thing, because to me, the post's claim about the benefits of SSA for flow analysis are obvious and unobjectionable, whereas you raised an objection. > it is - the allusion/claim in the post is that SSA is sparse because you don't need to keep track of facts/metadata for all variables at all program points. that's because of the same thing: SSA uniquely locates/identifies values and therefore you can uniquely map between SSA ids and metadata. so you don't need to have a table of stuff that's updated at every program point (like you do in dense analysis), just along control-flow/operand/result edges. So then what were you talking about when you said, "Not sure what this has to do with SSA or not?". Seems like you're now trying to explain to me exactly what this has to do with SSA or not.

pizlonator 1y ago

> Not sure what this has to do with SSA or not? Maybe you're saying if you don't have SSA then value numbering requires extra book-keeping to keep track of the names? that's true but the book-keeping only kicks when a name is updated, not at every program point. It is the case that if you do a flow-insensitive analysis of variables over SSA, it will be equivalent to a flow-sensitive analysis of variables, because of the static single assignment property. I think that's what the author is trying to say, and I agree. > To wit MLIR, an SSA IR, handily supports both sparse and dense dataflow analysis: I don't think dense vs sparse analysis is the same thing as the use of the word "sparse" in the post. > This is true of course but I struggle to think of a reasonable semantic that would enable you to refine/change/alter the type of a value that wasn't an operation. If you're compiling a dynamically typed language, for example.

almostgotcaught 1y ago
> It is the case that if you do a flow-insensitive analysis of variables over SSA, it will be equivalent to a flow-sensitive analysis of variables, because of the static single assignment property. you're saying the same thing i'm saying - the question/issue arises from value numbering and naming. see "engineering a compiler" page ~400 where they discuss the benefits of SSA for value numbering: https://imgur.com/a/bPabq7D https://imgur.com/a/bPabq7D > I don't think dense vs sparse analysis is the same thing as the use of the word "sparse" in the post. it is - the allusion/claim in the post is that SSA is sparse because you don't need to keep track of facts/metadata for all variables at all program points. that's because of the same thing: SSA uniquely locates/identifies values and therefore you can uniquely map between SSA ids and metadata. so you don't need to have a table of stuff that's updated at every program point (like you do in dense analysis), just along control-flow/operand/result edges.
- pizlonator 1y ago
  > you're saying the same thing i'm saying - the question/issue arises from value numbering and naming. see "engineering a compiler" page ~400 where they discuss the benefits of SSA for value numbering: https://imgur.com/a/bPabq7D https://imgur.com/a/bPabq7D We're definitely not saying the same thing, because to me, the post's claim about the benefits of SSA for flow analysis are obvious and unobjectionable, whereas you raised an objection. > it is - the allusion/claim in the post is that SSA is sparse because you don't need to keep track of facts/metadata for all variables at all program points. that's because of the same thing: SSA uniquely locates/identifies values and therefore you can uniquely map between SSA ids and metadata. so you don't need to have a table of stuff that's updated at every program point (like you do in dense analysis), just along control-flow/operand/result edges. So then what were you talking about when you said, "Not sure what this has to do with SSA or not?". Seems like you're now trying to explain to me exactly what this has to do with SSA or not.