Index: include/llvm/Transforms/Scalar/GVN.h =================================================================== --- include/llvm/Transforms/Scalar/GVN.h +++ include/llvm/Transforms/Scalar/GVN.h @@ -68,6 +68,13 @@ class ValueTable { DenseMap valueNumbering; DenseMap expressionNumbering; + DenseMap numberingExpression; + // Value number to PHINode mapping. Used for phi-translate in scalarpre. + DenseMap NumberingPhi; + // Cache for phi-translate in scalarpre. + typedef DenseMap, uint32_t> + PhiTranslateMap; + PhiTranslateMap PhiTranslateTable; AliasAnalysis *AA; MemoryDependenceResults *MD; DominatorTree *DT; @@ -79,6 +86,8 @@ Value *LHS, Value *RHS); Expression createExtractvalueExpr(ExtractValueInst *EI); uint32_t lookupOrAddCall(CallInst *C); + uint32_t phiTranslateImpl(const BasicBlock *BB, uint32_t Num); + uint32_t assignExpNewValueNum(Expression exp); public: ValueTable(); @@ -87,9 +96,10 @@ ~ValueTable(); uint32_t lookupOrAdd(Value *V); - uint32_t lookup(Value *V) const; + uint32_t lookup(Value *V, bool Verify = true) const; uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS); + uint32_t phiTranslate(const BasicBlock *BB, uint32_t Num); bool exists(Value *V) const; void add(Value *V, uint32_t num); void clear(); Index: lib/Transforms/Scalar/GVN.cpp =================================================================== --- lib/Transforms/Scalar/GVN.cpp +++ lib/Transforms/Scalar/GVN.cpp @@ -80,6 +80,7 @@ struct llvm::GVN::Expression { uint32_t opcode; Type *type; + bool commutative; SmallVector varargs; Expression(uint32_t o = ~2U) : opcode(o) {} @@ -235,6 +236,7 @@ Expression e; e.type = I->getType(); e.opcode = I->getOpcode(); + e.commutative = false; for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) e.varargs.push_back(lookupOrAdd(*OI)); @@ -246,6 +248,7 @@ assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!"); if (e.varargs[0] > e.varargs[1]) std::swap(e.varargs[0], e.varargs[1]); + e.commutative = true; } if (CmpInst *C = dyn_cast(I)) { @@ -256,6 +259,7 @@ Predicate = CmpInst::getSwappedPredicate(Predicate); } e.opcode = (C->getOpcode() << 8) | Predicate; + e.commutative = true; } else if (InsertValueInst *E = dyn_cast(I)) { for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end(); II != IE; ++II) @@ -281,6 +285,7 @@ Predicate = CmpInst::getSwappedPredicate(Predicate); } e.opcode = (Opcode << 8) | Predicate; + e.commutative = true; return e; } @@ -348,25 +353,28 @@ /// add - Insert a value into the table with a specified value number. void GVN::ValueTable::add(Value *V, uint32_t num) { valueNumbering.insert(std::make_pair(V, num)); + if (PHINode *PN = dyn_cast(V)) + NumberingPhi[num] = PN; } uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) { if (AA->doesNotAccessMemory(C)) { Expression exp = createExpr(C); - uint32_t &e = expressionNumbering[exp]; - if (!e) e = nextValueNumber++; + uint32_t e = expressionNumbering[exp]; + if (!e) + e = assignExpNewValueNum(exp); valueNumbering[C] = e; return e; } else if (AA->onlyReadsMemory(C)) { Expression exp = createExpr(C); - uint32_t &e = expressionNumbering[exp]; + uint32_t e = expressionNumbering[exp]; if (!e) { - e = nextValueNumber++; + e = assignExpNewValueNum(exp); valueNumbering[C] = e; return e; } if (!MD) { - e = nextValueNumber++; + e = assignExpNewValueNum(exp); valueNumbering[C] = e; return e; } @@ -522,23 +530,31 @@ case Instruction::ExtractValue: exp = createExtractvalueExpr(cast(I)); break; + case Instruction::PHI: + valueNumbering[V] = nextValueNumber; + NumberingPhi[nextValueNumber] = cast(V); + return nextValueNumber++; default: valueNumbering[V] = nextValueNumber; return nextValueNumber++; } - uint32_t& e = expressionNumbering[exp]; - if (!e) e = nextValueNumber++; + uint32_t e = expressionNumbering[exp]; + if (!e) + e = assignExpNewValueNum(exp); valueNumbering[V] = e; return e; } /// Returns the value number of the specified value. Fails if /// the value has not yet been numbered. -uint32_t GVN::ValueTable::lookup(Value *V) const { +uint32_t GVN::ValueTable::lookup(Value *V, bool Verify) const { DenseMap::const_iterator VI = valueNumbering.find(V); - assert(VI != valueNumbering.end() && "Value not numbered?"); - return VI->second; + if (Verify) { + assert(VI != valueNumbering.end() && "Value not numbered?"); + return VI->second; + } + return (VI != valueNumbering.end()) ? VI->second : 0; } /// Returns the value number of the given comparison, @@ -549,8 +565,9 @@ CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { Expression exp = createCmpExpr(Opcode, Predicate, LHS, RHS); - uint32_t& e = expressionNumbering[exp]; - if (!e) e = nextValueNumber++; + uint32_t e = expressionNumbering[exp]; + if (!e) + e = assignExpNewValueNum(exp); return e; } @@ -558,12 +575,19 @@ void GVN::ValueTable::clear() { valueNumbering.clear(); expressionNumbering.clear(); + numberingExpression.clear(); + NumberingPhi.clear(); + PhiTranslateTable.clear(); nextValueNumber = 1; } /// Remove a value from the value numbering. void GVN::ValueTable::erase(Value *V) { + uint32_t Num = valueNumbering.lookup(V); valueNumbering.erase(V); + // If V is PHINode, V <--> value number is an one-to-one mapping. + if (isa(V)) + NumberingPhi.erase(Num); } /// verifyRemoved - Verify that the value is removed from all internal data @@ -1451,6 +1475,53 @@ return false; } +uint32_t GVN::ValueTable::assignExpNewValueNum(Expression exp) { + numberingExpression[nextValueNumber] = exp; + expressionNumbering[exp] = nextValueNumber; + return nextValueNumber++; +} + +/// Wrap phiTranslateImpl to provide caching functionality. +uint32_t GVN::ValueTable::phiTranslate(const BasicBlock *BB, uint32_t Num) { + auto FindRes = PhiTranslateTable.find({Num, BB}); + if (FindRes != PhiTranslateTable.end()) + return FindRes->second; + uint32_t NewNum = phiTranslateImpl(BB, Num); + PhiTranslateTable.insert({{Num, BB}, NewNum}); + return NewNum; +} + +/// Translate value number \p Num using phis, so that it has the values of +/// the phis in BB. +uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *BB, uint32_t Num) { + if (PHINode *PN = NumberingPhi[Num]) { + for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { + if (PN->getIncomingBlock(i) == BB) + if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false)) + return TransVal; + } + return Num; + } + + auto FindRes = numberingExpression.find(Num); + if (FindRes == numberingExpression.end()) + return Num; + Expression Exp = FindRes->second; + + for (unsigned i = 0; i < Exp.varargs.size(); i++) + Exp.varargs[i] = phiTranslate(BB, Exp.varargs[i]); + + if (Exp.commutative) { + assert(Exp.varargs.size() == 2 && "Unsupported commutative expression!"); + if (Exp.varargs[0] > Exp.varargs[1]) + std::swap(Exp.varargs[0], Exp.varargs[1]); + } + + if (uint32_t NewNum = expressionNumbering[Exp]) + return NewNum; + return Num; +} + // In order to find a leader for a given value number at a // specific basic block, we first obtain the list of all Values for that number, // and then scan the list to find one whose block dominates the block in @@ -1945,7 +2016,8 @@ success = false; break; } - if (Value *V = findLeader(Pred, VN.lookup(Op))) { + uint32_t TValNo = VN.phiTranslate(Pred, VN.lookup(Op)); + if (Value *V = findLeader(Pred, TValNo)) { Instr->setOperand(i, V); } else { success = false; @@ -1962,10 +2034,12 @@ Instr->insertBefore(Pred->getTerminator()); Instr->setName(Instr->getName() + ".pre"); Instr->setDebugLoc(Instr->getDebugLoc()); - VN.add(Instr, ValNo); + + unsigned Num = VN.lookupOrAdd(Instr); + VN.add(Instr, Num); // Update the availability map to include the new instruction. - addToLeaderTable(ValNo, Instr, Pred); + addToLeaderTable(Num, Instr, Pred); return true; } @@ -2014,7 +2088,8 @@ break; } - Value *predV = findLeader(P, ValNo); + uint32_t TValNo = VN.phiTranslate(P, ValNo); + Value *predV = findLeader(P, TValNo); if (!predV) { predMap.push_back(std::make_pair(static_cast(nullptr), P)); PREPred = P; Index: test/Transforms/GVN/PRE/phi-translate-2.ll =================================================================== --- test/Transforms/GVN/PRE/phi-translate-2.ll +++ test/Transforms/GVN/PRE/phi-translate-2.ll @@ -0,0 +1,75 @@ +; RUN: opt < %s -gvn -S | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +@a = common global [100 x i64] zeroinitializer, align 16 +@b = common global [100 x i64] zeroinitializer, align 16 +@g1 = common global i64 0, align 8 +@g2 = common global i64 0, align 8 +@g3 = common global i64 0, align 8 +declare i64 @goo(...) local_unnamed_addr #1 + +define void @test1(i64 %a, i64 %b, i64 %c, i64 %d) { +entry: + %mul = mul nsw i64 %b, %a + store i64 %mul, i64* @g1, align 8 + %t0 = load i64, i64* @g2, align 8 + %cmp = icmp sgt i64 %t0, 3 + br i1 %cmp, label %if.then, label %if.end + +if.then: ; preds = %entry + %mul2 = mul nsw i64 %d, %c + store i64 %mul2, i64* @g2, align 8 + br label %if.end + +; Check phi-translate works and mul is removed. +; CHECK-LABEL: @test1( +; CHECK: if.end: +; CHECK: %[[MULPHI:.*]] = phi i64 [ {{.*}}, %if.then ], [ %mul, %entry ] +; CHECK-NOT: = mul +; CHECK: store i64 %[[MULPHI]], i64* @g3, align 8 +if.end: ; preds = %if.then, %entry + %b.addr.0 = phi i64 [ %d, %if.then ], [ %b, %entry ] + %a.addr.0 = phi i64 [ %c, %if.then ], [ %a, %entry ] + %mul3 = mul nsw i64 %a.addr.0, %b.addr.0 + store i64 %mul3, i64* @g3, align 8 + ret void +} + +define void @test2(i64 %i) { +entry: + %arrayidx = getelementptr inbounds [100 x i64], [100 x i64]* @a, i64 0, i64 %i + %t0 = load i64, i64* %arrayidx, align 8 + %arrayidx1 = getelementptr inbounds [100 x i64], [100 x i64]* @b, i64 0, i64 %i + %t1 = load i64, i64* %arrayidx1, align 8 + %mul = mul nsw i64 %t1, %t0 + store i64 %mul, i64* @g1, align 8 + %cmp = icmp sgt i64 %mul, 3 + br i1 %cmp, label %if.then, label %if.end + +; Check phi-translate works for the phi generated by loadpre. A new mul will be +; inserted in if.then block. +; CHECK-LABEL: @test2( +; CHECK: if.then: +; CHECK: %[[MUL_THEN:.*]] = mul +; CHECK: br label %if.end +if.then: ; preds = %entry + %call = tail call i64 (...) @goo() #2 + store i64 %call, i64* @g2, align 8 + br label %if.end + +; CHECK: if.end: +; CHECK: %[[MULPHI:.*]] = phi i64 [ %[[MUL_THEN]], %if.then ], [ %mul, %entry ] +; CHECK-NOT: = mul +; CHECK: store i64 %[[MULPHI]], i64* @g3, align 8 +if.end: ; preds = %if.then, %entry + %i.addr.0 = phi i64 [ 3, %if.then ], [ %i, %entry ] + %arrayidx3 = getelementptr inbounds [100 x i64], [100 x i64]* @a, i64 0, i64 %i.addr.0 + %t2 = load i64, i64* %arrayidx3, align 8 + %arrayidx4 = getelementptr inbounds [100 x i64], [100 x i64]* @b, i64 0, i64 %i.addr.0 + %t3 = load i64, i64* %arrayidx4, align 8 + %mul5 = mul nsw i64 %t3, %t2 + store i64 %mul5, i64* @g3, align 8 + ret void +} + + Index: test/Transforms/GVN/PRE/pre-gep-load.ll =================================================================== --- test/Transforms/GVN/PRE/pre-gep-load.ll +++ test/Transforms/GVN/PRE/pre-gep-load.ll @@ -37,7 +37,7 @@ %3 = load double, double* %arrayidx5, align 8 ; CHECK: sw.bb2: ; CHECK-NOT: sext -; CHECK-NEXT: phi double [ +; CHECK: phi double [ ; CHECK-NOT: load %sub6 = fsub double 3.000000e+00, %3 br label %return Index: test/Transforms/GVN/PRE/pre-load.ll =================================================================== --- test/Transforms/GVN/PRE/pre-load.ll +++ test/Transforms/GVN/PRE/pre-load.ll @@ -72,7 +72,7 @@ %PRE = load i32, i32* %P3 ret i32 %PRE ; CHECK: block4: -; CHECK-NEXT: phi i32 [ +; CHECK: phi i32 [ ; CHECK-NOT: load ; CHECK: ret i32 } @@ -104,7 +104,7 @@ %PRE = load i32, i32* %P3 ret i32 %PRE ; CHECK: block4: -; CHECK-NEXT: phi i32 [ +; CHECK: phi i32 [ ; CHECK-NOT: load ; CHECK: ret i32 } @@ -263,7 +263,7 @@ %PRE = load i32, i32* %P3 ret i32 %PRE ; CHECK: block4: -; CHECK-NEXT: phi i32 [ +; CHECK: phi i32 [ ; CHECK-NOT: load ; CHECK: ret i32 }