Index: lib/Target/ARM/ARMCodeGenPrepare.cpp =================================================================== --- lib/Target/ARM/ARMCodeGenPrepare.cpp +++ lib/Target/ARM/ARMCodeGenPrepare.cpp @@ -123,9 +123,10 @@ SmallPtrSetImpl *Sources; SmallPtrSetImpl *Sinks; SmallPtrSetImpl *SafeToPromote; + SmallPtrSetImpl *SafeUnderflow; void ReplaceAllUsersOfWith(Value *From, Value *To); - void PrepareConstants(void); + void PrepareUnderflowAdds(void); void ExtendSources(void); void ConvertTruncs(void); void PromoteTree(void); @@ -141,7 +142,8 @@ SetVector &Visited, SmallPtrSetImpl &Sources, SmallPtrSetImpl &Sinks, - SmallPtrSetImpl &SafeToPromote); + SmallPtrSetImpl &SafeToPromote, + SmallPtrSetImpl &SafeUnderflow); }; class ARMCodeGenPrepare : public FunctionPass { @@ -149,6 +151,7 @@ IRPromoter *Promoter = nullptr; std::set AllVisited; SmallPtrSet SafeToPromote; + SmallPtrSet SafeUnderflow; bool isSafeOverflow(Instruction *I); bool isSupportedValue(Value *V); @@ -392,6 +395,7 @@ return false; LLVM_DEBUG(dbgs() << "ARM CGP: Allowing safe overflow for " << *I << "\n"); + SafeUnderflow.insert(I); return true; } @@ -469,61 +473,34 @@ InstsToRemove.insert(I); } -void IRPromoter::PrepareConstants() { +void IRPromoter::PrepareUnderflowAdds() { + LLVM_DEBUG(dbgs() << "ARM CGP: Prepare underflowing adds.\n"); IRBuilder<> Builder{Ctx}; - // First step is to prepare the instructions for mutation. Most constants - // just need to be zero extended into their new type, but complications arise - // because: - // - For nuw binary operators, negative immediates would need sign extending; - // however, instead we'll change them to positive and zext them. We can do - // this because: - // > The operators that can wrap are: add, sub, mul and shl. - // > shl interprets its second operand as unsigned and if the first operand - // is an immediate, it will need zext to be nuw. - // > I'm assuming mul has to interpret immediates as unsigned for nuw. - // > Which leaves the nuw add and sub to be handled; as with shl, if an - // immediate is used as operand 0, it will need zext to be nuw. - // - We also allow add and sub to safely overflow in certain circumstances - // and only when the value (operand 0) is being decreased. - // - // For adds and subs, that are either nuw or safely wrap and use a negative - // immediate as operand 1, we create an equivalent instruction using a - // positive immediate. That positive immediate can then be zext along with - // all the other immediates later. - for (auto *V : *Visited) { - if (!isa(V)) - continue; - - auto *I = cast(V); - if (SafeToPromote->count(I)) { - - if (!isa(I)) - continue; - if (auto *Const = dyn_cast(I->getOperand(1))) { - if (!Const->isNegative()) - continue; + // For adds that safely wrap and use a negative immediate as operand 1, we + // create an equivalent instruction using a positive immediate. + // That positive immediate can then be zext along with all the other + // immediates later. + for (auto *I : *SafeUnderflow) { + if (I->getOpcode() != Instruction::Add) + continue; - unsigned Opc = I->getOpcode(); - if (Opc != Instruction::Add && Opc != Instruction::Sub) - continue; + LLVM_DEBUG(dbgs() << "ARM CGP: Adjusting " << *I << "\n"); + assert((isa(I->getOperand(1)) && + cast(I->getOperand(1))->isNegative()) && + "Wrapping should have a negative immediate as the second operand"); - LLVM_DEBUG(dbgs() << "ARM CGP: Adjusting " << *I << "\n"); - auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs()); - Builder.SetInsertPoint(I); - Value *NewVal = Opc == Instruction::Sub ? - Builder.CreateAdd(I->getOperand(0), NewConst) : - Builder.CreateSub(I->getOperand(0), NewConst); - LLVM_DEBUG(dbgs() << "ARM CGP: New equivalent: " << *NewVal << "\n"); - - if (auto *NewInst = dyn_cast(NewVal)) { - NewInst->copyIRFlags(I); - NewInsts.insert(NewInst); - } - InstsToRemove.insert(I); - I->replaceAllUsesWith(NewVal); - } + auto Const = cast(I->getOperand(1)); + auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs()); + Builder.SetInsertPoint(I); + Value *NewVal = Builder.CreateSub(I->getOperand(0), NewConst); + if (auto *NewInst = dyn_cast(NewVal)) { + NewInst->copyIRFlags(I); + NewInsts.insert(NewInst); } + InstsToRemove.insert(I); + I->replaceAllUsesWith(NewVal); + LLVM_DEBUG(dbgs() << "ARM CGP: New equivalent: " << *NewVal << "\n"); } for (auto *I : NewInsts) Visited->insert(I); @@ -731,6 +708,8 @@ NewInsts.clear(); TruncTysMap.clear(); Promoted.clear(); + SafeToPromote->clear(); + SafeUnderflow->clear(); } void IRPromoter::ConvertTruncs() { @@ -762,7 +741,8 @@ SetVector &Visited, SmallPtrSetImpl &Sources, SmallPtrSetImpl &Sinks, - SmallPtrSetImpl &SafeToPromote) { + SmallPtrSetImpl &SafeToPromote, + SmallPtrSetImpl &SafeUnderflow) { LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from " << ARMCodeGenPrepare::TypeSize << " to 32-bits\n"); @@ -775,6 +755,7 @@ this->Sources = &Sources; this->Sinks = &Sinks; this->SafeToPromote = &SafeToPromote; + this->SafeUnderflow = &SafeUnderflow; // Cache original types of the values that will likely need truncating for (auto *I : Sinks) { @@ -797,9 +778,9 @@ TruncTysMap[Trunc].push_back(Trunc->getDestTy()); } - // Convert adds and subs using negative immediates to equivalent instructions - // that use positive constants. - PrepareConstants(); + // Convert adds using negative immediates to equivalent instructions that use + // positive constants. + PrepareUnderflowAdds(); // Insert zext instructions between sources and their users. ExtendSources(); @@ -1025,7 +1006,8 @@ if (ToPromote < 2) return false; - Promoter->Mutate(OrigTy, CurrentVisited, Sources, Sinks, SafeToPromote); + Promoter->Mutate(OrigTy, CurrentVisited, Sources, Sinks, SafeToPromote, + SafeUnderflow); return true; } Index: test/CodeGen/ARM/CGP/arm-cgp-overflow.ll =================================================================== --- test/CodeGen/ARM/CGP/arm-cgp-overflow.ll +++ test/CodeGen/ARM/CGP/arm-cgp-overflow.ll @@ -194,7 +194,7 @@ } ; CHECK-LABEL: safe_sub_var_imm -; CHECK: add.w [[ADD:r[0-9]+]], r0, #8 +; CHECK: sub.w [[ADD:r[0-9]+]], r0, #248 ; CHECK-NOT: uxt ; CHECK: cmp [[ADD]], #252 define i32 @safe_sub_var_imm(i8* %b) { @@ -220,7 +220,7 @@ } ; CHECK-LABEL: safe_add_var_imm -; CHECK: sub.w [[SUB:r[0-9]+]], r0, #127 +; CHECK: add.w [[SUB:r[0-9]+]], r0, #129 ; CHECK-NOT: uxt ; CHECK: cmp [[SUB]], #127 define i32 @safe_add_var_imm(i8* %b) { @@ -248,3 +248,32 @@ %res = select i1 %cmp.0, i8 %mask.sel, i8 %arg ret i8 %res } + +; CHECK-LABEL: underflow_if_sub +; CHECK: add{{.}} [[ADD:r[0-9]+]], #245 +; CHECK: cmp [[ADD]], r1 +define i8 @underflow_if_sub(i32 %arg, i8 zeroext %arg1) { + %cmp = icmp sgt i32 %arg, 0 + %conv = zext i1 %cmp to i32 + %and = and i32 %arg, %conv + %trunc = trunc i32 %and to i8 + %conv1 = add nuw nsw i8 %trunc, -11 + %cmp.1 = icmp ult i8 %conv1, %arg1 + %res = select i1 %cmp.1, i8 %conv1, i8 100 + ret i8 %res +} + +; CHECK-LABEL: underflow_if_sub_signext +; CHECK: sub{{.*}} [[SUB:r[0-9]+]], #11 +; CHECK: uxtb [[UXT:r[0-9]+]], [[SUB]] +; CHECK: cmp [[UXT]] +define i8 @underflow_if_sub_signext(i32 %arg, i8 signext %arg1) { + %cmp = icmp sgt i32 %arg, 0 + %conv = zext i1 %cmp to i32 + %and = and i32 %arg, %conv + %trunc = trunc i32 %and to i8 + %conv1 = add nuw nsw i8 %trunc, -11 + %cmp.1 = icmp ugt i8 %arg1, %conv1 + %res = select i1 %cmp.1, i8 %conv1, i8 100 + ret i8 %res +}