Index: lib/Transforms/Scalar/LoopSimplifyCFG.cpp =================================================================== --- lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -88,6 +88,7 @@ LoopInfo &LI; DominatorTree &DT; MemorySSAUpdater *MSSAU; + LoopBlocksDFS DFS; // Whether or not the current loop has irreducible CFG. bool HasIrreducibleCFG = false; @@ -173,7 +174,6 @@ /// Fill all information about status of blocks and exits of the current loop /// if constant folding of all branches will be done. void analyze() { - LoopBlocksDFS DFS(&L); DFS.perform(&LI); assert(DFS.isComplete() && "DFS is expected to be finished"); @@ -454,10 +454,106 @@ } } + /// If some blocks haven't been removed, we need to update their loop info. + /// We iterate over these block and find the outer loop which is still + /// reachable from these blocks and assigns this loop to this block. It also + /// handles subloops all together. + bool updateLoopInfo() { + // If there is no blocks that are no longer in current loop, nothing to do. + if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() == + L.getNumBlocks()) + return false; + + assert(DFS.isComplete() && "Must be!"); + SmallPtrSet Visited; + // Traverse blocks in Postorder to preserve the following invariant: by the + // moment when we process a block, all its successors already have correct + // loops set. + for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) { + BasicBlock *BB = *I; + // If this block stayed in current loop, skip it. + if (BlocksInLoopAfterFolding.count(BB)) + continue; + + // If the block is already processed, skip it. + if (Visited.count(BB)) + continue; + + // The entire child subloop will be handled together with its header. + Loop *BBL = LI.getLoopFor(BB); + if (LI.getLoopFor(BB) != &L) + if (BBL->getParentLoop() != &L || BBL->getHeader() != BB) + continue; + + // We process blocks from L one by one, and blocks from its subloops all + // at once. + SmallVector BlocksToProcess; + if (BBL != &L) { + for (BasicBlock *B : BBL->blocks()) { + assert(!BlocksInLoopAfterFolding.count(B) && + "Either all blocks of a subloop of none should!"); + Visited.insert(B); + BlocksToProcess.push_back(B); + } + } else { + Visited.insert(BB); + BlocksToProcess.push_back(BB); + } + +#ifndef NDEBUG + // Make sure that all in-loop successors of the block(s) we are handling + // now have already been processed by this moment. + for (auto *B : BlocksToProcess) + for (auto *Succ : successors(B)) + if (!BlocksInLoopAfterFolding.count(Succ) && L.contains(Succ)) + assert(Visited.count(Succ) && "Bad order!"); +#endif + + // Find the most nested ancestor loop that is still BB's successor. BB + // also belongs to this loop. + Loop *ReachableOuterLoop = nullptr; + for (BasicBlock *B : BlocksToProcess) + for (BasicBlock *Succ : successors(B)) { + Loop *SuccL = LI.getLoopFor(Succ); + while (SuccL && (SuccL == &L || !SuccL->contains(L.getHeader()))) + SuccL = SuccL->getParentLoop(); + if (SuccL) + if (!ReachableOuterLoop || ReachableOuterLoop->getLoopDepth() > + SuccL->getLoopDepth()) + ReachableOuterLoop = SuccL; + } + + assert(ReachableOuterLoop != &L && "Should be some outer loop!"); + + // The block belongs to the innermost outer loop that is still reachable + // from it. + for (BasicBlock *B : BlocksToProcess) { + // Remove blocks from loops that no longer contain it. + if (BBL == &L) + LI.changeLoopFor(B, ReachableOuterLoop); + for (Loop *Current = &L; Current != ReachableOuterLoop; + Current = Current->getParentLoop()) + Current->removeBlockFromLoop(B); + } + + // If we are processing a child loop, reattach it to new parent. + if (BBL != &L) { + assert(BBL->getParentLoop() == &L && "Should be!"); + L.removeChildLoop(BBL); + if (ReachableOuterLoop) + ReachableOuterLoop->addChildLoop(BBL); + else + LI.addTopLevelLoop(BBL); + } + } + + return true; + } + public: ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT, MemorySSAUpdater *MSSAU) - : L(L), LI(LI), DT(DT), MSSAU(MSSAU) {} + : L(L), LI(LI), DT(DT), MSSAU(MSSAU), DFS(&L) {} bool run() { assert(L.getLoopLatch() && "Should be single latch!"); @@ -491,19 +587,6 @@ return false; } - // TODO: Support blocks that are not dead, but also not in loop after the - // folding. - if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() != - L.getNumBlocks()) { - LLVM_DEBUG( - dbgs() << "Give up constant terminator folding in loop " - << L.getHeader()->getName() - << ": we don't currently" - " support blocks that are not dead, but will stop " - "being a part of the loop after constant-folding.\n"); - return false; - } - // Dump analysis results. LLVM_DEBUG(dump()); @@ -514,6 +597,7 @@ // Make the actual transforms. handleDeadExits(); foldTerminators(); + bool NewExitsAppeared = updateLoopInfo(); if (!DeadLoopBlocks.empty()) { LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size() @@ -522,6 +606,10 @@ deleteDeadLoopBlocks(); } + // TODO: Is there a smarter way to do it? + if (NewExitsAppeared) + formLCSSA(L, DT, &LI, nullptr); + #ifndef NDEBUG // Make sure that we have preserved all data structures after the transform. DT.verify(); Index: test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll =================================================================== --- test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll +++ test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll @@ -12,16 +12,16 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_BE:%.*]], [[HEADER_BACKEDGE:%.*]] ] -; CHECK-NEXT: [[I_1:%.*]] = add i32 [[I]], 1 +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_1:%.*]], [[HEADER_BACKEDGE:%.*]] ] +; CHECK-NEXT: [[I_1]] = add i32 [[I]], 1 ; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[I_1]], 100 ; CHECK-NEXT: br i1 [[CMP1]], label [[HEADER_BACKEDGE]], label [[DEAD_BACKEDGE:%.*]] ; CHECK: header.backedge: -; CHECK-NEXT: [[I_BE]] = phi i32 [ [[I_1]], [[HEADER]] ], [ [[I_2:%.*]], [[DEAD_BACKEDGE]] ] ; CHECK-NEXT: br label [[HEADER]] ; CHECK: dead_backedge: -; CHECK-NEXT: [[I_2]] = add i32 [[I_1]], 10 -; CHECK-NEXT: br i1 false, label [[HEADER_BACKEDGE]], label [[EXIT:%.*]] +; CHECK-NEXT: [[I_1_LCSSA:%.*]] = phi i32 [ [[I_1]], [[HEADER]] ] +; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I_1_LCSSA]], 10 +; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: ; CHECK-NEXT: [[I_2_LCSSA:%.*]] = phi i32 [ [[I_2]], [[DEAD_BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_2_LCSSA]] @@ -49,18 +49,16 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_BE:%.*]], [[HEADER_BACKEDGE:%.*]] ] -; CHECK-NEXT: [[I_1:%.*]] = add i32 [[I]], 1 +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_1:%.*]], [[HEADER_BACKEDGE:%.*]] ] +; CHECK-NEXT: [[I_1]] = add i32 [[I]], 1 ; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[I_1]], 100 ; CHECK-NEXT: br i1 [[CMP1]], label [[HEADER_BACKEDGE]], label [[DEAD_BACKEDGE:%.*]] ; CHECK: header.backedge: -; CHECK-NEXT: [[I_BE]] = phi i32 [ [[I_1]], [[HEADER]] ], [ [[I_2:%.*]], [[DEAD_BACKEDGE]] ] ; CHECK-NEXT: br label [[HEADER]] ; CHECK: dead_backedge: -; CHECK-NEXT: [[I_2]] = add i32 [[I_1]], 10 -; CHECK-NEXT: switch i32 1, label [[EXIT:%.*]] [ -; CHECK-NEXT: i32 0, label [[HEADER_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[I_1_LCSSA:%.*]] = phi i32 [ [[I_1]], [[HEADER]] ] +; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I_1_LCSSA]], 10 +; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: ; CHECK-NEXT: [[I_2_LCSSA:%.*]] = phi i32 [ [[I_2]], [[DEAD_BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_2_LCSSA]] @@ -1585,7 +1583,7 @@ ; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] ; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]] ; CHECK: intermediate: -; CHECK-NEXT: br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -1593,8 +1591,6 @@ ; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] ; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] -; CHECK: loop_1_backedge.loopexit: -; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge.loopexit1: ; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge: @@ -1655,9 +1651,7 @@ ; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] ; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]] ; CHECK: intermediate: -; CHECK-NEXT: switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [ -; CHECK-NEXT: i32 0, label [[LOOP_3_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -1665,8 +1659,6 @@ ; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] ; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] -; CHECK: loop_1_backedge.loopexit: -; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge.loopexit1: ; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge: @@ -1727,7 +1719,7 @@ ; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] ; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]] ; CHECK: intermediate: -; CHECK-NEXT: br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]] +; CHECK-NEXT: br label [[LOOP_2_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -1793,9 +1785,7 @@ ; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] ; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]] ; CHECK: intermediate: -; CHECK-NEXT: switch i32 1, label [[LOOP_2_BACKEDGE]] [ -; CHECK-NEXT: i32 0, label [[LOOP_3_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[LOOP_2_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -1865,7 +1855,7 @@ ; CHECK: intermediate_loop: ; CHECK-NEXT: br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -1873,8 +1863,6 @@ ; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] ; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] -; CHECK: loop_1_backedge.loopexit: -; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge.loopexit1: ; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge: @@ -1945,9 +1933,7 @@ ; CHECK: intermediate_loop: ; CHECK-NEXT: br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [ -; CHECK-NEXT: i32 0, label [[LOOP_3_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -1955,8 +1941,6 @@ ; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] ; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] -; CHECK: loop_1_backedge.loopexit: -; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge.loopexit1: ; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge: @@ -2027,7 +2011,7 @@ ; CHECK: intermediate_loop: ; CHECK-NEXT: br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]] +; CHECK-NEXT: br label [[LOOP_2_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -2103,9 +2087,7 @@ ; CHECK: intermediate_loop: ; CHECK-NEXT: br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: switch i32 1, label [[LOOP_2_BACKEDGE]] [ -; CHECK-NEXT: i32 0, label [[LOOP_3_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[LOOP_2_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -2185,7 +2167,7 @@ ; CHECK: intermediate_block: ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]] +; CHECK-NEXT: br label [[LOOP_2_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -2268,9 +2250,7 @@ ; CHECK: intermediate_block: ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: switch i32 1, label [[LOOP_2_BACKEDGE]] [ -; CHECK-NEXT: i32 0, label [[LOOP_3_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[LOOP_2_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -2354,7 +2334,7 @@ ; CHECK: intermediate_block: ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -2362,8 +2342,6 @@ ; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] ; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] -; CHECK: loop_1_backedge.loopexit: -; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge.loopexit1: ; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge: @@ -2441,9 +2419,7 @@ ; CHECK: intermediate_block: ; CHECK-NEXT: br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]] ; CHECK: intermediate_exit: -; CHECK-NEXT: switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [ -; CHECK-NEXT: i32 0, label [[LOOP_3_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_3_backedge: ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]] @@ -2451,8 +2427,6 @@ ; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] ; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] -; CHECK: loop_1_backedge.loopexit: -; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge.loopexit1: ; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] ; CHECK: loop_1_backedge: