diff options
14 files changed, 94 insertions, 27 deletions
diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 4d3e4563c1e..2455ff2b59e 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -402,7 +402,9 @@ public: /// Interchange OuterLoop and InnerLoop. bool transform(); - void restructureLoops(Loop *InnerLoop, Loop *OuterLoop); + void restructureLoops(Loop *NewInner, Loop *NewOuter, + BasicBlock *OrigInnerPreHeader, + BasicBlock *OrigOuterPreHeader); void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop); private: @@ -453,6 +455,7 @@ struct LoopInterchange : public FunctionPass { AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); AU.addPreserved<DominatorTreeWrapperPass>(); + AU.addPreserved<LoopInfoWrapperPass>(); } bool runOnFunction(Function &F) override { @@ -1153,23 +1156,77 @@ void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop, llvm_unreachable("Couldn't find loop"); } -void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop, - Loop *OuterLoop) { +/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the +/// new inner and outer loop after interchanging: NewInner is the original +/// outer loop and NewOuter is the original inner loop. +/// +/// Before interchanging, we have the following structure +/// Outer preheader +// Outer header +// Inner preheader +// Inner header +// Inner body +// Inner latch +// outer bbs +// Outer latch +// +// After interchanging: +// Inner preheader +// Inner header +// Outer preheader +// Outer header +// Inner body +// outer bbs +// Outer latch +// Inner latch +void LoopInterchangeTransform::restructureLoops( + Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader, + BasicBlock *OrigOuterPreHeader) { Loop *OuterLoopParent = OuterLoop->getParentLoop(); + // The original inner loop preheader moves from the new inner loop to + // the parent loop, if there is one. + NewInner->removeBlockFromLoop(OrigInnerPreHeader); + LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent); + + // Switch the loop levels. if (OuterLoopParent) { // Remove the loop from its parent loop. - removeChildLoop(OuterLoopParent, OuterLoop); - removeChildLoop(OuterLoop, InnerLoop); - OuterLoopParent->addChildLoop(InnerLoop); + removeChildLoop(OuterLoopParent, NewInner); + removeChildLoop(NewInner, NewOuter); + OuterLoopParent->addChildLoop(NewOuter); } else { - removeChildLoop(OuterLoop, InnerLoop); - LI->changeTopLevelLoop(OuterLoop, InnerLoop); + removeChildLoop(NewInner, NewOuter); + LI->changeTopLevelLoop(NewInner, NewOuter); + } + while (!NewOuter->empty()) + NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin())); + NewOuter->addChildLoop(NewInner); + + // BBs from the original inner loop. + SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks()); + + // Add BBs from the original outer loop to the original inner loop (excluding + // BBs already in inner loop) + for (BasicBlock *BB : NewInner->blocks()) + if (LI->getLoopFor(BB) == NewInner) + NewOuter->addBlockEntry(BB); + + // Now remove inner loop header and latch from the new inner loop and move + // other BBs (the loop body) to the new inner loop. + BasicBlock *OuterHeader = NewOuter->getHeader(); + BasicBlock *OuterLatch = NewOuter->getLoopLatch(); + for (BasicBlock *BB : OrigInnerBBs) { + // Remove the new outer loop header and latch from the new inner loop. + if (BB == OuterHeader || BB == OuterLatch) + NewInner->removeBlockFromLoop(BB); + else + LI->changeLoopFor(BB, NewInner); } - while (!InnerLoop->empty()) - OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin())); - - InnerLoop->addChildLoop(OuterLoop); + // The preheader of the original outer loop becomes part of the new + // outer loop. + NewOuter->addBlockEntry(OrigOuterPreHeader); + LI->changeLoopFor(OrigOuterPreHeader, NewOuter); } bool LoopInterchangeTransform::transform() { @@ -1212,7 +1269,6 @@ bool LoopInterchangeTransform::transform() { return false; } - restructureLoops(InnerLoop, OuterLoop); return true; } @@ -1382,6 +1438,9 @@ bool LoopInterchangeTransform::adjustLoopBranches() { updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch); DT->applyUpdates(DTUpdates); + restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader, + OuterLoopPreHeader); + return true; } diff --git a/llvm/test/Transforms/LoopInterchange/call-instructions.ll b/llvm/test/Transforms/LoopInterchange/call-instructions.ll index c794fed824f..27182de2813 100644 --- a/llvm/test/Transforms/LoopInterchange/call-instructions.ll +++ b/llvm/test/Transforms/LoopInterchange/call-instructions.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t +; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t -verify-loop-info -verify-dom-info ; RUN: FileCheck --input-file=%t %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" diff --git a/llvm/test/Transforms/LoopInterchange/currentLimitation.ll b/llvm/test/Transforms/LoopInterchange/currentLimitation.ll index 90c46ba78b8..f644e043a78 100644 --- a/llvm/test/Transforms/LoopInterchange/currentLimitation.ll +++ b/llvm/test/Transforms/LoopInterchange/currentLimitation.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts -; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -S -debug 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll b/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll index caa27e8acc9..02a30f4c1f7 100644 --- a/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll +++ b/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts -; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -S -debug 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll b/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll index 698f6c308d0..3766c23173b 100644 --- a/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll +++ b/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -basicaa -da-delinearize -loop-interchange -verify-dom-info -S -pass-remarks=loop-interchange 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -da-delinearize -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -S -pass-remarks=loop-interchange 2>&1 | FileCheck %s @A10 = local_unnamed_addr global [3 x [3 x i32]] zeroinitializer, align 16 diff --git a/llvm/test/Transforms/LoopInterchange/interchange-no-deps.ll b/llvm/test/Transforms/LoopInterchange/interchange-no-deps.ll index 2ff3d4e322b..e737bab33aa 100644 --- a/llvm/test/Transforms/LoopInterchange/interchange-no-deps.ll +++ b/llvm/test/Transforms/LoopInterchange/interchange-no-deps.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -loop-interchange -simplifycfg -S -pass-remarks=loop-interchange 2>&1 | FileCheck %s +; RUN: opt < %s -loop-interchange -verify-dom-info -verify-loop-info -S \ +; RUN: -pass-remarks=loop-interchange 2>&1 | FileCheck %s ; CHECK: Loop interchanged with enclosing loop. ; no_deps_interchange just access a single nested array and can be interchange. diff --git a/llvm/test/Transforms/LoopInterchange/interchangeable.ll b/llvm/test/Transforms/LoopInterchange/interchangeable.ll index 437eae2e205..6b9f86dfd0b 100644 --- a/llvm/test/Transforms/LoopInterchange/interchangeable.ll +++ b/llvm/test/Transforms/LoopInterchange/interchangeable.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info -S | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll b/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll index 5b040042fc0..b19a4a4875b 100644 --- a/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll +++ b/llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll @@ -1,7 +1,8 @@ ; Test optimization remarks generated by the LoopInterchange pass. ; -; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-output=%t -pass-remarks-missed='loop-interchange' \ -; RUN: -pass-remarks='loop-interchange' -S +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -pass-remarks-output=%t -pass-remarks-missed='loop-interchange' \ +; RUN: -pass-remarks='loop-interchange' -S ; RUN: cat %t | FileCheck %s @A = common global [100 x [100 x i32]] zeroinitializer diff --git a/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll b/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll index 5cd2b586e3e..11010039f08 100644 --- a/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll +++ b/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts -; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -S -debug 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Transforms/LoopInterchange/not-interchanged-loop-nest-3.ll b/llvm/test/Transforms/LoopInterchange/not-interchanged-loop-nest-3.ll index b6a9826759c..7dfbe119537 100644 --- a/llvm/test/Transforms/LoopInterchange/not-interchanged-loop-nest-3.ll +++ b/llvm/test/Transforms/LoopInterchange/not-interchanged-loop-nest-3.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts -; RUN: opt < %s -basicaa -loop-interchange -S -debug 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -S -debug 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll b/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll index cf614ea9ce5..13f6e38914c 100644 --- a/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll +++ b/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts -; RUN: opt < %s -basicaa -loop-interchange -S -debug 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \ +; RUN: -S -debug 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Transforms/LoopInterchange/phi-ordering.ll b/llvm/test/Transforms/LoopInterchange/phi-ordering.ll index 2eb7949a82f..861313868ae 100644 --- a/llvm/test/Transforms/LoopInterchange/phi-ordering.ll +++ b/llvm/test/Transforms/LoopInterchange/phi-ordering.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -loop-interchange -verify-dom-info -S 2>&1 | FileCheck %s +; RUN: opt < %s -loop-interchange -verify-dom-info -verify-loop-info -S 2>&1 | FileCheck %s ;; Checks the order of the inner phi nodes does not cause havoc. ;; The inner loop has a reduction into c. The IV is not the first phi. diff --git a/llvm/test/Transforms/LoopInterchange/profitability.ll b/llvm/test/Transforms/LoopInterchange/profitability.ll index 2773ac4c451..ee4b7d50adb 100644 --- a/llvm/test/Transforms/LoopInterchange/profitability.ll +++ b/llvm/test/Transforms/LoopInterchange/profitability.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -loop-interchange -pass-remarks-output=%t \ +; RUN: opt < %s -loop-interchange -pass-remarks-output=%t -verify-dom-info -verify-loop-info \ ; RUN: -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange ; RUN: FileCheck -input-file %t %s diff --git a/llvm/test/Transforms/LoopInterchange/reductions.ll b/llvm/test/Transforms/LoopInterchange/reductions.ll index 9f823114198..ca37f7b271b 100644 --- a/llvm/test/Transforms/LoopInterchange/reductions.ll +++ b/llvm/test/Transforms/LoopInterchange/reductions.ll @@ -1,5 +1,5 @@ ; REQUIRES: asserts -; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s +; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info -S -debug 2>&1 | FileCheck %s @A = common global [500 x [500 x i32]] zeroinitializer @X = common global i32 0 |
