From owner-freebsd-x11@FreeBSD.ORG Mon Jun 17 11:20:02 2013 Return-Path: Delivered-To: freebsd-x11@smarthost.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id 2ABB3E85 for ; Mon, 17 Jun 2013 11:20:02 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:1900:2254:206c::16:87]) by mx1.freebsd.org (Postfix) with ESMTP id 1CAFD1E36 for ; Mon, 17 Jun 2013 11:20:02 +0000 (UTC) Received: from freefall.freebsd.org (localhost [127.0.0.1]) by freefall.freebsd.org (8.14.7/8.14.7) with ESMTP id r5HBK2WH018530 for ; Mon, 17 Jun 2013 11:20:02 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.7/8.14.7/Submit) id r5HBK2en018529; Mon, 17 Jun 2013 11:20:02 GMT (envelope-from gnats) Date: Mon, 17 Jun 2013 11:20:02 GMT Message-Id: <201306171120.r5HBK2en018529@freefall.freebsd.org> To: freebsd-x11@FreeBSD.org Cc: From: Dimitry Andric Subject: Re: ports/179625: x11-servers/xorg-server built with clang does not work, needs USE_GCC=any X-BeenThere: freebsd-x11@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: Dimitry Andric List-Id: X11 on FreeBSD -- maintaining and support List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 17 Jun 2013 11:20:02 -0000 The following reply was made to PR ports/179625; it has been noted by GNATS. From: Dimitry Andric To: bug-followup@FreeBSD.org, mexas@bristol.ac.uk Cc: Subject: Re: ports/179625: x11-servers/xorg-server built with clang does not work, needs USE_GCC=any Date: Mon, 17 Jun 2013 13:13:40 +0200 This is a multi-part message in MIME format. --------------040606090100040907040001 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit As Jung-uk Kim points out in his reply to the thread about this bug on -current , this may be due to a clang optimizer bug, specifically LLVM PR 16130 . Can you please verify it is exactly this bug, by applying the attached patch to your r249781 tree (I assume you have not yet upgraded), then rebuild clang by doing: cd /usr/src/lib/clang && make cd /usr/src/usr.bin/clang && make && sudo make install After the patched clang has been installed, rebuild your xorg-server without the USE_GCC=any setting, and check if the startup problem was resolved. -Dimitry --------------040606090100040907040001 Content-Type: text/x-diff; name="llvm-pr16130.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="llvm-pr16130.diff" Index: contrib/llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- contrib/llvm/include/llvm/Analysis/ScalarEvolution.h (revision 249781) +++ contrib/llvm/include/llvm/Analysis/ScalarEvolution.h (working copy) @@ -453,7 +453,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeExitLimitFromICmp - Compute the number of times the backedge of /// the specified loop will execute if its exit condition were a conditional @@ -461,7 +462,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeLoadConstantCompareExitLimit - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the @@ -483,7 +485,7 @@ namespace llvm { /// HowFarToZero - Return the number of times an exit condition comparing /// the specified value to zero will execute. If not computable, return /// CouldNotCompute. - ExitLimit HowFarToZero(const SCEV *V, const Loop *L); + ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); /// HowFarToNonZero - Return the number of times an exit condition checking /// the specified value for nonzero will execute. If not computable, return @@ -495,7 +497,7 @@ namespace llvm { /// computable, return CouldNotCompute. isSigned specifies whether the /// less-than is signed. ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned); + const Loop *L, bool isSigned, bool IsSubExpr); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one Index: contrib/llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- contrib/llvm/lib/Analysis/ScalarEvolution.cpp (revision 249781) +++ contrib/llvm/lib/Analysis/ScalarEvolution.cpp (working copy) @@ -3937,10 +3937,19 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) /// before taking the branch. For loops with multiple exits, it may not be the /// number times that the loop header executes because the loop may exit /// prematurely via another branch. +/// +/// FIXME: We conservatively call getBackedgeTakenCount(L) instead of +/// getExitCount(L, ExitingBlock) to compute a safe trip count considering all +/// loop exits. getExitCount() may return an exact count for this branch +/// assuming no-signed-wrap. The number of well-defined iterations may actually +/// be higher than this trip count if this exit test is skipped and the loop +/// exits via a different branch. Ideally, getExitCount() would know whether it +/// depends on a NSW assumption, and we would only fall back to a conservative +/// trip count in that case. unsigned ScalarEvolution:: -getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) { +getSmallConstantTripCount(Loop *L, BasicBlock */*ExitingBlock*/) { const SCEVConstant *ExitCount = - dyn_cast(getExitCount(L, ExitingBlock)); + dyn_cast(getBackedgeTakenCount(L)); if (!ExitCount) return 0; @@ -3967,8 +3976,8 @@ unsigned ScalarEvolution:: /// As explained in the comments for getSmallConstantTripCount, this assumes /// that control exits the loop via ExitingBlock. unsigned ScalarEvolution:: -getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock) { - const SCEV *ExitCount = getExitCount(L, ExitingBlock); +getSmallConstantTripMultiple(Loop *L, BasicBlock */*ExitingBlock*/) { + const SCEV *ExitCount = getBackedgeTakenCount(L); if (ExitCount == getCouldNotCompute()) return 1; @@ -3997,7 +4006,7 @@ unsigned ScalarEvolution:: } // getExitCount - Get the expression for the number of loop iterations for which -// this loop is guaranteed not to exit via ExitintBlock. Otherwise return +// this loop is guaranteed not to exit via ExitingBlock. Otherwise return // SCEVCouldNotCompute. const SCEV *ScalarEvolution::getExitCount(Loop *L, BasicBlock *ExitingBlock) { return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); @@ -4382,26 +4391,36 @@ ScalarEvolution::ComputeExitLimit(const Loop *L, B // Proceed to the next level to examine the exit condition expression. return ComputeExitLimitFromCond(L, ExitBr->getCondition(), ExitBr->getSuccessor(0), - ExitBr->getSuccessor(1)); + ExitBr->getSuccessor(1), + /*IsSubExpr=*/false); } /// ComputeExitLimitFromCond - Compute the number of times the /// backedge of the specified loop will execute if its exit condition /// were a conditional branch of ExitCond, TBB, and FBB. +/// +/// @param IsSubExpr is true if ExitCond does not directly control the exit +/// branch. In this case, we cannot assume that the loop only exits when the +/// condition is true and cannot infer that failing to meet the condition prior +/// to integer wraparound results in undefined behavior. ScalarEvolution::ExitLimit ScalarEvolution::ComputeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB) { + BasicBlock *FBB, + bool IsSubExpr) { // Check if the controlling expression for this loop is an And or Or. if (BinaryOperator *BO = dyn_cast(ExitCond)) { if (BO->getOpcode() == Instruction::And) { // Recurse on the operands of the and. - ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB); - ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB); + bool EitherMayExit = L->contains(TBB); + ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB, + IsSubExpr || EitherMayExit); + ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB, + IsSubExpr || EitherMayExit); const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); - if (L->contains(TBB)) { + if (EitherMayExit) { // Both conditions must be true for the loop to continue executing. // Choose the less conservative count. if (EL0.Exact == getCouldNotCompute() || @@ -4429,11 +4448,14 @@ ScalarEvolution::ComputeExitLimitFromCond(const Lo } if (BO->getOpcode() == Instruction::Or) { // Recurse on the operands of the or. - ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB); - ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB); + bool EitherMayExit = L->contains(FBB); + ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB, + IsSubExpr || EitherMayExit); + ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB, + IsSubExpr || EitherMayExit); const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); - if (L->contains(FBB)) { + if (EitherMayExit) { // Both conditions must be false for the loop to continue executing. // Choose the less conservative count. if (EL0.Exact == getCouldNotCompute() || @@ -4464,7 +4486,7 @@ ScalarEvolution::ComputeExitLimitFromCond(const Lo // With an icmp, it may be feasible to compute an exact backedge-taken count. // Proceed to the next level to examine the icmp. if (ICmpInst *ExitCondICmp = dyn_cast(ExitCond)) - return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB); + return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, IsSubExpr); // Check for a constant condition. These are normally stripped out by // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to @@ -4490,7 +4512,8 @@ ScalarEvolution::ExitLimit ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, - BasicBlock *FBB) { + BasicBlock *FBB, + bool IsSubExpr) { // If the condition was exit on true, convert the condition to exit on false ICmpInst::Predicate Cond; @@ -4542,7 +4565,7 @@ ScalarEvolution::ComputeExitLimitFromICmp(const Lo switch (Cond) { case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L); + ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } @@ -4553,24 +4576,24 @@ ScalarEvolution::ComputeExitLimitFromICmp(const Lo break; } case ICmpInst::ICMP_SLT: { - ExitLimit EL = HowManyLessThans(LHS, RHS, L, true); + ExitLimit EL = HowManyLessThans(LHS, RHS, L, true, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } case ICmpInst::ICMP_SGT: { ExitLimit EL = HowManyLessThans(getNotSCEV(LHS), - getNotSCEV(RHS), L, true); + getNotSCEV(RHS), L, true, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } case ICmpInst::ICMP_ULT: { - ExitLimit EL = HowManyLessThans(LHS, RHS, L, false); + ExitLimit EL = HowManyLessThans(LHS, RHS, L, false, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } case ICmpInst::ICMP_UGT: { ExitLimit EL = HowManyLessThans(getNotSCEV(LHS), - getNotSCEV(RHS), L, false); + getNotSCEV(RHS), L, false, IsSubExpr); if (EL.hasAnyInfo()) return EL; break; } @@ -5439,7 +5462,7 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRe /// effectively V != 0. We know and take advantage of the fact that this /// expression only being used in a comparison by zero context. ScalarEvolution::ExitLimit -ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { +ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr) { // If the value is a constant if (const SCEVConstant *C = dyn_cast(V)) { // If the value is already zero, the branch will execute zero times. @@ -5537,19 +5560,20 @@ ScalarEvolution::ExitLimit } // If the recurrence is known not to wraparound, unsigned divide computes the - // back edge count. We know that the value will either become zero (and thus - // the loop terminates), that the loop will terminate through some other exit - // condition first, or that the loop has undefined behavior. This means - // we can't "miss" the exit value, even with nonunit stride. + // back edge count. (Ideally we would have an "isexact" bit for udiv). We know + // that the value will either become zero (and thus the loop terminates), that + // the loop will terminate through some other exit condition first, or that + // the loop has undefined behavior. This means we can't "miss" the exit + // value, even with nonunit stride. // - // FIXME: Prove that loops always exhibits *acceptable* undefined - // behavior. Loops must exhibit defined behavior until a wrapped value is - // actually used. So the trip count computed by udiv could be smaller than the - // number of well-defined iterations. - if (AddRec->getNoWrapFlags(SCEV::FlagNW)) { - // FIXME: We really want an "isexact" bit for udiv. + // This is only valid for expressions that directly compute the loop exit. It + // is invalid for subexpressions in which the loop may exit through this + // branch even if this subexpression is false. In that case, the trip count + // computed by this udiv could be smaller than the number of well-defined + // iterations. + if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW)) return getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step); - } + // Then, try to solve the above equation provided that Start is constant. if (const SCEVConstant *StartC = dyn_cast(Start)) return SolveLinEquationWithOverflow(StepC->getValue()->getValue(), @@ -6315,9 +6339,14 @@ const SCEV *ScalarEvolution::getBECount(const SCEV /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// CouldNotCompute. +/// +/// @param IsSubExpr is true when the LHS < RHS condition does not directly +/// control the branch. In this case, we can only compute an iteration count for +/// a subexpression that cannot overflow before evaluating true. ScalarEvolution::ExitLimit ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned) { + const Loop *L, bool isSigned, + bool IsSubExpr) { // Only handle: "ADDREC < LoopInvariant". if (!isLoopInvariant(RHS, L)) return getCouldNotCompute(); @@ -6326,10 +6355,12 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, return getCouldNotCompute(); // Check to see if we have a flag which makes analysis easy. - bool NoWrap = isSigned ? - AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNW)) : - AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNW)); - + bool NoWrap = false; + if (!IsSubExpr) { + NoWrap = AddRec->getNoWrapFlags( + (SCEV::NoWrapFlags)(((isSigned ? SCEV::FlagNSW : SCEV::FlagNUW)) + | SCEV::FlagNW)); + } if (AddRec->isAffine()) { unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); const SCEV *Step = AddRec->getStepRecurrence(*this); --------------040606090100040907040001--