> You're right, I hadn't thought this through. The whole point of making them > local is to say that "I'm sure these callees won't modify that memory" > regardless of what functions actually get called, even indirectly. We can't > know that they won't modify the vptr in advance, so invariant doesn't work > here. Making it non-local just means that we would need to know the static > call graph, which we don't because we haven't devirtualized yet so all the > calls are indirect. > NickSo that means you're now saying that llvm.invariant.end ought to be left the way it is, right? I've been thinking about how to better take the invariant regions into account, and it quickly became clear that it would be easier to handle if we scanned forward instead of backwards. Any way you do it, there'd be a lot more scanning in memdep than there is at present... you can't tell just by looking at the instructions between a load and a preceding potential clobber that those two instructions are actually in an invariant region. Which led me to wonder if perhaps instead of tracing individual pointers on request with memdep, we should maybe create an generalization of mem2reg to handle all pointers mentioned in a function. A clobber outside of an invariant region would "unassign" the location and all of its may-aliases. A store would "assign" the location and all of its must-aliases and "unassign" all of its may-aliases. A load would then use the SSA assignment if one is unquestionably available, or remain in place as a load and then "assign" the load result back to the pointer. No attempt would be made to remove stores during this pass. AliasSetTracker would be helpful as soon as I could get it to optionally keep all of its sets "must alias" instead of downgrading them to "may alias" as soon as a may-alias of an existing set showed up. Then I'd use a "must alias" tracker and a "may alias" tracker so I could quickly answer "what are all of this pointer's MustAlias's?" and "what are all of this pointer's MayAlias's?". After such a pass runs, the loads that now get fed to memdep are already resolved as values whenever they can be and don't have to be traced again or cached separately.
Kenneth Uildriks wrote:>> You're right, I hadn't thought this through. The whole point of making them >> local is to say that "I'm sure these callees won't modify that memory" >> regardless of what functions actually get called, even indirectly. We can't >> know that they won't modify the vptr in advance, so invariant doesn't work >> here. Making it non-local just means that we would need to know the static >> call graph, which we don't because we haven't devirtualized yet so all the >> calls are indirect. >> Nick > > So that means you're now saying that llvm.invariant.end ought to be > left the way it is, right?I have no idea how to make use of llvm.invariant to help devirtualization. If no use or other use case for them can be found, maybe they should be removed.> I've been thinking about how to better take the invariant regions into > account, and it quickly became clear that it would be easier to handle > if we scanned forward instead of backwards.Right, there's been talk of a "reverse memdep". Owen? Any way you do it,> there'd be a lot more scanning in memdep than there is at present... > you can't tell just by looking at the instructions between a load and > a preceding potential clobber that those two instructions are actually > in an invariant region. > > Which led me to wonder if perhaps instead of tracing individual > pointers on request with memdep, we should maybe create an > generalization of mem2reg to handle all pointers mentioned in a > function. A clobber outside of an invariant region would "unassign" > the location and all of its may-aliases. A store would "assign" the > location and all of its must-aliases and "unassign" all of its > may-aliases. A load would then use the SSA assignment if one is > unquestionably available, or remain in place as a load and then > "assign" the load result back to the pointer. No attempt would be > made to remove stores during this pass. AliasSetTracker would be > helpful as soon as I could get it to optionally keep all of its sets > "must alias" instead of downgrading them to "may alias" as soon as a > may-alias of an existing set showed up. Then I'd use a "must alias" > tracker and a "may alias" tracker so I could quickly answer "what are > all of this pointer's MustAlias's?" and "what are all of this > pointer's MayAlias's?". > > After such a pass runs, the loads that now get fed to memdep are > already resolved as values whenever they can be and don't have to be > traced again or cached separately.This is complex enough that I would need to think about it some more. Nick
Hi Nick,> I have no idea how to make use of llvm.invariant to help > devirtualization. If no use or other use case for them can be found, > maybe they should be removed.the dragonegg plugin uses llvm.invariant to help the code generators optimize the code it produces for builtin_init_trampoline. It writes some values into memory which is then constant forever after. Because pointers to this memory are passed into all kinds of functions, the optimizers don't understand that the values are constant without help, thus the use of llvm.invariant. It doesn't work very well, but it is still better than not doing it at all. Ciao, Duncan.
On Wed, Oct 13, 2010 at 12:45 AM, Nick Lewycky <nicholas at mxc.ca> wrote:> Kenneth Uildriks wrote: >>> >>> You're right, I hadn't thought this through. The whole point of making >>> them >>> local is to say that "I'm sure these callees won't modify that memory" >>> regardless of what functions actually get called, even indirectly. We >>> can't >>> know that they won't modify the vptr in advance, so invariant doesn't >>> work >>> here. Making it non-local just means that we would need to know the >>> static >>> call graph, which we don't because we haven't devirtualized yet so all >>> the >>> calls are indirect. >>> Nick >> >> So that means you're now saying that llvm.invariant.end ought to be >> left the way it is, right? > > I have no idea how to make use of llvm.invariant to help devirtualization. > If no use or other use case for them can be found, maybe they should be > removed.Apply invariant to the vtpr as long as the corresponding instance pointer is in use within a function. With an invariant vtpr (and better invariant support, and a front-end that uses it), devirtualization happens more or less automatically with -std-compile-opts. Do the same wherever an instance pointer is passed. Mark its corresponding vtpr invariant from the beginning of the entry block until right after the last use of the instance pointer. Then a few simple improvements to inlining & partial specialization will give you some interprocedural devirtualization. Anyway, you convinced me a few messages ago that invariant.end really should be left the way it is. Especially since assuming invariance hasn't ended when it has is unsafe... we *must* be able to match an invariance start to its corresponding invariance end in all cases.