cloneLoopWithPreheader() currently only support innermost loop, and assert otherwise.
Consider using DenseMap.
[style] I like getting a reference that can be updated instead of another map lookup. I.e.
Loop *&NewLoop = LMap[CurLoop]; ... NewLoop = LI->AllocateLoop();
[serious] Since the iteration order of OrigLoop->getBlocks() is undefined, we might get a block that is nested in two loops without having visited the parent first, i.e. NewParentLoop would be null in this case.
Consider iterating over LoopInfo's loop tree before iterating over all block to ensure that the new loop structure has been created.