3 ms·
https://llvm.org/docs/Passes.html#passes-mem2reg https://llvm.org/docs/Passes.html#passes-mem2reg > -mem2reg: Promote Memory to Register > This file promotes
by dragontamer 5y ago
https://llvm.org/docs/Passes.html#passes-mem2reg https://llvm.org/docs/Passes.html#passes-mem2reg
> -mem2reg: Promote Memory to Register
> This file promotes memory references to be register references. It promotes alloca instructions which only have loads and stores as uses. An alloca is transformed by using dominator frontiers to place phi nodes, then traversing the function in depth-first order to rewrite loads and stores as appropriate. This is just the standard SSA construction algorithm to construct “pruned” SSA form.
-----------
https://llvm.org/docs/LangRef.html#alloca-instruction https://llvm.org/docs/LangRef.html#alloca-instruction
> The ‘alloca’ instruction allocates memory on the stack frame of the currently executing function, to be automatically released when this function returns to its caller. If the address space is not explicitly specified, the object is allocated in the alloca address space from the datalayout string.
--------
Based on my reading and understanding of alloca and mem2reg above, I have to disagree with your assessment. It seems like alloca roughly corresponds to a "push" in your typical x86 assembly language, or maybe a "add esp, #ofBytes".
By removing alloca instructions, the mem2reg step is turning stack-memory into registers.
- woodruffw 5y ago> By removing alloca instructions, the mem2reg step is turning stack-memory into registers. This is true, but it's also misleading: the transformation of stack slots into machine registers is a beneficial side effect of mem2reg. Reducing stack use is an important optimization, but producing an optimal SSA form is even more important, since key passes like folding, DCE and SRoA rely heavily on the SSA form. The "reg" in "mem2reg" refers explicitly to the latter (SSA registers), as the text you've excerpted directly says. You can also prove this to yourself by contriving an IR function that contains more SSA registers than machine registers: you'll see that, in addition to any ABI constraints, LLVM will be forced to spill any excess SSA registers back onto the stack. Edit: but also yes, to confirm: `alloca` corresponds more or less directly to `add ESP, <adjust>` within the x86 stack model. But it doesn't have to! LLVM's semantics are target independent even when the IR isn't.
- dragontamer 5y agoGotcha. I think I see what you're talking about now. I have crude familiarity with SSA (no personal experience but I've read a book once) but not with LLVM's terminology. I'm looking at the example in the blogpost, and I can see that its clearly adding in the important Phi functions needed Strange that llvm names their aggressive SSA step in this manner. But yes, adding the phi functions in this manner is a very important step before we can think about optimizations. The "inductive variable" is far easier to detect once its in a "Phi-form" so to speak.
- woodruffw 5y agoIt's an extremely confusing naming choice! I don't know why they did it, but to take a guess: a lot of compiler literature refers to SSA values as "registers," since the SSA model of a computer program directly corresponds to the concept of an (infinite) register machine in abstract computation. The end result being that we have the same word "register" referring to two opposed resources (one infinite, one extremely finite) :-).
- gsnedders 5y agoAt least historically LLVM has itself been inconsistent in the naming of SSA "values", and mem2reg is arguably just the most prominent example of the "register" name being used.
- ufo 5y agoIt's not the only place where this terminology confuses people. Another one is "register-based virtual machine", in the context of interpreters. In that case the registers belong to the VM and are actually stored in stack memory, not on actual CPU registers. However, people get that confused all the time!
- account42 5y ago> You can also prove this to yourself by contriving an IR function that contains more SSA registers than machine registers: you'll see that, in addition to any ABI constraints, LLVM will be forced to spill any excess SSA registers back onto the stack. Having more SSA register than machine registers does not mean there will be any spilling as unlike SSA registers, machine registers can be reused once the old value is no longer needed.