effekt-lang
Normalizer bug: a binding "tmp_XXX" is used but not defined
Seems to be an optimization issue (that's why I'm using flag and a random boolean, because otherwise the bug isn't triggered):
import random
interface Suspend {
def suspend[T](block: (T => Unit at {}) => Unit at {}): T
}
def handleSuspend(block: => Unit / Suspend at {}) = try block() with Suspend {
def suspend[T](block2) = block2(box resume)
}
def foo(flag: Bool): Unit = {
handleSuspend(box { do suspend[=> Unit at {}](box { resume =>
def r() = resume(box{}) // inlining this makes the bug not trigger
if (flag) (box r)() else resume(box r)
})()
})
}
def test() = minstd(2) { foo(randomBool()) }
Hi, thanks for the report.
This seems to be an optimiser issue, as it seems to not crash on both LLVM and JS when the --no-optimize flag is on.
Otherwise, LLVM shows a similar message: [error] Could not find info for free variable tmp.
Note that this will likely only be addressed once the ongoing rewrite of the Normalizer pass is finished.
EDIT: Yeah, if you comment out just this line (and fix the next one), everything compiles: https://github.com/effekt-lang/effekt/blob/ed2651c5a1a3e9e9d8992f4ee35a68edf94069f0/effekt/shared/src/main/scala/effekt/core/optimizer/Optimizer.scala#L40
I find it interesting that swapping out the randomBool for an extern / for if (random() > 0.5) true else false seems to make it compile again, the dependency on the random module seems to be doing some rather heavy lifting here. 🤔
This is as far as I've been able to get it while inlining random:
interface Suspend {
def suspend[T](block: (T => Unit at {}) => Unit at {}): T
}
def handleSuspend(block: => Unit / Suspend at {}) = try block() with Suspend {
def suspend[T](block2) = block2(box resume)
}
def foo(flag: Bool): Unit = {
handleSuspend(box { do suspend[=> Unit at {}](box { resume =>
def r() = resume(box{}) // inlining this makes the bug not trigger
if (flag) (box r)() else resume(box r)
})()
})
}
effect random(): Bool
def main() = {
var next = box { true }
next = box { false } // this seems to be necessary in order to trigger the bug [?]
try { foo(do random()) } with random { resume(next()) }
}
the misoptimized IR is has this clearly bad tmp_ binding:
def main_5568() = {
var next_5578 = (box { () =>
return true
});
next_5578 := (box { () =>
return false
});
let s_6209 = !next_5578;
def tmp_6334 = (unbox s_6209)
val v_r_6206: Bool_406 = tmp_6334();
if (v_r_6206) {
return ()
} else {
tmp_6176((box { () =>
return ()
}))
}
}
while the unoptimized IR does not
interface Suspend_5562 {
suspend_5571: [T_5569](((T_5569) => Unit_395 at {}) => Unit_395 at {}) => T_5569
}
interface random_5567 {
random_5577: () => Bool_406
}
def handleSuspend_5564(block_5563: (){Suspend_5590: Suspend_5562} => Unit_395 at {}) = {
val v_r_5849: Unit_395 = reset { {p_5844} =>
def Suspend_5843 = new Suspend_5562 {
def suspend_5571[T_5572](block2_5573: ((T_5572) => Unit_395 at {}) => Unit_395 at {}) =
shift(p_5844) { {k_5845} =>
def resume_5574(a_5846: T_5572) = resume(k_5845) {
return a_5846
}
val v_r_5847: Unit_395 = (unbox block2_5573)((box resume_5574));
return v_r_5847
}
}
val v_r_5848: Unit_395 = (unbox block_5563){Suspend_5843};
return v_r_5848
};
return v_r_5849
};
def foo_5566(flag_5565: Bool_406) = {
val v_r_5857: Unit_395 = handleSuspend_5564((box { {Suspend_5850} =>
val v_r_5855: () => Unit_395 at {} = Suspend_5850.suspend[() => Unit_395 at {}]((box { (resume_5575: (() => Unit_395 at {}) => Unit_395 at {}) =>
def r_5576() = {
val v_r_5851: Unit_395 = (unbox resume_5575)((box { () =>
return ()
}));
return v_r_5851
}
val v_r_5854: Unit_395 = if (flag_5565) {
val v_r_5852: Unit_395 = (unbox (box r_5576))();
return v_r_5852
} else {
val v_r_5853: Unit_395 = (unbox resume_5575)((box r_5576));
return v_r_5853
};
return v_r_5854
}));
val v_r_5856: Unit_395 = (unbox v_r_5855)();
return v_r_5856
}));
return v_r_5857
};
def main_5568() = {
val v_r_5834: () => Bool_406 at {} = return (box { () =>
return true
});
var next_5578 = v_r_5834;
{
val v_r_5861: Unit_395 = {
next_5578 := (box { () =>
return false
});
return ()
};
return ()
};
val v_r_5860: Unit_395 = reset { {p_5836} =>
def random_5835 = new random_5567 {
def random_5577() =
shift(p_5836) { {k_5839} =>
def resume_5579(a_5840: Bool_406) = resume(k_5839) {
return a_5840
}
val v_r_5838: () => Bool_406 at {} = {
let s_5837 = !next_5578;
return s_5837
};
val v_r_5841: Bool_406 = (unbox v_r_5838)();
val v_r_5842: Unit_395 = resume_5579(v_r_5841);
return v_r_5842
}
}
val v_r_5858: Bool_406 = random_5835.random();
val v_r_5859: Unit_395 = foo_5566(v_r_5858);
return v_r_5859
};
return v_r_5860
}
When I do optimise, but use --max-inline-size 0, the Core IR is already bad (see !!!)
def main_5568() = {
var next_5578 = (box { () =>
return true
});
next_5578 := (box { () =>
return false
});
let s_6215 = !next_5578;
def tmp_6345 = (unbox s_6215)
val v_r_6212: Bool_406 = tmp_6345();
reset { {p_6339} =>
val v_r_6334: () => Unit_395 at {} = shift(p_6339) { {k_6335} =>
def r_6338() = tmp_6178((box { () => // !!!
return ()
}))
def k_6337(v_r_6336: Unit_395) = return v_r_6336
if (v_r_6212) {
val v_r_6332: Unit_395 = resume(k_6335) {
return (box { () =>
return ()
})
};
k_6337(v_r_6332)
} else {
val v_r_6333: Unit_395 = resume(k_6335) {
return (box r_6338)
};
k_6337(v_r_6333)
}
};
def tmp_6351 = (unbox v_r_6334)
tmp_6351()
}
}
I keep running into this randomly. Will try with --no-optimize, but it's annoying since optimizations are useful to showcase sometimes, but alas.
EDIT: It thankfully works with --no-optimize, and compilation is insanely fast in comparison! I think my programs are doing too much crazy stuff that the optimizer takes a while to run, while just running the program outright takes way less time than the compilation itself lol
This is a quite subtle error. It seems it is caused by the renaming here
https://github.com/effekt-lang/effekt/blob/8c74342451594bb9aea7235c14027c394c6f404e/effekt/shared/src/main/scala/effekt/core/optimizer/Normalizer.scala#L436
in Normalizer.
The issue is that we rename bound variables to guarantee uniqueness. However, we need to copy the usage information from the old names to the new freshened ones.
Now the real issue seems to be:
One Id (11150) shows up multiple times, violating Barendregdt:
{ (){Suspend_8368 @ Suspend_8369: Suspend_8336} =>
let tmp_11156 = box {} { (resume_8351: (() => Unit at {}) => Unit at {}) =>
def r_8352() = {
def tmp_11150 = (unbox resume_8351: (() => Unit at {}) => Unit at {})
let tmp_11151 = box {} { () =>
return ()
}
tmp_11150: (() => Unit at {}) => Unit @ {}(tmp_11151: () => Unit at {})
}
def k_11509(v_r_8397: Unit) = {
return v_r_8397: Unit
}
if (flag_8340: Bool) {
let tmp_11152 = box {} r_8352: () => Unit @ {}
def tmp_11153() = {
def tmp_11150 = (unbox resume_8351: (() => Unit at {}) => Unit at {})
let tmp_11151 = box {} { () =>
return ()
}
tmp_11150: (() => Unit at {}) => Unit @ {}(tmp_11151: () => Unit at {})
}
def tmp_11507 = (unbox resume_8351: (() => Unit at {}) => Unit at {})
let tmp_11508 = box {} { () =>
return ()
}
tmp_11507: (() => Unit at {}) => Unit @ {}(tmp_11508: () => Unit at {})
} else {
def tmp_11154 = (unbox resume_8351: (() => Unit at {}) => Unit at {})
let tmp_11155 = box {} r_8352: () => Unit @ {}
tmp_11154: (() => Unit at {}) => Unit @ {}(tmp_11155: () => Unit at {})
}
}
val v_r_8398 = {
Suspend_8368: Suspend_8336 @ {Suspend_8369}.suspend_8345: ['T_8343]((('T_8343) => Unit at {}) => Unit at {}) => 'T_8343[() => Unit at {}](tmp_11156: ((() => Unit at {}) => Unit at {}) => Unit at {})
};
def tmp_11157 = (unbox v_r_8398: () => Unit at {})
tmp_11157: () => Unit @ {}()
}
When renamer traverses it, for each occurence we come up with a new fresh id. This line here happily overwrites the previous mapping from old to new name, effectively forgetting the usage information and assuming it is unused:
https://github.com/effekt-lang/effekt/blob/8c74342451594bb9aea7235c14027c394c6f404e/effekt/shared/src/main/scala/effekt/core/Renamer.scala#L35
As a fix I now map new_id to old_id instead of the other way around. This way we do not require Barendregdt in the input to Renamer, which seems like an easier fix for now than actually establishing Barendregdt :)