[LLVMdev] PATCH: Use size reduction -- wave2

[heisenbug]

On Apr 16, 2:13 am, Dan Gohman <goh... at apple.com> wrote:
> Hi Gabor,
>
> Can you provide performance data for this? I'd
> like to know what affect these changes have on
> compile time.

Hi Dan,

Unfortunately, no. I can feed you with some speculation, though,
see below.

The reason why I cannot do measurements (at the moment) is that
- I have no experience with performance measurements of llvm compile
time,
- I have no good test cases that would provide the data interesting
for you,
- I have no machine that can run Release-mode tests
  my PPC mac mini at home runs Tiger --> Xcode 2.4.1 is broken for
Release mode [1]
  I have access to a beefy Mac Pro, but it also miscompiles Release
for the same reason. Also it is an image-processing machine in
production, so I can only run "nice make ..."
  I have access to a Solaris 10 workstation, but I really do not want
to build llvm-gcc on this one. It also keeps my /home on NFS, which
has speed and quota problems.

But: It is very simple to do your measurements yourself (and I'd love
to hear the results!) :

   cd llvm
   svn switch http://llvm.org/svn/llvm-project/llvm/branches/ggreif/use-diet
.
   make

 rebuild llvm-gcc, etc.
 retest.

And now here is my educated speculation:
There are 2 things that became slower
1) Use::getUser()
2) Use::get/set due to tagging.

The former is seldom called:

$ find lib -name "*.cpp" | xargs grep "getUser(" | wc -l
      41

We could audit those to make sure that no unnecessary calls are done.
But the getUse() algorithm is not sooo inefficient, anyway.

The second is counterbalanced with a faster access to the Use object
in most cases:
  With exception of PHINode and SwitchInst, the getOperand() function
(if called on a specialized "this" pointer) does a "this"-relative
access instead of getting OperandList pointer first and going thru
that. This was the case before for fixed-arity instructions, but now
it applies to variadic ones too that cannot perform operand list
resizing.

Some things got faster, like
1) getOperand access on (say) CallInst is now fetching operands from
relative to "this". Also, there is no "new Use[n]" allocations (and
delete []) for these any more.
2) no need to maintain Use::U
3) data-cache related gains on smaller Use objects (not yet activated)

So, my idea is that these changes are performance neutral.

There are potentially more speedups to be realized:
- indexing operands in the decreasing direction eliminates the
getNumOperands() call in getOperand() for variadic arity instructions.
- shaving off (unneeded) operand related administrative members from
User.

I hope that this is interesting, but I'd like to ask anybody who is
comfortable with performance testing to help provide some hard
data :-)

Cheers,

    Gabor


[1] <http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-March/
013436.html>


>
> Thanks,
>
> Dan
>
> On Apr 15, 2008, at 3:32 PM, Gabor Greif wrote:
>
>
>
> > Hi All,
>
> > here comes the patch for the second wave of Use class size reduction.
>
> > I have included all the machinery that is needed, and it is
> > *active*. The User* inside of Use is even sometimes NULL,
> > but the algorithm is able to recover it.
> > If there is a non-null User* present, then I am
> > asserting that it equals the computed value.
>
> > I did not receive feedback for the algorithmic part yet,
> > so I assume, you are comfortable with it.
>
> > Unfortunately I had to introduce a new GlobalVariable::Create
> > mechanism (I hoped to have nailed all in wave 1, but life is cruel).
> > I will submit scripts for the easy conversion of external projects
> > like the last time.
>
> > I have split this review material into 3 files, corresponding to
> > - essential changes,
> > - related changes in .cpp files,
> > - collateral nitty-gritty, mostly mechanical stuff.
>
> > Outlook: The actual removal of the Use::U member
> > will happen in wave 3 after this stuff is merged to
> > trunk. I do not expect any problems.
> > Btw., I have already performed a test merge
> > and it also passes all tests (deja, clang, test-suite).
>
> > Cheers,
>
> >    Gabor
>
> > --------------------- STATS ------------------
> > ggreif$ ls -l wave2*
> > -rw-r--r--   1 ggreif  ggreif  79367 Apr 16 00:20 wave2-
> > essentials.diff
> > -rw-r--r--   1 ggreif  ggreif  51795 Apr 16 00:24 wave2-impl.diff
> > -rw-r--r--   1 ggreif  ggreif  25300 Apr 16 00:25 wave2-
> > nittygritty.diff
>
> > ggreif$ wc wave2*
> >    2189    9005   79367 wave2-essentials.diff
> >    1408    4793   51795 wave2-impl.diff
> >     521    1995   25300 wave2-nittygritty.diff
> >    4118   15793  156462 total
>
> > <wave2-essentials.diff><wave2-impl.diff><wave2-nittygritty.diff>
>