Florian Brandner
2007-Jun-15 14:16 UTC
[LLVMdev] alias information on machine instructions
hi, Florian Brandner wrote:> Dan Gohman wrote: >> On Wed, May 23, 2007 at 12:23:38AM -0700, Chris Lattner wrote: >>> Right. The original Value*'s are preserved in the DAG, but dropped when >>> MachineInstrs are created. We could add a machineoperand to capture this >>> Value* if desired. >> Another benefit of keeping the original Value*'s (and offsets) around is it >> would provide more information that could be used for verbose asm output >> and MachineInstr-level dumps, which would be quite nice. >> > > i'll do this and post a patch, unless someone else is already working on > this. >i have extended the DAG instruction selector and scheduler to preserve Value*'s. the values are attached to machine instructions as a separate operand list (at least for now). for now this looks very good. but i found that the alias analysis is not as good as expected. the problem seems to be the codegenprepare pass. GEP instructions are lowered to integer calculations (e.g. ptrtoint, add, inttoptr). this causes the (basic) alias analysis to answer MayAlias for most queries. this is also a problem for the DAG combiner, when the -combiner-global-alias-analysis switch is given to llc. any ideas how to handle this? florian
On Fri, Jun 15, 2007 at 04:16:57PM +0200, Florian Brandner wrote:> hi, > > > Florian Brandner wrote: > > Dan Gohman wrote: > >> On Wed, May 23, 2007 at 12:23:38AM -0700, Chris Lattner wrote: > >>> Right. The original Value*'s are preserved in the DAG, but dropped when > >>> MachineInstrs are created. We could add a machineoperand to capture this > >>> Value* if desired. > >> Another benefit of keeping the original Value*'s (and offsets) around is it > >> would provide more information that could be used for verbose asm output > >> and MachineInstr-level dumps, which would be quite nice. > >> > > > > i'll do this and post a patch, unless someone else is already working on > > this. > > > > i have extended the DAG instruction selector and scheduler to preserve > Value*'s. the values are attached to machine instructions as a separate > operand list (at least for now). for now this looks very good.Cool!> but i found that the alias analysis is not as good as expected. the > problem seems to be the codegenprepare pass. GEP instructions are > lowered to integer calculations (e.g. ptrtoint, add, inttoptr). this > causes the (basic) alias analysis to answer MayAlias for most queries. > > this is also a problem for the DAG combiner, when the > -combiner-global-alias-analysis switch is given to llc. > > any ideas how to handle this?I don't have any that are both easy and clean :-/. It probably wouldn't be difficult to teach the basic alias analysis how to dig past adds and casts to find base expressions. Or, make the CodeGenPrepare pass use getelementptrs directly instead of expanding addressing into integer operations. Or maybe instcombine could be run after CodeGenPrepare so it could fold the integer operations into getelementptrs? I think the long-term solution is to teach the SelectionDAG framework how to look beyond basic-block boundaries so that CodeGenPrepare doesn't have to do this de-hoisting of addressing. It also might make sense to write a SCEV-based AliasAnalysis some day. Dan -- Dan Gohman, Cray Inc.
On Jun 18, 2007, at 8:27 AM, Dan Gohman wrote:> On Fri, Jun 15, 2007 at 04:16:57PM +0200, Florian Brandner wrote: >> hi, >> >> >> Florian Brandner wrote: >>> Dan Gohman wrote: >>>> On Wed, May 23, 2007 at 12:23:38AM -0700, Chris Lattner wrote: >>>>> Right. The original Value*'s are preserved in the DAG, but >>>>> dropped when >>>>> MachineInstrs are created. We could add a machineoperand to >>>>> capture this >>>>> Value* if desired. >>>> Another benefit of keeping the original Value*'s (and offsets) >>>> around is it >>>> would provide more information that could be used for verbose >>>> asm output >>>> and MachineInstr-level dumps, which would be quite nice. >>>> >>> >>> i'll do this and post a patch, unless someone else is already >>> working on >>> this. >>> >> >> i have extended the DAG instruction selector and scheduler to >> preserve >> Value*'s. the values are attached to machine instructions as a >> separate >> operand list (at least for now). for now this looks very good. > > Cool! > >> but i found that the alias analysis is not as good as expected. the >> problem seems to be the codegenprepare pass. GEP instructions are >> lowered to integer calculations (e.g. ptrtoint, add, inttoptr). this >> causes the (basic) alias analysis to answer MayAlias for most >> queries. >> >> this is also a problem for the DAG combiner, when the >> -combiner-global-alias-analysis switch is given to llc. >> >> any ideas how to handle this? > > I don't have any that are both easy and clean :-/. > > It probably wouldn't be difficult to teach the basic alias analysis > how > to dig past adds and casts to find base expressions. Or, make theI think this is very much doable and would provide much immediate benefit. It's not a trivial task. We have to make sure DAG combiner and legalizer do not muck up alias information (among other challenges).> CodeGenPrepare pass use getelementptrs directly instead of expanding > addressing into integer operations. Or maybe instcombine could be run > after CodeGenPrepare so it could fold the integer operations into > getelementptrs? > > I think the long-term solution is to teach the SelectionDAG framework > how to look beyond basic-block boundaries so that CodeGenPrepare > doesn't > have to do this de-hoisting of addressing.Whole-function isel is being considered. No immediate plan yet though. Evan> > It also might make sense to write a SCEV-based AliasAnalysis some day. > > Dan > > -- > Dan Gohman, Cray Inc. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Fri, 15 Jun 2007, Florian Brandner wrote:> i have extended the DAG instruction selector and scheduler to preserve > Value*'s. the values are attached to machine instructions as a separate > operand list (at least for now). for now this looks very good. > > but i found that the alias analysis is not as good as expected. the > problem seems to be the codegenprepare pass. GEP instructions are > lowered to integer calculations (e.g. ptrtoint, add, inttoptr). this > causes the (basic) alias analysis to answer MayAlias for most queries.cool!> this is also a problem for the DAG combiner, when the > -combiner-global-alias-analysis switch is given to llc. > > any ideas how to handle this?Probably the best way is to enhance the LSR pass to insert GEP instructions instead of pointer arithmetic. For example, turn this: for (int i = 0...; ++i) A[i] = 0; into the equivalent of this: for (int i = 0, *p = &A[0]; ...; ++i, ++p) *p = 0; Inside the loop, this turns into a: next = getelementptr int* prev, 1 instead of a "cast, add 4, cast" sequence. -Chris -- http://nondot.org/sabre/ http://llvm.org/
On Mon, 18 Jun 2007, Dan Gohman wrote:> It probably wouldn't be difficult to teach the basic alias analysis how > to dig past adds and casts to find base expressions. Or, make the > CodeGenPrepare pass use getelementptrs directly instead of expanding > addressing into integer operations. Or maybe instcombine could be run > after CodeGenPrepare so it could fold the integer operations into > getelementptrs?Running instcombine is probably a bad idea, because it makes all sorts of transformations (e.g. constant folding casts) that can undo things carefully done by codegenprepare and lsr.> I think the long-term solution is to teach the SelectionDAG framework > how to look beyond basic-block boundaries so that CodeGenPrepare doesn't > have to do this de-hoisting of addressing.yes yes yes, absolutely.> It also might make sense to write a SCEV-based AliasAnalysis some day.That would be interesting as well, we could even hook dependence analysis up to it so that we could prove A[i] and A[j] don't alias etc. -Chris -- http://nondot.org/sabre/ http://llvm.org/
Florian Brandner
2007-Jul-23 12:19 UTC
[LLVMdev] alias information on machine instructions
hi, i know it took a while, but here is a patch that adds a list of source values to machine instructions. i modified the DAGISelEmiter to automatically catch regular loads/stores. custom instructions and loads/stores rewritten by the lowering pass are not automatically captured. during the instruction selection a source value operand is added to the DAG for patterns matching a load/store. after the scheduling these additional operands are added to the machine instruction automatically. one can add special source values for spills, using the machine instruction builder. i'm not to happy about the representation of the source values in the selection DAG. i would like to use a new SelectionDAG node, which then distinguishes between reads and writes, and adds additional information on the memory access. but so far the current scheme works fine. i've testet all this for our backend only, which is not public. i do not know how much has to be done to integrate this with the other, e.g., the x86, targets. does any of the other targets rewrite loads/stores during lowering? any comments how to integrate this into llvm, and how to proceed to get the alias analysis working after the codegen prepare pass? florian Florian Brandner wrote:> hi, > > > Florian Brandner wrote: >> Dan Gohman wrote: >>> On Wed, May 23, 2007 at 12:23:38AM -0700, Chris Lattner wrote: >>>> Right. The original Value*'s are preserved in the DAG, but dropped when >>>> MachineInstrs are created. We could add a machineoperand to capture this >>>> Value* if desired. >>> Another benefit of keeping the original Value*'s (and offsets) around is it >>> would provide more information that could be used for verbose asm output >>> and MachineInstr-level dumps, which would be quite nice. >>> >> i'll do this and post a patch, unless someone else is already working on >> this. >> > > i have extended the DAG instruction selector and scheduler to preserve > Value*'s. the values are attached to machine instructions as a separate > operand list (at least for now). for now this looks very good. > > but i found that the alias analysis is not as good as expected. the > problem seems to be the codegenprepare pass. GEP instructions are > lowered to integer calculations (e.g. ptrtoint, add, inttoptr). this > causes the (basic) alias analysis to answer MayAlias for most queries. > > this is also a problem for the DAG combiner, when the > -combiner-global-alias-analysis switch is given to llc. > > any ideas how to handle this? > florian > > > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-- Brandner Florian CD Laboratory - Compilation Techniques for Embedded Processors Institut für Computersprachen E185/1 Technische Universität Wien Argentinierstraße 8 / 185 A-1040 Wien, Austria Tel.: (+431) 58801-58521 E-Mail: brandner at complang.tuwien.ac.at -------------- next part -------------- A non-text attachment was scrubbed... Name: minstr_svops.patch Type: text/x-patch Size: 15517 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070723/a8204901/attachment.bin>
On Mon, Jul 23, 2007 at 02:19:38PM +0200, Florian Brandner wrote:> hi, > > i know it took a while, but here is a patch that adds a list of source > values to machine instructions.Cool!> i've testet all this for our backend only, which is not public. i do not > know how much has to be done to integrate this with the other, e.g., the > x86, targets. does any of the other targets rewrite loads/stores during > lowering?I tried out your patch on x86 and it didn't appear to need any special changes. With this code: define i32 @foo(i32* %p) { %q = getelementptr i32* %p, i32 17 %r = load i32* %q %s = add i32 %r, 10 ret i32 %s } The llc -march=x86 -print-machineinstrs output looks like this: : 0x8a99fc8, LLVM BB @0x8a94998, ID#0: %reg1024 = MOV32ri 10 SV:0 %reg1025 = MOV32rm <fi#-1>, 1, %NOREG, 0 SV:1[??] %reg1026 = ADD32rm %reg1024, %reg1025, 1, %NOREG, 68 SV:1[q] %EAX = MOV32rr %reg1026 SV:0 RET SV:0 (For those following along, the SV:1[??] and SV:1[q] are the new parts here). For the [??], it looks like the IsFrameIndex isn't getting set for the first instruction there. A few quick comments on specific parts of the patch that I noticed so far:> + TargetSrcValue,I'm curious why you added a new node kind, TargetSrcValue, instead of just using the existing SRCVALUE.> + else if (MRO.SrcValue && !MRO.SrcValue->getName().empty()) > + OS << "[" << MRO.SrcValue->getName() << "]";This code should also print the SVOffset value.> + SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain, > + SDOperand Ptr, SDOperand SV);This is code that was deleted from the LLVM trunk recently; it looks like it shouldn't be included in this patch. Dan -- Dan Gohman, Cray Inc.