Do not inline into passive positions

[phischu]

Consider the following program:

interface Fail {
  def fail(): Nothing
}

def choice(n: Int): Int / Fail =
  if (n < 1) {
    do fail() match {}
  } else {
    choice(n - 1)
  }

def run(n: Int) =
  try {
    val i = choice(n)
    val j = choice(i - 1)
    (i + j)
  } with Fail {
    def fail() = 0
  }

def main() = println(run(10))

I contains a loop choice which can not and will not be inlined. After optimization we produce the following Core:

interface Fail {
  fail: () => Nothing
}

def choice(n: Int){Fail} =
  if (infixLt(n, 1)) {
    val v_r: Nothing = Fail.fail();
    v_r match {
    }
  } else {
    choice(infixSub(n, 1), Fail)
  }

def main() =
  let v_r = run {reset { (){p} =>
    val i: Int = choice(10, new Fail {
      def fail() =
        shift(p) { (){k} => 0 }
    });
    val j: Int = choice(infixSub(i, 1), new Fail {
      def fail() =
        shift(p) { (){k} => 0 }
    });
    infixAdd(i, j)
  }};
  let v_r = println1(show(v_r))
  v_r

The code for new Fail { ... } is duplicated, which also leads to duplicate allocations. We should not inline at all, only when there is an immediate redex. After this, the program should be:

interface Fail {
  fail: () => Nothing
}

def choice(n: Int){Fail} =
  if (infixLt(n, 1)) {
    val v_r: Nothing = Fail.fail();
    v_r match {
    }
  } else {
    choice(infixSub(n, 1), Fail)
  }

def main() =
  let v_r = run {reset { (){p} =>
    def Fail = new Fail {
      def fail() =
        shift(p) { (){k} => 0 }
    };
    val i: Int = choice(10, Fail);
    val j: Int = choice(infixSub(i, 1), Fail);
    infixAdd(i, j)
  }};
  let v_r = println1(show(v_r))
  v_r

In some cases this could improve performance.

[serkm]

I think the key step for 2 is turning this:

def choice(n: Int){Fail} =
  if (infixLt(n, 1)) {
    val v_r: Nothing = Fail.fail();
    v_r match {
    }
  } else {
    choice(infixSub(n, 1), Fail)
  }

into this:

def choice(n: Int){Fail} = {
  def choice_helper(n: Int) = {
    if (infixLt(n, 1)) {
      val v_r: Nothing = Fail.fail();
      v_r match {
      }
    } else {
      choice_helper(infixSub(n, 1))
    }
  }
  choice_helper(n)
}

That would allow choice to be inlined, which then would make inlining Fail.fail() possible.

[serkm]

I did this manually on countdown.effekt and it helps a lot.

[phischu]

I have splitted the static argument transformation part into #690.

You are absolutely right about choice_helper (usually called something with worker).

@marvinborner wants to take on #690.