[LLVMdev] alias analysis in backend

[Hal Finkel]

----- Original Message -----
> From: "Andrew Trick" <atrick at apple.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Jonas Paulsson" <jonas.paulsson at ericsson.com>, llvmdev at cs.uiuc.edu
> Sent: Thursday, April 18, 2013 2:33:52 AM
> Subject: Re: [LLVMdev] alias analysis in backend
> 
> 
> On Apr 17, 2013, at 2:33 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> > ----- Original Message -----
> >> From: "Jonas Paulsson" <jonas.paulsson at ericsson.com>
> >> To: "Hal Finkel" <hfinkel at anl.gov>
> >> Cc: llvmdev at cs.uiuc.edu
> >> Sent: Wednesday, April 17, 2013 12:22:49 AM
> >> Subject: RE: [LLVMdev] alias analysis in backend
> >> 
> >> Hi Hal,
> >> 
> >> Thanks. How about a symbol with two different immediate offsets -
> >> the
> >> Value* would be the same, right? I don't see how
> >> AliasAnalysis::Location would handle this... And
> >> BasicAliasAnalysis
> >> does
> >> 
> >> if (V1 == V2) return MustAlias;
> >> 
> >> , so I'm not sure how this would be done .. ?
> > 
> > If you run with -enable-misched -enable-aa-sched-mi
> > 
> > then you'll get this logic from the end of MIsNeedChainEdge:
> > 
> >  // The following interface to AA is fashioned after
> >  DAGCombiner::isAlias
> >  // and operates with MachineMemOperand offset with some important
> >  // assumptions:
> >  //   - LLVM fundamentally assumes flat address spaces.
> >  //   - MachineOperand offset can *only* result from legalization
> >  and
> >  //     cannot affect queries other than the trivial case of
> >  overlap
> >  //     checking.
> >  //   - These offsets never wrap and never step outside
> >  //     of allocated objects.
> >  //   - There should never be any negative offsets here.
> >  //
> > ...
> > 
> >  int64_t MinOffset = std::min(MMOa->getOffset(),
> >  MMOb->getOffset());
> >  int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() -
> >  MinOffset;
> >  int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() -
> >  MinOffset;
> > 
> >  AliasAnalysis::AliasResult AAResult = AA->alias(
> >  AliasAnalysis::Location(MMOa->getValue(), Overlapa,
> >                          MMOa->getTBAAInfo()),
> >  AliasAnalysis::Location(MMOb->getValue(), Overlapb,
> >                          MMOb->getTBAAInfo()));
> > 
> >  return (AAResult != AliasAnalysis::NoAlias);
> 
> This conservatively compensates for loads/stores that were split into
> narrower accesses during lowering, so doesn't help Jonas.
> 
> The MachineMemOperand offset is used differently for
> FixedFrameIndices, but we don't currently special case it here to
> disambiguate them.

Thanks, I did not understand that. I thought that each different stack slot had its own frame index, or does that only apply to callee-saved and spill slots?

 -Hal

> The general problem is that we don't have a
>  CodeGen-level alias analysis API yet. It looks like this particular
> case could be fixed with an easy patch though, unless I'm missing
> something.
> 
> -Andy
> 
> >>> -----Original Message-----
> >>> From: Hal Finkel [mailto:hfinkel at anl.gov]
> >>> Sent: Tuesday, April 16, 2013 7:35 PM
> >>> To: Jonas Paulsson
> >>> Cc: llvmdev at cs.uiuc.edu
> >>> Subject: Re: [LLVMdev] alias analysis in backend
> >>> 
> >>> ----- Original Message -----
> >>>> From: "Jonas Paulsson" <jonas.paulsson at ericsson.com>
> >>>> To: llvmdev at cs.uiuc.edu
> >>>> Sent: Tuesday, April 16, 2013 11:24:36 AM
> >>>> Subject: [LLVMdev] alias analysis in backend
> >>>> 
> >>>> 
> >>>> 
> >>>> 
> >>>> 
> >>>> Hi,
> >>>> 
> >>>> 
> >>>> 
> >>>> I would like to implement alias analysis in my backend. I would
> >>>> like
> >>>> to for example get the result that two stack-accesses with
> >>>> different
> >>>> offsets (indexes), would return noAlias. However, I'm somewhat
> >>>> confused as there is no notion of offset for the Location
> >>>> object.
> >>>> 
> >>>> 
> >>>> 
> >>>> I would also like to call ScheduleDAGInstr::buildSchedGraph()
> >>>> with
> >>>> this AliasAnalysis and have MIsNeedsChainEdge() return false in
> >>>> this
> >>>> case.
> >>>> 
> >>>> 
> >>>> 
> >>>> What should I do? Adding a MemoryOperand to such an instruction
> >>>> seems
> >>>> right, but it doesn't seem to fit quite. What Value would be
> >>>> referenced?
> >>> 
> >>> I think that they should have pseudo-source values, see:
> >>> include/llvm/CodeGen/PseudoSourceValue.h
> >>> 
> >>> I was under the impression that different pseudo source values
> >>> from
> >>> different frame indices already have this no-alias property. If
> >>> they
> >>> don't, then this seems like a nice general improvement that would
> >>> benefit
> >>> all backends.
> >>> 
> >>> -Hal
> >>> 
> >>>> BasicAliasAnalysis returns MustAlias for the same Value,
> >>>> e g 'Stack'.
> >>>> 
> >>>> 
> >>>> 
> >>>> Should I implement a target AliasAnalysis, perhaps derived from
> >>>> BasicAliasAnalysis, and make it required for my pass that will
> >>>> be
> >>>> using it?
> >>>> 
> >>>> 
> >>>> 
> >>>> If not, could I make this work with BasicAliasAnalysis by adding
> >>>> the
> >>>> right memory operands?
> >>>> 
> >>>> 
> >>>> 
> >>>> Thanks,
> >>>> 
> >>>> 
> >>>> 
> >>>> Jonas Paulsson
> >>>> 
> >>>> 
> >>>> 
> >>>> 
> >>>> 
> >>>> 
> >>>> _______________________________________________
> >>>> LLVM Developers mailing list
> >>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >>>> 
> >> 
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
>