[LLVMdev] Inliner that does not destroy splitted cold edges

[Carl-Philip Hänsch]

Here I will introduce my idea of a inliner that can handle splitting cold
edge as well:
My idea is to use the inlined function, but inline from the uninlined
function.

1. Do normal optimizations without inlining
2. Split the cold edges into other functions
3. Copy each function @xyz to @xyz.i (or other name that does not clash)
and mark @xyz with 'inlines @xyz.i'
    ==> this needs an identifier to mark the shadow function for each
function
  All other operations are performed on @xyz. @xyz.i will contain the
uninlined version
4. Each function @xyz can now inline its contained functions @abc while you
don't inline @abc directly, but @abc.i
5. When a function @xyz becomes shorter than @xyz.i, the inline remark and
the non-inlined
6. After everything is inlined, new cold edges can appear. They can now be
split again. New optimizations are possible.
7. Functions that call functions containing these cold edges can now inline
them. These functions can be optimized again.

Example: (function signatures in LLVM, content in PSEUDO-Code)

Starting point:
---------------

define i32 @findNumber() {
  for i = 0 to 10000
    if @numberFits(i) then
      MYSTUFFINTHEFUNCTION
      THATISREALLYCOLD
    end
  end
}

define i1 @numberFits() {
  ret DO_A_SIMPLE_PRIME_TEST
}

After 1 and 2:
--------------

define i32 @findNumber() {
  for i = 0 to 10000
    if @numberFits(i) then
      call @findNumber.c(i)
    end
  end
}

define void @findNumber.c(i32 i) {
  MYSTUFFINTHEFUNCTION
  THATISREALLYCOLD
}

define i1 @numberFits(i32 i) {
  ret DO_A_SIMPLE_PRIME_TEST_i
}

After 3 and 4 (5-7 do not apply here):
--------------------------------------

define i32 @findNumber() inlines @findNumber.i {
  for i = 0 to 10000
    if DO_A_SIMPLE_PRIME_TEST_i then
      call @findNumber.c(i)
    end
  end
}
define i32 @findNumber.i() {
  for i = 0 to 10000
    if @numberFits(i) then
      call @findNumber.c(i)
    end
  end
}

define void @findNumber.c(i32 i) {
  MYSTUFFINTHEFUNCTION
  THATISREALLYCOLD
}

define i1 @numberFits(i32 i) {
  ret DO_A_SIMPLE_PRIME_TEST_i
}

The linker can now strip all 'inlines' dependencies
---------------------------------------------------


define i32 @findNumber() {
  for i = 0 to 10000
    if DO_A_SIMPLE_PRIME_TEST_i then
      call @findNumber.c(i)
    end
  end
}

define void @findNumber.c(i32 i) {
  MYSTUFFINTHEFUNCTION
  THATISREALLYCOLD
}


What do you think about the idea?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111112/0acabc6b/attachment.html>